Constraint programming approaches for the electric vehicle routing problem with simultaneous pickup and delivery

Öz

With the increasing consumption of resources and the environmental damage caused by conventional vehicles in transportation systems, the use of environmentally friendly electric vehicles has been gaining importance within sustainability-oriented efforts. This study focuses on the Electric Vehicle Routing Problem (EVRP) and the Simultaneous Pickup and Delivery Electric Vehicle Routing Problem (SPD-EVRP), in which delivery and collection operations are performed simultaneously. The studied problems aim to minimize the total cost, which includes the cost of distance-based electricity consumption and the cost of the total number of electric vehicles used. In this study, a mixed-integer linear programming (MILP) model and two different constraint programming (CP) models are developed for the EVRP by using different modeling approaches from the studies in the literature. Two novel MILP and two new CP models have also been developed for SPD-EVRP. Symmetry-breaking structures are used in the proposed MILP and CP models for the EVRP and SPD-EVRP to reduce the solution space of the problems. The performance of the developed mathematical models is tested on the generated instances by performing a detailed numerical analysis. When the numerical results are examined, it is observed that, as the problem size increases, the CP models demonstrate superior solution performance compared to the MILP models. Furthermore, the incorporation of symmetry-breaking structures enhances the computational efficiency of both CP and MILP approaches.

Anahtar Kelimeler

• Electric Vehicle Routing
• Simultaneous Pick-up and Delivery
• Mixed-Integer Linear Programming
• Constraint Programming

Eş zamanlı dağıtım ve toplamalı elektrikli araç rotalama problemi için kısıt programlama yaklaşımları

Öz

Ulaştırma faaliyetlerinde kaynak tüketimi ve geleneksel araçların çevreye verdiği zararların artması ile sürdürülebilirlik çalışmaları kapsamında çevre dostu elektrikli araçların kullanımı giderek artmaktadır. Bu çalışmada, elektrikli araç rotalama problemi (EARP) ve dağıtım ve toplama operasyonlarının eş zamanlı gerçekleştiği eş zamanlı dağıtım ve toplamalı elektrikli araç rotalama problemi (EDT-EARP) incelenmiştir. Çalışılan problemlerde, mesafeye bağlı toplam elektrik tüketim maliyeti ve kullanılan toplam elektrikli araç sayısının maliyetini içeren toplam maliyet minimizasyonu hedeflenmiştir. Bu çalışmada, literatürdeki çalışmalardan farklı modelleme yaklaşımları kullanılarak EARP için bir karma tam sayılı doğrusal programlama (KTDP) modeli ve iki farklı kısıt programlama (KP) modeli sunulmuştur. Ayrıca, EDT-EARP için iki özgün KTDP modeli ve iki özgün KP modeli de geliştirilmiştir. Çalışmada çözüm uzayını daraltmak amacıyla EARP ve EDT-EARP için önerilen KTDP ve KP modellerinde simetri-kırma yapısı kullanılmıştır. Geliştirilen matematiksel modellerin performansı üretilen veri örnekleri üzerinde detaylı sayısal analizler yapılarak karşılaştırılmıştır. Sayısal sonuçlar incelendiğinde, problemin boyutu arttıkça geliştirilen KP modellerinin KTDP modellerine kıyasla daha iyi çözüm performansı gösterdiği görülmüştür. Ayrıca, simetri-kırma yapısının kullanımı ile hem KP hem de KTDP modellerinin etkinliğinin arttığı gözlemlenmiştir.

Anahtar Kelimeler

• Elektrikli Araç Rotalama
• Eş Zamanlı Dağıtım Toplama
• Karma Tamsayılı Doğrusal Programlama
• Kısıt Programlama

Teşekkür

Bu çalışma 1. Yazar İclal Bağcı’nın İzmir Demokrasi Üniversitesi’nde yürütülen yüksek lisans tezinden üretilmiştir (Ulusal Tez Merkezi Tez Numarası: 882651)

Kaynakça

