A matheuristic approach for the robust coloured travelling salesman problem with multiple depots

Abtin Nourmohammadzadeh and Stefan Voß

European Journal of Operational Research, 2026, vol. 328, issue 2, 390-406

Abstract: In this work, a special type of the travelling salesman problem (TSP) called the coloured TSP (CTSP) is considered. The CTSP, which has many real-world applications, involves a set of salesmen, each assigned a specific colour, and cities that may have one or multiple colours. Salesmen are restricted to visiting only cities that share their colour. We consider a specific depot for each salesman, and the edge weights are uncertain, meaning that there is a set of possible scenarios for their values. A robust objective is considered and minimised using an artificial intelligence (AI)-driven matheuristic approach due to the high computational complexity of the problem. This approach integrates a variable neighbourhood search (VNS) framework with genetic algorithm (GA) and simulated annealing (SA) operators. More importantly, local improvements based on mathematical programming are applied to different parts of a proportion of the solutions using the concept of partial optimisation metaheuristic under special intensification conditions (POPMUSIC). A key innovation of our method is the use of an artificial neural network to guide the POPMUSIC procedure by selecting only solution segments with high improvement potential, thereby reducing computation time. Extensive computational experiments demonstrate the effectiveness of the proposed algorithm, which outperforms four state-of-the-art methods in solution quality and runs faster than three of them. We also investigate the contribution of individual algorithmic components and the cost of robustness. Furthermore, our method improves upon the best-known results for the single-depot deterministic version of the CTSP from the literature.

Keywords: Coloured travelling salesman problem (CTSP); Robust optimisation; Matheuristics; AI-driven optimisation; Partial optimisation metaheuristic under special intensification conditions (POPMUSIC) (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725004904
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:328:y:2026:i:2:p:390-406

DOI: 10.1016/j.ejor.2025.06.018

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().