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

Ç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.

Anahtar Kelimeler: Ç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

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