Arc routing

Arc routing problems (ARP) är en kategori av generella routingproblem (GRP), som även inkluderar nod routing problem (NRP). Målet i ARP:er och NRP:er är att korsa kanterna och noderna på en graf, respektive. Målet med bågdirigeringsproblem innebär att minimera det totala avståndet och tiden, vilket ofta innebär att minimera deadheading -tiden, den tid det tar att nå en destination. Bågdirigeringsproblem kan appliceras på sophämtning , planering av skolbussvägar , leverans av paket och tidningar, avisning och snöröjning med vinterservicefordon som strö salt på vägen, postutdelning , nätverksunderhåll, gatusotning , patrullering av polis och säkerhetsvakt, och snöröjning . Arc routing-problem är NP-hårda , i motsats till ruttinspektionsproblem som kan lösas i polynomtid .

Cristina R. Delgado Serna & Joaquín Pacheco Bonrostro använde approximationsalgoritmer för att hitta de bästa skolbusslinjerna i den spanska provinsen Burgos gymnasiesystem för ett verkligt exempel på bågdirigeringsproblem . Forskarna minimerade antalet rutter som tog längre tid än 60 minuter att korsa först. De minimerade också längden på den längsta rutten med ett fast maximalt antal fordon.

Det finns generaliseringar av bågdirigeringsproblem som introducerar flera brevbärare, till exempel k Chinese Postman Problem (KCPP).

Bakgrund

Den effektiva schemaläggningen och dirigeringen av fordon kan spara industrin och staten miljontals dollar varje år. Bågdirigeringsproblem har tillämpningar inom skolbussplanering, sophämtning och sophämtning i städer, post- och paketleverans av brevbärare och posttjänster, vintergrisning och saltläggning för att hålla vägarna säkra på vintern, snöröjning och -röjning, mätaravläsning inklusive fjärravläsningsteknik för radiofrekvensidentifiering, gatuunderhåll och sopning, ruttplanering av polispatrullbilar och mer.

Grund

Det grundläggande routingproblemet är: givet en uppsättning noder och/eller bågar som ska betjänas av en fordonsflotta, hitta rutter för varje fordon som börjar och slutar vid en depå. En fordonsrutt är en sekvens av punkter eller noder, som fordonet måste passera i ordning, med start och slut vid en depå.

Kinesisk brevbärarproblem

Det kinesiska brevbärarproblemet (CPP) syftar till att hitta den minsta cykellängden för en enskild brevbärare. CPP kräver att alla kanter korsas en gång, rural postman problem (RPP) kräver att en delmängd av kanterna korsas med minsta längdcykel.

Problem med fordonsdirigering/VRP

Bågdirigeringsproblem påverkar strategiska, taktiska och operativa planeringsbeslut. Den strategiska rollen för var en depå är placerad beror på den mest effektiva bågvägen som finns. Beslutet om fordonsflottans storlek och fordonstyper med varierande specifikationer relaterar till den taktiska aspekten av bågdirigeringsproblem inom operationsforskning. Routing- och schemaläggningsbeslut är operativa planeringsbeslut i bågdirigeringsproblem. I verksamhetsplaneringsbesluten ingår också den tid som fordonen används av arbetare med personalbeslut. Beslut om färdväg för fordon för placeringen av en depå beror på kostnaden för att transportera material över en geografisk region. Bodin et. al tillämpad fordonsdirigering till ratten ett åkproblem.

Lantligt brevbärarproblem

I vissa situationer skiljer sig uppsättningen av kanter som krävs från kanterna i grafen. Detta modelleras av Rural Postman Problem (RPP), där de erforderliga kanterna är en delmängd av systemet av kanter.

Algoritmer

