Efficient routing optimization with discrete penguins search algorithm for MTSP

Keywords: Multiple Travelling Salesman Problem, Metaheuristic, NP-Hard Combinatorial Optimization Problem, Penguins Search Optimization Algorithm, TSPLIB, Combinatorial Optimization Problem, NP-Hard


The Travelling Salesman Problem (TSP) is a well-known combinatorial optimization problem that belongs to a class of problems known as NP-hard, which is an exceptional case of traveling salesman problem (TSP), which determines a set of routes enabling multiple salesmen to start at and return to home cities (depots). The penguins search optimization algorithm (PeSOA) is a new metaheuristic optimization algorithm. This paper presents a discrete penguins search optimization algorithm (PeSOA) for solving the multiple traveling salesman problem (MTSP). The PeSOA is evaluated by a set of benchmarks of TSP instances from TSPLIB library. The experimental results show that PeSOA is very efficient in finding the right solutions in a reasonable time.


Download data is not yet available.


Alazzam, H., Alsmady, A., & Mardini, W. (2020). Solving Multiple Traveling Salesmen Problem using Discrete Pigeon Inspired Optimizer. 2020 11th International Conference on Information and Communication Systems (ICICS), 209–213. https://doi.org/10.1109/ICICS49469.2020.239528

ngel, R. D., Caudle, W. L., Noonan, R., & Whinston, A. (1972). Computer-Assisted School Bus Scheduling. Management Science, 18(6), B-279-B-288. https://doi.org/10.1287/mnsc.18.6.B279 DOI: https://doi.org/10.1287/mnsc.18.6.B279

Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209–219. DOI: https://doi.org/10.1016/j.omega.2004.10.004

Brumitt, B. L., & Stentz, A. (1998). GRAMMPS: a generalized mission planner for multiple mobile robots in unstructured environments. Proceedings. 1998 IEEE International Conference on Robotics and Automation (Cat. No.98CH36146), 2, 1564–1571 vol.2. https://doi.org/10.1109/ROBOT.1998.677360 DOI: https://doi.org/10.1109/ROBOT.1998.677360

Carter, A. E., & Ragsdale, C. T. (2006). A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, 175(1), 246–257. DOI: https://doi.org/10.1016/j.ejor.2005.04.027

Song, C.H., Lee, L., & Don Lee, W. (2003). Extended simulated annealing for augmented TSP and multi-salesmen TSP. Proceedings of the International Joint Conference on Neural Networks, 2003, 2340–2343. https://doi.org/10.1109/IJCNN.2003.1223777 DOI: https://doi.org/10.1109/IJCNN.2003.1223777

Du, P., Liu, N., Zhang, H., & Lu, J. (2021). An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem. Journal of Advanced Transportation, 2021, 1–16. https://doi.org/10.1155/2021/6642009

Gheraibia, Y., Moussaoui, A. (2013). Penguins Search Optimization Algorithm (PeSOA). In: Ali, M., Bosse, T., Hindriks, K.V., Hoogendoorn, M., Jonker, C.M., Treur, J. (eds) Recent Trends in Applied Artificial Intelligence. IEA/AIE 2013. Lecture Notes in Computer Science(), vol 7906. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38577-3_23 DOI: https://doi.org/10.1007/978-3-642-38577-3_23

Gilbert, K. C., & Hofstra, R. B. (1992). A New Multiperiod Multiple Traveling Salesman Problem with Heuristic and Application to a Scheduling Problem. Decision Sciences, 23(1), 250–259. DOI: https://doi.org/10.1111/j.1540-5915.1992.tb00387.x

Gorenstein, S. (1970). Printing Press Scheduling for Multi-Edition Periodicals. Management Science, 16(6), B-373-B-383. https://doi.org/10.1287/mnsc.16.6.B373 DOI: https://doi.org/10.1287/mnsc.16.6.B373

Hossam, A., Bouzidi, A., Riffi, M.E. (2020). Elephants Herding Optimization to Solve the Multiple Travelling Salesman Problem. In: Ezziyyani, M. (eds) Advanced Intelligent Systems for Sustainable Development (AI2SD’2019). AI2SD 2019. Advances in Intelligent Systems and Computing, vol 1105. Springer, Cham. https://doi.org/10.1007/978-3-030-36674-2_24