1. 1. Khan I., Hou F., Le H.P., The impact of natural resources, energy consumption, and population growth on environmental quality: Fresh evidence from the United States of America, Science of the Total Environment, 754, 142222, 2021.
2. 2. Van Fan Y., Lee C.T., Lim J.S., Klemeš J.J., Le P.T.K., Cross-disciplinary approaches towards smart, resilient and sustainable circular economy, Journal of Cleaner Production, 232, 1482–1491, 2019.
3. 3. Sobol Ł., Dyjakon A., The influence of power sources for charging the batteries of electric cars on CO₂ emissions during daily driving: A case study from Poland, Energies, 13 (16), 4267, 2020.
4. 4. Alrubaie A.J., Salem M., Yahya K., Mohamed M., Kamarol M., A comprehensive review of electric vehicle charging stations with solar photovoltaic system considering market, technical requirements, network implications, and future challenges, Sustainability, 15 (10), 8122, 2023.
5. 5. Zhao Z., Li X., Zhou X., Distribution route optimization for electric vehicles in urban cold chain logistics for fresh products under time-varying traffic conditions, Mathematical Problems in Engineering, 2020 (1), 9864935, 2020.
6. 6. Zhang S., Guan C., Qiu Y., Wu N., Multi-objective route optimization of urban cold chain distribution using electric and diesel powered vehicles, Research in Transportation Business and Management, 49, 100969, 2023. 7. Zhao M., Lu Y., A heuristic approach for a real-world electric vehicle routing problem, Algorithms, 12 (2), 45, 2019.
7. 8. Erdem M., Koç Ç., Analysis of electric vehicles in home health care routing problem, Journal of Cleaner Production, 234, 1471–1483, 2019.
8. 9. Li Y., Lim M.K., Tan Y., Lee Y., Tseng M.L., Sharing economy to improve routing for urban logistics distribution using electric vehicles, Resources, Conservation and Recycling, 153, 104585, 2020.

