Constraint Programming models for the parallel drone scheduling vehicle routing problem

DOI10.1016/J.EJCO.2023.100078MaRDI QIDQ6442834zbMATH OpenOpenAlexFDO

Authors Roberto Montemanni, Mauro Dell'Amico

Publication date 6 July 2023

Full work available at URL https://doi.org/10.1016/j.ejco.2023.100078

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Abstract: Drones are currently seen as a viable way for improving the distribution of parcels in urban and rural environments, while working in coordination with traditional vehicles like trucks. In this paper we consider the parallel drone scheduling vehicle routing problem, where the service of a set of customers requiring a delivery is split between a fleet of trucks and a fleet of drones. We consider two variations of the problem. In the first one the problem is more theoretical, and the target is the minimization of the time required to complete the service and have all the vehicles back to the depot. In the second variant more realistic constraints involving operating costs, capacity limitation and workload balance, are considered, and the target is to minimize the total operational costs. We propose several constraint programming models to deal with the two problems. An experimental champaign on the instances previously adopted in the literature is presented to validate the new solving methods. The results show that on top of being a viable way to solve problems to optimality, the models can also be used to derive effective heuristic solutions and high-quality lower bounds for the optimal cost, if the execution is interrupted after its natural end.

Recommendations

• The parallel drone scheduling problem with multiple drones and vehicles
• The min-cost parallel drone scheduling vehicle routing problem
• Matheuristic algorithms for the parallel drone scheduling traveling salesman problem
• The vehicle routing problem with drones: extended models and connections
• Parcel delivery cost minimization with time window constraints using trucks and drones

Cited in

(3)

• A constraint-programming approach for the storage space allocation problem in a distribution center
• Exact solution approaches for the traveling salesman problem with a drone station
• A compact model for the home healthcare routing and scheduling problem

This page was built for publication: Constraint Programming models for the parallel drone scheduling vehicle routing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6442834)