The growth rate in Courier Express Parcel markets presents a major challenge for the logistics industry worldwide.
Innovative approaches and solutions are needed. For densely populated areas, so-called delivery robots are a promising alternative to traditional trucking.
Delivery robots represent a rather new technology, capable of transporting small goods autonomously on sidewalks.
These robots drive at walking speed and are equipped with the same technology used for autonomous driving.
One advantage of these robots is that a delivery time, chosen by the customer, can be realized more easily compared to traditional trucking.

In this study, the goal is to maximize the number of customers served within their pre-specified time windows with a given fleet of robots, while observing battery restrictions.
This problem can be modeled as a team orienteering problem with time windows and battery constraints, which is solved exactly using a branch-and-price algorithm.
The pricing problem is implemented by solving a resource constrained elementary shortest path problem. This path is caluclated with a dynamic program based on a labeling algorithm.

First tests were carried out with the branch-and-price algorithm and an alternative mixed integer program.
Comparing these two approaches, it turned out that our algorithm outperforms the alternative formulation.