Asymetrický kapacitní rozvozní problém
Symetrická verze problému předpokládá stejnou vzdálenost mezi dvěma uzly, zatímco za asymetrickou úlohu je tento problém považován tehdy, je-li naměřena odlišná vzdálenost z bodu A do bodu B a z bodu B do bodu A. Tato situace může vzniknout tehdy, nachází-li se daná místa na trase, která zahrnují určitá dopravní omezení či jednosměrné úseky (Stevenson, 1992).
Standardní CVRP předpokládá, že vzdálenost mezi dvěma body je stejná v obou směrech, což není vždy realistické. ACVRP lépe odpovídá skutečnosti a umožňuje přesnější plánování tras v městské a průmyslové logistice.
Asymetrický problém, který zohledňuje pouze omezení kapacity vozidla (Laporte a kol., 1986; Vigo, 1996; Leggieri & Haouari, 2018) je dále rozpracován pro problémy se zpětným svozem (Toth & Vigo, 1999), s omezenou vzdáleností (Almoustafa a kol., 2013), využití heterogenní flotily (Herrero a kol., 2014), se současným rozvozem a svozem (Rieck & Zimmermann, 2013) nebo víceskladový problém (Li a kol., 2019).
Základní princip:
Reálný svět není symetrický. Tento problém nabízí efektivnější modelování logistických operací.
V mnoha městských oblastech nejsou cesty symetrické kvůli jednosměrkám, zákazům odbočení nebo rozdílným rychlostním limitům.
Zajímavosti:
V některých městech mohou mýtné poplatky nebo dynamické dopravní regulace způsobit, že jedna cesta je dražší než druhá.
Dálnice mohou umožnit rychlý přesun jedním směrem, ale návrat může být složitější kvůli absenci přímého sjezdu.
Asymetrie může být způsobena i rozdílným terénem, například v horských oblastech je cesta do kopce pomalejší a energeticky náročnější než cesta dolů.
Praktické aplikace:
DHL, FedEx nebo UPS se musí přizpůsobit jednosměrkám, zákazům vjezdu a zónám s omezeným provozem, což vytváří asymetrii v trasách. Optimalizace s ACVRP pomáhá minimalizovat zpoždění a zlepšit efektivitu doručování.
Popelářská vozidla čelí různým omezením, například mohou mít povolený vjezd pouze určitým směrem v danou dobu. Asymetrická optimalizace pomáhá minimalizovat čas a spotřebu paliva při svozu odpadu ve městech.
Vozidla rozvážející potraviny často čelí omezením vjezdů do center měst, kde se mohou lišit povolené trasy pro dodávky a návrat do skladu. Použití ACVRP umožňuje lepší plánování tras a minimalizaci prodlev, což je klíčové pro čerstvé zboží.
Zdroje:
[1] Almoustafa, S., Hanafi, S., & Mladenović, N. (2013). New exact method for large asymmetric distance-constrained vehicle routing problem. European Journal of Operational Research, 226(3).
[2] Herrero, R., Rodríguez, A., Cáceres-Cruz, J., & Juan, A. A. (2014). Solving vehicle routing problems with asymmetric costs and heterogeneous fleets. International Journal of Advanced Operations Management, 6(1).
[3] Laporte, G., Mercure, H., & Nobert, Y. (1986). An exact algorithm for the asymmetrical capacitated vehicle routing problem. Networks, 16(1).
[4] Leggieri, V., & Haouari, M. (2018). A matheuristic for the asymmetric capacitated vehicle routing problem. Discrete Applied Mathematics, 234.
[5] Li, J., Li, T., Yu, Y., Zhang, Z., Pardalos, P. M., Zhang, Y., & Ma, Y. (2019). Discrete firefly algorithm with compound neighborhoods for asymmetric multi-depot vehicle routing problem in the maintenance of farm machinery. Applied Soft Computing, 81.
[6] Rieck, J., & Zimmermann, J. (2013). Exact solutions to the symmetric and asymmetric vehicle routing problem with simultaneous delivery and pick-up. Business Research, 6(1).
[7] Stevenson, W. J. (1992). Production/operations management. Homewood: Irwin. ISBN 0-256-08029-1.
[8] Toth, P., & Vigo, D. (1999). A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls. European Journal of Operational Research, 113(3).
[9] Vigo, D. (1996). A heuristic algorithm for the asymmetric capacitated vehicle routing problem. European Journal of Operational Research, 89(1).