Att hitta en effektiv lösning med stora mängder data för det kinesiska brevbärarproblemet (CPP), Windy Postman Problem (WPP), Rural Postman Problem (RPP), det k-kinesiska brevbärarproblemet (KCPP), det blandade kinesiska brevbärarproblemet ( MCPP ) ), det riktade kinesiska brevbärarproblemet (DCPP), Downhill Ploughing Problemet (DPP), Ploughing with Precedence Problemet (PPP), Windy Rural Postman Problem (WRPP) och Windy General Routing Problem (WGRP) kräver användning av genomtänkta matematiska begrepp , inklusive heuristiska optimeringsmetoder , förgreningsmetoder , linjär heltalsprogrammering och tillämpningar av problemalgoritmer för resande säljare $) {\displaystyle O(n!)}$ Held –Karp-algoritmen gör en förbättring från till $O(2^{n}n^{2})$ . Utöver dessa algoritmer kan dessa klasser av problem även lösas med skärplansalgoritmen, konvex optimering , konvexa skrov , Lagrange-multiplikatorer och andra dynamiska programmeringsmetoder . I fall där det inte är möjligt att köra Held–Karp-algoritmen på grund av dess höga beräkningskomplexitet, kan algoritmer som denna användas för att approximera lösningen inom rimlig tid.

Euleriska kretsar

Den tidigaste dokumenterade hänvisningen till området för bågdirigeringsproblem är de klassiska broarna i Königsberg- utmaningen, som Euler visade sig vara omöjlig. Invånaren i Königsberg , nu en del av Kaliningrad , ville hitta ett sätt att korsa alla sju broarna över floden Pregel utan att backa eller gå tillbaka, det vill säga att korsa varje bro en gång och bara en gång. År 1736 reducerade Euler problemet till en fråga om noder och kanter och visade att problemet var omöjligt. 1873 arbetade Hierholzer mer med frågan om slutna kretsar.

Arbetet med de Euleriska kretsarna populariserades hos Scientific American den 1 juli 1953. Detta arbete utökades av Meigu Guan, även känd som Kwan Mei-Ko vid Shangtun Normal College. Meigu Guan var intresserad av en annan fråga istället för att bestämma en sluten krets. Guan arbetade för att ta reda på en minsta längd promenad som korsade varje kant av grafen minst en gång. Guan beskrev sitt mål 1962: "En brevbärare måste täcka sitt tilldelade segment innan han återvänder till postkontoret. Problemet är att hitta det kortaste gångavståndet för brevbäraren."

Problemtyper

Arc routing problem (ARP) skiljer sig åt i deras mål och heuristik. Men alla är kända för att vara NP-hårda .

Oriktat lantbrevbärarproblem

Detta problem är uppkallat efter brevbäraren och hans utmaning att leverera post i valfri ordning han kan välja, men att minimera hans kostnader som tid eller resavstånd. Det kallas också ibland för det oriktade kinesiska brevbärarproblemet . Problemet med det oriktade postbudet (URPP) syftar till att minimera den totala kostnaden för en rutt som kartlägger hela nätverket, eller i mer specifika fall, en rutt som kartlägger varje kant som kräver en tjänst. Om hela nätverket måste kartläggas kallas rutten som kartlägger hela nätverket en täckande tur . I de fall där endast vissa kanter behöver kartläggas syftar problemet till att lösa den rutt som optimerar kraven, genom att korsa över till icke erforderliga rutter ett minimalt antal gånger.

Problem med oriktad kapaciterad bågdirigering

Problemet med oriktad kapaciterad bågdirigering består av krav som ställs på kanterna och varje kant måste möta kravet. Ett exempel är sophämtning, där varje väg kan kräva både en sophämtning och en återvinningsbar insamling. Problem i verkliga applikationer kan uppstå om det finns tidsproblem, till exempel fallet där vissa rutter inte kan betjänas på grund av tids- eller schemakonflikter, eller begränsningar, till exempel en begränsad tidsperiod. Heuristiken som beskrivs i den här artikeln ignorerar alla sådana problem som uppstår på grund av applikationsbegränsningar.

Historia

URPP introducerades först 1974 och visade sig vara ett NP-hårt problem av Lenstra och Kan . UCARP kan härledas från URPP och är därför NP-hård också. 1981 lyckades ett annat par datavetare, Golden och Wong, bevisa att det var NP-svårt att till och med härleda en approximation på 0,5 till URPP. År 2000 publicerade Dror en bok som beskrev olika bågdirigeringsproblem.

Blåsigt brevbärarproblem och varianter

