Passenger and parcel share-a-ride problem with drones: Models and solutions

Description

Growing concerns about traffic congestion and environmental pollu-
tion necessitate innovative solutions to enhance urban mobility for both
people and goods. A novel approach involves combining passenger
and parcel delivery services using demand-responsive buses (DRBs)
and drones. This integration aims to reduce the number of vehicles
on the road by combining the movement of passengers and parcels.
In this scheme, each DRB is paired with a drone to work together.
While DRBs accommodate both passengers and parcels, drones are
used solely for delivering parcels. We introduce the concept of the
induced Route Planning Problem for DRBs and drones, termed the
Share-A-Ride Problem with Drones (SARP-D). We first developed an
arc-based mixed integer programming model to formulate this prob-
lem, which can be solved by CPLEX for instances with up to 12 nodes.
Then, we developed a path-based model and a column generation ap-
proach to solve medium instances with up to 50 nodes. The column
generation approach achieves either optimal solutions or solutions very
close to optimality within a 3-hour timeframe. Large instances with
up to 200 nodes are solved by an adaptive large-neighborhood search
metaheuristic, which can also efficiently solve vehicle routing prob-
lems with drones. Our experiments showed that SARP-D could reduce
the number of used DRBs and DRB-traveled miles. We offer several
key insights for management based on our research outcomes.

Period	1 Jul 2024
Event title	EURO-2024 Copenhagen: 33rd European Conference on Operational Research
Event type	Conference
Conference number	33
Location	Copenhagen, DenmarkShow on map
Degree of Recognition	International