Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Approximating Vehicle Routing Problems

Master Project - Winter 2022/23

An example of a single-depot vehicle routing [3].

Motivation

Covering vertices of a given graph using simpler structures, for example, paths, trees,
stars and so on, have long attracted the attention of the Computer Science and Operations Research
communities. This can be attributed to a variety of applications in vehicle routing, network design
and related problems. One classical example is the so-called ‘Nurse Location Problem’ [1]. The goal
is to place a group of nurses at different locations and find a tour for each of them so that every
patient is visited by a nurse. A similar setting arises in vehicle routing. Suppose we are given a set of
vehicles, initially located at a given set of depots. The goal is to find a tour for each of these vehicles,
each starting and ending at the respective depots to cover client demands at various locations.This
objective is especially relevant to the field of routing optimization for humanitarian relief efforts, where
the focus is to send the relief quickly to everyone. One of the most popular objectives is to minimize
the maximum distance travelled by any vehicle, also known as the make span of the solution. This
objective is especially popular in the field of humanitarian relief routing optimization, as the focus
there is to reach everyone quickly. This problem will be the focus of our project. Since this problem
is NP-Hard, our main focus will be on designing efficient approximation algorithms.

The Goal of this Project

In this project, we plan to study the following problems from the
view point of approximation algorithms. Rooted Min-Max Tree Cover (RMMTC): We are given an
undirected graph G with non-negative edge lengths, a pre-specified multiset of root vertices R and a
positive integer k. We wish to find a set of k sub-trees of G, each containing a unique vertex from R,
1such that every vertex of G is contained in at least one of these k trees. The objective is to minimize
the maximum cost among all the trees.
This problem generalises the Minimum Makespan Scheduling and is already NP-Hard when G is a
star and |R|=1. Even et al. [1] gave a 4-approximation algorithm for RMMTC and it has not been
improved since. There have been improvements in the approximation ratio for some special cases, but
the general problem still remains open. The goal of the project is to improve upon this approximation
factor. We will begin by looking at the special case when R is a singleton. We already have preliminary
ideas on improving the approximation guarantee in this case and hope to improve the approximation
ratio further by pushing these ideas and coming up with new ones.
We will also study a closely related problem, called the Rooted Min Max Tour Cover, where instead
of trees we wish to find closed walks starting and ending at r. There are many other closely related
variants of this problem as well (see [2]) and we hope that the ideas developed in the context of
RMMTC will be useful in developing improved approximation algorithms for these as well. We also
plan to evaluate the performance of the proposed algorithms through experimental simulations. We
would also be interested in obtaining better heuristics for the min-max problems, especially in the
context of humanitarian relief routing [4].

 

What we expect from you.

An aptitude for doing theoretical research in a relevant topic of Graph Theory. Curiosity to investigate the existing models and creativity to extend the current framework. Some basic coding skills to complement theoretical results with experiments.

What you can expect from us.

We will gently introduce you to the field and accompany you all along this interesting journey. If circumstances permit, our weekly meeting will be in person, otherwise via Zoom. This will be a team effort, and we aim at publishing our results at a renowned international conference.

[1]G. Even, N. Garg, J. Könemann, R. Ravi and A. Sinha. Min-Max Tree Covers of Graphs. Opera-
tions Research Letters, 32(4):309–315, 2004.
[2]W. Xu, W. Liang and X. Lin, Approximation Algorithms for Min-Max Cycle Cover Problems, in
IEEE Transactions on Computers, vol. 64, no. 3, pp. 600-613, March 2015.
[3]L. Kovács, A. Agárdi, T. Bányai, Fitness Landscape Analysis and Edge Weighting-Based Opti- mization of Vehicle Routing Problems. Processes, vol. 8, 1363, 2020
[4]Campbell, Ann Melissa, Dieter Vandenbussche, and William Hermann. "Routing for relief efforts." Transportation science 42.2 (2008): 127-145.

 

Project Team

The Master Project is organized by the Algorithm Engineering Group. The following group members are participating:

Supervisor

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: K-2.15
E-Mail: Friedrich(at)hpi.de

Dr. Davis Issac

Advisor
Hasso Plattner Institute

Office: K-2.07
Tel.: +49 331 5509-4841
E-Mail: Davis.Issac(at)hpi.de

Dr. Nikhil Kumar

Advisor
Hasso Plattner Institute

Office: K-2.07

Phone: +49 331 5509-3400

Email: Nikhil.Kumar (at) hpi.de