Det blåsiga brevbärarproblemet som Minieka föreslår är en variant av ruttinspektionsproblemet där ingången är en oriktad graf, men där varje kant kan ha en annan kostnad för att korsa den i en riktning än för att korsa den i den andra riktningen. Till skillnad från lösningarna för riktade och oriktade grafer är den NP-komplett . Kostnaden för att resa i en riktning är större när vinden blåser i ditt ansikte än när vinden är i ryggen, och detta är ursprunget till namnet Windy Postman-problemet. Arbetet som krävs för att korsa gatan i en riktning är annorlunda än arbetet som krävs för att korsa gatan i en annan riktning en blåsig dag.

Det blåsiga brevbärarproblemet är ett arc routing problem (ARP) som innehåller Mixed Chinese Postman Problem MCPP som ett specialfall.

Problemet kan definieras på följande sätt: "Ges en oriktad och sammankopplad graf G=(V,E) med två icke-negativa kostnader c $\displaystyle c_{i,j}}$ och $c_{j,i}$ associerad med varje kant $\{i,j\}\in E$ motsvarande kostnaden för att korsa den från i till j och från j till i , respektive, WPP ska hitta en minimikostnadstur på G som korsar varje kant minst en gång." Detta problem introducerades av Minieka. WPP är NP-komplett i allmänhet och kan lösas i polynomtid om G är Eulerian, om kostnaden för två motsatta orienteringar av varje cykel i G i samma eller om G är en serieparallell graf. Windy Rural Postman Problem (WRPP) är en generalisering av WPP där inte alla kanter i grafen måste korsas utan bara de i en given delmängd av erforderliga kanter. Vissa landsvägar krävs till exempel inte för att brevbäraren ska korsa och vissa vägar i branta backar tar längre tid att gå upp än ner.

Windy Rural Postman Problem (WRPP) är en generalisering av WPP där inte alla kanter i grafen måste korsas utan bara de i en given delmängd av erforderliga kanter. Vissa landsvägar krävs till exempel inte för att brevbäraren ska korsa och vissa vägar i branta backar tar längre tid att gå upp än ner. Betrakta en oriktad graf $G=\{E,V\}$ med två kostnader $c_{ij}$ och $c_{ji}$ associerade med kostnaden för att korsa kanten $(i,j)$ med början från i respektive j. G är den blåsiga grafen och vi är intresserade av delmängden av kanter, eller av matematiska symboler, $E_{R}\subseteq E$ .

Om WRPP inkluderar den ytterligare begränsningen att en viss uppsättning hörn måste besökas— ${\displaystyle V_{R}\subseteq V} ,$ förvandlas problemet till Windy General Routing Problem (WGRP). Benavent föreslog en heltalslinjär programmeringsformulering och olika heuristik och nedre gränser för WRPP.

Benavent et al publicerade en utvärdering av flera heuristiska metoder som används för att lösa WRPP på några sekunder med en avvikelse som inte är större än 1 % från den nedre gränsen på medelstora grafer. De förbättrade detta med en Scatter Search-algoritm som minskade skillnaden till 0,5 %. Scatter Search hittade lösningar som avvek med mindre än 2 % när de implementerades på nätverk med hundratals noder och tusentals kanter.

I verkliga tillämpningar finns det flera fordon som kan röra sig, vilket leder till generaliseringen som heter Min-Max K-vehicles Windy Rural Postman Problem (MM K-WRPP). Min–max K-fordon Windy Rural Postman Problem (MM K-WRPP) definieras enligt följande: Givet en blåsig graf $G=\{V,E\}$ , en distingerad vertex , $1\in V$ , som representerar depån, en delmängd av erforderliga kanter $E_{R}\subseteq E$ , och ett fast antal K fordon, MM K- WRPP består av att hitta en uppsättning K-turer för fordonen på ett sådant sätt att varje tur börjar och slutar vid depån och varje nödvändig kant betjänas av exakt ett fordon. Målet är att minimera längden på den längsta turen för att hitta en uppsättning balanserade vägar för fordonen. Några verkliga tillämpningar av routingproblem med min–max-mål är skolbuss routing (Delgado och Pacheco 2001), leverans av tidningar till kunder (Applegate et al. 2002) och avfallsinsamling (Lacomme et al. 2004).

