Hierarchical Chinese Postman Problem with Stochastic Parameter Values and an Application

Abstract

The importance is given to the transportation sector, which greatly affects the economic and social development of countries, and therefore the importance given to the routing problems is increasing day by day. Today, cost-cutting policies should be followed in routing activities in both public institutions and private sectors. In this context, it is important to deliver a product or person to its destination in the shortest time and with the least cost. Routing problems are divided into two as edge routing and node routing. In this study, The hierarchical Chinese postman problem (HCPP), which is one of the route routing problems and aims to find the shortest tour or tours by passing at least once on arcs which classified according to priority relations, is discussed. Parameters appear as random variables due to uncertainty in many real-life problems. Travel time between nodes in a network; which varies depending on various reasons such as weather conditions, traffic density, etc so HCPP was solved by the chance-constrained stochastic programming approach in this study. In the study, deterministic model was created by using the chance constrained stochastic programming model emerging, when the objective function coefficients, which are random variables, have normal distribution. The developed mathematical model with stochastic parameter values was solved in GAMS 24.2.3 package program using CPLEX solver.

Keywords

• Arc routing problem
• hierarchical Chinese postman problem
• chance- constrained stochastic programming

Stokastik Parametre Değerlerine Sahip Hiyerarşik Çinli Postacı Problemi ve Bir Uygulama

Abstract

Ülkelerin ekonomik ve sosyal gelişimini büyük oranda etkileyen ulaşım sektörüne ve dolayısıyla rotalama problemlerine verilen önem gün geçtikçe artmaktadır. Günümüzde gerek kamu kuruluşları, gerekse özel sektörlerde rotalama faaliyetlerinde maliyet azaltıcı politikaların izlenmesi gerekmektedir. Bu bağlamda bir ürün veya kişinin gideceği yere en kısa sürede ve en az maliyetle ulaştırılması önem arz etmektedir. Rotalama problemleri ayrıt rotalama ve düğüm rotalama olmak üzere ikiye ayrılmaktadır. Bu çalışmada ayrıt rotalama problemlerinden biri olup öncelik ilişkilerine göre sınıflandırılmış ayrıtlardan en az bir kez geçilerek en kısa tur veya turların bulunmasını hedefleyen hiyerarşik Çinli postacı problemi (HÇPP) ele alınmıştır. Gerçek hayat problemlerinin birçoğunda belirsizlik nedeniyle parametreler rasgele değişken olarak karşımıza çıkmaktadır. Bir şebekede düğümler arasındaki ulaşım süresi; hava şartları, trafik yoğunluğu gibi çeşitli sebeplerden ötürü değişkenlik gösterdiği için bu çalışmada HÇPP, şans kısıtlı stokastik programlama yaklaşımı ile çözülmüştür. Çalışmada rasgele değişken olan amaç fonksiyonu katsayılarının normal dağılıma sahip olması durumunda ortaya çıkan şans kısıtlı stokastik programlama modeli kullanılarak deterministik model oluşturulmuştur. Geliştirilen stokastik parametre değerlerine sahip matematiksel model GAMS 24.2.3 paket programında CPLEX çözücü kullanılarak çözülmüştür.

Keywords

• Ayrıt rotalama problemi
• hiyerarşik Çinli postacı problemi
• şans kısıtlı stokastik programlama

References

1. Anonim, 2020. Normal Dağılım ve Veri Bilim’indeki Yeri. https://medium.com/datarunner/normaldagilim-589846bb850a (Erişim Tarihi: 22.06.2020).
2. Ahuja RK, Magnanti TL, Orlin JB, 1993. Network Flows: Theory, Algorithms and Applications. Prentice Hall: New Jersey.
3. Aksaraylı M, Pala O, 2015. Şans Kısıtlı Stokastik Programlama Yaklaşımı ile Ofis Ürünleri Üretim Sistemi Modellemesi. 15. Üretim Araştırmaları Sempozyumu, Ekim 2015, İzmir.
4. Alankaya G, 2013. Şans Kısıtlı Stokastik Doğrusal Programlama. Marmara Üniversitesi Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi (Basılmış).
5. Arvianto A, Saptadi S, Budiawan W, Nartadhi RL, 2019. Vehicle routing problem model and simulation with probabilistic demand and sequential insertion, Proceedings of the 5th International Conference on Engineering, Technology, and Industrial Application (ICETIA) 2019, 12–13 December 2018, Surakarta, Indonesia.
6. Atalay KD, Apaydın A, 2011. Şans kısıtlı stokastik programlama problemlerinin deterministik eşitlikleri. Anadolu Üniversitesi Bilim ve Teknoloji Dergisi. 1: 1-18.
7. Bianchi L, Birattari M, Chiarandini M, Manfrin M, Mastrolilli M, Paquete L, Schiavinotto T, 2006. Hybrid metaheuristics for the vehicle routing problem with stochastic demands. Journal of Mathematical Modelling and Algorithms, 5: 91-110.
8. Calvet L, Bernaus AP, Travessat-Baro O, Juan AA, 2016. A Simheuristic for the heterogeneous site-dependent asymetric VRP with stochastic demands. Advances in Artificial Intelligence, 408-417.

