Department of Computer Science DIKU > Calendar > A Branch-and-Cut-and-P...

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

Master defence by 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.

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

The master defence comprises a 30 minutes presentation (15.15-15.45), followed by an examination (ca. 15.45-16.30). Both presentations and examinations are public.

The event is open to everybody.

Examinator: Martin Zachariasen, DIKU

Censor: Jesper Larsen, DTU