Úloha s jedním vozidlem

Dynamizace úlohy je zajištěna vznikem nového požadavku kdykoliv během jízdy vozidla.
Po vzniku nového požadavku se v první řadě zjišťuje, zda je možné splnit jej během již existující trasy a nalézt zákazníka, za kterého bude nejvýhodnější nový požadavek vložit. S výhodou se využívá vytváření rezervní kapacity vozidla.

Této problematice se věnuje Savelsbergh (1992), který uvažuje úlohu s jedním vozidlem a časovými okny řešenou výměnou hran na trase pro statickou úlohu. Fábry (2006) uvádí, že tento postup lze snadno modifikovat na dynamickou úlohu. Již první zmínka (Wilson & Colvin, 1977) o DVRP se zabývá požadavky zákazníků, které přicházejí dynamicky během cesty jediného vozidla z výchozího uzlu do cíle. V příštích letech byla provedena další analytická práce (Papastavrou & Swihart, 1997) pro tuto variantu problému. Během dalších výzkumů v oblasti dynamického směrování vozidel, byl zaveden koncept okamžitého požadavku (Psaraftis, 1980). Dynamický požadavek zákazníka vyžaduje okamžité přeplánování aktuální trasy vozidla.

Zajímavost

Tento problém reflektuje realitu doručovacích služeb, kde je nutné se rychle přizpůsobit novým objednávkám a dopravní situaci. Používá se v taxi službách, ambulantní dopravě a rozvozu jídla.

• Základní dynamický model:
  Tento problém je výchozím bodem pro celou skupinu dynamických VRP. Zákaznické požadavky přicházejí v průběhu cesty vozidla, což znamená, že plán trasy není známý předem, ale musí se průběžně aktualizovat.
• Flexibilní reakce na nové požadavky:
  Po přijetí nového požadavku se systém snaží vložit zákazníka do existující trasy na nejvhodnější místo, aby se minimalizovala prodleva a zvýšila efektivita.
• Použití rezervní kapacity:
  Využívá se rezervní kapacita vozidla, která umožňuje zařazovat nové požadavky i během probíhající cesty.
• Menší složitost oproti pokročilejším variantám:
  Na rozdíl od modelů s okamžitým přeplánováním (IR-D-SVRP) nebo obecného dynamického přístupu (G-D-SVRP), zde nejde o kompletní přeplánování celé trasy, ale o průběžné doplňování trasy o nové požadavky.

Praktické využití

Používá se např. v aplikacích jako Uber a Lyft, kde se trasy přizpůsobují v reálném čase podle dostupnosti řidičů a poptávky.

• Základní kurýrní služby:
  Například rozvoz zásilek v menším městě nebo regionu, kde jsou nové objednávky přijímány v průběhu dne a jsou flexibilně zařazovány do aktuální trasy vozidla.
• Technické zásahy:
  Např. servisní technik v terénu, kde je možné přidat nový požadavek do jeho plánu bez nutnosti přeplánovat celou trasu.
• Distribuce potravin nebo zboží s nižší frekvencí objednávek:
  Například farmářské produkty rozvážené na základě denní poptávky.
• Rozvoz v menších regionech:
  Ideální pro logistiku v regionech s nižším počtem objednávek, kde postačí jedno vozidlo a flexibilní plánování.

Tuto variantu DVRP je možné najít ve dvou modifikacích:

V tomto modelu je jedno vozidlo, které musí dynamicky reagovat na změny v poptávce a dopravní situaci. Cílem je minimalizovat časy obsluhy nebo optimalizovat jiné aspekty přepravy.

Dynamický problém směrování s jedním vozidlem (D-SVRP) je základní dynamický model, který řeší situace, kdy nové požadavky zákazníků přicházejí v průběhu rozvozu. Systém se snaží efektivně začlenit nové požadavky do stávající trasy bez nutnosti přeplánování celé cesty. Tento přístup využívá rezervní kapacity vozidla a nachází uplatnění zejména v základních kurýrních službách, technických zásazích v terénu a v distribučních sítích menšího rozsahu. Model poskytuje flexibilitu a zjednodušenou optimalizaci, která je vhodná pro prostředí s méně intenzivní poptávkou.

Zdroj:
[1] Savelsbergh, M. W. (1992). The vehicle routing problem with time windows: Minimizing route duration. ORSA journal on computing, 4(2).
[2] Fábry, J. (2006). Dynamické okružní a rozvozní úlohy (disertační práce). Dostupné z webových stránek VŠ: https://nb.vse.cz/~fabry/disertace.pdf
[3] Wilson, N. H. M., & Colvin, N. J. (1977). Computer control of the Rochester Dial-A-Ride system. Dept of Civil Engineering.
[4] Papastavrou, J. D., & Swihart, M. R. (1997). A Stochastic and Dynamic Model for the Single-Vehicle Pick-up and Delivery Problem. Working Paper, School of Industrial Engineering, Purdue University.
[5] Psaraftis, H. N. (1980). A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation Science, 14(2).