Junjie, P., & Dingwei, W. (2006). An Ant Colony Optimization Algorithm for Multiple Travelling Salesman Problem. First International Conference on Innovative Computing, Information and Control - Volume I (ICICIC’06), 1, 210–213. https://doi.org/10.1109/ICICIC.2006.40 DOI: https://doi.org/10.1109/ICICIC.2006.40

Király, A., & Abonyi, J. (2010). A Novel Approach to Solve Multiple Traveling Salesmen Problem by Genetic Algorithm. In I. J. Rudas, J. Fodor, & J. Kacprzyk (Eds.), Computational Intelligence in Engineering (pp. 141–151). Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-15220-7_12 DOI: https://doi.org/10.1007/978-3-642-15220-7_12

Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1987). Optimization by Simulated Annealing. In M. A. Fischler & O. Firschein (Eds.), Readings in Computer Vision (pp. 606–615). Morgan Kaufmann. https://doi.org/https://doi.org/10.1016/B978-0-08-051581-6.50059-3 DOI: https://doi.org/10.1016/B978-0-08-051581-6.50059-3

Lin, S. (1965). Computer Solutions of the Traveling Salesman Problem. Bell System Technical Journal, 44(10), 2245–2269. DOI: https://doi.org/10.1002/j.1538-7305.1965.tb04146.x

Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100. DOI: https://doi.org/10.1016/S0305-0548(97)00031-2

Mzili, I., Riffi, M. E., & Benzakri, F. (2020). Discrete penguins search optimization algorithm to solve flow shop scheduling problem. International Journal of Electrical and Computer Engineering, 10(4), 4426–4435.

Mzili, T., Riffi, M. E., Mzili, I., & Dhiman, G. (2022). A novel discrete Rat swarm optimization (DRSO) algorithm for solving the traveling salesman problem. Decision Making: Applications in Management and Engineering, 5(2), 287–299. DOI: https://doi.org/10.31181/dmame0318062022m

Pang, S., Li, T., Dai, F., & Yu, M. (2013). Particle Swarm Optimization Algorithm for Multisalesman Problem with Time and Capacity Constraints. Applied Mathematics & Information Sciences, 7(6), 2439–2444. DOI: https://doi.org/10.12785/amis/070637

Prajapati, V. K., Jain, M., & Chouhan, L. (2020). Tabu Search Algorithm (TSA): A Comprehensive Survey. 2020 3rd International Conference on Emerging Technologies in Computer Engineering: Machine Learning and Internet of Things (ICETCE), 1–8. https://doi.org/10.1109/ICETCE48199.2020.9091743

Reinelt, G. (1991). TSPLIB—A Traveling Salesman Problem Library. ORSA Journal on Computing, 3(4), 376–384. DOI: https://doi.org/10.1287/ijoc.3.4.376

Saleh, H. A., & Chelouah, R. (2004). The design of the global navigation satellite system surveying networks using genetic algorithms. Engineering Applications of Artificial Intelligence, 17(1), 111–122. DOI: https://doi.org/10.1016/j.engappai.2003.11.001

Savelsbergh, M. W. P., & Sol, M. (1995). The General Pickup and Delivery Problem. Transportation Science, 29(1), 17–29. DOI: https://doi.org/10.1287/trsc.29.1.17

Wang, L., Cai, R., Lin, M., & Zhong, Y. (2019). Enhanced List-Based Simulated Annealing Algorithm for Large-Scale Traveling Salesman Problem. IEEE Access, 7, 144366–144380. https://doi.org/10.1109/ACCESS.2019.2945570

Zhou, H., Song, M., & Pedrycz, W. (2018). A comparative study of improved GA and PSO in solving multiple traveling salesmen problem. Applied Soft Computing, 64, 564–580. DOI: https://doi.org/10.1016/j.asoc.2017.12.031

How to Cite
Mzili, I., Mzili, T., & Riffi , M. E. (2023). Efficient routing optimization with discrete penguins search algorithm for MTSP. Decision Making: Applications in Management and Engineering, 6(1), 730-743. https://doi.org/10.31181/dmame04092023m