EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

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

Invited abstract in session MA-26: Combinatorial optimization topics in transportation, stream Combinatorial Optimization.

Monday, 8:30-10:00
Room: 012 (building: 208)

Authors (first author is the speaker)

1. Rong Cheng
Industrial Engineering & Innovation Sciences, Eindhoven University of Technology
2. Yu Jiang
Department of Technology, Management and Economics
3. Otto Anker Nielsen
DTU
4. David Pisinger
Management, DTU
5. Tom van Woensel
Technische Universiteit Eindhoven

Abstract

Growing concerns about traffic congestion and environmental pollution 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 problem, which can be solved by CPLEX for instances with up to 12 nodes. Then, we developed a path-based model and a column generation approach 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 problems 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.

Keywords

Status: accepted

Back to the list of papers