Detta dokument är den andra delen av en omfattande undersökning om routingproblem som rör pickuper och leveranser. I grund och botten kan man urskilja två problemklasser. Den första delen handlade om transport av gods från depån till linehaulkunder och från backhaulkunder till depån. I den andra delen behandlas nu alla de problem där varor transporteras mellan pickup och leveransställen, betecknade som fordonsrutteringsproblem med pickuper och leveranser (VRPPD). Dessa är Pickup och leverans Vehicle Routing Problem (PDVRP - oparade pickup och leveranspunkter), den klassiska Pickup och leverans problem (PDP -parade pickup och leveranspunkter), och Dial-A-Ride problem (DARP -passenger transport mellan parad pickup och leveranspunkter och användarolägenheter beaktas). Enstaka och multi vehikel matematiska problemformuleringar för alla tre VRPPD-typer ges, och respektive exakta, heuristiska och metaheuristiska lösningsmetoder diskuteras. Syftet med detta dokument är att presentera ett klassificeringssystem samt en omfattande undersökning av problem med pickup och leverans och deras varianter. I del I i denna undersökning presenterades alla problemtyper som hör till klassen fordons Routing Problem med Backhauls (VRPB), där varor transporteras från en depå till linehaul kunder och från backhaul kunder till en depå. Dessutom gavs motivet till denna undersökning. Del II omfattar alla problemtyper där varor transporteras mellan pickup- och leveransplatser, så kallade fordonsrutteringsproblem med pickuper och leveranser (VRPPD). De två hämtnings- och leveransproblemklasserna samt deras underklasser beskrivs i figur 1. Den grå delen diskuterades i del I i denna undersökning. De nummer som anges i fälten anger de avsnitt som täcker respektive problem. De två första indikatorerna avser modelleringsdelen medan de sista hänvisar till avsnitten om lösningsmetoder. Klassen vi betecknar VRPPD avser problem där varor transporteras från pickup till leveransställen. Den kan delas in ytterligare i två underklasser. Den första underklassen avser situationer där pickup och leveransplatser är oparerade. Man tar hänsyn till en homogen vara. Varje enhet som plockas upp kan användas för att uppfylla efterfrågan hos en leveranskund. I litteraturen oftast den enda fordon fall hanteras, betecknas som kapaciated resa 1 Figur 1 : Pickup och leverans problem. Siffrorna avser de avsnitt som täcker respektive problem. Problem (GDP) transport från / till en depå (VRPB) säljare problem med pickuper och leveranser (Anily och Bramel, 1999), One-Commodity Pickup och leverans Traveling Salesman Problem (1-PDTSP) (Hernández-Pérez och SalazarGonzález, 2003), och resande säljare problem med pickup och leverans (Hernández-Pérez och Salazar-González, 2004a ). Eftersom även en multi vehicle application har rapporterats i litteraturen (se Dror et al., 1998) kommer vi att beteckna denna problemklass som Pickup och leverans Vehicle Routing Problem (PDVRP) och Pickup och Delivery Traveling Salesman Problem (PDTSP), i multi och i det enda fordon fallet, respektive. Den andra VRPPD-underklassen omfattar det klassiska Pickup- och leveransproblemet (PDP) och Dial-A-Ride-problemet (DARP). Båda typerna överväger transportförfrågningar, var och en i samband med ett ursprung och en destination, vilket resulterar i parade pickup och leveranspunkter. PDP behandlar varutransporter medan DARP behandlar passagerartransporter. Denna skillnad uttrycks vanligen i form av ytterligare begränsningar eller mål som uttryckligen tar hänsyn till användarens (i) bekvämlighet. Den enda fordonsvarianten av PDP har också kallats pickup-delivery travelman problem (Kalantari et al., 1985) och multifordon fall som fordon routing problem med pickup och leverans (Drigs och Döhmer, 2008). En majoritet av de publicerade verken betecknar dock denna problemklass som Pickup- och leveransproblem (PDP) (se t.ex. Dumas et al., 1991, van der Bruggen et al., 1993. Vi kommer att följa detta namn. Dial-a-ride problem kallas också oftast som sådana. Men vissa författare, såsom Toth och Vigo (1996), betecknar samma problem som de funktionshindrade personer transport problem. Den dynamiska versionen kallas också efterfrågeflexibel transport (jämför t.ex. Mageean och Nelson, 2003). Vi betecknar fallet med ett enda fordon i PDP som SPDP, fallet med ett enda fordon i DARP som SDARP. När det gäller transporter kan två problemklasser urskiljas: problem med full lastbilslast och problem med mindre last än lastbilslast. Problem med full lastbilslast handlar om fordon med enhetskapacitet samt enhetsefterfrågan eller utbudet på varje kundplats. Vid parad pickup och leverans platser, ingen annan kund kan besökas mellan en pickup och dess tillhörande leverans plats (se Archetti och Speranza, 2004, Coslovich et al., 2006a, Currie och Salhi, 2003, de Meulemeester et al., 1997, Doerner et al., 2001, Fleischmann et al., 2004, Gronalt et al., 2003, Gronalt och Hirsch, 2007, Imai et al., 2007, Jordanien och Burns, 1984, Jordanien, 1987, Powell et al., 1995,b, Regan et al., 1996a, b, 1998, Russell och Challinor, 1988, Wang och Regan, 2002, Yang et al., 1998. Dessutom finns det en problemklass som per definition inte ingår i fulllastklassen, eftersom fordon med kapacitet två beaktas. Dessa problem är dock starkt relaterade till kategorin full lastbilslast eftersom de kommer från samma användningsområde (container avsändning). Syftet med detta dokument är att presentera ett koncist klassificeringssystem och en översikt som är begränsad till problem med fordonskörning i samband med pickup- och leveransverksamhet där routing och inte schemaläggning är av största betydelse. Tillvägagångssätt för leverans av full lastbilslast och metoder som är starkt relaterade till denna klass (se t.ex. Archetti et al., 2005, le Blanc et al., 2006 kommer inte att omfattas av denna artikel. Även litteratur om sekvensproblem, t.ex. som uppstår vid intermodala stationer, inbegripet upphämtning och leverans av kranar (jämför t.ex. Böse et al., 1999, Böse et al., 2000, Gutenschwager et al., 2003 kommer inte att ingå i denna undersökning. Resten av detta dokument är organiserat enligt följande. För det första, för att tydligt definiera de olika VRPPD-typerna, ges konsekventa matematiska problemformuleringar för singeln och för flerfordonsfallet. Därefter diskuteras lösningsmetoder i underavsnitt som ägnas åt motsvarande problem. I vart och ett av dessa underavsnitt presenteras exakta, heuristiska och metaheuristiska lösningsmetoder. Även relaterat arbete kommer att nämnas. I avsnitt 4 ges en översikt över befintliga referensfall för de olika problemklasserna samt viss information om de mest kända lösningarna. Avslutande kommentarer och möjliga anvisningar för framtida forskning ges i slutet av denna undersökning. I följande avsnitt kommer konsekventa matematiska problemformuleringar att presenteras. För det första anges den notation som används under hela undersökningen. Därefter införs två grundläggande problemformuleringar, en för singeln och en för multifordonsväskan. Dessa är anpassade till den oparade pickup och leverans problem, den klassiska pickup och leverans problem, och dial-a-ride problem, respektive. Observera att de matematiska modellerna endast ges för definitionsändamål, oavsett styrkan i deras LP avkopplingar eller om de användes i samband med additiv begränsning, gren och skära algoritmer, eller Lagrange avkopplingar. Vi hänvisar den intresserade läsaren till det arbete som sammanfattas i avsnitten om exakta lösningsförfaranden för ytterligare information om dessa aspekter. Alla problem som definieras är NP-hårda eftersom de generaliserar den välkända Traveling Salesman Problem (TSP) (Garey och Johnson, 1979 Observera att denna notation gäller för symmetriska och asymmetriska fall. I det symmetriska fallet kan t k ij = t k ji och c k ij = c k ji, båge (i, j) och båge (j, i) modelleras med en kant. Följaktligen skulle färre variabler behövas. Men eftersom vi fokuserar på problemdefinition och inte på beräkningseffektivitet, avstår vi från att presentera dessa varianter här. VRPPD är modellerade på kompletta grafer G = (V, A) där V är uppsättningen av alla hörn V = {0, n +ñ + 1}  och A uppsättningen av alla bågar. Av praktiska skäl kan båguppsättningen reduceras till Under optimeringsprocessen bestäms några eller alla av följande beslutsvariabler, beroende på vilket problem som övervägs. Observera att fordonsberoende start samt slutvertik kan enkelt införas i modellen. Men för enkelhetens skull kommer vi inte att överväga denna utvidgning i vår formulering. I det enda fordonet problem formulering superscript k kan utelämnas, vilket resulterar i parameterkoefficienter c ij, t ij, C, T och besluten variabler x ij, Q i, B i. Modellen med ett fordon för olika VRPPD baseras på en öppen TSP-formulering. För Då, den öppna TSP formulering är min föremål för: j:(i,j) till A Den objektiva funktionen (1) minimerar total routing kostnad. Jämlikheter (2) och (3) säkerställa att varje vertex besöks exakt en gång. Restriktioner (4) ger en av flera möjligheter att säkerställa linjeanslutning. För andra alternativ hänvisar vi till del I i denna undersökning. 4 Här antas att varje enhet som plockas upp kan användas för att tillfredsställa varje leveranskunds efterfrågan. I likhet med TSPMB, som beskrivs i del I av denna undersökning, fordonsbelastning begränsningar måste ändras till formulering (1) - (5), I motsats till TSPMB den ursprungliga lasten av fordonet är fri här (se Hernández-Pérez och Salazar-González, 2004a). Dessutom är PDTSP (PDVRP) den enda VRPPD-klass där jämlikhet behövs i (6a), för alla andra problemtyper skulle ett "-"tecken räcka. SPPP tar hänsyn till situationer där pickup och leverans hörn paras, dvs.. n =ñ..................................................................................................... I litteraturen är det vanligt att hänvisa till en sådan vertex par som en begäran, indexerad av i = 1,..., n med i är ursprung eller pickup punkt och n + i motsvarande destination eller leveransställe. För att säkerställa att varje destination endast besöks efter sitt ursprung, förutom 1) - 3, 5 och (6), krävs företrädesbegränsningar som vanligtvis modelleras med hjälp av tidsvariabler, anges det i Restriktioner (7) att varje ursprung ska besökas före destinationen och (8) säkerställa att tidsvariablerna överensstämmer med rese- och tjänstetiderna. Observera att (8) också garanterar att korta cykler undviks och därmed ojämlikhet (4) inte behövs, med tanke på att (SDARP handlar om transport av människor. Sådana problem uppstår, t.ex. i samband med transporter av funktionshindrade eller äldre personer. En annan möjlig tillämpning är emellertid transport av lättfördärvliga varor, som också kräver maximal körtid. Utöver den grundmodell som anges i punkterna 1 - 3 och 5 - 8 måste användarolägenheter beaktas. Detta kan hanteras med en annan term i den objektiva funktionen eller genom ytterligare begränsningar. Här väljer vi att formulera en maximal körtid för användaren, Restriktioner som hänvisar till överensstämmelse med Time Windows (TW), kan läggas till i alla ovanstående formuleringar. När det gäller passagerartransporter är TW vanligtvis närvarande. Observera att ovanstående formuleringar inte är linjära på grund av begränsningar (6a) och (8). Dessa kan linjäriseras med hjälp av en stor M-formulering (jfr. Cordeau, 2006). 5 Grundmodellen för multifordonshämtning och leveransproblem är en anpassad tre index fordon routing problemformulering av den föreslagna i (Cordeau et al., 2002, s. Denna förordning träder i kraft den tjugonde dagen efter det att den har offentliggjorts i Europeiska unionens officiella tidning. för VRPTW. min subject to: i:(i,j) till A Den objektiva funktionen (11) minimerar den totala routingkostnaden. Restriktioner (12) anger att varje vertex måste serveras exakt en gång. Jämlikheter (13) och (14) garanterar att varje fordon startar vid depån och återvänder till depån i slutet av sin rutt. Observera att detta inte innebär att varje fordon måste användas. Ett fordon får endast använda bågen (0, n +ñ + 1), dvs. Den lämnar inte depån. Flödesbevarande säkerställs genom (15). Tidsvariabler används för att eliminera subtours i (16), med tanke på att (t k ij + d i ) > 0 för alla (i, j) A. Restriktioner (17) och (18) garanterar att ett fordons kapacitet inte överskrids under hela dess färd. Det bör noteras att denna formulering kräver införandet av ytterligare beslutsvariabler, Q k i, som motsvarar den totala fordonsbelastningen k vid vertex i. Dessa variabler behövs inte för att formulera den grundläggande VRP men är nödvändiga för dess utvidgning till en pickup och leverans problem. I VRP-formuleringar används ojämlikheter som liknar (17) ibland för att säkerställa vägkonnektivitet (uppfylls av (16) i ovanstående formulering). Dessutom behövs i (17) jämlikhet endast för PDVRP (PDTSP). För alla andra VRPPD-typer kan den ersättas med " ska". Icke-linjära begränsningar som anges i (16) och (17) kan linjäriseras med hjälp av en stor M-formulering (jfr. Cordeau, 2006). Den speciella egenskapen hos PDVRP är att varje enhet som plockas upp kan användas för att tillfredsställa varje kunds efterfrågan. Ovanstående formulering (11) -(19) är redan en lämplig formulering för PDVRP. Inga ytterligare anpassningar behövs. Här förknippas varje pickuppunkt med en leveranspunkt och därför n =ñ. Förutom (11) -(19) behövs ytterligare två uppsättningar begränsningar. För det första, både ursprung och destination för 6 en begäran måste betjänas av samma fordon, Dessutom kan leverans endast ske efter upphämtning, dvs.. För att utvidga multifordonets parkeringsbromssystem till flerfordonsbromssystemet måste man återigen, liksom i fallet med ett enda fordon, lägga till begränsningar i samband med användarolägenheter. När det gäller den enda fordonsversionen kommer vi att begränsa detta krav till att lägga till maximala begränsningar av körtiden för användaren i formuleringen (11) - (21): Ytterligare två uppsättningar begränsningar kan läggas till alla ovannämnda problemklasser. Detta är tidsfönster och begränsningar för maximal resvägstid, 3 Lösningsmetoder för VRPPD I följande avsnitt presenteras en översikt över de olika lösningsmetoderna för PDVRP, PDP och DARP. Lösningsmetoder klassificeras i exakta, heuristiska och metaheuristiska metoder. En beskrivning av de referensfall som används ges i avsnitt 4. För hänvisningar till allmän information om de lösningskoncept som tillämpas hänvisar vi till den första delen av detta dokument. En annan undersökning om olika lösningsmetoder finns i (Berbeglia et al., 2007). På grund av maximala papperslängdsbegränsningar var det inte möjligt att beskriva allt arbete som publicerats i detalj. En översikt över de föreslagna metoderna ges i tabellform. Endast bidrag som vi ansåg vara särskilt viktiga, av aktualitets- eller originalitetsskäl, beskrivs närmare. Dessa markeras med en asterisk i de olika tabellerna. Lösningsmetoder beställs kronologiskt i tabellerna, enligt enkel- och flerfordonsinflygningar. Ytterligare detaljer om lösningsalgoritmer ges i samma ordning. PDVRP, dvs. Den problemklass där alla varor kan plockas upp och transporteras var som helst, fick inte lika mycket uppmärksamhet i litteraturen som de andra problemklasserna. Dessutom är merparten av litteraturen begränsad till PDTSP. Därför, med undantag av (Dror et al., 1998), är alla lösningsmetoder som presenteras endast tillämpliga på ett fordonsfall. Till författarnas kännedom har inget metaheuristiskt tillvägagångssätt för PDTSP föreslagits fram till idag. 7 Den enda exakta metod som föreslagits för det aktuella problemet infördes i Salazar-González 2003, 2004a). Det är en gren och klippa algoritm. För att påskynda algoritmkonstruktionen och förbättringen tillämpas heuristik. De används för att erhålla genomförbara lösningar från lösningen av LP avslappning vid nuvarande nod. Konstruktionen heuristiska är en anpassning av den närmaste insättningsalgoritmen. Det förbättras genom 2-opt och 3-opt utbyten (Lin, 1965). De testfall som lösts är anpassningar av de som används i (Mosheiov, 1994) och (Gendreau et al., 1999), som innehåller upp till 75 kunder. Ett specialfall av PDTSP beaktas i (Chalasani och Motwani, 1999); antalet varor som ska hämtas är lika med antalet varor som ska levereras; efterfrågan (utbudet) vid varje leverans (upphämtning) plats är lika med en. Detta problem är en utvidgning av växlingsproblemet där fordonets kapacitet också är satt till en. Chalasani och Motwani föreslår en approximationsalgoritm med ett värsta fall bundet till 9,5. De använder Christofides heuristic (Christofides, 1975) för att konstruera två resande försäljare turer, en med endast pickup platser, och en med endast leverans platser. Dessa två turer kombineras sedan med hjälp av nedbrytning och matchning. Anily och Bramel (1999) utforma en polynom tid itererad tur matchande algoritm för samma problem. Två heuristiska metoder finns i (Hernández-Pérez och Salazar-González, 2004b). Den första algoritmen är av konstruktionsförbättringstyp, med hjälp av en girig konstruktion förfarande, förbättras genom 2-opt och 3-opt utbyten. Den andra heuristiska är baserad på ofullständig optimering; grenen och skär procedur, beskrivs i (Hernández-Pérez och Salazar-González, 2004a), används på ett minskat antal variabler som förknippas med lovande kanter. Slumpmässiga fall med upp till 500 kunder är lösta. En approximationsalgoritm på en trädgraf utvecklas i (Lim et al., 2005). Den bygger på en återkommande konstruktionsprocess och har ett värsta fall som är bundet till 2. Den PDTSP på ett träd och på en linje är också föremål för utredning i (Wang et al., 2006). De föreslår en O( och V)-algoritm för linjefallet. Enhetens kapacitet samt den okapaciteterade versionen kan lösas i linjär tid. På ett träd är en O( skav) algoritm utformad för fallet med enhetskapacitet och en O( skaV  ska 2 ) algoritm för den okapacitetsfyllda fallet. Äntligen, Dror et al. (1998) föreslår en heuristisk algoritm för tillämpning av PDVRP för flera fordon på omfördelning av självbetjäningsbilar. Det är relaterat till Dijkstra algoritm (Dijkstra, 1959). Även andra lösningar diskuteras kortfattat. Lösningsmetoder för den klassiska pickup och leverans problem (PDP), där varje transport begäran är associerad med en pickup och ett leveransställe, presenteras i detta avsnitt. Lokin (1978) var den förste som diskuterade införlivandet av företrädesbegränsningar i den traditionella TSP som behövdes för att formulera PDP. Det första försöket att generalisera PDP i enhetlig notation föreslogs i (Savelsbergh och Sol, 1995), som täcker alla möjliga versioner av PDP, inklusive dial-a-ride problem. De ger också en kort översikt över befintliga lösningsmetoder fram till 1995. Mitrović-Minić (1998) presenterar en undersökning om PDP med Time Windows (PDPTW). En tidig undersökning av problem med fordonsrouting redan inklusive PDP ges i (Desrochers m.fl., 1988). Cordeau m.fl. (2004) se över efterfrågan på miljövänliga transporter som omfattar PDP och DARP. En översyn av det senaste arbetet med att fokusera på exakta tillvägagångssätt ges i. Ytterligare undersökningar om lösningsmetoder finns i (Assad, 1988, Desaulliers m.fl., 2002, Desrochers m.fl., 1988. I de följande 8 styckena sammanfattas de olika lösningsteknikerna för den statiska PDP enligt exakta, heuristiska och metaheuristiska metoder. Ett antal exakta lösningsförfaranden har presenterats för den statiska PDP. I tabell 1 beskrivs de olika teknikerna kortfattat. Referenserna till litteraturen, målen och de ytterligare begränsningar som beaktas anges. Dessutom tillhandahålls antingen de referensfall som används, eller storleken på den största instans som lösts till optimalitet, uttryckt i antal förfrågningar. Poster markerade med en asterisk beskrivs närmare nedan. Ruland och Rodin (1997) presenterar en gren och skär algoritm för att lösa SPPP. Den omfattar kapning av plangenerering i gränsfasen samt ett girigt vägbyggesförfarande för att generera den första övre gränsen. En gren och bunden algoritm för det enda fordonet PDPTW med Last-In-First-Out (LIFO) lastning, dvs. Varor måste levereras i omvänd ordning de plockades upp, rapporteras i (Cordeau et al., 2006). De föreslår tre matematiska problemformuleringar och olika giltiga ojämlikheter. Dessa bygger på befintliga ojämlikheter för PDP och nya problemspecifika sådana. Den första exakta lösningsmetoden som gäller för både singel- och flerfordonsfallet går tillbaka till (Kalantari et al., 1985). Den gren och bundna algoritm som beskrivs är en förlängning av den som utvecklats av Little et al. (1963) 9 En kolumn generation metod utarbetas i. De tar hänsyn till heterogena fordon, tidsfönster och flera depåer. De begränsade kortaste stigproblemen löses med hjälp av en framåtgående dynamisk programmeringsalgoritm. Ropke och Cordeau (2006) inför en bransch- och prisalgoritm med ytterligare giltiga ojämlikheter. Den elementära begränsning kortaste vägen problem med tidsfönster, kapacitet, och pickup och leveransbegränsningar är den naturliga prisproblem PDPTW. Det är löst med hjälp av en etikett inställning kortaste vägen algoritm. Giltiga ojämlikheter läggs till i en bransch och skuris ned; deras inverkan på prissättningsproblemets struktur diskuteras. En gren och klippa algoritm som avviker från två olika 2-index PDPTW formuleringar studeras i. Formulering man använder sig av tid variabler. I formuleringen två tidsrelaterade begränsningar modelleras med hjälp av ogenomförbara väg ojämlikheter. Den senare formuleringen visar sig vara effektivare när den används som grund för grenen och klippa algoritmen. Nya giltiga ojämlikheter för att stärka de föreslagna formuleringarna diskuteras också. Heuristik för den statiska PDP har först föreslagits på 1980-talet. Tabell 2 ger en översikt över de olika heuristiska lösningar som utvecklats sedan dess. Information om vilken typ av problem som övervägs, vilka mål som används, ytterligare begränsningar, vilken typ av algoritm som föreslås samt antingen de referensfall som lösts eller den största instans som beaktas för testningsändamål ges. Sexton och Choi (1986) använder Benders nedbrytningsprocedur för att lösa det statiska SPDP ungefär. Initiala lösningar är konstruerade med hjälp av en rum-tid heuristic. Stegförbättringsfasen är baserad på Benders nedbrytning. Eftersom mjuka tidsfönster beaktas, tar den objektiva funktionen hänsyn till den totala drifttiden samt straffavgifter för överträdelse av tidsfönster. En bygg-förbättring heuristisk algoritm för den statiska SPDP diskuteras i (van der Bruggen et al., 1993). För det första konstrueras en genomförbar första lösning. Sedan förbättras denna lösning genom utbytesförfaranden som hela tiden bibehåller genomförbarheten. Renaud m.fl. (2000) föreslår också en algoritm för att förbättra konstruktionen för samma problem. De använder en dubbel insättning konstruktion heuristic förbättras genom radering och återinsättning (4-opt* (Renaud et al., 1996) ). Renaud m.fl. (2002) presenterar sju olika perturbationsheuristik för att generera nära optimala lösningar för det statiska SPDP. I alla sju genomförandena beräknas för det första en första lösning som förbättras av en 4-opt** heuristisk, en anpassning av 4-opt* heuristiska, så att företrädesbegränsningar alltid respekteras. Därefter tillämpas ett perturbationsschema (intans, algoritmisk eller lösningsperturbering), följt av en postoptimeringsfas. De två sista stegen upprepas tills ett stoppkriterium är uppfyllt. De bästa resultaten erhålls med lösningen perturbationsschemat. Xu och al. (2003) föreslå en kolumngenereringsbaserad heuristisk algoritm för multifordonsfallet. De överväger flera ytterligare begränsningar, såsom flera tidsfönster vid pickup och leveransställen, lastningsbegränsningar, kompatibilitet mellan varor och fordon samt förarens arbetstider. Kolumngenerationens huvudproblem kan lösas med hjälp av en kommersiell LP-lösare. De resulterande subproblemen löses med hjälp av två heuristiker som kallas sammanfogning och tvåfas, d.v.s. Sammanslagning resor och girig radering och införande av förfrågningar. Lu och Dessouky (2006) utvecklar en byggnadsheuristisk. Den innehåller inte bara en ökning av avståndet i utvärderingskriteriet utan även en minskning av tidsfönstrets slack samt en visuell dragningskraft (i procent av korsningens längd). De respektive referensfallen beskrivs i avsnitt 4. De poster som markeras med en asterisk (*) beskrivs närmare i texten. 1 dvs. Ett iterativt förfarande baserat på en insättningsalgoritm. Den prioriterar förfrågningar som orsakade svårigheter i tidigare iterationer. Tabell 3 ger en översikt över de olika metaheuristiska lösningsmetoder som föreslås för den statiska PDP. För varje referens anges samma uppgifter som i de föregående tabellerna. En variabel sökning i grannskapet efter en förlängning av SPPP diskuteras i (Carrabs et al., 2007). Det problem som tas upp omfattar ytterligare begränsningar när det gäller last i baksätet, dvs. Varor kan endast levereras i ett LIFO-material. Åtta olika konstruktionsmetoder används för att generera en första lösning. Grannarna definieras av parbyten, blockbyten, omlokaliseringsblock, 2-opt-L (2-opt med endast LIFO-genomförbara ljusbågsbyten) och multi-relocate operatörer. 10 Li och Lim (2001) utvecklar en inbäddad simulerad glödgningsmetod för PDP. Hämtning och leverans par swap kvarter definieras. Dessa bygger på ett skift, en 11 byte, och en omorganisation operatör. De två första definierar de områden som genomsöks av metaheuristic, den tredje används för postoptimering. Pankratz (2005b) föreslår en gruppering av genetisk algoritm för PDP. Det skiljer sig från traditionella genetiska algoritmer genom att en grupporienterad genetisk kodning används. Den kodning som används av Pankratz (2005b) motsvarar den grupp av förfrågningar som bildar en rutt. Routing-aspekten, som inte ingår i kodningen, läggs till när kromosomen avkodas. Ropke och Pisinger (2006a) presenterar en adaptiv stor stadsdelssökningsalgoritm för PDPTW. Flera depåer och existensen av servicetider kan hanteras av det tillvägagångssätt som finns. I Pisinger, 2006b ) den föreslagna metoden används för att lösa VRP och VRPB instanser genom att omvandla dem till rika PDPTW. Vi hänvisar till del I i denna undersökning för ytterligare detaljer om detta lösningsförfarande. En två-stegs hybrid algoritm för den statiska PDPTW presenteras i. I den första fasen används simulerad glödgning för att minska antalet fordon som behövs. Den andra fasen består av en stor kvarterssökning algoritm för att minska den totala resekostnader. Derigs och Döhmer (2008) diskuterar en indirekt (evolutionär) lokal sökning heuristisk för samma problem. I indirekta söklösningar kodas så att problemet med att säkra genomförbarheten separeras från den metaheuristiska sökprocessen. Här används en girig avkodning. Sammanfattning, den största statiska PDP problem instans löst till optimalitet med en toppmodern metod omfattar 205 förfrågningar (Sigurd et al., 2004). Storleken på den största instansen som lösts är dock inte alltid en bra indikator; hårt begränsade problem är lättare att lösa än mindre hårt begränsade. Referensdatamängden som oftast används för att bedöma prestandan hos (meta)heuristiska metoder för den statiska PDPTW är den som beskrivs i ) (LL01, LL01+, se tabell 6 ). Nya bästa resultat har presenterats i (Ropke och Pisinger, 2006a) och, två metaheuristiska lösningsförfaranden. Metaheuristic av Li och Lim (2001) har fortfarande de bästa resultaten för en del av de mindre fallen. Men också exakta metoder avancerade; den mer snävt begränsade delen av LL01 datauppsättningen har nyligen lösts av en toppmodern gren och klippa och prisalgoritm (Ropke och Cordeau, 2006).
Se REF för en undersökningsartikel.
A survey on pickup and delivery problems: Part i: Transportation between customers and depot
{'venue': 'Journal für Betriebswirtschaft', 'journal': None, 'mag_field_of_study': ['Computer Science']}