Precedence-Constrained Colored Traveling Salesman Problem: An Augmented Variable Neighborhood Search Approach

Xiangping Xu, Jun Li, Mengchu Zhou, Xinghuo Yu

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

A colored traveling salesman problem (CTSP) as a generalization of the well-known multiple traveling salesman problem utilizes colors to distinguish the accessibility of individual cities to salesmen. This work formulates a precedence-constrained CTSP (PCTSP) over hypergraphs with asymmetric city distances. It is capable of modeling the problems with operations or activities constrained to precedence relationships in many applications. Two types of precedence constraints are taken into account, i.e., 1) among individual cities and 2) among city clusters. An augmented variable neighborhood search (VNS) called POPMUSIC-based VNS (PVNS) is proposed as a main framework for solving PCTSP. It harnesses a partial optimization metaheuristic under special intensification conditions to prepare candidate sets. Moreover, a topological sort-based greedy algorithm is developed to obtain a feasible solution at the initialization phase. Next, mutation and multi-insertion of constraint-preserving exchanges are combined to produce different neighborhoods of the current solution. Two kinds of constraint-preserving k -exchange are adopted to serve as a strong local search means. Extensive experiments are conducted on 34 cases. For the sake of comparison, Lin-Kernighan heuristic, two genetic algorithms and three VNS methods are adapted to PCTSP and fine-tuned by using an automatic algorithm configurator-irace package. The experimental results show that PVNS outperforms them in terms of both search ability and convergence rate. In addition, the study of four PVNS variants each lacking an important operator reveals that all operators play significant roles in PVNS.

Original languageEnglish (US)
Pages (from-to)9797-9808
Number of pages12
JournalIEEE Transactions on Cybernetics
Volume52
Issue number9
DOIs
StatePublished - Sep 1 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Electrical and Electronic Engineering
  • Control and Systems Engineering
  • Computer Science Applications

Keywords

  • Colored traveling salesman problem (CTSP)
  • constrained optimization
  • hypergraph
  • machine learning
  • partial optimization metaheuristic under special intensification conditions (POPMUSIC)
  • precedence constraint
  • variable neighborhood search (VNS)

Fingerprint

Dive into the research topics of 'Precedence-Constrained Colored Traveling Salesman Problem: An Augmented Variable Neighborhood Search Approach'. Together they form a unique fingerprint.

Cite this