A survey on pickup and delivery problems

Journal für Betriebswirtschaft - Tập 58 Số 1 - Trang 21-51 - 2008
Sophie N. Parragh1, Karl F. Doerner1, Richard F. Hartl1
1Institut für Betriebswirtschaftslehre, Universität Wien, Wien, Austria

Tóm tắt

Từ khóa


Tài liệu tham khảo

Aarts E, Lenstra J (1997) Local Search in Combinatorial Optimization. Wiley, Chichester

Alshamrani A, Mathur K, Ballou RH (2007) Reverse logistics: Simultaneous design of delivery routes and returns strategies. Comput Oper Res 34:595–619

Angelelli E, Mansini R (2002) The vehicle routing problem with time windows and simultaneous pick-up and delivery. In: Klose A, Speranza MG, VanWassenhove LN (eds) Quantitative Approaches to Distribution Logistics and Supply Chain Management. Springer, Berlin-Heidelberg, pp 249–267

Anily S (1996) The vehicle-routing problem with delivery and back-haul options. Naval Res Logist 43:415–434

Anily S, Mosheiov G (1994) The traveling salesman problem with delivery and backhauls. Oper Res Lett 16:11–18

Archetti C, Hertz A, Speranza MG (2006a) A tabu search algorithm for the split delivery vehicle routing problem. Transport Sci 40:64–73

Archetti C, Savelsbergh M, Speranza MG (2006b) Worst-case analysis for split delivery vehicle routing problems. Transport Sci 40:226–234

Baldacci R, Hadjiconstantinou E, Mingozzi A (2003) An exact algorithm for the traveling salesman problem with deliveries and collections. Networks 42:26–41

Barnhart C, Johnson E, Nemhauser G, Savelsbergh M, Vance P (1998) Branch-and-price: Column generation for solving huge integer programs. Oper Res 46:316–329

Berbeglia G, Cordeau JF, Gribkovskaia I, Laporte G (2007) Static pickup and delivery problems: A classification scheme and survey. TOP 15:1–31

Beullens P (2001) Location, Process Selection, and Vehicle Routing Models for Reverse Logistics. Ph.D. thesis, Centre for Industrial Management, Katholieke Université it Leuven, Belgium, pp 95–125, (Chapter 5)

Beullens P, Van Oudheusden D, VanWassenhove LN (2004) Collection and vehicle routing issues in reverse logistics. In: Dekker R, Fleischmann M, Inderfurth K, Van Wassenhove LN (eds) Reverse Logistics, Quantitative Models for Closed-Loop Supply Chains. Springer, Berlin, pp 95–134

Bianchessi N, Righini G (2007) Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Comput Oper Res 34:578–594

Brandão J (2006) A new tabu search algorithm for the vehicle routing problem with backhauls. Eur J Oper Res 173:540–555

Bräysy O, Gendreau M (2005) Vehicle routing with time windows. Part II: Metaheuristics. Transport Sci 39:119–139

Casco D, Golden B, Wasil E (1988) Vehicle routing with backhauls: Models, algorithms, and case studies. In: Golden B, Assad A (eds) Vehicle Routing: Methods and Studies. North-Holland, Amsterdam, pp 127–147

Chen JF, Wu TH (2006) Vehicle routing problem with simultaneous deliveries and pickups. J Oper Res Soc 57:579–587

Chisman JA (1975) The clustered traveling salesman problem. Comput Oper Res 2:115–119

Christofides N (1975) Worst-case analysis of a new heuristic for the travelling salesman problem. Tech Rep Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University

Christofides N, Eilon S (1969) An algorithm for the vehicle-dispatching problem. Oper Res Quart 20:309–318

Christofides N, Mingozzi A, Toth P (1979) The vehicle routing problem. In: Christofides N, Mingozzi A, Toth P, Sandi C (eds) Combinatorial Optimization. Wiley, Chichester, pp 315–338

Clarke G, Wright JW (1964) Scheduling of vehicles from a central depot to a number of delivery points. Oper Res 12:568–581

Cordeau JF (2006) A branch-and-cut algorithm for the dial-a-ride problem. Oper Res 54:573–586

Cordeau JF, Desaulniers G, Desrosiers J, Solomon MM, Soumis F (2002) VRP with time windows. In: Toth P, Vigo D (eds) The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. vol 9. SIAM, Philadelphia, PA, pp 175–193

