A Branch-and-Cut-and-Price Algorithm for the Vehicle Routing Problem with Subcontractors

Specialeforsvar ved Rene Rosendahl Rasmussen 

Abstract

In this thesis a Branch-and-Cut-and-Price algorithm (BCP) is presented for the Vehicle Routing Problem with Subcontractors (VRPSC). The algorithm uses the Dantzig-Wolfe decomposition (DW) to obtain a set-partition master problem and a Shortest Path Problem with Resource Constraints (SPPRC). The Capacity Inequalities for the Capacitated Vehicle Routing Problem (CVRP) is investigated and the Rounded Capacity Inequality (RCI) is used. Furthermore a new inequality is presented, which is based on the RCI but utilizes another resource that is specfic for the VRPSC. The algorithm is able to solve the root node of approx. half the test instances and with an instance size of maximum 50 customers. The inequalities used is able to lower the gap on several instances but at the cost of fewer solved root nodes.

.............................................................................

Specialeforsvaret består en 30-minutters præsentation (15.15-15.45), efterfulgt af en eksamination (ca. 15.45-16.30). Både præsentation og eksamination er offentlige.

Alle er velkomne.

Eksaminator: Martin Zachariasen, DIKU

Censor: Jesper Larsen, DTU