CREATING THE BEST ROUTING BY HEURISTIC ALGORITHM

Mehmet ŞİRİN; Tuğba ALTINTAŞ; Ali GÜNEŞ

doi:10.29121/ijetmr.v4.i12.2017.132

Authors

Mehmet ŞİRİN Department of Computer Engineering, Istanbul Aydin University, Istanbul, Turkey
Tuğba ALTINTAŞ Department of Health Sciences, Uskudar University, Istanbul, Turkey
Ali GÜNEŞ Department of Computer Engineering, Istanbul Aydin University, Istanbul, Turkey

DOI:

https://doi.org/10.29121/ijetmr.v4.i12.2017.132

Keywords:

Ant Colony Algorithm, Travelling Salesman Problem, Web-Based Application, Routing

Abstract

In this study, Travelling Salesman Problem (TSP), an NP-hard problem, is addressed. In order to get the best results with a view to directing TSP heuristics, the ant colony algorithm was used for solution purposes. The purpose was to solve the problem of setting a course for the bread distribution trucks of Istanbul Halk Ekmek (Public Bread) Company using the ant colony algorithm on TSP. A liquid called Pheromone, which ants release in order to establish communication among them, is known as the most fundamental matter to provide this communication. In this research, artificial ants, which function with the logic of finding the shortest path in the area where they are located, were utilized. The purpose of our programme is to determine the shortest route for the arrival of the distribution trucks to the kiosks where bread is sold to the public. The route developed by the programme is displayed over Google maps. Motivation/Background: Explain the importance of the problem investigated in the paper. Include here a statement of the main research question. Method: Give a short account of the most important methods used in your investigation. Results: Present the main results reported in the paper. Conclusions: Briefly present the conclusions and importance of the results. Concisely summarize the study’s implications. Please do not include any citations in the abstract.

Downloads

Download data is not yet available.

References

G. Laporte and I. H. Osman, Potvin, J., Y., (1996). “Genetic algorithms for the travelling salesman problem”, forthcoming in Annals of Operations Research on "Metaheuristics in Combinatorial Optimization",eds. 63: 339-370

Dantzig, G.B., Ramser J.B., (1959) The Truck Dispatching Problem. Management Sci. 6, 80-91 DOI: https://doi.org/10.1287/mnsc.6.1.80

Bellman, R. (1958), “On a routing problem”, in Quarterly of Applied Mathematics, 16(1): 87-90. DOI: https://doi.org/10.1090/qam/102435

Cruyssen, V. D. P., Rijkaert. M.,(1978), “Heuristic for the asymetric travelling salesmanproblem”, The Journal of the Operational Research Society, 29(7):697–701. DOI: https://doi.org/10.1057/jors.1978.147

Ahuja, R. K., Magnanti, T. L., Orlin, J. B. (1993), “Network Flows: Theory, algorithmsand applications”, Prentice Hall: New Jersey, 37:211-276.

Eiselt, H. A.,, Gendreau, M., Laporte, G.(1995), “Arc routing problems, Part 1:TheChinese Postman Problem”, Operations Research, 43(2): 231–242. DOI: https://doi.org/10.1287/opre.43.2.231

Golden, B.,Bodin L., Doyle T., Stewart W,(1980), “Approximate Traveling Salesman Algorithms”,Operations Research, June 1, : 694-711. DOI: https://doi.org/10.1287/opre.28.3.694

Pan, L., (2015). Cutting Plane Method. The Chinese University of Hong Kong,Operations Research and Logistics Jan. 20.

Araque, J.R., Kudva, G., Morin, T.L., Pekny, J.F., (1994). A branch-and-cut algorithm for vehicle routing problems. Annals of Operations Research 50, 37-59. DOI: https://doi.org/10.1007/BF02085634

Başkaya Z., Avcı Öztürk, B.,(2005). Tamsayılı programlamada dal kesme yöntemi ve bir ekmek fabrikasında oluşturulan araç rotalama problemine uygulanması. Uludağ Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi Cilt XXIV, Sayı 1, s. 101-114.

Cordeau, J.F., Gendreau, M., Laporte, G., Potvin, J.Y., Semet, F., (2002). A Guide to Vehicle Routing Heuristics. The Journal of the Operational Research Society, Vol. 53, No. 5 pp. 512-522. DOI: https://doi.org/10.1057/palgrave.jors.2601319

Bozyer, Z., Alkan, A., Fığlalı, A., (2014). Kapasite Kısıtlı Araç Rotalama Probleminin Çözümü için Önce Grupla Sonra Rotala Merkezli Sezgisel Algoritma Önerisi. Bilişim Teknolojileri Dergisi, Cilt: 7, Sayı: 2

Atmaca, E., (2012). Bir Kargo Şirketinde Araç Rotalama Problemi ve Uygulaması. Türk Bilim Araştırma Vakfı Dergisi, Cilt:5, Sayı:2, Sayfa: 12-27

Eryavuz, M., Gencer, C., (2001). Araç Rotalama Problemlerine Ait Bir Uygulama.Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi C.6, S.1, s.139-155.

Nilsson, C., (2003). Heuristics for the Traveling Salesman Problem. Linköping University.

Nurcahyo, G.W., Alias, R.A., Shamsuddın, S.M., Sap., M.N.M., (2002), Sweep Algorithm in Vehicle Routing Problem For Public Transport. Jurnal Antarabangsa (Teknologi Maklumat) 2(2002): 51-64.

Ropke, S., (2005). Heuristic and exact algorithms for vehicle routing problems.

Düzakın, E., Demircioğlu, M., (2009). Araç Rotalama Problemleri ve Çözüm Yöntemleri. Çukurova Üniversitesi İİBF Dergisi Cilt:13. Sayı:1, ss.68-87.

Laporte, G., (1992). The Vehicle Routing Problem: An overview of exact and approximatealgorithms. European Journal of Operational Research 59, 345-358. DOI: https://doi.org/10.1016/0377-2217(92)90192-C

Şahin, Y., Eroğlu, A., (2014). Kapasite Kısıtlı Araç Rotalama Problemi İçin Metasezgisel Yöntemler: Bilimsel Yazın Taraması.Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi C.19, S.4, s.337-355.

Genreau, M., Potvin, J.Y., Braysy, O., Hasle, G., Lokketangen, A., (2007). Metaheuristics for the vehicle routing problem and its extensions: a categorized bibliography. CIRRELT-2007-27.

Çevik, K.K., Koçer, H.E., (2013). Parçacık Sürü Optimizasyonu ile Yapay Sinir Ağları Eğitimine Dayalı Bir Esnek Hesaplama Uygulaması. Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 17 (2), 39-45.