Okamžité přeplánování trasy
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.
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.
Zajímavost
- Problém používá algoritmy predikce dopravní situace, což je užitečné pro osobní i nákladní dopravu.
- Reakce v reálném čase:
Tento problém je považován za jeden z nejdynamičtějších modelů ve směrování vozidel, protože každá nová objednávka vyvolá okamžité přeplánování celé trasy. - Koncept okamžitého požadavku (Psaraftis, 1980):
Nové požadavky zákazníků se objevují kdykoli během cesty vozidla a vyžadují rychlé přepočítání celé trasy. - Využití pokročilých algoritmů:
Model spoléhá na rychlé heuristiky nebo metaheuristiky, které zvládnou okamžité přeplánování, například edge exchange (Savelsbergh, 1992). - Flexibilita vs. složitost:
Přináší velkou flexibilitu v obsluze zákazníků, ale zároveň vysoké nároky na výpočetní kapacitu a kvalitu predikcí v reálném čase.
Praktické využití
- Expresní kurýrní služby:
Například rozvoz důležitých dokumentů nebo zásilek s požadavkem na maximální rychlost doručení, kde mohou během cesty vznikat další urgentní požadavky. - Zdravotnická logistika:
Okamžité dodání léků, zdravotnického materiálu nebo urgentních krevních transfúzí. - Servisní zásahy:
Servisní technik je na cestě a během jízdy přicházejí nové žádosti o zásah, systém mu okamžitě přepočítá trasu. - Distribuce čerstvých potravin:
Model lze použít i pro rozvoz potravin, kde je potřeba rychle reagovat na nové objednávky v průběhu rozvozu.
Dynamický problém směrování s jedním vozidlem a okamžitým přeplánováním trasy (IR-D-SVRP) řeší situace, kdy během realizace stávající trasy přicházejí nové požadavky zákazníků, na které je potřeba reagovat okamžitým přepočítáním celé trasy. Model klade důraz na rychlou reakci systému a maximální flexibilitu. Používá se zejména tam, kde je vysoký tlak na rychlost obsluhy a proměnlivost objednávek, jako jsou kurýrní služby, zdravotnická logistika či urgentní servisní zásahy. Pro efektivní fungování model vyžaduje rychlé algoritmy a výpočetní výkon pro okamžité přeplánování tras v reálném čase.
Zdroj:
[1] 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
[2] Larsen, A., & Madsen, O. B. (2000). The dynamic vehicle routing problem (Doctoral dissertation, Institute of Mathematical Modelling, Technical University of Denmark).
[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] Savelsbergh, M., & Sol, M. (1998). Drive: Dynamic routing of independent vehicles. Operations Research, 46(4).
[6] 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).