Kapacitní směrování se stochastickou poptávkou
Tato verze problému obsahuje stochastické požadavky zákazníků, které se stanou známou veličinou až po stanovení trasy. Problém je obvykle modelován jako dvoustupňový.
Zajímavosti
- Nejistota jako jádro modelu:
CVRPSD je jedním z nejběžnějších stochastických VRP, kde je poptávka zákazníků známá pouze přibližně (např. jako pravděpodobnostní rozdělení). To odráží reálné situace, kdy zákazníci neobjednávají dopředu, nebo se jejich potřeby liší den ode dne. - Potřeba rezervní kapacity:
Jelikož není jisté, kolik zboží každý zákazník skutečně požaduje, vozidla musí být plánována s rezervou. V některých případech může být nutné přerušit trasu a vrátit se do depa pro doplnění. - Rozdíl mezi očekáváním a realitou:
Trasy jsou často plánovány na základě očekávané poptávky, ale v průběhu rozvozu se situace může výrazně lišit — model proto vyžaduje robustnost a adaptabilitu. - Podklad pro další varianty:
CVRPSD slouží jako základ pro mnoho rozšířených modelů (např. s možností doplňování, více depy, časovými okny, preventivní zásobou apod.).
Praktické využití
- Distribuce do maloobchodních provozoven:
Například doručování zboží do poboček, které neobjednávají konkrétní množství předem, ale systém je zásobuje podle historické nebo očekávané spotřeby. - Rozvoz léků nebo zdravotnického materiálu:
Nemocnice a lékárny mohou vykazovat proměnlivou spotřebu, ale potřebují zásoby včas. - Zásobování venkovských oblastí nebo škol:
Kde poptávka kolísá (např. počet strávníků ve školní jídelně) a není známa předem. - Služby, kde řidič rozhoduje operativně:
Například při svozu odpadu nebo zásilek, kde není známo přesné množství, ale musí být vše vyzvednuto a kapacita vozidla je omezená.
Jednotlivé varianty CVRP se stochastickou poptávkou můžeme najít zde:
Metody řešení
- ALNS
- Simulace Monte Carlo
- Re-optimalizační přístupy (všechny tři typy: běžná, preventivní, přesná)
- Programování s pravděpodobnostními omezeními
- Hybridní metaheuristiky
Kapacitní okružní dopravní problém se stochastickou poptávkou (CVRPSD) představuje variantu klasického VRP, ve které není předem znám přesný objem požadavků jednotlivých zákazníků. Místo toho je poptávka modelována jako náhodná veličina s daným rozdělením. Vozidla musí být plánována s rezervní kapacitou, aby byla schopna obsloužit i vyšší než očekávanou poptávku. V případě překročení kapacity může být vyžadován návrat do depa. Tento model se využívá v distribučních systémech s proměnlivou poptávkou, například v zásobování maloobchodních poboček, zdravotnických zařízení nebo v případě, že se objednávky neplánují s přesností. CVRPSD tvoří základ pro mnohé další stochastické varianty VRP.
Zdroj:
[1] Laporte, G., Louveaux, F. V., & Van Hamme, L. (2002). An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research, 50(3).