Bi-Trajectory Hybrid Search to Solve Bottleneck-Minimized Colored Traveling Salesman Problems

Yangming Zhou, Wenqiang Xu, Mengchu Zhou, Zhang Hua Fu

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


A bottleneck-minimized colored traveling salesman problem is an important variant of colored traveling salesman problems. It is useful in handling the planning problems with partially overlapped workspace such as the scheduling transportation resources for timely delivery of goods. In this work, we propose an efficient bi-trajectory hybrid search method for it. The proposed method integrates a route-based crossover operator to generate promising offspring solutions, a multi-neighborhood simulated annealing to perform local optimization, and a stagnation-detect-escape mechanism to help the search escape from local optima. We also propose a bidirectional adjacency solution representation method to encode a solution, which extends the traditional adjacency representation method by additionally employing an array to represent its reverse counterpart. Extensive evaluations on two sets of 58 widely used benchmark instances demonstrate that the proposed method significantly outperforms state-of-the-art algorithms. Investigations on key algorithm modules are performed to confirm the novelty and effectiveness of the proposed ideas and strategies. Finally, we verify the generalization of the proposed method via its use to solve a colored traveling salesman problem with its aim to balance workload among salesmen. Note to Practitioners - This work is motivated by the problems of scheduling transportation resources for timely delivery of goods. It proposes an effective bi-trajectory hybrid search to tackle bottleneck-minimized colored traveling salesman problem. The proposed approach performs bi-trajectory hybrid evolutionary search by maintaining only two individuals during the whole search process. Extensive numerical experiments and comparisons show that our proposed algorithm significantly outperforms state-of-the-art algorithms and can help decision-makers in designing best-routing solutions.

Original languageEnglish (US)
Pages (from-to)895-905
Number of pages11
JournalIEEE Transactions on Automation Science and Engineering
Issue number1
StatePublished - Jan 1 2024

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering
  • Control and Systems Engineering


  • Traveling salesman problem
  • bottleneck
  • evolutionary computation
  • memetic search
  • metaheuristic


Dive into the research topics of 'Bi-Trajectory Hybrid Search to Solve Bottleneck-Minimized Colored Traveling Salesman Problems'. Together they form a unique fingerprint.

Cite this