Cordeau JF, Gendreau M, Hertz A, Laporte G, Sormany JS (2005) New heuristics for the vehicle routing problem. In: Langevin A, Riopel D (eds) Logistics Systems: Design and Optimization. Springer, New York, pp 279–297

Crispim J, Brandão J (2005) Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls. J Oper Res Soc 56:1296–1302

Crispim J, Brandão J (2001) Reactive tabu search and variable neighbourhood descent applied to the vehicle routing problem with backhauls. In: MIC 2001 4th Metaheuristic International Conference. Porto, Portugal, 16–20 July 2001

Deif I, Bodin LD (1984) Extensions of the Clarke andWright algorithm for solving the vehicle routing problem with backhauling. In: Proceedings of the Babson College Conference of Software Uses in Transportation and Logistics Management. Babson Park, MA. pp 75–96

Dell’Amico M, Righini G, Salani M (2006) A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transport Sci 40:235–247

Derigs U, Metz A (1992) A matching-based approach for solving a delivery/pickup VRP with time constraints. OR-Spektrum 14:91–106

Desaulniers G, Desrosiers J, Ioachim I, Solomon M, Soumis F, Villeneuve D (1998) A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. In: Crainic T, Laporte G (eds) Fleet Management and Logistics. Kluwer Academic Publisher, Boston, Dordrecht, London, pp 57–93

Desaulniers G, Desrosiers J, Solomon M (eds) (2005) Column Generation, No. 5. In: GERAD 25th Anniversary. Springer

Dethloff J (2001) Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up. OR Spektrum 23:79–96

Dethloff J (2002) Relation between vehicle routing problems: An insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls. J Oper Res Soc 53:115–118

Dueck G (1993) New optimization heuristics: The great deluge algorithm and the record-to-record travel. J Comput Phys 104:86–92

Duhamel C, Potvin JY, Rousseau JM (1997) A tabu search heuristic for the vehicle routing problem with backhauls and time windows. Transport Sci 31:49–59

Eurostat (2004) Energy, transport and environment indicators – Data 1991–2001. Luxembourg: Office for Official Publications of the European Communities. Online: http://europa.eu.int/comm/eurostat/

Eurostat (2006) Key figures on Europe – Statistical Pocketbook 2006 – Data 1995–2005. Luxembourg: Office for Official Publications of the European Communities. Online: http://europa.eu.int/comm/eurostat/

Fischetti M, Toth P (1989) An additive bounding procedure for combinatorial optimization problems. Oper Res 37:319–328

Fischetti M, Toth P, Vigo D (1994) A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Oper Res 42:846–859

Fleischmann M, Bloemhof-Ruwaard JM, Dekker R, van der Laan E, van Nunen JAEE, Van Wassenhove LN (1997) Quantitative models for reverse logistics: A review. Eur J Oper Res 103:1–17

Funke B, Grünert T, Irnich S (2005) Local search for vehicle routing and scheduling problems: Review and conceptual integration. J Heuristics 11:267–306

Ganesh K, Narendran TT (2007) CLOVES: A cluster-and-search heuristic to solve the vehicle routing problem with delivery and pick-up. Eur J Oper Res 178:699–717

Garey RM, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. Bell Laboratories, Murray Hill, NJ

Gélinas S, Desrochers M, Desrosiers J, Solomon MM (1995) A new branching strategy for time constrained routing problems with application to backhauling. Ann Oper Res 61:91–109

Gendreau M, Hertz A, Laporte G (1992) New insertion and postoptimization procedures for the traveling salesman problem. Oper Res 40:1086–1094

Gendreau M, Hertz A, Laporte G (1996a) The traveling salesman problem with backhauls. Comput Oper Res 23:501–508

Gendreau M, Hertz A, Laporte G (1997) An approximation algorithm for the traveling salesman problem with backhauls. Oper Res 45:639–641

Gendreau M, Laporte G, Potvin JY (1996b) Heuristics for the clustered traveling salesman problem. Combin Optim 1:41–56

Gendreau M, Laporte G, Vigo D (1999) Heuristics for the traveling salesman problem with pickup and delivery. Comput Oper Res 26:699–714

Ghaziri H, Osman IH (2003) A neural network algorithm for the traveling salesman problem with backhauls. Comput Ind Eng 44:267–281

