Model formulations for pickup and delivery problems in designated driver services

Abstract

Designated driver services use company vehicles to deliver drivers to customers. The drivers then drive the customers from their origins to their destinations in the customers' own cars at the destinations, the drivers are picked up by a company vehicle. We typically see teams of drivers assigned to company vehicles serving customers. However, when the drivers may be dropped off by one vehicle and picked up by another, a challenging pick-up and delivery problem arises. In this paper, we study the structural properties of the designated driver problem focusing on the synchronization between company vehicles and drivers. We present a two-index formulations to generate optimal, least-cost routes using a general-purpose solver. We benchmark the two-index formulations against a 3-index formulation and a path enumeration strategy. Based on a set of experiments, we find that the two-index formulation performs well, both in terms of quality and solution time, especially on the formulations with more flexibility in the pairing of drivers to company vehicles. Our computational experiments show that up to 75% cost savings are possible from using a flexible operating strategy as compared to a strategy in which drivers and company vehicles stay together throughout a shift.