Dial-a-Ride problem består av en uppsättning V av n hörn i ett metriska utrymme (betecknar restiden mellan hörn) och en uppsättning m objekt som representeras som käll-destination par {(s i, t i )} m i=1, där varje objekt kräver att flyttas från sin källa till destination vertex. I flerfordons Dial-a-Ride problem, det finns q fordon, var och en har kapacitet k och där varje fordon j... [q] har sin egen depå-vertex r j... V. En genomförbar schema består av en kapaciated rutt för varje fordon (där fordonet j har sitt ursprung och slutar vid sin depå r j ) som tillsammans flytta alla objekt från sina källor till destinationer. Målet är att hitta en genomförbar tidsplan som minimerar den maximala färdigställandetiden (dvs. makepan) för fordon, där färdigställandetiden för fordon j är den tid då det återvänder till sin depå r j i slutet av sin rutt. Vi studerar den förebyggande versionen av flerfordons Dial-a-Ride, där ett föremål kan lämnas kvar på mellanliggande hörn och transporteras med mer än ett fordon, medan det flyttas från källa till destination. Våra huvudsakliga resultat är en O(log 3 n)-tillnärmning algoritm för förebyggande multi-fordon Dial-a-Ride, och en förbättrad O(log t)-tillnärmning för sitt specialfall när det inte finns någon kapacitetsbegränsning (här t ≤ n är antalet distinkta depå-vertik). Det finns en (log 1/4− n) hårdhet approximation känd även för en enda fordon kapacitated Dial-a-Ride [Gørtz 2006]. För okapaciteterade flerfordons Dial-a-Ride, visar vi att det finns fall när naturliga nedre gränser (används i vår algoritm) är (logt) faktor bort från den optimala. Vi betraktar också den speciella klassen av mätvärden inducerad av grafer exklusive eventuella fasta mindre (t.ex. plana mätvärden). I detta fall får vi förbättrade garantier för O(log 2 n) för kapaciated multi-vehicle Dial-a-Ride, och O(1) för okapacitetsproblem. 23:2 I. L. Gørtz et al. när som helst. Två versioner av Dial-a-Ride studeras, baserat på om objektvägar är förebyggande eller inte. I denna artikel, vi anser att den mindre granskade förebyggande version, i vilken preemption (även känd som transshipment) av objekt kan förekomma på någon vertex i metriska. Standardmålen i Dial-a-Ride-problem är total färdigställandetid och maximal färdigställandetid (makespan). Flera fordon totalt slutförande tid problemet medger en enkel minskning till en fordon Dial-a-Ride, som diskuteras nedan. Här studerar vi makespan-versionen av problemet, vilket är mer intressant ur algoritmisk synvinkel. Vårt huvudsakliga resultat är ett polylogaritmiskt approximationsförhållande för detta problem. Även om flera kvalifikationer kan få problemet att framstå som löst, är det just detta problem som modellerar kurir- eller postleverans över en dag från flera stadsdepåer: preemption är billigt och användbart för paket, lastbilar kapaciteras och makepan återspeglar den dagliga arbetstidsgränsen för varje lastbil. Trots dess allestädes närvarande har detta problem inte studerats lika väl som andra Dial-a-Ride-versioner. Ett skäl från den empiriska sidan är svårigheten att hantera möjligheten till företräden i en rimlig matematisk programmeringsmodell. På den teoretiska sidan, som står i centrum för detta dokument, kvarstår svårigheten att använda preemption på ett meningsfullt sätt; den förvärras ytterligare av hårdheten i makespan-målet. Det förebyggande problemet Dial-a-Ride har diskuterats tidigare med ett enda fordon, för vilket en O(log n) approximation [Charikar och Raghavachari 1998] och en (log 1/4— n) hårdhet approximation [Gørtz 2006] är kända; här n är antalet hörn. Observera att slutförandet och makespan-målen sammanfaller i fallet med ett fordon. Genom att gå över till flera fordon, medger det totala målet för slutförandet en enkel tillnärmning av O(log n) i linje med problemet med ett fordon [Charikar och Raghavachari 1998]: med hjälp av probabilistiska träd inbäddning [Fakcharoenphol et al. 2004], man kan minska till träd mätvärden vid förlust av en förväntad O(log n) faktor, och det finns en enkel konstant faktor approximation för detta problem på träd. Makespan-målet, som vi behandlar i den här artikeln, visar sig vara betydligt svårare. På grund av nonlinearity av makespan mål, denna minskning till träd mätvärden håller inte. Dessutom verkar problemet med madepan inte särskilt lättare att lösa ens på träd. MDAR problemet fångar aspekter av både maskin schemaläggning och nätverk design problem. Till skillnad från i fallet med ett fordon får ett föremål i flerfordons Dial-a-Ride transporteras med flera fordon det ena efter det andra. Det är därför viktigt att fordonsvägarna samordnas så att föremålen spårar giltiga vägar från respektive källor till destinationer. Till exempel, ett fordon kan behöva vänta vid en vertex för andra fordon som transporterar gemensamma föremål att anlända. På grund av sådana schemaläggning problem, mDAR problemet är icke-trivial även i avsaknad av kapacitet begränsningar. I den här artikeln ger vi först en approximation algoritm för den okapacitet mDaR problem, vilket är intressant i sig. Sedan generaliserar vi resultatet till den kapacierade inställningen. Vi visar också att förbättrade approximationskvoter kan uppnås i båda fallen för mätvärden som utesluter vissa fasta minor (t.ex. plana mätvärden). Vi noterar att även om vår modell tillåter ett antal företräden och företräden på alla hörn, använder våra algoritmer inte denna möjlighet i sin fulla utsträckning. Algoritmen för det kapaciterade fallet förebådar varje objekt högst en gång. Algoritmen i det oskadliggjorda fallet förhindrar objekt endast vid depåvertices och högst ett logaritmiskt antal gånger. Vi representerar en ändlig metrisk som (V, d) där V är uppsättningen av hörn och d är en symmetrisk avstånd funktion som uppfyller triangeln ojämlikhet. För delmängderna A, B och V betecknar vi minimimåttet Makespan Multi Vehicle Dial-a-Ride 23:3 med d(A, B) det minsta avståndet mellan en vertex i A och en annan i B, så d(A, B) = min{d(u, v). För en delmängd E  och V 2 kanter, d(E) := e.E d e betecknar den totala längden av kanter i E. MDAR problemet består av en n-vertex metrisk (V, d), m objekt som anges som källdestination par {s i, t i } m i=1, q fordon med respektive depå-vertices {r j } q j=1, och en gemensam fordonskapacitet k. En genomförbar schema är en uppsättning q-vägar, en för varje fordon (där rutten för fordon j  och [q] startar och slutar vid r j ), så att inget fordon bär mer än k objekt när som helst och varje objekt flyttas från sin källa till destination. Efterbehandlingstiden C j för varje fordon j  på [q] är den tid då fordonet j återvänder till sin depå r j i slutet av sin rutt (schemat antas börja vid tidpunkten 0). Målet i mDaR är att minimera makespan, d.v.s. min max j till[q] C j. Vi betecknar med S := {s i  till i [m]} uppsättningen källor, T := {t i... i [m]} uppsättningen av destinationer, R := {r j  till j [q]} uppsättningen av distinkta depå-vertiker, och t :=  på antalet distinkta depåer. Hela tiden anser vi att den förebyggande versionen, där objekt kan lämnas på mellanliggande hörn och transporteras av flera fordon, medan flyttas från källa till destination.
I REF ges en approximation för förebyggande CPDP, där föremål släpps av vid pickuppunkter och hämtas av andra fordon senare.
Minimum Makespan Multi-Vehicle Dial-a-Ride
{'venue': 'TALG', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}