On the Design and Performance of a Novel Metaheuristic Solver for the Extended Colored Traveling Salesman Problem

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.

I. Introduction

Among all the optimization problems that can be formulated in scenarios related to Transportation and Mobility, the Travelling Salesman Problem (TSP) can be regarded as the most widely studied one in the literature for decades [1]. In essence, the TSP seeks to discover the shortest route that a salesman can take to visit a set of cities and return to its starting point, without visiting any city more than once. This classic optimization problem is representative of a myriad of practical use cases in transportation and logistics, including the optimization of delivery routes, travel itinerary planning, flight scheduling, or the design of supply chain networks, to mention a few [2]. Furthermore, finding an optimal solution to the TSP can help minimize a diversity of objectives related to the optimized routes, such as transportation costs, delivery times or fuel consumption.