9. 10. Keskin M., Çatay B., A matheuristic method for the electric vehicle routing problem with time windows and fast chargers, Computers and Operations Research, 100, 172–188, 2018.
10. 11. Keçeci B., Altıparmak F., Kara İ., Heterogeneous vehicle routing problem with simultaneous pickup and delivery: Mathematical formulations and a heuristic algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 30 (2), 185–195, 2015.
11. 12. Belgin Ö., Karaoğlan İ., Altıparmak F., Mathematical programming based heuristic approach for two-echelon vehicle routing problem with simultaneous pickup and delivery, Journal of the Faculty of Engineering and Architecture of Gazi University, 36 (3), 1566–1579, 2021.
12. 13. Küçük M., Yıldız Ş.T., A constraint programming approach for the pickup and delivery problem with time windows, Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 25 (9), 1041–1049, 2019.
13. 14. Boz, E., Çalık, A., & Şahin, Y., Solution approaches for the green vehicle routing problem with time window and simultaneous pickup and delivery, Journal of the Faculty of Engineering and Architecture of Gazi University, 39 (2), 757-770, 2024.
14. 15. Kucukoglu I., Dewil R., Cattrysse D., The electric vehicle routing problem and its variations: A literature review, Computers and Industrial Engineering, 161, 107650, 2021.
15. 16. Bruglieri M., Pezzella F., Pisacane O., Suraci S., A variable neighborhood search branching for the electric vehicle routing problem with time windows, Electronic Notes in Discrete Mathematics, 47, 221–228, 2015.
16. 17. Goeke D., Schneider M., Routing a mixed fleet of electric and conventional vehicles, European Journal of Operational Research, 245 (1), 81–99, 2015.
17. 18. Hiermann G., Puchinger J., Ropke S., Hartl R.F., The electric fleet size and mix vehicle routing problem with time windows and recharging stations, European Journal of Operational Research, 252 (3), 995–1018, 2016.
18. 19. Schneider M., Stenger A., Goeke D., The electric vehicle-routing problem with time windows and recharging stations, Transportation Science, 48 (4), 500–520, 2014.
19. 20. Dönmez S., Koç Ç., Altıparmak F., The mixed fleet vehicle routing problem with partial recharging by multiple chargers: A formulation and an insertion based constructive heuristic, Journal of the Faculty of Engineering and Architecture of Gazi University, 39 (1), 1-16, 2024.
20. 21. Grandinetti L., Guerriero F., Pezzella F., Pisacane O., A pick-up and delivery problem with time windows by electric vehicles, International Journal of Productivity and Quality Management, 18 (2–3), 403–423, 2016.
21. 22. Lin J., Zhou W., Wolfson O., Electric vehicle routing problem, Transportation Research Procedia, 12, 508–521, 2016.
22. 23. Goeke D., Granular tabu search for the pickup and delivery problem with time windows and electric vehicles, European Journal of Operational Research, 278 (3), 821–836, 2019.
23. 24. Sayarshad H.R., Mahmoodian V., Gao H.O., Non-myopic dynamic routing of electric taxis with battery swapping stations, Sustainable Cities and Society, 57, 102113, 2020.
24. 25. Soysal M., Çimen M., Belbağ S., Pickup and delivery with electric vehicles under stochastic battery depletion, Computers and Industrial Engineering, 146, 106512, 2020.
25. 26. Ghobadi A., Tavakkoli Moghadam R., Fallah M., Kazemipoor H., Multi-depot electric vehicle routing problem with fuzzy time windows and pickup/delivery constraints, Journal of Applied Research on Industrial Engineering, 8 (1), 1–18, 2021.
26. 27. Murarețu I., Bădică C., Optimal agent-based pickup and delivery with time windows and electric vehicles, Applied Sciences, 14 (17), 7528, 2024.
27. 28. İbiş Bozyel M., Soysal M., Çimen M., A many-to-many pick-up and delivery problem under stochastic battery depletion of electric vehicles, Transportation Letters, 16 (10), 1287–1304, 2024.
28. 29. Abdulaal A., Cintuglu M.H., Asfour S., Mohammed O.A., Solving the multivariant EV routing problem incorporating V2G and G2V options, IEEE Transactions on Transportation Electrification, 3 (1), 238–248, 2016.
29. 30. Li L., Li T., Wang K., Gao S., Chen Z., Wang L., Heterogeneous fleet electric vehicle routing optimization for logistic distribution with time windows and simultaneous pick-up and delivery service, 16th International Conference on Service Systems and Service Management, 1–6, Temmuz 2019.
30. 31. Yilmaz Y., Kalayci C.B., Variable neighborhood search algorithms to solve the electric vehicle routing problem with simultaneous pickup and delivery, Mathematics, 10 (17), 3108, 2022.
31. 32. Xu W., Zhang C., Cheng M., Huang Y., Electric vehicle routing problem with simultaneous pickup and delivery: Mathematical modeling and adaptive large neighborhood search heuristic method, Energies, 15 (23), 9222, 2022.
32. 33. Cai W., Zhang Y., Huang F., Ma C., Delivery routing problem of pure electric vehicle with multi-objective pick-up and delivery integration, Plos One, 18 (2), e0281131, 2023.
33. 34. Devaux Y., Bahri O., Amodeo L., A new simultaneous pickup and delivery problem with time windows using an heterogeneous fleet of electric vehicle and considering energy consumption, 9th International Conference on Control, Decision and Information Technologies, 2223–2228, Temmuz 2023.
34. 35. Xu W., Cheng M., Intelligent scheduling on electric vehicle routing problem with simultaneous pickup and delivery, 3rd International Conference on Artificial Intelligence and Education, 1168–1174, Aralık 2022.
35. 36. Wang L., Ding Y., Chen Z., Su Z., Zhuang Y., Heuristic algorithms for heterogeneous and multi-trip electric vehicle routing problem with pickup and delivery, World Electric Vehicle Journal, 15 (2), 69, 2024.
36. 37. Akbay M.A., Kalayci C.B., Blum C., Application of Adapt-CMSA to the two-echelon electric vehicle routing problem with simultaneous pickup and deliveries, Lecture Notes in Computer Science, 13987, 16–33, 2023.
37. 38. Akbay M.A., Kalayci C.B., Blum C., Application of CMSA to the electric vehicle routing problem with time windows, simultaneous pickup and deliveries, and partial vehicle charging, Lecture Notes in Computer Science, 13838, 1–16, 2022.
38. 39. Akbay M.A., Blum C., Kalayci C.B., Application of Adapt-CMSA to the electric vehicle routing problem with simultaneous pickup and deliveries, Lecture Notes in Computer Science, 15172, 90–106, 2024.
39. 40. Booth K.E., Beck J.C., A constraint programming approach to electric vehicle routing with time windows, Integration of Constraint Programming, Artificial Intelligence, and Operations Research, 129–145, 2019.
40. 41. Lam E., Desaulniers G., Stuckey P.J., Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations, Computers and Operations Research, 145, 105870, 2022.
41. 42. Ahmadi S., Tack G., Harabor D., Kilby P., Vehicle dynamics in pickup-and-delivery problems using electric vehicles, International Conference on Principles and Practice of Constraint Programming, 11, 2021.
42. 43. Desaulniers G., Errico F., Irnich S., Schneider M., Exact algorithms for electric vehicle-routing problems with time windows, Operations Research, 64 (6), 1388–1405, 2016.
43. 44. Toth P., Vigo D., Models, relaxations and exact approaches for the capacitated vehicle routing problem, Discrete Applied Mathematics, 123 (1–3), 487–512, 2002.
44. 45. Bağcı İ. EARP ve EDT-EARP için veri örnekleri.https://drive.google.com/file/d/1jepfoDBgzpU5bkUc7u07WDA9FPQ-QOf_/view?usp=sharing.Yayın tarihi, 2026. Erişim tarihi, 2026.
45. 46. Edis E.B., Constraint programming approaches to disassembly line balancing problem with sequencing decisions, Computers and Operations Research, 126, 105111, 2021.
46. 47. Bağcı İ., Eş zamanlı dağıtım ve toplamalı elektrikli araç rotalama problemi için çözüm yöntemleri, Yüksek Lisans Tezi, İzmir Demokrasi Üniversitesi, Fen Bilimleri Enstitüsü, İzmir, 2024.