A self-adaptive genetic algorithm for the flying sidekick travelling salesman problem
This paper presents a novel approach to solving the Flying Sidekick Travelling Salesman Problem (FSTSP) using a state-of-the-art self-adaptive genetic algorithm. The Flying Sidekick Travelling Salesman Problem is a combinatorial optimisation problem that extends the Travelling Salesman Problem (TSP) by introducing the use of drones. In FSTSP, the objective is to minimise the total time to visit all locations while strategically deploying a drone to serve hard-to-reach customer locations. Also, to the best of my knowledge, this is the first time a self-adaptive genetic algorithm (GA) has been used to solve the FSTSP problem. Experimental results on smaller-sized problem instances demonstrate that this algorithm can find a higher quantity of optimal solutions and a lower percentage gap to the optimal solution compared to rival algorithms. Moreover, on larger-sized problem instances, this algorithm outperforms all rival algorithms on each problem size while maintaining a reasonably low computation time.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Hybrid Genetic Algorithm and Mixed Integer Linear Programming for Flying Sidekick TSP
The increasing use of drones to perform various tasks has motivated an exponential growth of research aimed at optimizing the use of these means, benefiting both military and civilian applications, including logistics de…
Traveling Salesman ProblemA Hybrid Genetic Algorithm with Type-Aware Chromosomes for Traveling Salesman Problems with Drone
There are emerging transportation problems known as the Traveling Salesman Problem with Drone (TSPD) and the Flying Sidekick Traveling Salesman Problem (FSTSP) that involve using a drone in conjunction with a truck for p…
Decision MakingTraveling Salesman ProblemA Variable Neighborhood Search for Flying Sidekick Traveling Salesman Problem
The efficiency and dynamism of Unmanned Aerial Vehicles (UAVs), or drones, present substantial application opportunities in several industries in the last years. Notably, the logistic companies gave close attention to th…
Traveling Salesman ProblemOptimization of Multi-Agent Flying Sidekick Traveling Salesman Problem over Road Networks
The mixed truck-drone delivery systems have attracted increasing attention for last-mile logistics, but real-world complexities demand a shift from single-agent, fully connected graph models to multi-agent systems operat…
Traveling Salesman ProblemExact and Heuristic Approaches to Drone Delivery Problems
The Flying Sidekick Traveling Salesman Problem (FSTSP) considers a delivery system composed by a truck and a drone. The drone launches from the truck with a single package to deliver to a customer. Each drone must return…
Traveling Salesman Problem