Vehicle Routing Problems with Special Constraints for the Risk Management
Abstract:
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).
Keywords:
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).