9. Chepuri K, Homem-De-Mello T, 2005. Solving the vehicle routing problem with stochastic demands using the cross-entropy method. Annals of Operations Research, 134: 153-181.
10. Corberan A, Marti R, Sanchis JM, 2002. A grasp heuristic for the mixed chinese postman problem. European Journal of Operational Research, 142: 70-80.
11. Çodur MK, Yılmaz M, 2020. A time-dependent hierarchical Chinese postman problem. Central European Journal of Operations Research, 28: 337-366.
12. Dror M, Stern H, Trudeau P, 1987. Postman tour on a graph with precedence relation on arcs. Networks, 17: 283-294.
13. Filho GM, Junqueira RDÁR, 2006. Chinese postman problem: solution methods choice and computational time analysis. Production, 16: 538-551.
14. Florio AM, Hartl RF, Minner S, 2018. New exact algorithm and solution properties for the vehicle routing problem with stochastic demands. Technical Report. arXiv: 1806.08549.
15. Gee SB, Arokiasami WA, Jiang J, Tan K.C, 2016. Decomposition-based multi-objective evolutionary algortihm for vehicle routing problem with stochastic demands. Soft Computing, 20: 3443-3453.
16. Gendreau M, Laporte G, Guo B, 1996. Stochastic vehicle routing: Invited review. European Journal of Operational Research, 88: 3-12.
17. Hu C, Lu J, Liu X, Zhang G, 2018. Robust vehicle routing problem with hard time windows under demand and travel time uncertaint. Computational Optimization and Applications, 61: 463-487.
18. Hulsurkar S, Biswal MP, Sinha SB, 1997. Fuzzy programming approach to multi-objective stochastic linear programming problems. Fuzzy Sets and Systems, 88:173-181.
19. Hvattum LM, Lokketangen A, Laporte G, 2004. A heuristic solution method to a stochastic vehicle routing problem. In Proceedings of TRISTAN V—The Fifth Triennial Symposium on Transportation Analysis, 2004, 13-18 June, Guadeloupe, France.
20. İşleyen SK, 2008. Lojistik Yönetim Sistemlerinde Stokastik Talepli Araç Rotalama Problemi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Doktora Tezi (Basılmış).
21. Korteweg P, Volgenant T, 2006. On the hierarchical Chinese postman problem with linear ordered classes. European Journal of Operational Research, 169: 41-52.
22. Li X, Tian P, Leung SC, 2010. Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm. International Journal of Production Economics, 125: 137-145.
23. Liu C, Kou G, Huang F, 2016. Vehicle coordinated strategy for vehicle routing problem with fuzzy demands. Mathematical Problems in Engineering, 1-10.
24. Majumder S, Kar S, Pal T, 2019. Uncertain multi-objective Chinese postman problem. Soft Computing, 23: 11557-11572.
25. Mak KL, Guo ZG, 2004, A genetic algorithm for vehicle routing problems with stochastic demand and soft time windows, Proceedings of the 2004 IEEE Systems and Information Engineering Design Symposium, 2004, Virginia, USA.
26. Miranda DM, Conceição SV, 2016. The vehicle routing problem with hard time windows and stochastic travel and service time. Expert Systems with Applications, 64: 104-116.
27. Qin J, Ye Y, Cheng B, Zhao X, Ni L, 2017. The emergency vehicle routing problem with uncertain demand under sustainability environment. Sustainability, 9: 288.
28. Shafahi A, Haghani A, 2015. Generalized maximum benefit multiple chinese postman problem. Transportation Research Part C: Emerging Technologies, 55: 261-272.
29. Shen Z, Ordónez F, Dessouky MM, 2009. The stochastic vehicle routing problem for minimum unmet demand. Optimization and Logistics Challenges in the Enterprise, 30: 349-371.
30. Sökmen ÖÇ, Yılmaz M, 2019. Stochastic chinese postman problem and an application. 4th International Energy and Engineering Congress. Gaziantep, 24- 25 October, 2019, 1160-1168.
31. Subramanyam A, Repoussis PP, Gounaris CE, 2018. Robust optimization of broad class of heterogeneous vehicle routing problems under demand uncertainty. INFORMS Journal on Computing. 1-54.
32. Taha HA, 2000.Yöneylem Araştırması, 1.basım, Literatür Yayıncılık, İstanbul.
33. Tan G, Cui X, Zhang Y, 2005. Chinese postman problem in stochastic networks. In Joint International Conference on Autonomic and Autonomous Systems and International Conference on Networking and Services (icas-isns'05). Papeete, Tahiti, French Polynesia, October 23-28, 2005, pp:78-78.
34. Taş D, Gendreau M, Dellaert N, Van Woensel T, De Kok AG, 2014. Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach. European Journal of Operational Research, 236: 789-799.
35. Thimbleby H, 2003. Explaining code for publication. Software: Practice and Experience, 33: 975-1001.
36. Uslu A, Çetinkaya C, İşleyen SK, 2017. Vehicle routing problem in post-disaster humanitarian relief logistics: A case study in Ankara. Sigma Journal of Engineering and Natural Science, 35: 481-499.
37. Willemse EJ, Joubert JW, 2016. Splitting procedures for the mixed capacitated arc routing problem under time restrictions with intermediate facilities. Operations Research Letters, 44: 569-574.
38. Yılmaz M, Çodur MK, Yılmaz H, 2017. Chinese postman problem approach for a large-scale conventional rail network in Turkey. Tehnički Vjesnik, 24: 1471-1477.
39. Yılmaz M, 2018. Karayolları bakım çalışmasında kullanılan araçların güzergâhlarının hiyerarşik Çinli postacı problemi kullanılarak düzenlenmesi. Iğdır Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 8: 107-115.