Abstrakt. De bästa exakta algoritmerna för kapaciated vehicle Routing Problem (CVRP) har baserats på antingen gren-och-cut eller Lagrangean avkoppling/kolumn generation. Detta dokument presenterar en algoritm som kombinerar båda tillvägagångssätt: det fungerar över skärningspunkten mellan två polytoper, en associerad med en traditionell Lagrangean avkoppling över q-rutter, den andra definieras av bundna, grad och kapacitet begränsningar. Detta motsvarar ett linjärt program med exponentiellt många variabler och begränsningar som kan leda till lägre gränser som är överlägsna dem som ges av tidigare metoder. Den resulterande gren-andcut-and-price algoritmen kan lösa till optimalitet alla instanser från litteraturen med upp till 135 hörn. Detta fördubblar storleken på de fall som kan lösas konsekvent.
Den algoritm som föreslås i REF är mycket konsekvent när det gäller att lösa fall från litteraturen med upp till 135 kunder.
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem
{'venue': 'Math. Program.', 'journal': None, 'mag_field_of_study': ['Computer Science']}