×

zbMATH — the first resource for mathematics

Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints. (English) Zbl 1305.90408
Summary: We extend the multiple traveling repairman problem by considering a limitation on the total distance that a vehicle can travel; the resulting problem is called the multiple traveling repairmen problem with distance constraints (MTRPD). In the MTRPD, a fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from and ends at the depot is not allowed to travel a distance longer than a predetermined limit and each customer must be visited exactly once. The objective is to minimize the total waiting time of all customers after the vehicles leave the depot. To optimally solve the MTRPD, we propose a new exact branch-and-price-and-cut algorithm, where the column generation pricing subproblem is a resource-constrained elementary shortest-path problem with cumulative costs. An ad hoc label-setting algorithm armed with bidirectional search strategy is developed to solve the pricing subproblem. Computational results show the effectiveness of the proposed method. The optimal solutions to 179 out of 180 test instances are reported in this paper. Our computational results serve as benchmarks for future researchers on the problem.

MSC:
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C11 Mixed integer programming
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
Software:
TSPLIB
PDF BibTeX Cite
Full Text: DOI
References:
[1] Afrati, F.; Cosmadakis, S.; Papadimitrious, C. H.; Papageorgiou, G.; Papakostantinou, N., The complexity of the travelling repairman problem, Theoretical Informatics and Applications, 20, 79-87, (1986) · Zbl 0585.68057
[2] Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, N.J.: Prentice Hall, pp. 166-249. · Zbl 1201.90001
[3] Aloise, D. J.; Aloise, D.; Rocha, C. T.M.; Ribeiro, C. C.; Ribeiro Filho, J. C.; Moura, L. S.S., Scheduling workover rigs for onshore oil production, Discrete Applied Mathematics, 154, 685-702, (2006) · Zbl 1120.90015
[4] Archer, A.; Levin, A.; Williamson, D. P., A faster, better approximation algorithm for the minimum latency problem, SIAM Journal on Computing, 37, 1472-1498, (2008) · Zbl 1181.68326
[5] Archetti, C.; Bouchard, M.; Desaulniers, G., Enhanced branch and price and cut for vehicle routing with split deliveries and time windows, Transportation Science, 45, 285-298, (2011)
[6] Arora, S.; Karakostas, G., Approximation schemes for minimum latency problems, SIAM Journal on Computing, 32, 1317-1337, (2003) · Zbl 1047.68166
[7] Arora, S.; Karakostas, G., A 2 + ε approximation algorithm for the k-MST problem, Mathematical Programming, Series A, 107, 491-504, (2006) · Zbl 1111.90101
[8] Azi, N.; Gendreau, M.; Potvin, J.-Y., An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, European Journal of Operational Research, 202, 756-763, (2010) · Zbl 1176.90047
[9] Baldacci, R.; Christofides, N.; Mingozzi, A., An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts, Mathematical Programming, Series A, 115, 351-385, (2008) · Zbl 1279.90139
[10] Bektas, T., The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 34, 209-219, (2006)
[11] Bennett, B. T.; Gazis, D. C., School bus routing by computer, Transportation Research/UK/, 6, 317-325, (1972)
[12] Bettinelli, A.; Ceselli, A.; Righini, G., A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows, Transportation Research Part C: Emerging Technologies, 19, 723-740, (2011)
[13] Bianco, L.; Mingozzi, A.; Ricciardelli, S., The traveling salesman problem with cumulative costs, Networks, 23, 81-91, (1993) · Zbl 0821.90121
[14] Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., & Sudan, M. (1994). The minimum latency problem. In Proceedings of the twenty-sixth annual ACM symposium on theory of computing (STOC’94) (pp. 163-171). Montréal, Québec, Canada. · Zbl 1345.90073
[15] Boland, N.; Dethridge, J.; Dumitrescu, I., Accelerated label setting algorithms for the elementary resource constrained shortest path problem, Operations Research Letters, 34, 58-68, (2006) · Zbl 1080.90077
[16] Christofides, N.; Mingozzi, A.; Toth, P., State-space relaxation procedures for the computation of bounds to routing problems, Networks, 11, 145-164, (1981) · Zbl 0458.90071
[17] Contardo, C., Cordeau, J. -F., & Gendron, B. (2011).A branch-and-cut-and-price algorithm for the capacitated location-routing problem. Technical Report, CIRRELT-2011-44, Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation. · Zbl 1356.90070
[18] Desaulniers, G., Branch-and-price-and-cut for the split-delivery vehicle routing problem with time windows, Operations Research, 58, 179-192, (2010) · Zbl 1233.90065
[19] 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 Academic Publishers), 57-93 · Zbl 0966.90007
[20] (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column generation, (2005), Springer) · Zbl 1084.90002
[21] Desaulniers, G.; Lessard, F.; Hadjar, A., Tabu search, partial elementary, and generalized k-path inequalities for the vehicle routing problem with time windows, Transportation Science, 42, 387-404, (2008)
[22] Desrochers, M.; Desrosiers, J.; Solomon, M. M., A new optimization algorithm for the vehicle routing problem with time windows, Operations Research, 40, 342-354, (1992) · Zbl 0749.90025
[23] Erera, A. L.; Morales, J. C.; Savelsbergh, M. W.P., The vehicle routing problem with stochastic demand and duration constraints, Transportation Science, 44, 474-492, (2010)
[24] Fakcharoenphol, J.; Harrelson, C.; Rao, S., The k-traveling repairmen problem, ACM Transactions on Algorithms, 3, (2007) · Zbl 1446.90133
[25] Feillet, D.; Dejax, P.; Gendreau, M.; Gueguen, C., An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems, Networks, 44, 216-229, (2004) · Zbl 1056.90014
[26] Fischetti, M.; Laporte, G.; Martello, S., The delivery man problem and cumulative matroids, Operations Research, 41, 1055-1064, (1993) · Zbl 0791.90062
[27] Fukasawa, R.; Longo, H.; Lysgaard, J.; de Aragão, M. P.; Reis, M.; Uchoa, E., Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Mathematical Programming, Series A, 106, 491-511, (2006) · Zbl 1094.90050
[28] García, A.; Jodrá, P.; Tejel, J., A note on the traveling repairman problem, Networks, 40, 27-31, (2002) · Zbl 1027.90104
[29] (Glover, F.; Laguna, M., Tabu search, (1998), Kluwer Academic Publishers 101 Philip Drive, Assinippi Park, Norwell, Massachusetts 02061, USA) · Zbl 0930.90083
[30] Gutiérrez-Jarpa, G.; Desaulniers, G.; Laporte, G.; Marianov, V., A branch-and-price algorithm for the vehicle routing problem with deliveries, selective pickups and time windows, European Journal of Operational Research, 206, 341-349, (2010) · Zbl 1188.90029
[31] Ioachim, I.; Gélinas, S.; Soumis, F.; Desrosiers, J., A dynamic programming algorithm for the shortest path problem with time windows and linear node costs, Networks, 31, 193-204, (1998) · Zbl 1002.90084
[32] Irnich, S.; Desaulniers, G., Shortest path problems with resource constraints, (Desaulniers, G.; Desrosiers, J.; Solomon, M. M., Column generation, (2005), Springer), 33-65 · Zbl 1130.90315
[33] Jepsen, M.; Petersen, B.; Spoorendonk, S.; Pisinger, D., Subset-row inequalities applied to the vehicle-routing problem with time windows, Operations Research, 56, 497-511, (2008) · Zbl 1167.90413
[34] Kara, I., Kara, B. Y., & Yetiş, M. K. (2008). Cumulative vehicle routing problems. In T. Caric, & H. Gold (Eds.), Vechicle routing problem (pp. 85-98). I-Tech, Vienna Austria.
[35] Kohl, N.; Desrosiers, J.; Madsen, O. B.G.; Solomon, M. M.; Soumis, F., 2-path cuts for the vehicle routing problem with time windows, Transportation Science, 33, 101-116, (1999) · Zbl 1004.90015
[36] Laporte, G.; Nobert, Y.; Desrochers, M., Optimal routing under capacity and distance restrictions, Operations Research, 33, 1050-1073, (1985) · Zbl 0575.90039
[37] Li, C.-L.; Simchi-Levi, D.; Desrochers, M., On the distance constrained vehicle routing problem, Operations Research, 40, 790-799, (1992) · Zbl 0758.90028
[38] Li, L. Y.O.; Fu, Z., The school bus routing problem: A case study, The Journal of the Operational Research Society, 53, 552-558, (2002) · Zbl 1059.90025
[39] Méndez-Díaz, I.; Zabala, P.; Lucena, A., A new formulation for the traveling deliveryman problem, Discrete Applied Mathematics, 156, 3223-3237, (2008) · Zbl 1155.90471
[40] Minieka, E., The delivery man problem on a tree network, Annals of Operations Research, 18, 261-266, (1989) · Zbl 0707.90094
[41] Ngueveu, S. U.; Prins, C.; Wolfler Calvo, R., An effective memetic algorithm for the cumulative capacitated vehicle routing problem, Computers and Operations Research, 37, 1877-1885, (2010) · Zbl 1188.90037
[42] Pacheco, A. V.F.; Ribeiro, G. M.; Mauri, R., A grasp with path-relinking for the workover rig scheduling problem, International Journal of Natural Computing Research, 1, 1-14, (2010)
[43] Park, J.; Kim, B.-I., The school bus routing problem: A review, European Journal of Operational Research, 202, 311-319, (2010) · Zbl 1175.90339
[44] Pessoa, A.; Uchoa, E.; de Aragão, M. P., A robust branch-cut-and-price algorithm for the heterogeneous fleet vehicle routing problem, Networks, 54, 167-177, (2009) · Zbl 1205.90081
[45] Reinelt, G., TSPLIB—traveling salesman problem library, ORSA Journal on Computing, 3, 376-384, (1991) · Zbl 0775.90293
[46] Ribeiro, G. M.; Desaulniers, G.; Desrosiers, J., A branch-price-and-cut algorithm for the workover rig routing problem, Computers and Operations Research, 39, 3305-3315, (2012) · Zbl 1349.90112
[47] Ribeiro, G. M.; Laporte, G., An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem, Computers and Operations Research, 39, 728-735, (2012) · Zbl 1251.90057
[48] Ribeiro, G. M.; Laporte, G.; Mauri, G. R., A comparison of three metaheuristics for the workover rig routing problem, European Journal of Operational Research, 220, 28-36, (2012) · Zbl 1253.90062
[49] Righini, G.; Salani, M., Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints, Discrete Optimization, 3, 255-273, (2006) · Zbl 1149.90167
[50] Righini, G.; Salani, M., New dynamic programming algorithms for the resource constrained elementary shortest path problem, Networks, 51, 155-170, (2008) · Zbl 1144.90514
[51] Ropke, S.; Cordeau, J.-F., Branch and cut and price for the pickup and delivery problem with time windows, Transportation Science, 43, 267-286, (2009)
[52] Salani, M.; Vacca, I., Branch and price for the vehicle routing problem with discrete split deliveries and time windows, European Journal of Operational Research, 213, 470-477, (2011) · Zbl 1218.90045
[53] Salehipour, A.; Sörensen, K.; Goos, P.; Bräysy, O., Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem, 4OR: A Quarterly Journal of Operations Research, 9, 189-209, (2011) · Zbl 1221.90077
[54] Shen, C.; Qin, H.; Lim, A., A capacitated vehicle routing problem with toll-by-weight rule, (Chien, B.-C.; Hong, T.-P., Opportunities and challenges for next-generation applied intelligence, Studies in computational intelligence, Vol. 214, (2009), Springer Berlin, Heidelberg), 311-316
[55] Svestka, J. A.; Huckfeldt, V. E., Computational experience with an m-salesman traveling salesman algorithm, Management Science, 19, 790-799, (1973) · Zbl 0255.90033
[56] (Toth, P.; Vigo, D., The vehicle routing problem, (2002), SIAM Philadelphia, PA) · Zbl 0979.00026
[57] Zhang, J.; Tang, J.; Fung, R. Y.K., A scatter search for multi-depot vehicle routing problem with weight-related cost, Asia-Pacific Journal of Operational Research, 28, 323-348, (2011) · Zbl 1217.90041
[58] Zhang, J.; Tang, J.-F.; Pan, Z.-D.; Yuan, K., Scatter search algorithm for solving weighted vehicle routing problem, Journal of Systems Engineering, 25, 91-97, (2010) · Zbl 1224.90089
[59] Zhang, Z.; Qin, H.; Zhu, W.; Lim, A., The single vehicle routing problem with toll-by-weight scheme: A branch-and-bound approach, European Journal of Operational Research, 220, 295-304, (2012) · Zbl 1253.90161
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.