Efficient routing optimization with discrete penguins search algorithm for MTSP
DOI:
https://doi.org/10.31181/dmame04092023mKeywords:
Multiple Travelling Salesman Problem, Metaheuristic, NP-Hard Combinatorial Optimization Problem, Penguins Search Optimization Algorithm, TSPLIB, Combinatorial Optimization Problem, NP-HardAbstract
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.
Downloads
References
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
Angel, 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
Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 34(3), 209–219.
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
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.
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
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
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.
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
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
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
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
Lin, S. (1965). Computer Solutions of the Traveling Salesman Problem. Bell System Technical Journal, 44(10), 2245–2269.
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097–1100.
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.
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.
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.
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.
Savelsbergh, M. W. P., & Sol, M. (1995). The General Pickup and Delivery Problem. Transportation Science, 29(1), 17–29.
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2023 Decision Making: Applications in Management and Engineering
This work is licensed under a Creative Commons Attribution 4.0 International License.
