Problem z trasowaniem pługa śnieżnego

Problem wyznaczania trasy pługa śnieżnego to zastosowanie struktury problemów wyznaczania trasy łuku (ARP) i problemów wyznaczania trasy pojazdu (VRP) do usuwania śniegu , które traktuje drogi jako krawędzie grafu.

Problem polega na prostym problemie z trasowaniem, gdy czasy przybycia nie są określone. Problemy z pługiem śnieżnym uwzględniają ograniczenia, takie jak koszt orki w dół w porównaniu z orką pod górę. Mieszany problem chińskiego listonosza ma zastosowanie do tras śnieżnych, gdzie krawędzie skierowane reprezentują ulice jednokierunkowe, a krawędzie niekierowane reprezentują ulice dwukierunkowe.

Tło

Wyznaczanie tras i ustalanie harmonogramów pojazdów do odśnieżania jest ważnym tematem dla planistów transportu i badaczy eksploatacyjnych Ten zestaw problemów jest częścią większego obszaru problemów określanych jako Arc Routing Problems , który jest podzbiorem większego obszaru o nazwie Vehicle Routing Problems . Trasowanie i planowanie pojazdów obejmuje odśnieżanie, listonosza dostarczającego pocztę, odczyt liczników w celu zebrania pieniędzy dla miasta, wyznaczanie tras autobusów szkolnych, wywóz śmieci i śmieci oraz konserwację ulic.

Kontekst

Problem odśnieżania polega na oczyszczeniu dróg tak, aby były bezpieczne dla ruchu pojazdów utrzymywanych przez podmiot publiczny lub prywatny w jak najkrótszym czasie. Problem wyznaczania tras pojazdów śnieżnych wiąże się z wyższymi wynagrodzeniami kierowców pojazdów oraz wysokimi kosztami paliwa i wysokimi kosztami zakupu i utrzymania pojazdów śnieżnych. W sektorze publicznym celem jest rzadziej minimalizacja kosztów, a częściej maksymalizacja bezpieczeństwa i wygody, np. poprzez zmniejszenie liczby skrętów w lewo na głównych drogach, które są niebezpieczne dla pojazdów.