Směrování oblouku - Arc routing

Směrování oblouku je proces výběru nejlepší cesty v síti na základě trasy. Na rozdíl od běžných problémů se směrováním, které obvykle zahrnují mapování a trasa mezi uzly se směrování oblouku více zaměřuje na samotnou trasu. Cílem mnoha problémů se směrováním oblouku je vyrobit trasu s minimálním počtem mrtvý kilometr, přičemž také plně zahrnuje požadované hrany. Mezi příklady aplikací pro směrování oblouku patří sběr odpadků, posypová komunikace, doručování pošty, údržba sítě atd sněžný pluh.

Typy problémů

Problémy se směrováním oblouku (ARP) se liší svým cílem a heuristikou. Je však známo, že jsou všechny NP-tvrdé.

Neusměrněný problém venkovského pošťáka

Tento problém je pojmenován po pošťákovi a jeho výzvě doručovat poštu v libovolném pořadí, které si zvolí, ale minimalizuje tak své náklady, jako je čas nebo cestovní vzdálenost. To je také někdy nazýváno problém s neorientovaným čínským pošťákem. Problém neřízeného venkovského pošťáka (URPP) si klade za cíl minimalizovat celkové náklady na trasu, která mapuje celou síť, nebo ve specifičtějších případech trasu, která mapuje všechny okraje, které vyžadují službu. Pokud musí být namapována celá síť, trasa, která mapuje celou síť, se nazývá a krycí prohlídka. V případě, že je třeba mapovat pouze určité hrany, je cílem problému vyřešit trasu, která optimalizuje požadavky, přejezd na nepotřebné trasy minimálně několikrát.[1]

Problém směrování neřízeného kapacitního oblouku

Problém směrování neřízeného kapacitního oblouku se skládá z požadavků kladených na hrany a každá hrana musí splňovat požadavek. Příkladem je uvolňování paměti, kde každá trasa může vyžadovat uvolnění paměti a recyklovatelnou kolekci. Problémy v reálných aplikacích mohou nastat, pokud existují problémy s časováním, jako je například případ, kdy určité trasy nelze obsluhovat kvůli konfliktům časování nebo plánování nebo omezením, jako je omezené časové období. Heuristika popsaná v tomto článku ignoruje jakékoli takové problémy, které vzniknou v důsledku omezení aplikace.[2]

Dějiny

URPP byl poprvé představen v roce 1974 a byl prokázán jako NP-těžký problém Lenstra a Kan. UCARP lze odvodit z URPP, a proto je také NP-tvrdý. V roce 1981 se další dvojici počítačových vědců, Goldenovi a Wongovi, podařilo dokázat, že i odvození 0,5 přiblížení k URPP bylo NP-tvrdé. V roce 2000 vydal Dror knihu popisující různé problémy se směrováním oblouku.

Heuristika a algoritmy

Většina algoritmů vyžaduje předběžné zpracování grafu, což zjednodušuje počáteční graf odstraněním všech hran, které nejsou v nejkratší cestě mezi 2 požadovanými hranami. Další zjednodušení, které předzpracování přidává, je to, že transformuje nejkratší cestu mezi 2 požadovanými hranami na jednu nepotřebnou hranu bez ohledu na počet hran v cestě, za předpokladu, že v cestě nebyly žádné požadované hrany.

Po dokončení předběžného zpracování lze problém zobecnit na a konvexní obal problém, přičemž hrany jsou body trupu. Problém s konvexním trupem lze vyřešit pomocí lineárního programování nebo pomocí algoritmů s konvexním trupem, ale proces hledání konvexního trupu je problémem exponenciálním.

Metody řešení URPP po provedení předběžného zpracování sestávají z algoritmus řezné roviny a metodologie odvětví a řezu.[3]

Poznámky

externí odkazy

Reference

  1. ^ H. A., Eiselt; Michel, Gendreau (1995). „Problémy se směrováním oblouku, část II: Problém venkovského pošťáka“. Operační výzkum. 43 (3): 399–414. doi:10,1287 / opre.43.3.399.
  2. ^ H. A., Eiselt; Michel, Gendreau (1995). „Problémy se směrováním oblouku, část II: Problém venkovského pošťáka“. Operační výzkum. 43 (3): 399–414. doi:10,1287 / opre.43.3.399.
  3. ^ http://www.gerad.ca/~alainh/Trends.pdf