×

The multi-vehicle cumulative covering tour problem. (English) Zbl 1381.90019

Summary: This paper introduces the multi-vehicle cumulative covering tour problem whose motivation arises from humanitarian logistics. The objective is to determine a set of tours that must be followed by a fleet of vehicles in order to minimize the sum of arrival times (latency) at each visited location. There are three types of locations: mandatory, optional, and unreachable. Each mandatory location must be visited, and optional locations are visited in order to cover the unreachable locations. To guarantee the vehicle autonomy, the duration of each tour should not exceed a given time limit. A mixed integer linear formulation and a greedy randomized adaptive search procedure are proposed for this problem. The performance of the algorithm is assessed over a large set of instances adapted from the literature. Computational results confirm the efficiency of the proposed algorithm.

MSC:

90B06 Transportation, logistics and supply chain management
90C05 Linear programming
90C11 Mixed integer programming

Software:

GRASP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altay, N., & Green, W, I. I. I. (2006). OR/MS research in disaster operations management. European Journal of Operational Research, 175(1), 475-493. · Zbl 1137.90574 · doi:10.1016/j.ejor.2005.05.016
[2] Anaya-Arenas, A., Renaud, J., & Ruiz, A. (2014). Relief distribution networks: A systematic review. Annals of Operations Research, 223(1), 53-79. · Zbl 1306.90021 · doi:10.1007/s10479-014-1581-y
[3] Archer, A., & Blasiak, A. (2010). Improved approximation algorithms for the minimum latency problem via prize-collecting strolls. In Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms (SODA), Philadelphia, USA, pp. 429-447. · Zbl 1288.68100
[4] 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), Montreal, Canada, pp. 163-171. · Zbl 1345.90073
[5] Campbell, A. M., Vandenbussche, D., & Hermann, W. (2008). Routing for relief efforts. Transportation Science, 42(2), 127-145. · doi:10.1287/trsc.1070.0209
[6] Chen, P., Dong, X., & Niu, Y. (2012). An iterated local search algorithm for the cumulative capacitated vehicle routing problem. Technology for Education and Learning, Advances in Intelligent Systems and Computing, 136, 575-581. · doi:10.1007/978-3-642-27711-5_76
[7] Davoudpour, H., & Ashrafi, M. (2009). Solving multi-objective SDST flexible flow shop using GRASP algorithm. The International Journal of Advanced Manufacturing Technology, 44(7-8), 737-747. · doi:10.1007/s00170-008-1887-5
[8] De La Torre, L. E., Dolinskaya, I. S., & Smilowitz, K. R. (2012). Disaster relief routing: Integrating research and practice. Socio-Economic Planning Sciences, Special Issue: Disaster Planning and Logistics: Part 1, 46(1), 88-97. · doi:10.1016/j.seps.2011.06.001
[9] Ezzine, I. O., & Elloumi, S. (2012). Polynomial formulation and heuristic based approach for the \[k\] k-travelling repairman problem. International Journal of Mathematics in Operational Research, 4(5), 503-514. · Zbl 1390.90580 · doi:10.1504/IJMOR.2012.048928
[10] Fakcharoenphol, J., Harrelson, C., & Rao, S. (2007). The \[k\] k-traveling repairmen problem. ACM Transactions on Algorithms, 3(4), 40:1-40:16. · Zbl 1446.90133 · doi:10.1145/1290672.1290677
[11] Festa, P., & Resende, M. G. C. (2009). An annotated bibliography of GRASP—Part II: Applications. International Transactions in Operational Research, 16(2), 131-172. · Zbl 1168.90582 · doi:10.1111/j.1475-3995.2009.00664.x
[12] Galindo, G., & Batta, R. (2013). Review of recent developments in OR/MS research in disaster operations management. European Journal of Operational Research, 230(2), 201-211. · doi:10.1016/j.ejor.2013.01.039
[13] Gendreau, M., Laporte, G., & Semet, F. (1997). The covering tour problem. Operations Research, 45(4), 568-576. · Zbl 0887.90122 · doi:10.1287/opre.45.4.568
[14] Há, M. H., Bostel, N., Langevin, A., & Rousseau, L. M. (2013). An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices. European Journal of Operational Research, 226(2), 211-220. · Zbl 1292.90050 · doi:10.1016/j.ejor.2012.11.012
[15] Hachicha, M., Hodgson, M. J., Laporte, G., & Semet, F. (2000). Heuristics for the multi-vehicle covering tour problem. Computers & Operations Research, 27(1), 29-42. · Zbl 0973.90019 · doi:10.1016/S0305-0548(99)00006-4
[16] Hmayer, A., & Ezzine, I. (2013). CLARANS heuristic based approch for the \[k\] k-traveling repairman problem. In International conference on advanced logistics and transport (ICALT), Sousse, Tunisie, pp. 535-538.
[17] Hodgson, M. J., Laporte, G., & Semet, F. (1998). A covering tour model for planning mobile health care facilities in Suhum District, Ghana. Journal of Regional Science, 38(4), 621-638. · doi:10.1111/0022-4146.00113
[18] Jozefowiez, N. (2011). A column generation approach for the multi-vehicle covering tour problem. In ROADEF 2011, March 2-4, Saint-Etienne, France. · Zbl 1304.90004
[19] Jozefowiez, N. (2014). A branch-and-price algorithm for the multivehicle covering tour problem. Networks, 64(3), 160-168. · doi:10.1002/net.21564
[20] Kammoun, M., Derbel, H., Ratli, M., & Jarboui, B. (2015). A variable neighborhood search for solving the multi-vehicle covering tour problem. Electronic Notes in Discrete Mathematics, 47, 285-292. · Zbl 1362.90090 · doi:10.1016/j.endm.2014.11.037
[21] Ke, L., & Feng, Z. (2013). A two-phase metaheuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research, 40(2), 633-638. · Zbl 1349.90859 · doi:10.1016/j.cor.2012.08.020
[22] Lopes, R., Souza, V. A., & da Cunha, A. S. (2013). A branch-and-price algorithm for the multi-vehicle covering tour problem. Electronic Notes in Discrete Mathematics, 44, 61-66. · doi:10.1016/j.endm.2013.10.010
[23] Luo, Z., Qin, H., & Lim, A. (2014). Branch-and-price-and-cut for the multiple traveling repairman problem with distance constraints. European Journal of Operational Research, 234(1), 49-60. · Zbl 1305.90408 · doi:10.1016/j.ejor.2013.09.014
[24] Lysgaard, J., & Wøhlk, S. (2014). A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. European Journal of Operational Research, 236(3), 800-810. · Zbl 1304.90038 · doi:10.1016/j.ejor.2013.08.032
[25] Murakami, K. (2014). A column generation approach for the multi-vehicle covering tour problem. In IEEE international conference on automation science and engineering (CASE), New Taipei, Taiwan, pp. 1063-1068).
[26] Naji-Azimi, Z., Renaud, J., Ruiz, A., & Salari, M. (2012). A covering tour approach to the location of satellite distribution centers to supply humanitarian aid. European Journal of Operational Research, 222(3), 596-605. · doi:10.1016/j.ejor.2012.05.001
[27] Ngueveu, S. U., Prins, C., & Wolfler Calvo, R. (2010). An effective memetic algorithm for the cumulative capacitated vehicle routing problem. Computers & Operations Research, 37(11), 1877-1885. · Zbl 1188.90037 · doi:10.1016/j.cor.2009.06.014
[28] Oliveira, W. A., Mello, M. P., Moretti, A. C., & Reis, E. F. (2013). The multi-vehicle covering tour problem: Building routes for urban patrolling. arXiv:1309.5502.
[29] Ozsoydan, F. B., & Sipahioglu, A. (2013). Heuristic solution approaches for the cumulative capacitated vehicle routing problem. Optimization, 62(10), 1321-1340. · Zbl 1360.90036 · doi:10.1080/02331934.2013.841158
[30] Ribeiro, G. M., & Laporte, G. (2012). An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research, 39(3), 728-735. · Zbl 1251.90057 · doi:10.1016/j.cor.2011.05.005
[31] Sahni, S., & Gonzales, T. (1974). P-complete problems and approximate solutions. In IEEE conference record of 15th annual symposium on switching and automata theory, New York, USA, pp. 28-32. · Zbl 1137.90574
[32] Salazar-Aguilar, M. A., Ríos-Mercado, R. Z., & González-Velarde, J. L. (2013). GRASP strategies for a bi-objective commercial territory design problem. Journal of Heuristics, 19(2), 179-200. · doi:10.1007/s10732-011-9160-8
[33] Sitters, R. (2014). Polynomial time approximation schemes for the traveling repairman and other minimum latency problems, Portland, USA, pp. 604-616. doi:10.1137/1.9781611973402.46. · Zbl 1422.68314
[34] Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3), 658-673. · Zbl 1304.90004 · doi:10.1016/j.ejor.2013.09.045
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.