An Application of Genetic Algorithm in Determining Salesmen’s Routes: A Case Study

Noufal Zhafira (Universitas Andalas)
Feri Afrinaldi    (Universitas Andalas)
Taufik Taufik (Universitas Andalas)

 ) Corresponding Author
This paper presents a case study of determining vehicles’ routes. The case is taken from a pharmaceutical products distribution problem faced by a distribution company located in the city of Padang, Indonesia. The objective of this paper is to reduce the total distribution time required by the salesmen of the company. Since the company uses more than one salesman, then the problem is modeled as a multi traveling salesman problem (m-TSP). The problem is solved by employing genetic algorithm (GA) and a Matlab® based computer program is developed to run the algorithm. It is found that, by employing two salesmen only, the routes produced by GA results in a 30% savings in total distribution time compared to the current routes used by the company (currently the company employs three salesmen). This paper determines distances based on the latitude and longitude of the locations visited by the salesmen. Therefore, the distances calculated in this paper are approximations. It is suggested that actual distances are used for future research.
Genetic algorithm; traveling salesman; vehicle routing
  Click to Read the Full Text

[1] I. N. Pujawan, Supply chain management. Denpasar: Guna Widya, 2005.

[2] S. Chopra and P. Meindl, Supply chain management, strategy, planning and operations. New Jersey: Pearson Education Inc., 2007.

[3] T. T. Dimyati and A. Dimyati, Operations Research Model-Model Pengambilan Keputusan. Bandung: Sinar Baru Algensindo, 1992.

[4] M. Gen and R. Cheng, Genetic algorithms and engineering optimization, Vol. 7. John Wiley & Sons., 2000.

[5] N. K. Mayuliana, E. N. Kencana, and L. P. I. Harini, “Penyelesaian Multi Traveling Salesman Problem dengan Algoritma Genetika,” E-Jurnal Mat., vol. 6, no. 1, pp. 1–6, 2015.

[6] N. M. Razali, “An efficient genetic algorithm for large scale vehicle routing problem subject to precedence constraints,” Procedia-Social Behav. Sci., vol. 195, pp. 1922–1931, 2015.

[7] E. Madonna and I. Muhammad, “Aplikasi Metode Nearest Neighbor pada Penentuan Jalur Evakuasi Terpendek untuk Daerah Rawan Gempa dan Tsunami,” J. Elektron, vol. 5, no. 2, pp. 45–46, 2013.

[8] A. C. Sembiring, “Penentuan rute distribusi produk yang optimal dengan menggunakan algoritma heuristik pada PT Coca Cola Bottling Indonesia Medan,” Universitas Sumatra Utara, 2008.

[9] A. W. Widodo and W. F. Mahmudy, “Penerapan algoritma genetika pada sistem rekomendasi wisata kuliner,” J. Ilm. KURSOR, vol. 5, no. 4, pp. 205–211, 2010.

[10] P. Junjie and W. Dingwei, “An ant colony optimization algorithm for multiple travelling salesman problem,” in First International Conference on Innovative Computing, Information and Control, 2006. ICICIC’06., 2006, pp. 210–213.

[11] B. Setiyono and J. M. FMIPA-ITS, “Pembuatan Perangkat Lunak Penyelesaian Multi Travelling Salesman Problem (m-TSP),” KAPPA, vol. 3, no. 2, pp. 55–65, 2002.

[12] R. Dhammpal, S. Kumar, and V. K. Patle, “Route optimization by ant colony optimization technique,” Procedia Comput. Sci., vol. 92, pp. 48–55, 2016.

[13] M. D. A. Serna, C. A. S. Uran, J. A. Z. Cortes, and A. F. A. Benitez, “Vehicle routing to multiple warehouses using a memetic algorithm,” Procedia-Social Behav. Sci., vol. 160, pp. 587–596, 2014.

[14] A. Utamima, K. R. Pradina, N. S. Dini, and H. Studiawan, “Distribution route optimization of gallon water using genetic algorithm and tabu search,” Procedia Comput. Sci., no. 72, pp. 503–510, 2015.

[15] D. A. R. Wati, Sistem kendali cerdas. Yogyakarta: Graha Ilmu, 2011.

[16] A. Basuki, “Strategi menggunakan algoritma genetika,” 2003. [Online]. Available: [Accessed: 20-Feb-2017].

[17] Y. Liu, H. Dong, N. Lohse, and S. Petrovic, “A multi-objective genetic algorithm for optimisation of energy consumption and shop floor production performance,” Int. J. Prod. Econ., vol. 179, pp. 259–272, 2016.

[18] J. De, T. Banerjee, R. S. Sen, B. Oraon, and G. Majumdar, “Multi-objective optimization of electroless ternary Nickel–Cobalt–Phosphorous coating using non-dominant sorting genetic algorithm-II,” Eng. Sci. Technol. an Int. J., vol. 19, no. 3, pp. 1526–1533, 2016.

[19] E. Spinnräker, D. Koschwitz, R. Markovic, J. Frisch, and C. Van Treeck, “Software-supported identification of an economically optimized retrofit order by minimizing life-cycle costs using a genetic algorithm including constraints,” Energy Procedia, vol. 122, pp. 739–744, 2017.

[20] H. Zhang, R. Chen, F. Wang, H. Wang, and Y. Wang, “Multi-objective optimization for operational parameters of a micro-turbine CCHP system based on genetic algorithm,” Procedia Eng., vol. 205, pp. 1807–1814, 2017.

[21] K. S. Sangwan and G. Kant, “Optimization of machining parameters for improving energy efficiency using integrated response surface methodology and genetic algorithm approach,” Procedia CIRP, vol. 61, pp. 517–522, 2017.

StatisticsArticle Metrics

This article has been read : 115 times
PDF file viewed/downloaded : 47 times