A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs

Erdener ÖZÇETİN, (Hitit Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Çorum, Türkiye)
Gürkan ÖZTÜRK (Eskişehir Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Eskişehir, Türkiye)
Gazi Mühendislik Bilimleri Dergisi
2 0
Yıl: 2021 Cilt: 7 Sayı: 2 Sayfa Aralığı: 90 - 98 Metin Dili: İngilizce DOI: 10.30855/gmbd.2021.02.02 İndeks Tarihi: 29-07-2022

A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs

Öz:
In this study, the vehicle routing problem (VRP) which is a well-known NP-hard combinatorial optimization problem is handled on graphic processing units (GPUs). Solving any kind of VRP is extremely hard when the instance size is large. For this reason, researchers tend to solve the VRP with meta-heuristics. Although, many well-designed meta-heuristics produce near-optimal solutions in reasonable time, still a challenge to solve large scale instances. To accomplish this issue, researchers need novel, fast and wisely designed parallel operators for the proposed algorithms. Furthermore, the success of these operators directly depends on the way the solution is represented. This paper offers a new permutation based solution representation technique (π+) for vehicle routing problems on GPUs. Results show that proposed technique can be used in many algorithms to accelerate computations.
Anahtar Kelime: GPU vehicle routing problem parallel programming

Araç Rotalama Problemleri için Grafik İşlem Birimleri Üzerinde Yeni Bir Çözüm Gösterim Tekniği

Öz:
Bu çalışmada, NP-Hard kombinatorik optimizasyon problemlerinden olan araç rotalama problemi (ARP), grafik işlem birimleri (GPU) üzerinde ele alınmıştır. Problem boyutunun büyümesiyle birlikte ARP'nin herhangi bir türünü optimal olarak çözmek oldukça zorlaşmaktadır. Araştırmacılar bu yüzden metasezgisel yöntemlere yönelmektedir. Her ne kadar bu metasezgisel algoritmalar kabul edilebilir sürelerde optimale yakın sonuçlar üretse de büyük boyutlu problemler için bu durum farklıdır. Bu durumu aşmak için, araştırmacılar önerilen algoritmalar için yeni, hızlı ve akıllıca tasarlanmış paralel operatörlere ihtiyacı bulunmaktadır. Bu operatörlerin başarısı doğrudan çözümün temsil edilme şekline bağlıdır. Bu makale, ARP'yi GPU'lar üzerinde etkin bir şekilde ele alabilmek için yeni bir permütasyon tabanlı çözüm gösterim tekniği (π +) sunmaktadır. Sonuçlar, önerilen tekniğin hesaplamaları hızlandırmak için birçok algoritmada kullanılabileceğini göstermektedir.
Anahtar Kelime:

