On the Design and Performance of a Novel Metaheuristic Solver for the Extended Colored Traveling Salesman Problem
- Branko Miloradovic,
- ,
- ,
- Vuk Vujovic,
- Alessandro V. Papadopoulos
Abstract
Intelligent transportation systems face various challenges, including traffic congestion, environmental pollution, and inefficient transportation management. Optimizing routes and schedules for efficient delivery of goods and services can mitigate the aforementioned problems. Many transportation and routing problems can be modeled as variants of the Traveling Salesmen Problem (TSP) depending on the specific requirements of the scenario at hand. This means that to efficiently solve the routing problem, all locations have to be visited by the available salesmen in a way that minimizes the overall makespan. This becomes a non-trivial problem when the number of salesmen and locations to be visited increases. The problem at hand is modeled as a special TSP variant, called Extended Colored TSP (ECTSP). It has additional constraints when compared to the classical TSP, which further complicates the search for a feasible solution. This work proposes a new metaheuristic approach to efficiently solve the ECTSP. We compare the proposed approach to existing solutions over a series of test instances. The results show a superior performance of our metaheuristic approach with respect to the state of the art, both in terms of solution quality and algorithm's runtime.
Research Output Information
Output type
Original language
EnglishPages from-to (Number of pages)
Pages 1955-1962 (8 pages)Publication milestones
- Published - 2023
Publication status
Publisher
Institute of Electrical and Electronics Engineers Inc., United StatesPublication series
- Publication series name: IEEE Conference on Intelligent Transportation Systems, Proceedings, ITSC
ISSN (Print): 2153-0009
ISSN (Electronic): 2153-0017
ISBN (Electronic)
9798350399462Publication IDs
- Scopus: 85186509322
Host publication title
2023 IEEE 26th International Conference on Intelligent Transportation Systems, ITSC 2023Sustainable Development Goals
- SDG 11 Sustainable Cities and Communities
