Çok periyotlu araç rotalama problemi için kesi-temelli formülasyon yaklaşımları

Abstract

Çok periyotlu araç rotalama problemi (ÇPARP), birden fazla periyot içeren planlama ufkunda, müşterilerin belirlenen ziyaret sıklıklarını karşılayacak şekilde minimum maliyetli rotaların oluşturulmasını amaçlayan, klasik araç rotalama probleminin önemli bir genellemesidir. Bu çalışmada, ÇPARP için farklı kesi-temelli formülasyonlar geliştirilmiş ve bu formülasyonların çözümü için dal-ve-kesi yöntemi uygulanmıştır. Literatürde ÇPARP’nin farklı bir türevi için önerilen bir model uyarlanarak temel formülasyon elde edilmiş ve ardından alternatif formülasyonlar geliştirilmiştir. Bu alternatif modeller, bağlantı/alt tur eleme kısıtları, çizelge seçim kısıtları ve araç indislerinin modele dahil edilip edilmemesi gibi yönlerden farklılık göstermektedir. Geliştirilen formülasyonların hesaplama performansları, literatürde yer alan bir veri kümesinden seçilen örnekler kullanılarak yapılan kapsamlı bilgisayısal deneylerle karşılaştırılmıştır. Elde edilen sonuçlar, araç indisli değişkenler içermeyen bir formülasyonun özellikle küçük boyutlu problemler için çözüm süresi bakımından üstünlük sağladığını, araç indisli temel modelin ise daha zor örneklerde daha yüksek kaliteli çözümler üretebildiğini göstermektedir. Çalışmamız, önerdiği yeni kesi-temelli formülasyonlarla ÇPARP kesin çözüm literatürünü ileriye taşımakta ve yapılan kapsamlı değerlendirmelerle, periyodik rotalama problemlerinde model karmaşıklığı ile çözüm kalitesi arasındaki dengenin nasıl kurulacağına dair belirleyici kanıtlar sunmaktadır.

Keywords

• Çok periyotlu araç rotalama
• Kesi-temelli formülasyon
• Dal-ve-kesi yöntemi
• Matematiksel programlama
• Optimizasyon

Cut-Based formulations for the period vehicle routing problem

Abstract

The Period Vehicle Routing Problem (PVRP) is an important generalization of the classical vehicle routing problem, aiming to design minimum-cost routes over a multi-period planning horizon while satisfying predefined customer visit frequencies. In this study, different cut-based formulations are developed for the PVRP, and the branch-and-cut method is applied to solve these formulations. A model proposed in the literature for a different variant of the PVRP is adapted to obtain the baseline formulation, and then alternative formulations are developed. These alternative models differ in terms of the connectivity/subtour elimination constraints, schedule selection constraints, and whether vehicle indices are included in the model. The computational performance of the developed formulations is evaluated through extensive experiments using a benchmark dataset from the literature. The results indicate that the formulation without vehicle-indexed variables provides superior solution times, especially for smaller problem instances, while the vehicle-indexed baseline model generates higher-quality solutions for more challenging instances. Consequently, this study advances the exact solution literature for the PVRP by introducing novel cut-based formulations and, through a rigorous evaluation, offers decisive evidence on how to balance model complexity with solution quality in periodic routing problems.

Keywords

• Periodic vehicle routing
• Cut-based formulation
• Branch-and-cut method
• Mathematical programming
• optimization

References

1. [1] Dantzig GB, Ramser JH. “The truck dispatching problem”. Management Science, 6(1), 80-91, 1959.
2. [2] Topaloğlu D, Polat O, Kalaycı CB. “Çok kompartımanlı heterojen filolu zaman pencereli araç rotalama probleminin çözümü için sezgisel algoritmalar”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 29(8), 870-884, 2023.
3. [3] İnkaya HK, Haldenbilen S, Polat O. “Akıllı çöp konteynerleri ile değişken ağ yapısına sahip çöp rotalama optimizasyonu”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 30(6), 742-755, 2024.
4. [4] Beltrami EJ, Bodin LD. “Networks and vehicle routing for municipal waste collection”. Networks, 4(1), 65-94, 1974.
5. [5] Russell R, Igo W. “An assignment routing problem”. Networks, 9(1), 1-17, 1979.
6. [6] Christofides N, Beasley JE. “The period routing problem”. Networks, 14(2), 237-256, 1984.
7. [7] Golden BL, Wasil EA. “Or practice-computerized vehicle routing in the soft drink industry”. Operations Research, 35(1), 6-17, 1987.
8. [8] Banerjea-Brodeur M, Cordeau JF, Laporte G, Lasry A. “Scheduling linen deliveries in a large hospital”. Journal of the Operational Research Society, 49(8), 777-780, 1998.

9. [9] Hemmelmayr V, Doerner KF, Hartl RF, Savelsbergh MW. "Delivery strategies for blood products supplies". OR Spectrum 31(4), 707-725, 2009.
10. [10] Archetti C, Jabali O, Speranza MG. “Multi-period vehicle routing problem with due dates”. Computers & Operations Research, 61, 122-134, 2015.
11. [11] Archetti C, Fernández E, Huerta-Muñoz DL. “The flexible periodic vehicle routing problem”. Computers & Operations Research, 85, 58-70, 2017.
12. [12] Larrain H, Coelho LC, Archetti C, Speranza MG. “Exact solution methods for the multi-period vehicle routing problem with due dates”. Computers & Operations Research, 110, 148-158, 2019.
13. [13] Rodríguez-Martín I, Salazar-González JJ, Yaman H. “The periodic vehicle routing problem with driver consistency”. European Journal of Operational Research, 273(2), 575-584, 2019.
14. [14] Clarke G, Wright JW. “Scheduling of vehicles from a central depot to a number of delivery points”. Operations Research, 12(4), 568-581, 1964.
15. [15] Tan CCR, Beasley JE. “A heuristic algorithm for the period vehicle routing problem”. Omega, 12(5), 497-504, 1984.
16. [16] Chao IM, Golden BL, Wasil EA. “An improved heuristic for the period vehicle routing problem”. Networks, 26(1), 25-44, 1995.
17. [17] Cacchiani V, Hemmelmayr VC, Tricoire F. “A set-covering based heuristic algorithm for the periodic vehicle routing problem”. Discrete Applied Mathematics, 163, 53-64, 2014.
18. [18] Baldacci R, Bartolini E, Mingozzi A, Valletta A. “An exact algorithm for the period routing problem”. Operations Research, 59(1), 228-241, 2011.
19. [19] Rothenbächer AK. “Branch-and-price-and-cut for the periodic vehicle routing problem with flexible schedule structures”. Transportation Science, 53(3), 850-866, 2019.
20. [20] Basir SA, Şahin G, Özbaygın G. “A comparative study of alternative formulations for the periodic vehicle routing problem”. Computers & Operations Research, 165, 106583, 2024.
21. [21] Laporte G, Nobert Y, Desrochers M. “Optimal routing under capacity and distance restrictions”. Operations Research, 33(5), 1050-1073, 1985.