A survey on pickup and delivery problems
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
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, 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
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
Mosheiov G (1994) The traveling salesman problem with pickup and delivery. Eur J Oper Res 79:299–310
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)
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