This thesis focuses on two pickup-and-delivery problems with transfers and time horizon. It provides models, theoretical results and methods to manage them.

The first problem is an Item Relocation Problem with transfers and time horizon. A 2-commodity flow model over a Time-Expanded network is introduced and a “Project and Lift” approach is proposed to manage this model. First, we derive a “projected model” which handles time constraints implicitly and which provides a lower bound for the cost of an optimal solution to the problem. The projected model is strengthened by adding specific constraints and solved by brach-and-cut. The “Lift” problem consists of calculating good quality solutions from solutions of the projected model.

The second problem is a classic Pickup-and-delivery Problem with transfers and time horizon. We introduce the “Virtual Path Problem” which consists of the modification of a directed acyclic graph with an underlying constraint system. The objective is to construct a directed path connecting two given vertices, while minimizing a cost function and maintaining a feasible constraint system. We propose an A* type algorithm to solve this problem in an exact way. Then, we show that the exact insertion of a request in a Pickup-and-delivery schedule can be seen as a particular case of this problem, and we also propose a heuristic based on Dijkstra's algorithm. Finally, we combine these single insertion algorithms with classic metaheuristics to manage the insertion of several requests.

Jury:

Maurício CARDOSO DE SOUZA - Universidade Federal de Minas Gerais - Rapporteur and examiner

Pierre FOUILHOUX - Université Sorbonne Paris Nord - Rapporteur and examiner

Alain QUILLIOT - Université Clermont Auvergne - Thesis director

Eric SANLAVILLE - Université du Havre - Examiner

Hélène TOUSSAINT - Université Clermont Auvergne - Thesis co-director

Annegret WAGLER - Université Clermont Auvergne - Thesis co-director.