Fuzzy linear programming approach for the capacitated vehicle routing problem

Abstract

In recent years, with both technological advances and the effect of globalization, businesses have entered a very intense competition. In this harsh competitive environment, customer satisfaction has become a critical concept. Firms implement costs reducing strategies in order to increase profitability levels and gain competitive advantage in the market. Researches show that a significant ratio of the cost of a product is derived from the transport activities. Therefore, it has become important for companies to find the optimal route during transportation. In this study, it is addressed as capacity constrained vehicle routing. First, a deterministic model is proposed for the addressed problem. Second, in accordance with real life conditions, a fuzzy linear programming model has been developed in case of the vehicle capacities are uncertain. The Verdegay approach has been adopted for the fuzzy linear programming model. The proposed model was implemented to a real life problem in the food sector. The results are compared with the results of a deterministic model and they show that the fuzzy linear programming model proposed in this study gives cost effective results in uncertain environment.

Keywords

• Vehicle Routing Problem
• Fuzzy Logic
• Verdegay Method

References

1. Alağaş, H. M., Çetin, S., Yerlikaya, A., & Eren, T. (2016). Heterojen Eş-Zamanlı Topla-Dağıt Rotalama Problemi: Tehlikeli Malzeme Sevkiyatı. 4th International Symposium on Innovative Technologies in Engineering and Science (ISITES2016), 472–780.
2. Aliahmadi, S. Z., Barzinpour, F., & Pishvaee, M. S. (2021). A novel bi-objective credibility-based fuzzy model for municipal waste collection with hard time windows. Journal of Cleaner Production, 296, 126364. https://doi.org/10.1016/j.jclepro.2021.126364
3. Arab, R., Ghaderi, S. F., & Tavakkoli-Moghaddam, R. (2020). Bi-objective inventory routing problem with backhauls under transportation risks: two meta-heuristics. Transportation Letters, 12(2), 113–129. https://doi.org/10.1080/19427867.2018.1533624
4. Atmaca, H. E., Vardar, S., Akbabaöz, S., Vural, A., & Uruş, G. (2015). Ankara İlinde Ürün Dağıtımı Yapan Bir Beyaz Eşya Yetkili Servisinin Araç Rotalama Problemine Çözüm Yaklaşımı. Politeknik Dergisi, 18(2), 99–105.
5. Ayvaz, B., Kuşakcı, A. O., Öztürk, F., & Sırakaya, M. (2018). Biyodizel tedarik zinciri ağ tasarımı için çok amaçlı karma tam sayılı doğrusal programlama modeli önerisi. Uludağ University Journal of The Faculty of Engineering, 23(4), 55–70. https://doi.org/10.17482/uumfd.455307
6. Bahri, O., Talbi, E.-G., & Ben Amor, N. (2018). A generic fuzzy approach for multi-objective optimization under uncertainty. Swarm and Evolutionary Computation, 40, 166–183. https://doi.org/10.1016/j.swevo.2018.02.002
7. Başkaya, Z. (2011). Bulanık Doğrusal Programlama. Ekin Yayınevi.
8. Başkaya, Z., & Öztürk, B. A. (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, 24(1), 101–114.

9. Baykasoğlu, A., & Subulan, K. (2015). An analysis of fully fuzzy linear programming with fuzzy decision variables through logistics network design problem. Knowledge-Based Systems, 90, 165–184. https://doi.org/10.1016/j.knosys.2015.09.020
10. Bilgen, B. (2010). Application of fuzzy mathematical programming approach to the production allocation and distribution supply chain network problem. Expert Systems with Applications, 37(6), 4488–4495. https://doi.org/10.1016/j.eswa.2009.12.062
11. Brito, J., Campos, C., Castro, J. P., Martínez, F. J., Melián, B., Moreno, J. A., & Moreno, J. M. (2008). Fuzzy Vehicle Routing Problem with Time Windows. Proceedings of IPMU, Málaga, Spain, 1266-1273.
12. Brito, J., Moreno-Pérez, J. A., & Verdegay, J. L. (2009). Fuzzy Optimization in Vehicle Routing Problems. Proceedings of the Joint 2009 International Fuzzy Systems Association World Congress and 2009 European Society of Fuzzy Logic and Technology Conference, Lisbon, Portugal, 1547-1552.
13. Caccetta, L., & Hill, S. P. (2001). Branch and cut methods for network optimization. Mathematical and Computer Modelling, 33(4–5), 517–532. https://doi.org/10.1016/S0895-7177(00)00258-2
14. Dai, Z., & Zheng, X. (2015). Design of close-loop supply chain network under uncertainty using hybrid genetic algorithm: A fuzzy and chance-constrained programming model. Computers & Industrial Engineering, 88, 444–457. https://doi.org/10.1016/j.cie.2015.08.004
15. El-Sherbeny, N. A. (2011). Imprecision and Flexible Constraints in Fuzzy Vehicle Routing Problem. American Journal of Mathematical and Management Sciences, 31(1–2), 55–71. https://doi.org/10.1080/01966324.2011.10737800
16. Ergülen, A., & Kazan, H. (2007). Taşımacılık sektörünün işleyiş süreci, Bulanık dağıtım probleminin tamsayılı doğrusal programlama model denemesi. Uluslararası Yönetim İktisat ve İşletme Dergisi, 3(6), 109–126.
17. Eryavuz, M., & Gencer, C. (2001). Araç Rotalama Problemine Ait Bir Uygulama. Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 6(1), 139–155.
18. Fazlollahtabar, H., Mahdavi, I., & Mohajeri, A. (2013). Applying fuzzy mathematical programming approach to optimize a multiple supply network in uncertain condition with comparative analysis. Applied Soft Computing, 13(1), 550–562. https://doi.org/10.1016/j.asoc.2012.08.016
19. Giallanza, A., & Puma, G. L. (2020). Fuzzy green vehicle routing problem for designing a three echelons supply chain. Journal of Cleaner Production, 259, 120774. https://doi.org/10.1016/j.jclepro.2020.120774
20. Güngör, İ., & Ergülen, A. (2006). Bulanık Araç Rotalama Problemlerine Bir Model Önerisi ve Bir Uygulama. Yönetim ve Ekonomi: Celal Bayar Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 13(1), 53–60.
21. Güvez, H., Dege, M., & Eren, T. (2012). Medical Waste Collection with Vehicle Routing Problem in Kırıkkale. Uluslararası Mühendislik Araştırma ve Geliştirme Dergisi, 4(1), 41–45.
22. Karagül, K., & Güngör, İ. (2014). Havalimanından otellere tek tip araçlarla turist dağıtımı problemine çözüm önerisi ve Alanya uygulaması. Dumlupınar Üniversitesi Sosyal Bilimler Dergisi, 189–196.
23. Kesen, S. E. (2012). Bütünleşik üretim ve dağıtım problemleri için yeni bir çözüm yaklaşımı: Matematiksel modelleme. Selçuk Üniversitesi Mühendislik, Bilim Ve Teknoloji Dergisi, 27(3), 99–110.
24. Kovacs, A. A., Parragh, S. N., & Hartl, R. F. (2015). The multi-objective generalized consistent vehicle routing problem. European Journal of Operational Research, 247(2), 441–458. https://doi.org/10.1016/j.ejor.2015.06.030
25. Lin, J., Zhou, W., & Wolfson, O. (2016). Electric Vehicle Routing Problem. Transportation Research Procedia, 12, 508–521. https://doi.org/10.1016/j.trpro.2016.02.007
26. Men, J., Jiang, P., & Xu, H. (2019). A chance constrained programming approach for HazMat capacitated vehicle routing problem in Type-2 fuzzy environment. Journal of Cleaner Production, 237, 117754. https://doi.org/10.1016/j.jclepro.2019.117754
27. Mohammed, A., & Wang, Q. (2017). The fuzzy multi-objective distribution planner for a green meat supply chain. International Journal of Production Economics, 184, 47–58. https://doi.org/10.1016/j.ijpe.2016.11.016
28. Mousavi, S. M., Vahdani, B., Tavakkoli-Moghaddam, R., & Hashemi, H. (2014). Location of cross-docking centers and vehicle routing scheduling under uncertainty: A fuzzy possibilistic–stochastic programming model. Applied Mathematical Modelling, 38(7–8), 2249–2264. https://doi.org/10.1016/j.apm.2013.10.029
29. Nadizadeh, A., & Kafash, B. (2019). Fuzzy capacitated location-routing problem with simultaneous pickup and delivery demands. Transportation Letters, 11(1), 1–19. https://doi.org/10.1080/19427867.2016.1270798
30. Özkök, B. A., & Kurul, F. C. (2014). Araç rotalama problemine tam sayılı lineer programlama modeli ve gıda sektöründe bir uygulama. İstanbul Üniversitesi İşletme Fakültesi Dergisi, 43, 251–260.
31. Öztürk, F. (2014). Qualität, effizienzsteigerung und integrierte managementsystemen im türkischen eisenbahnsektor. Social and Natural Sciences Journal, 8(2). https://doi.org/10.12955/snsj.v8i2.657
32. Öztürk, F. (2021). A Hybrid Type-2 Fuzzy Performance Evaluation Model for Public Transport Services. Arabian Journal for Science and Engineering, 46(10), 10261–10279. https://doi.org/10.1007/s13369-021-05687-4
33. Öztürk, F., & Kaya, G. K. (2020). Afet sonrası toplanma alanlarının PROMETHEE metodu ile değerlendirilmesi. Uludağ University Journal of The Faculty of Engineering, 1239–1252. https://doi.org/10.17482/uumfd.697097
34. Öztürk, F., Kuşakcı, A. O., Ayvaz, B., & Sırakaya Karakoç, M. (2020). Biyoyakıt tedarik zinciri ağ tasarımı çalışmaları için öz düzenleyici haritalar. Mühendislik Bilimleri ve Tasarım Dergisi, 8(2), 345–356. https://doi.org/10.21923/jesd.509079
35. Paksoy, T., Özceylan, E., & Pehlivan, N. Y. (2013). Bulanık küme teorisi. Nobel Akademik Yayıncılık.
36. Radojičić, N., Djenić, A., & Marić, M. (2018). Fuzzy GRASP with path relinking for the Risk-constrained Cash-in-Transit Vehicle Routing Problem. Applied Soft Computing, 72, 486–497. https://doi.org/10.1016/j.asoc.2018.05.022
37. Şahin, Y., & Eroğlu, A. (2015). Sipariş Toplama ve Kapasite Kısıtlı Araç Rotalama Problemlerinin Hiyerarşik Çözümü. Süleyman Demirel Üniversitesi Mühendislik Bilimleri ve Tasarım Dergisi, 3, 15–28.
38. Shao, S., Guan, W., Ran, B., He, Z., & Bi, J. (2017). Electric Vehicle Routing Problem with Charging Time and Variable Travel Time. Mathematical Problems in Engineering, 2017, 1–13. https://doi.org/10.1155/2017/5098183
39. Szeto, W. Y., Wu, Y., & Ho, S. C. (2011). An artificial bee colony algorithm for the capacitated vehicle routing problem. European Journal of Operational Research, 215(1), 126–135. https://doi.org/10.1016/j.ejor.2011.06.006
40. Tang, J., Pan, Z., Fung, R. Y. K., & Lau, H. (2009). Vehicle routing problem with fuzzy time windows. Fuzzy Sets and Systems, 160(5), 683–695. https://doi.org/10.1016/j.fss.2008.09.016
41. Taş, D., Jabali, O., & Van Woensel, T. (2014). A Vehicle Routing Problem with Flexible Time Windows. Computers & Operations Research, 52, 39–54. https://doi.org/10.1016/j.cor.2014.07.005
42. Toth, P., & Vigo, D. (2002). The Vehicle Routing Problem. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9780898718515
43. Ultaş, A., Bayrakçıl, A. O., & Kutlu, B. (2017). Araç rotalama probleminin tasarruf algoritması ile çözümü: Sivas’ta Bir Ekmek Fırını İçin Uygulama. Cumhuriyet Üniversitesi İktisadi ve İdari Bilimler Dergisi, 18(1), 185–197.
44. Verdegay, J. L. (1984). Applications of fuzzy optimization in operational research. Control and Cybernetics, 13, 229–240.
45. Werners, B. (1987). Interactive multiple objective programming subject to flexible constraints. European Journal of Operational Research, 31(3), 342–349. https://doi.org/10.1016/0377-2217(87)90043-9
46. Werners, B., & Drawe, M. (2003). Capacitated Vehicle Routing Problem with Fuzzy Demand (pp. 317–335). https://doi.org/10.1007/978-3-540-36461-0_21
47. Yu, J., & Dong, Y. (2013). Maximizing profit for vehicle routing under time and weight constraints. International Journal of Production Economics, 145(2), 573–583. https://doi.org/10.1016/j.ijpe.2013.05.009
48. Yücenur, G. N., & Demirel, N. Ç. (2011). A hybrid algorithm with genetic algorithm and ant colony optimization for solving multi-depot vehicle routing problems. Sigma Journal of Engineering and Natural Sciences, 29, 340–350.
49. Zhang, J., Zhao, Y., Xue, W., & Li, J. (2015). Vehicle routing problem with fuel consumption and carbon emission. International Journal of Production Economics, 170, 234–242. https://doi.org/10.1016/j.ijpe.2015.09.031
50. Zhang, S., Chen, M., Zhang, W., & Zhuang, X. (2020). Fuzzy optimization model for electric vehicle routing problem with time windows and recharging stations. Expert Systems with Applications, 145, 113123. https://doi.org/10.1016/j.eswa.2019.113123