Inicio  /  Algorithms  /  Vol: 16 Par: 1 (2023)  /  Artículo
ARTÍCULO
TITULO

Solving the Parallel Drone Scheduling Traveling Salesman Problem via Constraint Programming

Roberto Montemanni and Mauro Dell?Amico    

Resumen

Drones are currently seen as a viable way of improving the distribution of parcels in urban and rural environments, while working in coordination with traditional vehicles, such as trucks. In this paper, we consider the parallel drone scheduling traveling salesman problem, where a set of customers requiring a delivery is split between a truck and a fleet of drones, with the aim of minimizing the total time required to serve all the customers. We propose a constraint programming model for the problem, discuss its implementation and present the results of an experimental program on the instances previously cited in the literature to validate exact and heuristic algorithms. We were able to decrease the cost (the time required to serve customers) for some of the instances and, for the first time, to provide a demonstrated optimal solution for all the instances considered. These results show that constraint programming can be a very effective tool for attacking optimization problems with traveling salesman components, such as the one discussed.

 Artículos similares

       
 
Danial Rooyani and Fantahun Defersha    
The work in this paper is motivated by a recently published article in which the authors developed an efficient two-stage genetic algorithm for a comprehensive model of a flexible job-shop scheduling problem (FJSP). In this paper, we extend the applicati... ver más
Revista: Algorithms

 
Yongmeng Qi, Qiang Li, Zhigang Zhao, Jiahua Zhang, Lingyun Gao, Wu Yuan, Zhonghua Lu, Ningming Nie, Xiaomin Shang and Shunan Tao    
Large-scale floods are one of the major events that impact the national economy and people?s livelihood every year during the flood season. Predicting the factors of flood evolution is a worldwide problem. We use the two-dimensional Saint-Venant equation... ver más
Revista: Applied Sciences

 
Weicheng Pei, Yuyan Jiang and Shu Li    
In aerospace engineering, high-order computational fluid dynamics (CFD) solvers suitable for three-dimensional unstructured meshes are less developed than expected. The Runge?Kutta discontinuous Galerkin (RKDG) finite element method with compact weighted... ver más
Revista: Aerospace

 
Petteri Annunen, Harri Haapasalo    
The construction industry has been suffering from modest productivity development in recent decades. To address the recognized problems, collaborative delivery methods are replacing traditional project delivery models, especially in large and complex pro... ver más

 
Congmin Yang, Tao Zhu, Yang Zhang, Huansheng Ning, Liming Chen and Zhenyu Liu    
The particle swarm optimization (PSO) algorithm has been widely used in various optimization problems. Although PSO has been successful in many fields, solving optimization problems in big data applications often requires processing of massive amounts of... ver más
Revista: Information