Traveling of multiple salesmen to dynamically changing locations for satisfying multiple goals

Abstract

Polymer grade scheduling, maritime surveillance, e-food delivery, e-commerce, and military tactics necessitate multiple agents (e.g., extruders, speed boats, salesmen) capable of visiting (or completing) dynamically changing locations (or tasks) in minimum time and distance. This study proposes a novel methodology based on clustering and local heuristic-based evolutionary algorithms to address the dynamic traveling salesman problem (TSP) and the dynamic multi-salesman problem with multiple objectives. The proposed algorithm is evaluated on 11 benchmark TSP problems and large-scale problems with up to 10,000 instances. The results show the superior performance of the proposed methodology called the dynamic two-stage evolutionary algorithm as compared to the dynamic hybrid local search evolutionary algorithm. Furthermore, the algorithm's applicability is illustrated through various scenarios involving up to four salesmen and three objectives with dynamically changing locations. To demonstrate real-world relevance, a maritime surveillance problem employing a helideck monitoring system is solved, wherein the objective is to minimize the patrolling route while visiting faulty vessels that threaten marine vessels. This study provides a general framework of TSP which finds application in several sectors, including planning and scheduling in chemical and manufacturing industries, the defense sector, and the e-commerce sector. Finally, the results showcase the effectiveness of the proposed methodology in solving the dynamic multiobjective, and multiple salesmen problem, which represents a more generalized version of the TSP.

Keywords

• Dynamic traveling salesman problem
• Multiple salesmen
• Multiobjective optimization
• Evolutionary algorithm
• Maritime surveillance