Denna artikel presenterar en exakt algoritm för multi-depot fordon routing problem (MDVRP) under kapacitet och sträcka begränsningar. MDVRP formuleras med hjälp av en vehicle-flow och en set-partitioning formulering, som båda utnyttjas i olika stadier av algoritmen. Den nedre gräns som beräknas med vehikelflödesformuleringen används för att eliminera icke- lovarande kanter, vilket minskar komplexiteten i det prisunderproblem som används för att lösa den set-partitionerande formuleringen. Flera klasser av giltiga ojämlikheter läggs till för att stärka båda formuleringarna, inklusive en ny familj av giltiga ojämlikheter som används för att förbjuda cykler av godtycklig längd. För att validera vårt tillvägagångssätt anser vi också att problemet med kapaciated vehicle routing (CVRP) är ett särskilt fall av MDVRP, och utför omfattande beräkningsförsök på flera fall från litteraturen för att visa dess effektivitet. Beräkningsresultaten visar att den föreslagna algoritmen är konkurrenskraftig mot toppmoderna metoder för dessa två klasser av fordon routing problem, och kan lösa till optimalitet några tidigare öppna instanser. För de fall som inte kan lösas med den föreslagna algoritmen visar sig dessutom de slutliga lägre gränserna vara starkare än de som erhållits genom tidigare metoder.
Under kapacitets- och väglängdsbegränsningar för att lösa multi-depot fordon routing problem C. Contardo, R. Martinelli et al., REF föreslagna variabel fastställande, kolumn-och-cut generation.
A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints
{'venue': 'Discret. Optim.', 'journal': 'Discret. Optim.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}