This research concerns solving two transportation problems that integrate constraints or objective-fonctions related to the risk management :
the m-Peripatetic Vehicle Routing Problem (m-PVRP) and the Cumulative Capacitated Vehicle Routing Problem (CCVRP).
Applications can be found in the security logistics field, such as money transportation, and the humanitarian logistics field, such as vital goods
supply after a natural disaster.
Most of our work is about the m-PVRP. It consists in finding a set of routes of minimal total cost over m periods such that each customer is served once per period and two customers are never sequenced consecutively during two different periods. Different mathematical models are presented and the problem complexity is discussed. Then, we propose polynomial lower bounds, two metaheuristics including a tabu search with diversification and guided by a b-matching solution, a column-generation-like approach combining dual heuristics with q-routes generation, and finally two branch-and-cut algorithms.
The CCVRP consists in minimizing the sum of arrival times at customers, instead of the classical route cost or length, subject to the vehicle capacity. We propose a memetic algorithm (MA). Its efficiency lies upon the optimal splitting procedure of chromosomes without trip delimiters into feasible routes to obtain a feasible solution. Pre-computations to speed up MA and valid formulas to compute lower bounds are deduced from some CCVRP properties we identified. Up to now, this MA is the best metaheuristic published on the special case of the Traveling Repairman Problem ( = single-vehicle PTVCC = TRP).
|Supervisors:||Christian PRINS,||Full Professor,||Laboratoire d'Optimisation des Systèmes Industriels (LOSI - UTT)|
|Roberto WOLFLER CALVO,||Full Professor,||Laboratoire d'Informatique de Paris-Nord (LIPN)|
Operations Research, Combinatorial Optimization, Logistics, Transportation, Vehicle Routing, Security, Humanitarian, Metaheuristics,
Column generation, Branch-and-cut.
PhD thesis defended: October 27th, 2009 at the LOSI (Laboratory of Industrial Systems Optimization) of UTT (University of Technology of Troyes).
|Thesis (in french)|
|Thesis Defence (in french)|