Resource extension functions: properties, inversion, and generalization to segments
Tóm tắt
The unified modeling and solution framework, presented by Desaulniers et al. (Fleet Management and Logistics. Kluwer Academic, Boston, pp 57–93, 1998), is applicable to nearly all types of vehicle-routing and crew-scheduling problems found in the literature thus far. The framework utilizes resource extension functions (REFs) as its main tool for handling complex side constraints that relate to a single vehicle route or crew schedule. The intention of this paper is to clarify which properties of REFs allow important algorithmic procedures, such as efficient representation of (partial) paths, efficient cost computations, and constant time feasibility checking for partial paths (= segments) and their concatenations. The theoretical results provided by the paper are useful for developing highly efficient solution methods for both exact and heuristic approaches. Acceleration techniques for solving resource-constrained shortest-path subproblems are a key success factor for those exact algorithms which are based on column generation or Lagrangean relaxation. Similarly, those heuristic algorithms which are based on resource-constrained paths can benefit from efficient operations needed to construct or manipulate segments. Fast operations are indispensable for efficient local-search algorithms that explore edge-exchange or node-exchange neighborhoods. Efficiency is crucial, since these operations are repeatedly performed in many types of metaheuristics.
Tài liệu tham khảo
Ahn B, Shin J (1991) Vehicle-routeing with time windows and time-varying congestions. J Oper Res Soc 42:393–400
Ahuja R, Magnanti T, Orlin J (1993) Network flows: theory, algorithms, and applications. Prentice Hall, Englewood Cliffs
Avella P, Boccia M, Sforza A (2004) Resource constrained shortest path problems in path planning for fleet management. J Math Model Algorithms 3(1):1–17
Beasley J, Christofides N (1989) An algorithm for the resource constrained shortest path problem. Networks 19:379–394
Borndörfer R, Grötschel M, Löbel A (2001) Scheduling duties by adaptive column generation. Technischer Bericht (ZIB-Report) 01-02, Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB), Berlin
Christiansen M (1996) Inventory and time constrained ship routing—a math approach. Ph.D. dissertation, Norwegian University of Science and Technology, Trondheim, Norway
Christofides N, Eilon S (1969) An algorithm for the vehicle-dispatching problem. Oper Res Q 20(3):309–318
Desaulniers G, Villeneuve D (2000) The shortest path problem with time windows and linear waiting costs. Transport Sci 34(3):312–319
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, Chap. 3. Kluwer Academic, Boston, pp 57–93
Desaulniers G, Desrosiers J, Lasry A, Solomon MM (1999) Crew pairing for a regional carrier. In: Wilson N (eds) Computer-aided transit scheduling, lecture notes in computer science vol. 471. Springer, Berlin, pp 19–41
Desaulniers G, Desrosiers J, Solomon M (eds) (2005) Column generation. Springer, Berlin
Desaulniers G, Lessard F, Hadjar A (2006). Tabu search, generalized k-path inequalities, and partial elementarity for the vehicle routing problem with time windows. Les Cahiers du GERAD G-2006-45, GERAD, École des Hautes Études Commerciales, Montréal, Canada
Desrochers M, Soumis F (1988) A generalized permanent labelling algorithm for the shortest path problem with time windows. Inf Syst Oper Res 26(3):191–212
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
Dumas Y, Soumis F, Desrosiers J (1990) Optimizing the schedule for a fixed vehicle path with convex inconvenience costs. Transport Sci 24(2):145–152
Dumas Y, Desrosiers J, Soumis F (1991) The pick-up and delivery problem with time windows. Eur J Oper Res 54:7–22
Elhallaoui I, Villeneuve D, Soumis F, Desaulniers G (2005) Dynamic aggregation of set-partitioning constraints in column generation. Oper Res 53(4):632–645
Gamache M, Soumis F, Villeneuve D, Desrosiers J, Gélinas E (1998) The preferential bidding systems at Air Canada. Transport Sci 32(3):246–255
Gamache M, Soumis F, Marquis G (1999) A column generation approach for large-scale aircrew rostering problems. Oper Res 47(2):247–263
Gendreau M, Dejax P, Feillet D, Gueguen C (2005) Vehicle routing with time windows and split deliveries. Unpublished technical report, Laboratoire d’Informatique d’Avignon, Avignon, France. (Work in progress).
Gietz M (1994) Computergestützte Tourenplanung mit zeitkritischen Restriktionen. Physica, Heidelberg
Gribkovskaia I, Halskau sr Ø, Laporte G, Vlček M (2006) General solutions to the single vehicle routing problem with pickups and deliveries. Technical report, Molde University College, Molde, Norway
Halse K (1992) Modelling and solving complex vehicle routing problems. Ph.D. dissertation No. 60, IMSOR, Technical University of Denmark, Lyngby, Denmark
Hasle G, Kloster O, Bräysy O, Gendreau M, Kjenstad D, Riise A (2003) A conceptual model for rich VRPs. Presentation at the EURO/INFORMS Joint International Meeting, Istanbul
Helgason R, Kennington J, Stewart B (1993) The one-to-one shortest-path problem: An empirical analysis with the two-tree Dijkstra algorithm. Comput Optim Appl 1:47–75
Hempsch C, Irnich S (2007) Vehicle-routing problems with inter-tour resource constraints. Technical report 2007-01, Deutsche post endowed chair of optimization of distribution networks, RWTH Aachen University, Aachen, Germany. Available at http://www.dpor.rwth-aachen.de
Hill A, Benton W (1992) Modelling intra-city time-dependent travel speeds for vehicle scheduling problems. J Oper Res Soc 43:343–351
Ibaraki T, Imahori S, Kubo M, Masuda T, Uno T, Yagiura M (2005) Effective local search algorithms for routing and scheduling problems with general time-window constraints. Transport Sci 39(2):206–232
Ioachim I, Desrosiers J, Soumis F, Bélanger N (1994) Fleet routing with schedule synchronization. Les Cahiers du GERAD G-94-48, École des HEC, Montréal, Canada, H3T 2A7
Ioachim I, Gélinas S, Desrosiers J, Soumis F (1998). A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks 31:193–204
Irnich S (2006) A unified modeling and solution framework for vehicle routing and local search-based metaheuristics. Technical report 2006-02, Deutsche post endowed chair of optimization of distribution networks, RWTH Aachen University, Aachen, Germany. Available at http://www.dpor.rwth-aachen.de
Irnich S (2007) Speeding up column-generation algorithms by using reduced costs of paths to eliminate arcs. Technical report 2007-02, Deutsche post endowed chair of optimization of distribution networks, RWTH Aachen University, Aachen, Germany. Available at http://www.dpor.rwth-aachen.de
Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. In: Desaulniers et al. (eds) Column generation, Chap. 2. Springer, Berlin, pp 33–65
Irnich S, Funke B, Grünert T (2006) Sequential search and its application to vehicle-routing problems. Comput Oper Res 33(8):2405–2429
Jepsen M, Spoorendonk S, Petersen B, Pisinger D (2006) A non-robust branch-and-cut-and-price algorithm for the vehicle routing problem with time windows. DIKU Technical Report no. 06/03, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark
Malandraki C, Daskin M (1992) Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. Transport Sci 26(3):185–200
Min H (1989) The multiple vehicle routing problem with simultaneous delivery and pick-up points. Trans Res 23:377–386
Salani M (2005) Branch-and-price algorithms for vehicle routing problems. Ph.D. dissertation, Università degli Studi di Milano, Facoltà die Scienze Matematiche, Fisiche e Naturali, Dipartimento di Tecnologie dell’Informatione, Milan, Italy
Sexton T, Bodin L (1985a) Optimizing single vehicle many-to-many operations with desired delivery times: I. Scheduling. Transport Sci 19(4):378–410
Sexton T, Bodin L (1985b) Optimizing single vehicle many-to-many operations with desired delivery times: II. Routing. Transport Sci 19(4):411–435
Sexton T, Choi Y (1986). Pickup and delivery of partial loads with “soft” time windows. Am J Math Manage Sci 6(3,4):369–398
Solomon M (1987) Algorithms for the vehicle routing and scheduling problem with time window constraints. Oper Res 35(2):254–265
Taillard D, Laporte G, Gendreau M (1996) Vehicle routeing with multiple use of vehicles. J Oper Res Soc 47(8):1065–1070
Vance P, Barnhart C, Johnson E, Nemhauser G (1997) Airline crew scheduling: A new formulation and decomposition algorithm. Oper Res 45(2):188–200