Application of Genetic Algorithms to Solve MTSP Problems with Priority (Case Study at the Jakarta Street Lighting Service)

Main Article Content

Sugih Sudharma Tjandra
Fran Setiawan
Hanoum Salsabila


Transportation, Multiple TSP, Priority Node, Genetic Algorithm, Neighbor Algorithm


Transportation is one thing that is very important and is the highest cost in the supply chain. One way to reduce these costs is to optimize vehicle routes. The Multiple Traveling Salesman Problem (MTSP) and Capacitated Vehicle Routing Problem (CVRP) are models that have been extensively researched to optimize vehicle routes. In its development based on actual events in the real world, some priorities must be visited first in optimizing vehicle routes. Several studies on MTSP and CVRP models have been conducted with exact solutions and algorithms. In a real case in the Jakarta City Street Lighting Section, the problem of determining the route in three shifts is a crucial problem that must be resolved to increase worker productivity to improve services. Services in MCB (Miniature Circuit Breaker) installation and maintenance activities for general street lights and priority is given to light points that require replacement. Because, in this case, the delivery capacity is not taken into account, the priority of the lights visited is random, and the number of street light points is enormous, in this study, we use the MTSP method with priority and solve by a genetic algorithm assisted by the nearest neighbor algorithm. From the resolution of this problem, it was found that the travel time reduction was 32 % for shift 1, 24 % for shift 2, and 23 % for shift 3. Of course, this time reduction will impact worker productivity so that MCB installation can be done faster for all lights and replace a dead lamp.


Download data is not yet available.


[1] S. Chopra, and P. Meindl, Supply Chain Management: Strategy, Planning, and Operation. New Jersey : Pearson Education, Inc. , 2016.
[2] Y. Tseng, W. L. Yue, and M. A. Taylor, “The Role of Transportation in Logistics Chain”, Eastern Asia Society for Transportation Studies, vol. 5, pp. 1657-1672, 2005.
[3] M. Goetschalckx, Supply Chain Engineering. New York : Springer, 2011.
[4] S. M. Hardi, M. Zarlis, and E. Budiarti, “Analisis Mapping pada Partially Mapped Crossover dalam Algoritma Genetika pada Traveling Salesman Problem”, TECHSI, vol. 4(1), pp. 127-156, 2014.
[5] K. Pachamgam, Y. Xiong, B. Golden, B. Dussault, and E. Wasil. The Hierarchical Traveling Salesman Problem. Optimization Letters, 7(7),
[6] T. T. Dam, D. T. Nguyen, Q. T. Bui, and T. K. Do, On the Traveling Salesman Problem with Hierarchical Objective Function, 11th International Conference on Knowledge and System Engineering,
[7] G. Laporte, The Traveling Salesman Problem: An Overview of Exact and Approximate Algorithms, European Journal of Operational Research, vol. 59, pp. 231-247, 1992.
[8] D.L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook, The Travelling Salesman Problem. New Jersey: Princeton University Press, 2006.
[9] Y. Kao and M. Chen, Solving the CVRP Problem Using a Hybrid PSO Approach, Computational Intelligence, 59-67, 2011.
[10] S. F. Ghannadpour, S. Noori, and R. Tavakkoli-Moghaddam, A multi-objective vehicle routing and scheduling problem with uncertainty in customers’ request and priority, Journal of Combinatorial Optimization, Vol. 28, pp. 414-446, 2014.
[11] S. Nucamendi-Guillén, D. Flores-Díaz, E. Olivares-Benitez, and A. Mendoza, A Memetic Algorithm for the Cumulative Capacitated Vehicle Routing Problem Including Priority Indexes, Applied Sciences, Vol. 10(11). doi:10.3390/app10113943, 2020.
[12] Y. Sheng, H. Ma, and W. Xia, A Pointer Neural Network for the Vehicle Routing Problem with Task Priority and Limited Resources, Information Technology and Control, Vol.49, 237-248, 2020.
[13] A. Oran, K. C. Tan, B. H. Ooi, M. Sim, dan P. Jaillet, Location and Routing Models for Emergency Response Plans with Priorities, Future Security, pp. 129-140.
[14] [14] S. L. Smith, M. Pavone, F. Bullo, and E. Frazzoli, Dynamic Vehicle Routing with Priority Classes of Stochastic Demands. SIAM Journal on Control and Optimization, 48(5), pp. 3224-3245, 2010.
[15] T. Bektas, “The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures”, Omega: The International Journal of Management Science, vol. 34, pp. 209-219, 2008.
[16] E. G. Talbi, Metaheuristics from Design to Implementation. Lille, France: John Wiley & Sons, 2009.
[17] D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, “An Analysis of Several Heuristics for the Traveling Salesman Problem”, SIAM Journal on Computing, vol. 6(3), pp. 563-581,
[18] D. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Boston, United States: Addison-Wesley Longman Publishing, 1989.
[19] J. Kirk, “Fixed Start/End Point Multiple Traveling Salesmen Problem – Genetic Algorithm”, Mathworks, May 6, 2014. [Online]. Available:
[20] Z. Wang, X. Fang, H. Li, and H. Jin, “An Improved Partheno-Genetic Algorithm With Reproduction Mechanism for the Multiple Traveling Salesperson Problem”, IEEE Access, vol. 8, pp. 102607-102615,
[21] B. Santosa, Pengantar Metaheuristik Implementasi dengan Matlab. Surabaya, Indonesia : ITS Tekno Sains, 2017.