Vzdálenostně omezený kapacitní rozvozní problém

Jedná se o první důležitou modifikaci CVRP spočívající v omezení délky trasy vozidla.

Trendem poslední doby je hledání vhodného začlenění závislosti rychlosti jízdy na denní době – takzvané modelování dopravních špiček.
V tomto případě se musí vyřešit dva důležité problémy – náročnost modelu a vyčíslení nákladů silniční sítě v závislosti na čase.

DCVRP je varianta klasického kapacitního okružního dopravního problému (CVRP), kde kromě omezení na kapacitu vozidla existuje i omezení na maximální vzdálenost (nebo čas) jednotlivých tras. To znamená, že každá dodávka musí být naplánována tak, aby celková ujetá vzdálenost nepřekročila stanovený limit, což je důležité například u vozidel s omezeným dojezdem (elektromobily) nebo u řidičů s pracovní dobou omezenou zákonem.

Zajímavosti:

• Aplikace jako Uber Eats nebo Wolt řeší obdobný problém při rozvozu jídla – i když místo kapacity dodávky sledují časové omezení. Každý kurýr může doručit jen určitý počet objednávek v rámci svého časového okna, což je analogické s omezením vzdálenosti. Algoritmy musí rozhodnout, které objednávky spojit do jedné trasy, aby kurýr stihl doručit jídlo ještě teplé.

• Rovněž je možné brát v úvahu také dobu potřebnou pro rozvoz, než bude náklad znehodnocen, jak je uvedeno v aplikačním článku pojednávajícím o svozu a rozvozu mléka v tropických oblastech (Sankaran & Ubgade, 1994).

Praktická aplikace
V reálném světě se DCVRP uplatňuje například při rozvozu zboží elektromobily, které mají omezený dojezd na jedno nabití. Firmy jako Amazon nebo DHL implementují optimalizační modely pro plánování tras tak, aby jejich elektrické dodávky dokázaly obsloužit co nejvíce zákazníků bez nutnosti dodatečného nabíjení.

Zdroj:
[1] Sankaran, J. K., & Ubgade, R. R. (1994). Routing tankers for dairy milk pickup. Interfaces, 24(5).