Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries

References

• Applegate DL, Bixby RE, Chvátal V, Cook WJ (2006) The Traveling Salesman Problem: A Computational Study (Princeton University Press, Princeton, NJ).Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Battarra M, Cordeau J-F, Iori M (2014) Pickup and delivery problems for goods transportation. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (SIAM, Philadelphia), 161–192.Crossref, Google Scholar
• Benders JF (1962) Partitioning procedures for solving mixed variables programming problems. Numer. Math. 4(1):238–252.Crossref, Google Scholar
• Berbeglia G, Cordeau J-F, Gribkovskaia I, Laporte G (2007) Static pickup and delivery problems: A classification scheme and survey. TOP 15(1):1–31.Crossref, Google Scholar
• Bruck BP, dos Santos AG (2012) Hybrid approach for the multiple vehicle routing problem with deliveries and selective pickups. Abraham A, Zomaya A, Wadhai V, Yager R, Muda AK, Koeppen M, eds. Proc. 12th Internat. Conf. Hybrid Intelligent Systems, HIS ’12 (IEEE, Piscataway, NJ), 265–270.Crossref, Google Scholar
• Bruck BP, dos Santos AG, Arroyo JEC (2012) Metaheuristics for the single vehicle routing problem with deliveries and selective pickups. Abraham A, Zomaya A, Ventura S, Yager R, Snásel V, Muda AK, Samuel P, eds. Proc. 12th Internat. Conf. Intelligent Systems Design Appl., ISDA ’12 (IEEE, Piscataway, NJ), 723–728.Google Scholar
• Chemla D, Meunier F, Wolfler Calvo R (2013) Bike sharing systems: Solving the static rebalancing problem. Discrete Optim. 10(2):120–146.Crossref, Google Scholar
• Codato G, Fischetti M (2006) Combinatorial Benders’ cuts for mixed-integer linear programming. Oper. Res. 54(4):756–766.Link, Google Scholar
• Coelho IM, Munhoz PLA, Haddad MN, Souza MJF, Ochi LS (2012) A hybrid heuristic based on general variable neighborhood search for the single vehicle routing problem with deliveries and selective pickups. Electronic Notes Discrete Math. 39:99–106.Crossref, Google Scholar
• Cordeau JF, Dell’Amico M, Falavigna S, Iori M (2015) A rolling horizon algorithm for auto-carrier transportation. Transportation Res. Part B 76(June):68–80.Crossref, Google Scholar
• Côté J-F, Dell’Amico M, Iori M (2014) Combinatorial Benders’ cuts for the strip packing problem. Oper. Res. 62(3):643–661.Link, Google Scholar
• Daniel V, Guide R Jr, Van Wassenhove LN (2009) The evolution of closed-loop supply chain research. Oper. Res. 57(1):10–18.Link, Google Scholar
• Doerner K, Salazar-González J-J (2014) Pickup and delivery routing problems for people transportation. Toth P, Vigo D, eds. Vehicle Routing: Problems, Methods, and Applications, 2nd ed. (SIAM, Philadelphia), 193–212.Crossref, Google Scholar
• Feillet D, Dejax P, Gendreau M (2001) Traveling salesman problems with profits: An overview. Transportation Sci. 39(2):188–205.Link, Google Scholar
• Golden BL, Assad AA (1986) Perspectives on vehicle routing: Exciting new developments. Oper. Res. 34(5):803–810.Link, Google Scholar
• Golden BL, Assad AA, Wasil EA (2002) Routing vehicles in the real world: Applications in the solid waste, beverage, food, dairy, and newspaper industries. Toth P, Vigo D, eds. The Vehicle Routing Problem (SIAM, Philadelphia), 245–286.Crossref, Google Scholar
• Gribkovskaia I, Laporte G (2008) One-to-many-to-one single vehicle pickup and delivery problems. Golden B, Raghavan S, Wasil E, Sharda R, Voss S, eds. The Vehicle Routing Problem: Latest Advances and New Challenges, Vol. 43 (Springer, Berlin), 359–377.Crossref, Google Scholar
• Gribkovskaia I, Laporte G, Shyshou A (2008) The single vehicle routing problem with deliveries and selective pickups. Comput. Oper. Res. 35(9):2908–2924.Crossref, Google Scholar
• Gribkovskaia I, Halskau Ø, Laporte G, Vlcek M (2007) General solutions to the single vehicle routing problem with pickups and deliveries. Eur. J. Oper. Res. 180(2):568–584.Crossref, Google Scholar
• Gutiérrez-Jarpa G, Marianov V, Obreque C (2009) A single vehicle routing problem with fixed delivery and optional collections. IIE Trans. 41(12):1067–1079.Crossref, Google Scholar
• Gutiérrez-Jarpa G, Desaulniers G, Laporte G, Marianov V (2010) A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows. Eur. J. Oper. Res. 206(2):341–349.Crossref, Google Scholar
• Hernández-Pérez H, Salazar-González J-J (2004) A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery. Discrete Appl. Math. 145(1):126–139.Crossref, Google Scholar
• Irnich S, Laganà CD, Schlebusch VF (2015) Two-phase branch-and-cut for the mixed capacitated general routing problem. Eur. J. Oper. Res. 243(1):17–29.Crossref, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Kaparis K, Letchford A (2010) Separation algorithms for 0-1 knapsack polytopes. Math. Programming 124(1–2):69–91.Crossref, Google Scholar
• Laporte G, Martello S (1990) The selective travelling salesman problem. Discrete Appl. Math. 26(2–3):193–207.Crossref, Google Scholar
• Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulations and traveling salesman problems. J. ACM 7(4):326–329.Crossref, Google Scholar
• Nagy G, Salhi S (2005) Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. Eur. J. Oper. Res. 162(1):126–141.Crossref, Google Scholar
• Nowak M, Ergun Ö, White CC (2008) Pickup and delivery with split loads. Transportation Sci. 42(1):32–43.Link, Google Scholar
• Padberg M, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33(1):60–100.Crossref, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9(1):61–100.Crossref, Google Scholar
• Pferschy U, Staněk R (2017) Generating subtour elimination constraints for the TSP from pure integer solutions. Central Eur. J. Oper. Res. 25(1):231–260.Crossref, Google Scholar
• Privé J, Renaud J, Boctor F, Laporte G (2006) Solving a vehicle-routing problem arising in soft-drink distribution. J. Oper. Res. Soc. 57(9):1045–1052.Crossref, Google Scholar
• Righini G, Salani M (2008) New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51(3):155–170.Crossref, Google Scholar
• Salazar-González J-J, Santos-Hernández B (2015) The split-demand one-commodity pickup-and-delivery travelling salesman problem. Transportation Res. Part B 75(May):58–73.Crossref, Google Scholar
• Subramanian A, Uchoa E, Pessoa AA, Ochi LS (2011) Branch-and-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery. Oper. Res. Lett. 39(5):338–341.Crossref, Google Scholar
• Süral H, Bookbinder JH (2003) The single-vehicle routing problem with unrestricted backhauls. Networks 41(3):127–136.Crossref, Google Scholar
• Toth P, Vigo D (2002) An overview of vehicle routing problems. Toth P, Vigo D, eds. The Vehicle Routing Problem (SIAM, Philadelphia), 1–24.Crossref, Google Scholar
• Van Roy TJ, Wolsey LA (1987) Solving mixed integer programming problems using automatic reformulation. Oper. Res. 35(1):45–57.Link, Google Scholar
• Vigo D (1999) VRPLIB: A Vehicle Routing Problem LIBrary. Technical Report OR/99/9, DEIS, University of Bologna, Italy. http://or.dei.unibo.it/library/vrplib-vehicle-routing-problem-library.Google Scholar
• Wolsey LA (1998) Integer Programming, Wiley Series in Discrete Mathematics and Optimization, Vol. 52 (John Wiley & Sons, New York).Google Scholar