A Discrete Crested Porcupine Optimizer for the Spherical Asymmetric Traveling Salesman Problem
Honglei Ma1, Yingxuan Luo2, Jie Li3,*, Jia Chen1
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 https://doi.org/10.32604/cmc.2026.087350
Received 15 June 2026; Accepted 06 August 2026; Published online 24 August 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
Spherical asymmetric traveling salesman problem; discrete crested porcupine optimizer; metaheuristic; 2-opt local search; discrete optimization
Open Access
Login
Register
Submit a Paper
Propose a Special lssue
Download PDF
Downloads
Citation Tools
