TY - JOUR

T1 - An adaptive large neighborhood search metaheuristic for a passenger and parcel share-a-ride problem with drones

AU - Cheng, R.

AU - Jiang, Y.

AU - Anker Nielsen, O.

AU - Pisinger, D.

PY - 2023/8/31

Y1 - 2023/8/31

N2 - With the increasing concerns about traffic congestion and climate change, much effort has been made to enhance sustainable urban mobility for passengers and goods. One emerging promising strategy is to transport passengers and goods in an integrated manner, as it could reduce the number of vehicles on the road compared with the separate transportation of passengers and goods. This study proposes the simultaneous transportation of passengers and goods using demand-responsive buses and drones. Compared with the prevalent strategies that rely only on ground vehicles to integrate passenger and parcel transportation, we propose the joint usage of ground vehicles and drones to transport passengers and deliver parcels. The ground vehicles for passenger and parcel delivery are on-demand buses, which combine the advantages of the flexibility of taxis and the large capacity of public transport modes. The drones automatically take off from and land on the on-demand buses’ rooftops and are only for parcel delivery. A new optimization problem that designs the routes for both demand-responsive buses and drones is proposed and denoted as the passenger and parcel share-a-ride problem with drones (SARP-D). A mixed-integer nonlinear programming model is devised; the nonlinearity exists because drone launch/recovery can occur simultaneously with request servicing by a bus at the same node. To solve the model for large-scale instances, we develop an adaptive large neighborhood search metaheuristic. Numerical experiments are conducted to validate the correctness of the model and evaluate the efficiency of the metaheuristic. Moreover, sensitivity analyses are performed to explore the influences of the maximum number of intermediate stops during one passenger request service, the drone flight endurance, and the unit delay penalty on the total cost, which comprises the transportation and delay costs.

AB - With the increasing concerns about traffic congestion and climate change, much effort has been made to enhance sustainable urban mobility for passengers and goods. One emerging promising strategy is to transport passengers and goods in an integrated manner, as it could reduce the number of vehicles on the road compared with the separate transportation of passengers and goods. This study proposes the simultaneous transportation of passengers and goods using demand-responsive buses and drones. Compared with the prevalent strategies that rely only on ground vehicles to integrate passenger and parcel transportation, we propose the joint usage of ground vehicles and drones to transport passengers and deliver parcels. The ground vehicles for passenger and parcel delivery are on-demand buses, which combine the advantages of the flexibility of taxis and the large capacity of public transport modes. The drones automatically take off from and land on the on-demand buses’ rooftops and are only for parcel delivery. A new optimization problem that designs the routes for both demand-responsive buses and drones is proposed and denoted as the passenger and parcel share-a-ride problem with drones (SARP-D). A mixed-integer nonlinear programming model is devised; the nonlinearity exists because drone launch/recovery can occur simultaneously with request servicing by a bus at the same node. To solve the model for large-scale instances, we develop an adaptive large neighborhood search metaheuristic. Numerical experiments are conducted to validate the correctness of the model and evaluate the efficiency of the metaheuristic. Moreover, sensitivity analyses are performed to explore the influences of the maximum number of intermediate stops during one passenger request service, the drone flight endurance, and the unit delay penalty on the total cost, which comprises the transportation and delay costs.

KW - Urban logistics

KW - On-demand transit

KW - Adaptive large neighborhood search

KW - Integrated passenger-and-goods transportation

KW - Share-a-ride problem with drones

KW - Vehicle routing problem with drones

U2 - 10.1016/j.trc.2023.104203

DO - 10.1016/j.trc.2023.104203

M3 - Journal article

VL - 153

JO - Transportation Research Part C: Emerging Technologies

JF - Transportation Research Part C: Emerging Technologies

SN - 0968-090X

M1 - 104203

ER -