On Clustered Vehicle-Routing Problems
Date issued
Authors
Editors
Journal Title
Journal ISSN
Volume Title
Publisher
License
Abstract
The thesis at hand tackles two variants of the vehicle-routing problem (VRP) in which customers are partitioned into clusters: The clustered VRP (CluVRP) and the soft-clustered VRP (SoftCluVRP). Both versions arise in practical scenarios where the routing decision must respect already taken clustering decisions. An example is parcel/small-package delivery in courier companies, where a large number of customers is divided into regional zones. For the heuristic solution, we develop two new large multiple neighborhood searches, one for each of the two problem variants. A major novelty is a generalization of the Balas-Simonetti neighborhood for the CluVRP. It is able to decide on the permutation of the clusters in a route and the routing through each cluster simultaneously. Furthermore, for the exact solution of the SoftCluVRP, we design and analyze different branch-and-price algorithms that differ in the way the column-generation subproblem is solved (either by dynamic-programming based labeling algorithms or with a branch-and-cut algorithm). Extensive computational studies prove the usefulness of the proposed solution methods.