You are required to read and agree to the below before accessing a full-text version of an article in the IDE article repository.

The full-text document you are about to access is subject to national and international copyright laws. In most cases (but not necessarily all) the consequence is that personal use is allowed given that the copyright owner is duly acknowledged and respected. All other use (typically) require an explicit permission (often in writing) by the copyright owner.

For the reports in this repository we specifically note that

  • the use of articles under IEEE copyright is governed by the IEEE copyright policy (available at
  • the use of articles under ACM copyright is governed by the ACM copyright policy (available at
  • technical reports and other articles issued by M‰lardalen University is free for personal use. For other use, the explicit consent of the authors is required
  • in other cases, please contact the copyright owner for detailed information

By accepting I agree to acknowledge and respect the rights of the copyright owner of the document I am about to access.

If you are in doubt, feel free to contact

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



Branko Miloradovic, Eneko Osaba , Javier Del Ser , Vuk Vujovic , Alessandro Papadopoulos

Publication Type:

Conference/Workshop Paper


26th IEEE International Conference on Intelligent Transportation Systems




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.


author = {Branko Miloradovic and Eneko Osaba and Javier Del Ser and Vuk Vujovic and Alessandro Papadopoulos},
title = {On the Design and Performance of a Novel Metaheuristic Solver for the Extended Colored Traveling Salesman Problem},
pages = {1955--1962},
month = {September},
year = {2023},
booktitle = {26th IEEE International Conference on Intelligent Transportation Systems},
url = {}