Den bästa MM K_WRPP-algoritmen var mycket nära minimilösningen med 2 och 3 fordon, mindre än 0,4 % i genomsnitt. Gapet ökar till cirka 1,00 % och 1,60 % vid 4 och 5 fordon.

Enligt Dussault et al och Benavent et al kan en multi-objektiv simulerande glödgningsalgoritm (MOSA) lösa de olika begränsningarna som åläggs WRPP. WRPP är ett viktigt Arc Routing-problem som generaliserar många av enkelfordons Arc Routing-problem. I riktiga tillämpningar av matematik är en lösning som minimerar de totala kostnaderna för alla fordonsvägar och längden på den längsta turen att föredra. Det är svårt att vara på en plats där ditt paket alltid är timmar försenat. Vi bör börja med antagandet att flera fordon med en specifik mätbar kapacitet att betjäna kunder är mer realistiskt än ett fordon med omätbar oändlig kapacitet. Rabbani et. al mätte prestandan för MOSA-algoritmer och -modeller med hjälp av en multi-objektiv utveckling av Cuckoo Search – utvecklad av Yang et al, även kallad Multi-objective Cuckoo Search och förkortat av MOCS. De drog slutsatsen att MOSA-metoder var effektivare än MOCS-metoder. I framtiden kan jämförelser med andra metaheuristiska metoder undersökas, inklusive Non-dominated Sorting Genetic Algorithm (NSGA-), multi-objektiv partikelsvärmoptimeringsalgoritm (MOPSO) och multi-objektiv imperialistisk kompetitiv algoritm.

I modellen Windy Postman Problem (WPP) är kostnaden för att gå i en riktning annorlunda än kostnaden det tar att gå åt andra hållet. Till exempel, om vinden blåser nerför gatan tar det mer tid och energi att gå mot vinden än med vinden. Ett annat exempel på WPP är att kostnaden för att plöja uppför är högre än kostnaden för att plöja nedför. Detta modelleras av en variant som studerats av Dussault et al, Downhill Ploughing Problem (DPP).

En gren- och skäralgoritm publicerades av Angel Corberan för det blåsiga brevbärarproblemet. Algoritmen är baserad på heuristiska och exakta metoder för att manipulera udda ojämlikhetskränkningar.

Ansökningar

Olika kombinatoriska problem har reducerats till det kinesiska brevbärarproblemet, inklusive att hitta ett maximalt snitt i en plan graf och en minsta medellängdkrets i en oriktad graf.

Snöplogar

På vintern är en vanlig fråga vilken uppsättning rutter som har den minsta (minsta) maximala ruttlängden? Vanligtvis bedöms detta som ett bågdirigeringsproblem med en graf. Tiden det tar att resa en gata, känd som dödläge, är snabbare än tiden det tar att ploga snön från gatorna (eller leverera post eller lämna paket). En annan aspekt som måste beaktas när man tillämpar bågsträckning vid snöplogning är det faktum att det på branta gator är antingen svårt eller omöjligt att ploga uppför. Målet är en rutt som undviker att ploga uppför på branta gator som slutför jobbet snabbare genom att maximera dödlägestiden för att hitta platsen. Detta modellerades med en heuristisk algoritm som approximerar en nedre gräns av Dussault, Golden och Wasil. Detta är Downhill Plough Problem (DPP). Snöteam föredrar att ploga nedför och dödsbacke uppför. Detta problem förutsätter att förhållandena är tillräckligt hårda för att gatorna är avstängda och det inte finns någon trafik.

Downhill Plough Problem ignorerar Ploughing with Precedence Problem (PPP), som är byggt på det rimliga antagandet att om snön är för djup kan snöplogen inte döda en oplogad gata. DPP gör antagandet att snönivån är tillräckligt låg för att gatorna som inte är plogade kan vara döda, men att snön är tillräckligt djup för att det inte finns någon trafik. Om det är trafik på vägarna kan antagandet att det är omöjligt att ploga uppför inte längre hållas. Simuleringen för DPP-gatan utan plöjning med dödhuvud ungefär 5 % av tiden, vilket är ett ämne för framtida grafteori och bågdirigeringsforskning.

