Sözlük · approach
Kapasiteli Araç Rotalama
Tek depodan başlayıp depoya dönen, her müşteriyi tam bir kez ziyaret eden ve tur başına toplam talebi araç kapasitesinin altında tutan minimum maliyetli araç rotalarının tasarımı.
Capacitated Vehicle Routing ProblemCVRPKapasiteli VRPKamyon Sevkiyat Problemi
Capacitated Vehicle Routing Problem (CVRP), (a) tek depoda başlayan ve biten, (b) her müşteriyi tam bir kez ziyaret eden, (c) her turda toplam talebi araç kapasitesinde veya altında tutan minimum maliyetli araç rotaları kümesini bulma problemidir. Zaman penceresi yoktur — bu uzantı VRPTW'dir. Maliyet genelde toplam mesafe, toplam süre, ya da yakıt+sürücü ücretinin bileşimidir. CVRP NP-hard'tır ve tüm VRP ailesinin kanonik atasıdır; Dantzig ve Ramser'in 1959'da 'The Truck Dispatching Problem' adıyla başlattığı problemdir. Standart referans kitap Toth ve Vigo (2014). Pratik çözüm yöntemleri klasik Clarke-Wright savings sezgiselinden (1964 — orta ölçek için hâlâ benchmark kalitesinde), 2-opt ve Or-opt iyileştirmesinden, modern branch-and-cut-and-price exact algoritmaları (Fukasawa ve arkadaşları 2006) ile ALNS (Adaptive Large Neighborhood Search) metaheuristiklerine uzanır.
Örnek
Bir bölge distribütörü tek depodan 80 müşteriye günlük teslimat yapar; her müşterinin kg cinsinden talebi belli; araçlar 2 ton taşır; soru: kaç araç çıksın, hangi araç hangi müşterileri ziyaret etsin, hangi sırayla — toplam km minimum olsun.