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

Noufal Zhafira; Feri Afrinaldi; Taufik Taufik

doi:10.25077/josi.v17.n1.p26-34.2018

Noufal Zhafira

Universitas Andalas

Feri Afrinaldi

Universitas Andalas

Taufik Taufik

Universitas Andalas

Keywords

Genetic algorithm, traveling salesman, vehicle routing

Abstract

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 travelling 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.

Downloads

Download data is not yet available.

References

[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. https://doi.org/10.1007/978-3-8349-9320-5_22

[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. https://doi.org/10.1109/ICICIC.2006.40

[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. https://doi.org/10.1016/j.procs.2016.07.322

[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. https://doi.org/10.1016/j.procs.2015.12.132

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

[16] A. Basuki, “Strategi menggunakan algoritma genetika,” 2003. [Online]. Available: http://lecturer.eepis-its.edu/~basuki/lecture/StrategiAlgoritmaGenetika. [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. https://doi.org/10.1016/j.ijpe.2016.06.019

[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. https://doi.org/10.1016/j.egypro.2017.07.389

[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. https://doi.org/10.1016/j.proeng.2017.10.236

[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. https://doi.org/10.1016/j.procir.2016.11.162

PDF

Published

Apr 27, 2018

https://doi.org/10.25077/josi.v17.n1.p26-34.2018

How to Cite

[1]

N. Zhafira, F. Afrinaldi, and T. Taufik, “An Application of Genetic Algorithm in Determining Salesmen’s Routes: A Case Study”, J. Optimasi Sist. Ind., vol. 17, no. 1, pp. 26–34, Apr. 2018.

Issue

Vol. 17 No. 1 (2018): Published in April 2018

Section

Articles

Authors' Retention of Copyright

Authors retain the copyright of their original work published in Jurnal Optimasi Sistem Industri (JOSI). By submitting their manuscript to the journal, authors grant Jurnal Optimasi Sistem Industri (JOSI) a non-exclusive license to publish the work under the CC BY-NC-SA 4.0 International License. This means that others are permitted to:

Share and adapt the work for non-commercial purposes, provided proper attribution is given to the original authors and source.
Create derivative works based on the original article, as long as the new work is non-commercial and under the same CC BY-NC-SA 4.0 International License.

Non-Commercial Usage

The CC BY-NC-SA 4.0 International License restricts commercial use of the published work and its derivatives. Commercial use includes generating revenue, financial gain, or any form of commercial exploitation. This limitation aims to preserve the scholarly and educational nature of the content.

ShareAlike Requirement

If you remix, adapt, or build upon the work, you must distribute your contributions under the same CC BY-NC-SA 4.0 International License as the original work. This "ShareAlike" requirement ensures that any new works based on the original content adhere to the same non-commercial, share-alike principles.

Usage, Attribution, and Citations

Authors and readers are allowed to:

Share and distribute the published article in any medium or format.
Adapt, remix, transform, and build upon the article for non-commercial purposes.
Provide appropriate attribution to the original authors and the journal.

When using content from Jurnal Optimasi Sistem Industri (JOSI), proper attribution must be provided through citation of the original source and authors.

Copyright Infringement and Ethical Considerations

If you believe that any material published in Jurnal Optimasi Sistem Industri (JOSI) infringes upon your copyright or the copyright of someone you represent, please contact the editorial team promptly. The journal is committed to addressing copyright concerns in accordance with established ethical guidelines set forth by the Committee on Publication Ethics (COPE).

For any questions or inquiries related to copyright and licensing, please contact the editorial team at editor_josi[at]eng.unand.ac.id.