Ghaziri H, Osman IH (2006) Self-organizing feature maps for the vehicle routing problem with backhauls. J Sched 9:97–114

Gillett BE, Johnson JG (1976) Multi-terminal vehicle dispatch algorithm. Omega 4:639–641

Goetschalckx M, Jacobs-Blecha C (1989) The vehicle routing problem with backhauls. Eur J Oper Res 42:39–51

Goetschalckx M, Jacobs-Blecha C (1993) The vehicle routing problem with backhauls: Properties and solution algorithms. Tech. Rep. MHRC-TR-88-13, Georgia Institute of Technology

Golden B, Baker E, Alfaro J, Schaffer J (1985) The vehicle routing problem with backhauling: Two approaches. In: Hammesfahr RD (ed) Proceedings of the Twenty-First Annual Meeting of S. E. TIMS. Myrtle Beach, SC, pp 90–92

Gribkovskaia I, Halskau Ø, Laporte G, Vlček M (2007) General solutions to the single vehicle routing problem with pickups and deliveries. Eur J Oper Res 180:568–584

Hall RW (1996) Pickup and delivery systems for overnight carriers. Transport Res A-Pol 30:173–187

Halse K (1992) Modeling and solving complex vehicle routing problems. Ph.D. thesis, Institute of Mathematical Statistics and Operations Research (IMSOR), Technical University of Denmark

Halskau Ø, Gribkovskaia I, Myklebost KNB (2001) Models for pick-up and deliveries from depots with lasso solutions. In: Proceedings of the 13th Annual Conference on Logistics Research – NOFOMA 2001 Collaboration in logistics: Connecting Islands using Information Technology, Reykjavik, Iceland, 2001-06-14 – 2001-06-15, Chalmers University of Technology. Göteborg, Sweden, pp 279–293

Hasama T, Kokubugata H, Kawashima H (1998) A heuristic approach based on the string model to solve vehicle routing problem with backhauls. In: Proceedings of the 5th World Congress on Intelligent Transport Systems (ITS). Seoul, 1998

Hoff A, Løkketangen A (2006) Creating lasso-solutions for the traveling salesman problem with pickup and delivery by tabu search. Cent Eur J Oper Res 14:125–140

Hoos H, Stützle T (2005) Stochatic Local Search Foundations and Applications. Morgan Kaufmann Publishers, Elsevier, San Francisco, CA

Irnich S (2000) A multi – depot pickup and delivery problem with a single hub and heterogeneous vehicles. Eur J Oper Res 122:310–328

Jongens K, Volgenant T (1985) The symmetric clustered traveling salesman problem. Eur J Oper Res 19:68–75

Kontoravdis G, Bard JF (1995) A GRASP for the vehicle routing problem with time windows. ORSA J Comput 7:10–23

Kuhn HW (1955) The Hungarian method for the assignment algorithm. Naval Res Logist Q 1:88–97

Laporte G, Potvin JY, Quilleret F (1996) A tabu search heuristic using genetic diversification for the clustered traveling salesman problem. J Heuristics 2:187–200

Lin S (1965) Computer solutions of the traveling salesman problem. AT&T Tech J 44:2245–2269

Lokin FCJ (1978) Procedures for traveling salesman problems with additional constraints. Eur J Oper Res 3:135–141

Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J ACM 7:326–329

Min H (1989) The multiple vehicle routing problem with simultaneous delivery and pickup points. Transport Res A-Pol 23:377–386

Min H, Current J, Schilling D (1992) The multiple depot vehicle routing problem with backhauling. J Bus Log 13:259–288

Mingozzi A, Giorgi S, Baldacci R (1999) An exact method for the vehicle routing problem with backhauls. Transport Sci 33:315–329

Mladenovic N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24:1097–1100

Mosheiov G (1994) The traveling salesman problem with pickup and delivery. Eur J Oper Res 79:299–310

Mosheiov G (1995) The pick-up and delivery location problem on networks. Networks 26:243–251

Mosheiov G (1998) Vehicle routing with pick-up and delivery: Tour-partitioning heuristics. Comput Ind Eng 34:669–684

Nagy G, Salhi S (2005) Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries. Eur J Oper Res 162:126–141

Or I (1976) Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Ph.D. thesis, Northwestern University, Evanston, IL

Osman IH (1993) Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problems. Ann Oper Res 41:421–452

Osman IH, Wassan NA (2002) A reactive tabu search metaheuristic for the vehicle routing problem with backhauls. J Sched 5:263–285

