Solving shortest path problems with a weight constraint and replenishment arcs. (English) Zbl 1251.90072
Summary: This paper tackles a generalization of the weight constrained shortest path problem (WCSPP) in a directed network with replenishment arcs that reset the accumulated weight along the path to zero. Such situations arise, for example, in airline crew pairing applications, where the weight represents duty hours, and replenishment arcs represent crew overnight rests; and also in aircraft routing, where the weight represents time elapsed, or flight time, and replenishment arcs represent maintenance events. In this paper, we review the weight constrained shortest path problem with replenishment (WCSPP-R), develop preprocessing methods, extend existing WCSPP algorithms, and present new algorithms that exploit the inter-replenishment path structure. We present the results of computational experiments investigating the benefits of preprocessing and comparing several variants of each algorithm, on both randomly generated data, and data derived from airline crew scheduling applications.
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C35 | Programming involving graphs or networks |
| 05C38 | Paths and cycles |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
References:
| [1] | Barnhart, C.; Boland, N. L.; Clarke, L. W.; Johnson, E. L.; Nemhauser, G. L.; Shenoi, R. G., Flight string models for aircraft fleeting and routing, Transportation Science, 32, 3, 208-220 (1998) · Zbl 0987.90504 |
| [2] | Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Vance, P., Crew scheduling, (Handbook of transportation science (1999), Kluwer Academic Publishers), 493-521, [chapter 14] |
| [3] | Bhattacharya, B.; Hu, Y.; Kononov, A., Approximation algorithms for the black and white traveling salesman problem, (Lin, G., Computing and combinatorics—COCOON 2007, Proceedings of the 13th annual international conference on computing and combinatorics, Banff, Canada. Lecture notes in computer science, vol. 4598 (2007)), 559-567 · Zbl 1213.90206 |
| [4] | Boland, N.; Dethridge, J.; Dumitrescu, I., Accelerated label setting algorithms for the elementary resource constrained shortest path problem, Operations Research Letters, 34, 1, 58-68 (2006) · Zbl 1080.90077 |
| [5] | Boland, N. L.; Clarke, L. W.; Nemhauser, G. L., The asymmetric traveling salesman problem with replenishment arcs, European Journal of Operational Research, 123, 2, 408-427 (2000) · Zbl 1054.90058 |
| [6] | Bourgeois, M.; Laporte, G.; Semet, F., Heuristics for the black and white traveling salesman problem, Computers & Operations Research, 30, 1, 75-85 (2003) · Zbl 1029.90061 |
| [7] | Cabral, E. A.; Erkut, E.; Laporte, G.; Patterson, R. A., Wide area telecommunication network design: application to the Alberta SuperNet, Journal of the Operational Research Society, 59, 11, 1460-1470 (2008) · Zbl 1168.90652 |
| [8] | Cabral, E. A.; Erkut, E.; Laporte, G.; Patterson, R. A., The network design problem with relays, European Journal of Operational Research, 180, 2, 834-844 (2007) · Zbl 1125.90010 |
| [9] | Carlyle, W. M.; Royset, J. O.; Wood, R. K., Lagrangian relaxation and enumeration for solving constrained shortest-path problems, Networks, 52, 4, 256-270 (2008) · Zbl 1180.90346 |
| [10] | Cohn, A. M.; Barnhart, C., Improving crew scheduling by incorporating key maintenance routing decisions, Operations Research, 51, 3, 387-396 (2003) · Zbl 1163.90485 |
| [11] | Cordeau, J. F.; Stojkovic, G.; Soumis, F.; Desrosiers, J., Benders decomposition for simultaneous aircraft routing and crew scheduling, Transportation Science, 35, 4, 375-388 (2001) · Zbl 1069.90525 |
| [12] | Day, P. R.; Ryan, D. M., Flight attendant rostering for short-haul airline operations, Operations Research, 45, 5, 649-661 (1997) · Zbl 0902.90115 |
| [13] | Desaulniers, G.; Desrosiers, J.; Dumas, Y.; Marc, S.; Rioux, B.; Solomon, M. M., Crew pairing at Air France, European Journal of Operational Research, 97, 2, 245-259 (1997) · Zbl 0944.90040 |
| [14] | Desaulniers, G.; Desrosiers, J.; Ioachim, I.; Solomon, M. M.; Soumis, F.; Villeneuve, D., A unified framework for deterministic time constrained vehicle routing and crew scheduling problems, (Crainic, T. G.; Laporte, G., Fleet management and logistics (1998), Kluwer: Kluwer Boston), 57-93 · Zbl 0966.90007 |
| [15] | Desrochers, M.; Soumis, F., A generalized permanent labeling algorithm for the shortest-path problem with time windows, INFOR, 26, 3, 191-212 (1988) · Zbl 0652.90097 |
| [16] | Desrosiers, J.; Dumas, Y.; Solomon, M.; Soumis, F., Time constrained routing and scheduling, (Handbook in operations research and management science. Network routing (1995), Springer), 35-139, [chapter 8] · Zbl 0861.90052 |
| [17] | Dumitrescu, I.; Boland, N., Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem, Networks, 42, 3, 135-153 (2003) · Zbl 1031.68144 |
| [18] | Cabral EA. Wide area telecommunication network design: problems and solution algorithms with application to the Alberta SuperNet. PhD thesis, University of Alberta, Canada; 2005.; Cabral EA. Wide area telecommunication network design: problems and solution algorithms with application to the Alberta SuperNet. PhD thesis, University of Alberta, Canada; 2005. |
| [19] | Fahle, T.; Junker, U.; Karisch, S. E.; Kohl, N.; Sellmann, M.; Vaaben, B., Constraint programming based column generation for crew assignment, Journal of Heuristics, 8, 1, 59-81 (2002), First workshop on integration of AI and OR techniques in constraint programming for combinatorial optimization problems (CP-AI-OR 1999), Ferrara, Italy; February 1999 · Zbl 1073.90542 |
| [20] | Falkner, J. C.; Ryan, D. M., Express—set paritioning for bus crew scheduling in christchurch, (Desrochers, M.; Rousseau, J. M., Computer-aided transit scheduling. Lecture notes in economics and mathematical systems, vol. 386 (1992), Natl. Sci. Eng. Res. Council, Springer-Verlag: Natl. Sci. Eng. Res. Council, Springer-Verlag Canada, Berlin), 359-378, 5th international workshop on computer-aided scheduling of public transport, Montreal, Canada |
| [21] | Garey, M. R.; Johnson, D. S., Computers and intractability. A guide to the theory of NP-completeness (1979), Freeman: Freeman Oxford, UK · Zbl 0411.68039 |
| [22] | Ghiani, G.; Laporte, G.; Semet, F., The black and white traveling salesman problem, Operations Research, 54, 2, 366-378 (2006) · Zbl 1167.90666 |
| [23] | Hart, P. E.; Nilsson, N. J.; Raphael, B., A formal basis for heuristic determination of minimum cost paths, IEEE Transactions on Systems, Science and Cybernetics, SSC4, 2, 100-107 (1968) |
| [24] | Irnich, S., Resource extension functions: properties, inversion, and generalization to segments, OR Spectrum, 30, 1, 113-148 (2008) · Zbl 1133.90309 |
| [25] | Irnich, S.; Desaulniers, G., Shortest path problems with resource constraints, (Column generation (2005), Springer), 33-66, [chapter 2] · Zbl 1130.90315 |
| [26] | Jiang, H.; Zhang, X.; Li, M.; Che, H., Using Gavish-Grave LP to formulate the directed black and white traveling salesman problem, (Shi, Y.; Dongarra, J.; Sloot, P. M.A., Computational Science—ICCS 2007, Pt 3, Proceedings of the 7th international conference on computational science, Beijing, China, May 27-30, 2007. Lecture notes in computer science, vol. 4489 (2007)) |
| [27] | Klabjan, D.; Johnson, E. L.; Nemhauser, G. L.; Gelman, E.; Ramaswamy, S., Airline crew scheduling with time windows and plane-count constraints, Transportation Science, 36, 3, 337-348 (2002) · Zbl 1134.90386 |
| [28] | Laporte, G.; Pascoal, M. M.B., Minimum cost path problems with relays, Computers & Operations Research, 38, 1, Sp. Iss. SI, 165-173 (2011), 11th international workshop on project managment and scheduling, Istanbul, Turkey · Zbl 1231.90108 |
| [29] | Mak, V.; Boland, N., Heuristic approaches to the asymmetric travelling salesman problem with replenishment arcs, International Transactions in Operational Research, 7, 4, 431 (2000) |
| [30] | Mak, V.; Boland, N., Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs, Discrete Optimization, 3, 1, 33-49 (2006) · Zbl 1109.90067 |
| [31] | Mak, V.; Boland, N., Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs, Discrete Applied Mathematics, 155, 16, 2093-2110 (2007) · Zbl 1144.90469 |
| [32] | Mercier, A.; Cordeau, J. F.; Soumis, F., A computational study of Benders decomposition for the integrated aircraft routing and crew scheduling problem, Computers and Operations Research, 32, 6, 1451-1476 (2005) · Zbl 1122.90355 |
| [33] | Mercier, A.; Soumis, F., An integrated aircraft routing, crew scheduling and flight retiming model, Computers and Operations Research, 34, 8, 2251-2265 (2007) · Zbl 1144.90390 |
| [34] | Muhandiramge, R.; Boland, N., Simultaneous solution of Lagrangean dual problems interleaved with preprocessing for the weight constrained shortest path problem, Networks, 53, 4, 358-381 (2009) · Zbl 1207.05201 |
| [35] | Sellmann, M.; Zervoudakis, K.; Stamatopoulos, P.; Fahle, T., Crew assignment via constraint programming: integrating column generation and heuristic tree search, Annals of Operations Research, 115, 1-4, 207-225 (2002), 2nd international workshop on the integration of AI and OR techniques on constant programming for combinatorial optimization problems, PADERBORA, Germany; March 2000 · Zbl 1013.90091 |
| [36] | Vance, P. H.; Barnhart, C.; Johnson, E. L.; Nemhauser, G. L., Airline crew scheduling: a new formulation and decomposition algorithm, Operations Research, 45, 2, 188-200 (1997) · Zbl 0891.90087 |
| [37] | Yan, S.; Tung, T. T.; Tu, Y. P., Optimal construction of airline individual crew pairings, Computers & Operations Research, 29, 4, 341-363 (2002) · Zbl 1048.90130 |
| [38] | Zhu Z. The aircraft rotation problem. PhD thesis, Georgia Institute of Technology; 1994.; Zhu Z. The aircraft rotation problem. PhD thesis, Georgia Institute of Technology; 1994. |
| [39] | Ziarati, K.; Soumis, F.; Desrosiers, J.; Gelinas, S.; Saintonge, A., Locomotive assignment with heterogeneous consists at CN North America, European Journal of Operational Research, 97, 2, 281-292 (1997) · Zbl 0930.90068 |
| [40] | Ziegelmann, M., Constrained shortest paths and related problems: constrained network optimization (2007), VDM-Verlag |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