Belge Türü: Makale Makale Türü: Derleme Erişim Türü: Erişime Açık
  • [1] Gilbert Laporte, “The vehicle routing problem: An overview of exact and approximate algorithms”, European Journal of Operational Research, vol. 5 no. 3, pp. 345-358, 1992. doi:https:// dx.doi.org/10.1016/0377-2217(92)90192-C
  • [2] G. Dantzig and J. Ramser, “The Truck Dispatching Problem”, Management Science, vol. 6, pp. 80-91, 1959. doi: https://dx.doi.org/10.1287/mnsc.6.1.80
  • [3] P. Toth and D. Vigo, “The granular tabu search and its application to the vehicle-routing problem”, Informs Journal on Computing, vol. 15, no. 4, pp. 333-346, 2003. doi: https://dx.doi.org/10.1287/ijoc.15.4.333.24890
  • [4] D. Pisinger and S. Ropke, “A general heuristic for vehicle routing problems”, Computers & Operations Research, vol. 34, pp. 2403-2435, 2007. doi: https://dx.doi.org/10.1016/j.cor.2005.09.012
  • [5] S. N. Kumar and R. Panneerselvam, “A Survey on the Vehicle Routing Problem and Its Variants”, Intelligent Information Management, vol. 4, pp. 66-74, 2012. doi: https://dx.doi.org/10.4236/ iim.2012.43010
  • [6] E. Taillard, P. Badeau, M. Gendreau, F. Guertin and J.Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows”, Transportation Science, vol 31, no. 2, pp. 101-195, 1997. doi:https://dx.doi.org/10.1287/trsc.31.2.170
  • [7] K. Fleszar, I. Osman and K. Hindi, “A variable neighbourhood search for the open vehicle routing problem”, European Journal of Operational Research, vol. 195, pp. 803-809, 2009. doi: https://dx.doi.org/10.1016/j.ejor.2007.06.064
  • [8] Bin Yu, Zhong-Zhen Yang, Baozhen Yao, “An improved ant colony optimization for vehicle routing problem”, European Journal of Operational Research, vol. 196, no. 1, pp. 171-176, 2009. doi:https://dx.doi.org/10.1016/j.ejor.2008.02.028
  • [9] Shigeyoshi Tsutsui and Noriyuki Fujimoto, “Solving quadratic assignment problems by genetic algorithms with GPU computation: a case study,” in Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers (GECCO '09), New York, USA, 2009, pp. 2523– 2530. doi:https://dx.doi.org/10.1145/1570256.1570355
  • [10] S. Tsutsui and N. Fujimoto, "Fast QAP solving by ACO with 2-opt local search on a GPU," 2011 IEEE Congress of Evolutionary Computation (CEC), 2011, pp. 812-819. doi: https://dx.doi.org/10.1109/CEC.2011.5949702.
  • [11] M. Czapinski, “An effective Parallel Multistart Tabu Search for Quadratic Assignment Problem CUDA platform”, J. Parallel Distrib. Comput. , vol. 73, pp. 1461-1468, 2013. doi:https://dx.doi.org/10.1016/j.jpdc.2012.07.014
  • [12] E. Özçetin, G. Öztürk, “A Parallel Iterated Local Search Algorithm on GPUs for Quadratic Assignment Problem”, International Journal of Engineering Technologies, vol. 4, no. 2, pp. 123-127, 2018.
  • [13] E. Özçetin, G. Öztürk, “A Hybrid Genetic Algorithm for the Quadratic Assignment Problem on Graphics Processing Units”, Anadolu University Journal of Science and Technology-A Applied Sciences and Engineering, vol. 17, no. 1, pp. 167-180, 2016. doi: https://dx.doi.org/10.18038/btda.15399
  • [14] J. M. Cecilia, J. M. Garcia, A. Nisbet, M. Amos and M. Ujaldon, “Enhancing data parallelism for Ant Colony Optimization on GPUs”, J. Parallel Distrib. Comput., vol. 73, pp. 42-51, 2013. doi: https://dx.doi.org/10.1016/j.jpdc.2012.01.002
  • [15] A. Delevacq, P. Delisle, M. Gravel and M. Krajecki, “Parallel Ant Colony Optimization on Graphics Processing Units”, J. Parallel Distrib. Comput., vol. 73, pp. 52-61, 2013. doi: https://dx.doi.org/10.1016/j.jpdc.2012.01.003
  • [16] C. Shulz, “Efficient local search on the GPUInvestigations on the vehicle routing problem”, J. Parallel Distrib. Comput., vol. 73, no.1, pp. 14-31, 2013.
  • [17] C. Groer, B. Golden and E. Wasil, “A Parallel Algorithm for the Vehicle Routing Problem”, INFORMS Journal on Computing, vol. 23, pp. 315-330, 2011. doi: https://dx.doi.org/10.1287/ ijoc.1100.0402
  • [18] J. Szymon and Z. Dominik, “Solving Multicriteria Vehicle Routing Problem by Parallel Tabu Search on GPU”, Procedia Computer Science, vol. 18, pp. 2529-2532, 2013.
  • [19] Thé Van Luong, Nouredine Melab, El-Ghazali Talbi. “GPU Computing for Parallel Local Search Metaheuristics”, IEEE Transactions on Computers, vol. 62, no. 2, pp.173-185, 2013. doi: https://dx.doi.org/10.1109/TC.2011.206
  • [20] M.A. O’Neil, D. Tamir, M. Burtscher, “A parallel GPU version of the traveling salesman problem,” in: Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, Lasvegas, Nevada, USA, 2011, pp.348-353.
  • [21] I. Coelho, L. Ochi, P. Munhoz, M.Souza, C. Bentes, R. Farias, “The Single Vehicle Routing Problem with Deliveries and Selective Pickups in a CPU-GPU Heterogeneous Environment”, International Journal of Production Research, vol. 54, no. 4, 945-962, 2016. doi:https:// dx.doi.org/10.1080/00207543.2015.1035811
  • [22] K. Rocki and R. Suda, “Accelerating 2-opt and 3-opt Local Search Using GPU in the Travelling Salesman Problem” 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, 2012, pp. 705-706. doi: https://dx.doi.org/10.1109/CCGrid.2012.133.
  • [23] N. Melab, E.G. Talbi, S. Cahon, E. Alba, G. Luque, “Parallel Metaheuristics: Models and Frameworks,” in E.G. Talbi Parallel Combinatorial Optimization, John Wiley & Sons, Inc., New York, 2006, pp. 149-161.
  • [24] André R. Brodtkorb, Trond R. Hagen, Christian Schulz, Geir Hasle, “GPU computing in discrete optimization. Part I: Introduction to the GPU”, EURO Journal on Transportation and Logistics, vol. 2, no. 1–2, pp. 129-157, 2013. doi: https://dx.doi.org/10.1007/s13676-013-0025-1
  • [25] T. Davidović, P. Hansen, N. Mladenovic, “Permutation-based genetic, tabu and variable neighborhood search heuristics for multiprocessor scheduling with communication delays”, Asia Pacific Journal of Operational Research, vol. 22, no.3, 2005. doi:https://dx.doi.org/10.1142/S021759590500056X
  • [26] A. Klöckner, N. Pinto, Y. Lee, B. Catanzaro, P. Ivanov ve A. Fasih, “PyCUDA and PyOpenCL: A scripting-based approach to GPU run-time code generation”, Parallel Computing, vol. 38, no. 3, pp. 157-174, 2012.
APA OZCETIN E, Ozturk G (2021). A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. , 90 - 98. 10.30855/gmbd.2021.02.02
Chicago OZCETIN Erdener,Ozturk Gurkan A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. (2021): 90 - 98. 10.30855/gmbd.2021.02.02
MLA OZCETIN Erdener,Ozturk Gurkan A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. , 2021, ss.90 - 98. 10.30855/gmbd.2021.02.02
AMA OZCETIN E,Ozturk G A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. . 2021; 90 - 98. 10.30855/gmbd.2021.02.02
Vancouver OZCETIN E,Ozturk G A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. . 2021; 90 - 98. 10.30855/gmbd.2021.02.02
IEEE OZCETIN E,Ozturk G "A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs." , ss.90 - 98, 2021. 10.30855/gmbd.2021.02.02
ISNAD OZCETIN, Erdener - Ozturk, Gurkan. "A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs". (2021), 90-98. https://doi.org/10.30855/gmbd.2021.02.02
APA OZCETIN E, Ozturk G (2021). A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. Gazi Mühendislik Bilimleri Dergisi, 7(2), 90 - 98. 10.30855/gmbd.2021.02.02
Chicago OZCETIN Erdener,Ozturk Gurkan A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. Gazi Mühendislik Bilimleri Dergisi 7, no.2 (2021): 90 - 98. 10.30855/gmbd.2021.02.02
MLA OZCETIN Erdener,Ozturk Gurkan A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. Gazi Mühendislik Bilimleri Dergisi, vol.7, no.2, 2021, ss.90 - 98. 10.30855/gmbd.2021.02.02
AMA OZCETIN E,Ozturk G A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. Gazi Mühendislik Bilimleri Dergisi. 2021; 7(2): 90 - 98. 10.30855/gmbd.2021.02.02
Vancouver OZCETIN E,Ozturk G A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs. Gazi Mühendislik Bilimleri Dergisi. 2021; 7(2): 90 - 98. 10.30855/gmbd.2021.02.02
IEEE OZCETIN E,Ozturk G "A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs." Gazi Mühendislik Bilimleri Dergisi, 7, ss.90 - 98, 2021. 10.30855/gmbd.2021.02.02
ISNAD OZCETIN, Erdener - Ozturk, Gurkan. "A Novel Permutation Based Solution Representation Technique for Vehicle Routing Problems on GPUs". Gazi Mühendislik Bilimleri Dergisi 7/2 (2021), 90-98. https://doi.org/10.30855/gmbd.2021.02.02
Sayfa Oluşturulma Tarihi
15-05-2024 8:38

İLETİŞİM

TÜBİTAK ULAKBİM TR Dizin

Yüzüncüyıl, İşçi Blokları Mahallesi

Muhsin Yazıcıoğlu Caddesi No:51/C

06530 Çankaya / ANKARA +90 (312) 298 92 00

trdizin@tubitak.gov.tr

TÜBİTAK ULAKBİM Ulusal Akademik Ağ ve Bilgi Merkezi Cahit Arf Bilgi Merkezi © Tüm Hakları Saklıdır. Gizlilik Politikası Kullanım Şartları