Scientific Program > Talks by Speaker > Tamke Felix

A new mixed integer programming formulation for the vehicle routing problem with drones
Felix Tamke  1@  , Laura Manzke  1@  
1 : Technische Universität Dresden  (TUD)  -  Website
TU Dresden 01062 Dresden -  Germany

Growing Urbanization, increasing online purchases, and higher customer requirements in terms of speed, flexibility, and costs of home deliveries are challenges to every company related with the last mile. Technological advances have paved the way for urban parcel delivery by unmanned aerial vehicles (UAV). With the promise of cost-reductions and time-efficiency, a large number of companies has begun to redirect some of their resources to develop drone based delivery systems. Yet, the limited range and capacity of UAVs remain a challenge. This makes the possibility of pairing drones with well-established means of transportation highly attractive. However, the optimization problem arising in joint delivery by truck and drone has only recently been considered in the literature.

To contribute to this field of research, we enhance the mixed integer programming model of the flying sidekick traveling salesman problem developed by Murray and Chu as well as expand it by multiple vehicle-drone pairs to the vehicle problem with drones. Furthermore, we introduce valid inequalities to strengthen the linear relaxation and, consequently, speed up the solution process. Extensive numerical studies with small test instances from the literature as well self-generated slightly larger instances with up to 15 customers are performed to demonstrate the influence of different assumptions on the objective value and to show the limits of the current solution procedure. Moreover, we compare the actual savings obtained by using truck-drone tandems instead of solely trucks with the theoretical savings proposed by Wang, Poikonen and Golden.


Online user: 2 RSS Feed