Med tanke på en oriktad graf $G=\{V,A\}$ där $V$ är uppsättningen av hörn och noder och $A$ är uppsättningen av bågar . Varje båge som representeras av $(v_{i},v_{j})$ har fyra kostnader: $c_{ij}^{+}$ , definierade som kostnad för plöjning från $v_{i}$ till $v_{j}$ , $c_{ji}^{+}$ , kostnaden för plöjning från $v_{j}$ till $v_{i}$ , $c_{ij}^{-}$ , kostnaden för deadheading från $v_{i }$ till $v_{j}$ , och $c_{ji}^{-}$ , kostnaden för deadheading från $v_{j}$ till $v_{i}$ . Inställningen antar att $v_{j}$ har en högre höjd $v_{i}$ , vilket leder till påståendet: $c_{ij}^{+}\gg c_{ji}^{+}\gg c_{ij}^{-}\geq c_{ji}^{-}$ . I praktiken är plogningstiden i nedförsbacke två gånger så effektiv som plogning i uppförsbacke, och deadheading är dubbelt så effektiv som plogning. Algoritmen hittar $k$ rutter som var och en börjar och slutar vid depån ${\displaystyle v_{0}} ,$ plöj bågen två gånger eftersom den vänstra och högra sidan av gatan tar två pass att plöja.

Den bästa lösningen kommer att minimera den maximala ruttlängden. Dussault, Golden och Wasil hittade en algoritm som inte översteg den nedre gränsen med 5,5 % i över 80 testkörningar. Avvikelsen ökade när komplexiteten i modellen ökade eftersom det finns fler ooptimerade approximationer än optimerade approximationer när modellen växer. En förbättring av Dussault et. al:s DPP-algoritm kan ha straff för att göra U-svängar och vänstersvängar, eller gå rakt över en korsning, vilket tar ytterligare tid och skjuter in snö i mitten av korsningen. (se The Directed Rural Postman Problem with Turn Penalties problem, ofta kallad DRPP-TP nedan).

k -problem med kinesisk brevbärare ( k -CPP)

Den k -kinesiska brevbäraren kan uttryckas på följande sätt: "med en sammanhängande kantvägd graf G och heltal p och k , bestäm om det finns minst k slutna promenader så att varje kant av G finns i minst en av dem och den totala vikten av kanterna i promenaderna är högst p ?" Processen för att erhålla lösningen till k -CPP är NP komplett. Gutin, Muciaccia och Yeo bevisade 2013 att k -CPP kan hanteras med fasta parametrar. Författarna bevisar att k -CPP tillåter en kärna med $O(k^{2}\log(k))$ hörn och den riktade versionen av k -CPP är NP komplett.

Rural postman problem (RPP) och generaliseringar

Rural postman problem (RPP) gör vissa rutter obligatoriska och absoluta men personen som korsar grafen behöver inte gå i en viss riktning. RPP är NP-hård och komplett, på samma sätt som kCPP, DPP, PPP, är NP-hård. Benevant studerade en generalisering av detta namngivna Directed Rural Postman Problem with Turn Penalties (DRPP-TP). Benevants algoritm approximerade lösningen genom att omvandla DRPP-TP till ett asymmetriskt resandeförsäljarproblem (ATSP).

Heuristik och algoritmer

De flesta algoritmer kräver en förbearbetning av grafen, vilket förenklar den initiala grafen genom att ta bort alla kanter som inte är i den kortaste vägen mellan två nödvändiga kanter. En annan förenkling som förbearbetningen tillför är att den omvandlar den kortaste vägen mellan 2 erforderliga kanter till en enda, icke erforderlig kant, oavsett antalet kanter i banan, förutsatt att det inte fanns några erforderliga kanter i banan.

När väl förbearbetningen är klar kan problemet generaliseras till ett konvext skrovproblem , där kanterna är skrovets spetsar. Problemet med konvexa skrov kan lösas genom linjär programmering eller genom konvexa skrovalgoritmer, men processen att hitta det konvexa skrovet är ett exponentiellt problem.

