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

1 Scopus citations

Abstract

A 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)
JournalIEEE Transactions on Cybernetics
DOIs
StateAccepted/In press - 2021

All Science Journal Classification (ASJC) codes

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

Keywords

  • Color
  • constrained optimization
  • hypergraph
  • machine learning
  • Measurement
  • Optimization
  • partial optimization metaheuristic under special intensification conditions (POPMUSIC)
  • precedence constraint
  • Systematics
  • Task analysis
  • traveling salesman problem (CTSP)
  • Traveling salesman problems
  • Urban areas
  • 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