Parameterized Complexity of Vehicle Routing

Master Project - Winter 2024/25

Supervisors: Prof. Dr. Tobias Friedrich, Dr. Kirill Simonov, Dr. Shaily Verma, Michelle Döring, Farehe Soheil

Motivation

Optimizing logistics has been an important driver of the theory of computing since its very dawn, and, with the ever-growing digitalization and decentralization of services, it remains a productive direction to this day. One of the canonical challenges in the area, Vehicle Routing Problem (VRP), introduced by George Dantzig and John Ramser in 1959, can be informally summarized as follows: "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?"

Formally, we can use a weighted graph to represent the relevant locations and the travel costs between them, with a particular vertex marked as the depot, where the vehicles and their goods are originally located, and some other vertices are marked as clients that await the delivery; see the figure for an example. Depending on the optimization objective and additional constraints, a multitude of variants and extensions of the problem may be considered, capturing vehicle load restrictions, working conditions of the drivers, delivery time-frames, etc. However, even the most basic version of the problem is quite demanding, in particular generalizing the famous NP-hard Travelling Salesperson problem. Therefore, practical solvers for VRP are mostly based on heuristics, which do not provide guarantees on the quality of the solution. Some variants of the problem have also been studied from the viewpoint of approximation algorithms.

Tools

In this project, we plan to study the Vehicle Routing Problem and its variants through the lens of parameterized complexity. Parameterized complexity aims to identify efficient algorithms by introducing another dimension to the problem, called the parameter. The principal idea is to constrain the exponential dependence in the running time to the parameter, so that the running time remains polynomial as soon as the value of the parameter is small enough. In the context of the Vehicle Routing Problem specifically, the relevant parameters may be, for example, the number of available vehicles or the maximum number of orders per vehicle. Even more promising could be non-explicit parameters, capturing the structure of the road network, or the restrictions on how the orders are arranged in the network. While the parameterized complexity of VRP itself was not studied directly, there was substantial recent progress on closely-related graph problems, such as finding shortest paths hitting a certain selection of vertices.

Goal of the project

The goal of the project is to identify parameterizations for the Vehicle Routing Problem that would lead to efficient algorithms. There are several potential directions to explore.

How can the structure of the network be exploited? We may start by considering standard width parameters of the underlying graph, such as treewidth and clique-width, as well as look for more problem-specific measures.
Could the geometric embedding of the network be helpful? Road networks are always planar or almost planar, and there are many algorithmic techniques that are helpful for such instances.
Are there productive above-guarantee parameterizations for VRP? That means, the parameter measures the distance to some easily computable solution. For example, we recently had progress on a closely-related Path Cover problem in relation to the size of the maximum independent set in the graph.

While we plan to focus on theoretical results, our project also offers space for experimental research, such as analyzing the structure of existing datasets for VRP in order to identify most promising parameterizations, or testing the empirical performance of various algorithms to complement the theoretical analysis.