Metoder för att lösa URPP efter att förbearbetningen är klar består av skärplansalgoritmen och gren- och skärmetoden .

Komplexitet

Detta är en lista över beräkningskomplexiteter för olika bågdirigeringsproblem.

CP variant	Klassisk komplexitet	Approximation	Parametriserad komplexitet
Oriktad	$O(\|V\|^{3})$ -tidsalgoritm
Riktad	$O(\|V\|^{3})$ -tidsalgoritm $O((\|E\|-\|V\|)\|V\|^{2})$ -tidsalgoritm
Blandad	NP-komplett $O(\|V\|^{3})$ -tidslöslig om varje vertex har jämn grad	$O(\max\{\|V\|^{3},\|A\|(\max \{\|A\|,\|E\|\})^{2}\})$ -tidsfaktor 3/2	$O(2^{\|E\|}\cdot \|V\|^{3})$ -tidsalgoritm I FPT med avseende på \|A\| I XP med avseende på trädbredd
Blåsigt	NP-komplett P i vissa speciella fall	Faktor 3/2
k-hierarkisk	NP-komplett $O(k\|V\|^{4})$ -tidslöslig om företrädesrelationen linjär
Min-sum k brevbärare	$O(\|V\|^{3})$ -tidsalgoritm med postkontorspunkt, annars NP-komplett		I FPT med avseende på k utan postkontorspunkt
Min-max k brevbärare	NP-komplett	$O(\|V\|^{3})$ -tidsfaktor(2-1/k)

Lista över bågdirigeringsvarianter


Problem	Förkortning	Beskrivning	Output Notes	Exempel
Arc Routing Problem	ARP	Bestäm en lägsta kostnadsövergång av en specificerad bågdelmängd av en graf, med eller utan begränsningar.		Königsbergs sju broar
Problem med kinesiska brevbärare	CPP	oriktad graf G med hörn V och viktade kanter E	Passera varje kant minst en gång med minimal kostnad	"En brevbärare måste täcka sitt tilldelade segment innan han återvänder till postkontoret. Problemet är att hitta det kortaste gångavståndet för brevbäraren."
Lantligt brevbärarproblem	RPP	oriktad graf G med hörn V och viktade kanter E	Passera en delmängd av kanterna E minst en gång med minimal kostnad
Regisserad Rural Postman Problem	DRPP
Rural Postman Problem med Turn Penalties	RPP-TP, RPPTP
Blåsigt brevbärarproblem	WPP
Blåsigt lantligt brevbärarproblem	WRPP
Street Sweeper problem	SPP
m-plöjningsproblem	m-PP
Kapaciterad plogproblem	C-PP
Downhill Plog Problem	DPP
Downhill Plog Problem med Turn Penaltys	DPP-TP
Landsbygdens downhill-plogproblem med svängstraff	RDPP-TP
Problem med kapaciterad bågdirigering	KARP
k-Plow Blåsigt lantligt brevbärarproblem	k-WRPP
Min-Max Downhill Plog Problem med flera plogar	MM k-DPP
Min-Max Blåsigt lantligt brevbärarproblem	MM k-WRPP
Plöjning med företrädesproblem	PPP
Min-Max Extended Downhill Plog Problem	MM k-DPPE
Kapaciterad kinesisk brevbärare Problem	CCPP
Regisserad Chinese Postman Problem	DCPP
Regisserad Rural Postman Problem	DRPP
Extended Capacitated Arc Routing Problem	ECARP
Hierarkiskt kinesiskt brevbärarproblem	HCPP
Problem med blandad kapaciterad bågrouting	MCARP
Blandat kinesiskt brevbärarproblem	MCPP
Stacker Crane Problem	SCP	Vissa bågar måste passeras minst en gång i en riktning men kan korsas lika många gånger i den andra riktningen
Resande säljare problem	TSP
Problem med oriktad kapaciterad bågdirigering	UCARP
Oriktat lantbrevbärarproblem	URPP
Problem med fordonsdirigering	VRP
Min-Max Problem med flera depåer på landsbygden	MMMDRPP
Generaliserat problem med fordonsdirigering	GVRP

externa länkar

Se även