Final published version
Licence: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Model formulations for pickup and delivery problems in designated driver services
AU - Arslan, Alp
AU - Agatz, Niels
AU - Srour, Jordan
PY - 2024/4/30
Y1 - 2024/4/30
N2 - 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.
AB - 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.
KW - Routing
KW - Dial-a-ride
KW - Pickup and delivery problem
KW - Designated driver services
KW - Routing with precedence
U2 - 10.1016/j.cor.2024.106547
DO - 10.1016/j.cor.2024.106547
M3 - Journal article
VL - 164
JO - Computers and Operations Research
JF - Computers and Operations Research
SN - 0305-0548
M1 - 106547
ER -