Open Access

ARTICLE

A Discrete Crested Porcupine Optimizer for the Spherical Asymmetric Traveling Salesman Problem

Honglei Ma¹, Yingxuan Luo², Jie Li^3,*, Jia Chen¹

1 School of Computer Application, Guilin University of Technology, Guilin, China
2 Department of Mechanical Engineering, The University of Hong Kong, Hong Kong, China
3 School of Artificial Intelligence, South China Normal University, Foshan, China

* Corresponding Author: Jie Li. Email:

Computers, Materials & Continua 2026, 89(2), 70 https://doi.org/10.32604/cmc.2026.087350

Received 15 June 2026; Accepted 06 August 2026; Issue published 15 September 2026

Abstract

The Spherical Asymmetric Traveling Salesman Problem (SATSP), characterized by spherical geometry and direction-dependent travel costs, is a challenging combinatorial optimization problem, particularly in large-dimensional scenarios. Although the recently proposed Crested Porcupine Optimizer (CPO) has shown promising performance in continuous optimization, its applicability to discrete asymmetric routing problems remains largely unexplored. To address this limitation, we propose a Discrete Crested Porcupine Optimizer (DCPO), which integrates a discrete solution representation with dual crossover operators, namely order crossover and partially mapped crossover, as well as a multi-strategy mutation mechanism including inversion mutation and swap mutation. A 2-opt local search strategy is embedded to enhance local refinement while maintaining global exploration. DCPO is applied to SATSP instances to validate the effectiveness and stability of the proposed algorithm. Experimental comparisons with several representative metaheuristic algorithms, including the Discrete Mayfly Algorithm (DMA), Flower Pollination Algorithm (FPA), Discrete Sparrow Search Algorithm (DSSA), Genetic Algorithm (GA), Randomized Bias Genetic Algorithm (RBGA), and Discrete Marine Predators Algorithm (DMPA), demonstrate that DCPO obtains the best mean and best-found objective values in 11 out of 12 SATSP instances of different scales, corresponding to 91.7%, and achieves the lowest standard deviation in 8 instances, corresponding to 66.7%, indicating strong solution quality and stability. For large-dimensional scenarios with 1000 to 1200 cities, DCPO achieves improvements of 13.09%–19.46% in mean objective values over the best competing algorithms, further confirming its effectiveness and scalability for complex SATSP optimization.

---

Keywords

---