Ph.D. Thesis

Vehicle routing problems with trailers [full text in .pdf]

Vehicle routing problems (VRPs) are a class of combinatorial optimization problems with application in many different domains ranging from the distribution of goods to the delivery of services. In this thesis we have studied VRPs in which the capacity of the vehicles is increased with the use of detachable trailers. This thesis comprises three parts:

The first part is devoted to the single truck and trailer routing problem with satellite depots (STTRPSD), where a single truck with a detachable trailer based at a depot serves the demand of a set of customers accessible only by truck. For this problem we have developed three heuristics, two metaheuristics based on GRASP and evolutionary local search, and an exact branch-and-cut algorithm.

The second part addresses the truck and trailer routing problem (TTRP) that models the multi-vehicle case, where a heterogeneous fixed fleet of trucks and trailers is used to serve the demand of a set of customers, some of them with accessibility restrictions. To solve the TTRP we have developed two methods: (i) a hybrid metaheuristic combining GRASP, variable neighborhood search (VNS) and path relinking; and (ii) a matheuristic that uses the routes of the local optima produced by a GRASP/VNS to solve a set-partitioning formulation of the TTRP with a commercial optimizer.

Finally, the third part presents an object-oriented framework for the rapid prototyping of heuristic methods based on the route-first, cluster-second principle. This framework provides a set of reusable components that can be adapted to tackle different VRP extensions.

Advisors: Andrés L. Medaglia (Universidad de los Andes – Colombia), and Christian Prins (Université de Technologie de Troyes – France).

Co-advisors: Nubia Velasco (Universidad de los Andes – Colombia) and Caroline Prodhon (Université de Technologie de Troyes – France),  2010.

Extended abstract: An extended abstract has been published in 4-OR (A Quarterly Journal of Operations Research). A journal published by the Belgian, French and Italian Operations Research Societies.  [see the extended abstract at publisher]

Test instances: Test instances and computational results reported in the thesis can be downloaded here.