Obecný dynamický přístup

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.

Zajímavosti

• Obecnější model dynamického směrování:
  Na rozdíl od základního dynamického problému (D-SVRP) a specifického okamžitého přeplánování (IR-D-SVRP), tento model kombinuje flexibilní přepočítávání trasy s možností optimalizace celé trasy při příchodu nových požadavků, ale bez nutnosti okamžité reakce.
• Algoritmická dynamika:
  Trasa se upravuje pomocí optimalizačních algoritmů jako je heuristika výměny hran (edge exchange heuristic, Savelsbergh, 1992). Model je tak robustnější oproti čistě reaktivnímu modelu, protože umožňuje komplexnější rozhodování o trase.
• Historické pozadí:
  Inspirace sahá až k prvním zmínkám o dynamickém VRP u Wilsona & Colvina (1977), kdy začalo být zkoumáno postupné vkládání nových požadavků do již existující trasy.
• Rezervní kapacita vozidla:
  Součástí strategií je i plánování rezervní kapacity, aby bylo možné flexibilně přijímat nové požadavky během jízdy.

Praktické využití

• Kurýrní a expresní doručování:
  Především v městské logistice, kdy během rozvozu přicházejí další objednávky a je potřeba pružně optimalizovat trasu, ale není nutné ji přepočítávat úplně okamžitě při každé nové objednávce.
• Rozvoz potravin nebo zboží e-commerce:
  Model vhodný tam, kde dochází k postupnému naplňování objednávek a kde lze trasy v průběhu dne několikrát upravit.
• Zásilkové služby:
  Například u balíkové logistiky, kde během dne dorazí další zásilky do systému a trasa se průběžně optimalizuje.
• Servisní zásahy:
  Ve firmách provádějících technickou podporu v terénu může systém optimalizovat denní trasu technika při přidání dalších zákaznických hlášení.
• Dispečinky pohotovostních služeb (záchranáři, hasiči) pro efektivnější zásahy.

Obecný dynamický problém směrování s jedním vozidlem (G-D-SVRP) se zaměřuje na situace, kdy požadavky zákazníků vznikají v průběhu cesty vozidla. Na rozdíl od modelů vyžadujících okamžité přeplánování nabízí flexibilní, algoritmicky řízenou úpravu trasy, která optimalizuje pořadí návštěv zákazníků s cílem zvýšit efektivitu a snížit náklady. Klíčovým prvkem je možnost vkládání nových požadavků do existující trasy a využití rezervní kapacity vozidla.

Tento model nachází využití například v kurýrních službách, doručování potravin nebo ve službách technické podpory v terénu, kde je důležité flexibilně reagovat na nové požadavky v průběhu dne.

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