Padberg M, Rinaldi G (1991) A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev 33:60–100

Potvin JY, Duhamel C, Guertin F (1996) A genetic algorithm for vehicle routing with backhauling. Appl Intell 6:345–355

Potvin JY, Guertin F (1996) The clustered traveling salesman problem: A genetic approach. In: Osman IH, Kelly JP (eds) Meta-heuristics theory and applications. Kluwer, Boston, pp 619–631

Potvin JY, Rousseau JM (1995) An exchange heuristic for routeing problems with time windows. J Oper Res Soc 46:1433–1446

Reimann M, Doerner K, Hartl RF (2002) Insertion based ants for vehicle routing problems with backhauls and time windows. In: Dorigo M, Di Caro G, Sampels M (eds) Ant Algorithms: Third InternationalWorkshop, ANTS 2002, Brussels, Belgium, 12–14 September 2002. Springer, Heidelberg-Berlin, pp 135–148

Reimann M, Ulrich H (2006) Comparing backhauling strategies in vehicle routing using ant colony optimization. Cent Eur J Oper Res 14:105–123

Ropke S, Pisinger D (2006) A unified heuristic for a large class of vehicle routing problems with backhauls. Eur J Oper Res 171:750–775

Salani M (2005) Branch-and-price algorithms for Vehicle Routing Problems. Ph.D. thesis, Universitá degli Studi di Milano, Facoltá die Scienze Matematiche, Fisiche e Naturali, Dipartimento di Tecnologie dell’Informatione, Milan, Italy

Salhi S, Nagy G (1999) A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling. J Oper Res Soc 50:1034–1042

Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: Proceedings CP-98 (Fourth International Conference on Principles and Practice of Constraint Programming)

Solomon M (1987) Algorithms for the vehicle routing problem with time windows. Oper Res 35:254–265

Süral H, Bookbinder JH (2003) The single-vehicle routing problem with unrestricted backhauls. Networks 41:127–136

Tang Montané FA, Galvão RD (2006) A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service. Comput Oper Res 33:595–619

Thangiah SR, Potvin JY, Sun T (1996) Heuristic approaches to vehicle routing with backhauls and time windows. Comput Oper Res 23:1043–1057

Toth P, Vigo D (1996) A heuristic algorithm for the vehicle routing problem with backhauls. In: Bianco L, Thot P (eds) Advanced Methods in Transportation Analysis. Springer, Berlin, pp 585–608

Toth P, Vigo D (1997) An exact algorithm for the vehicle routing problem with backhauls. Transport Sci 31:372–385

Toth P, Vigo D (1999) A heuristic algorithm for the symmetric and asymmetric vehicle routing problem with backhauls. Eur J Oper Res 113:528–543

Toth P, Vigo D (2002a) An overview of vehicle routing problems. In: Toth P, Vigo D (eds) The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. vol. 9. SIAM, Philadelphia, pp 1–26

Toth P, Vigo D (2002b) VRP with backhauls. In: Toth P, Vigo D (eds) The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications. vol. 9. SIAM, Philadelphia, PA, pp 195–224

Tzoreff TE, Granot D, Granot F, Sošić G (2002) The vehicle routing problem with pickups and deliveries on some special graphs. Discrete Appl Math 116:193–229

van Breedam A (1995) Vehicle routing: Bridging the gap between theory and practice. JORBEL 35:63–80

van Breedam A (2001) Comparing descent heuristics and metaheuristics for the vehicle routing problem. Comput Oper Res 28:289–315

van Breedam A (2002) A parametric analysis of heuristics for the vehicle routing problem with side-constraints. Eur J Oper Res 137:348–370

Wade A, Salhi S (2004) An ant system algorithm for the mixed vehicle routing problem with backhauls. In: Metaheuristics: computer decision-making. Kluwer Academic Publishers, Norwell, MA, USA, pp 699–719

Wade AC, Salhi S (2002) An investigation into a new class of vehicle routing problem with backhauls. Omega 30:479–487

Yano CA, Chan TJ, Richter LK, Cutler T, Murty KG, McGettigan D (1987) Vehicle routing at quality stores. Interfaces 17:52–63

Zhong Y, Cole MH (2005) A vehicle routing problem with backhauls and time windows: A guided local search solution. Transport Res E-Log 41:131–144