zbMATH — the first resource for mathematics

Time constrained maximal covering salesman problem with weighted demands and partial coverage. (English) Zbl 1349.90117
Summary: In a routing framework, it may not be viable to visit every single customer separately due to resource limitations or efficiency concerns. In such cases, utilizing the notion of coverage; i.e., satisfying the demand of multiple customers by visiting a single customer location, may be advantageous. With this motivation, we study the time constrained maximal covering salesman problem (TCMCSP) in which the aim is to find a tour visiting a subset of customers so that the amount of demand covered within a limited time is maximized. We provide flow and cut formulations and derive valid inequalities. Since the connectivity constraints and the proposed valid inequalities are exponential in the size of the problem, we devise different branch-and-cut schemes. Computational experiments performed on a set of problem instances demonstrate the effectiveness of the proposed valid inequalities in terms of strengthening the linear relaxation bounds as well as speeding up the solution procedure. Moreover, the results indicate the superiority of using a branch-and-cut methodology over a flow-based formulation. Finally, we discuss the relation between the problem parameters and the structure of optimal solutions based on the results of our experiments.

90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI
[1] Naji-Azimi, Z.; Salari, M., The time constrained maximal covering salesman problem, Appl Math Model, 38, 15, 3945-3957, (2014)
[2] Current, J. R.; Schilling, D. A., The covering salesman problem, Transp Sci, 23, 3, 208-213, (1989) · Zbl 0682.90092
[3] Arkin, E. M.; Hassin, R., Approximation algorithms for the geometric covering salesman problem, Discret Appl Math, 55, 3, 197-218, (1994) · Zbl 0819.90115
[4] Current, J. R.; Schilling, D. A., The Median tour and maximal covering tour problemsformulations and heuristics, Eur J Oper Res, 73, 1, 114-126, (1994) · Zbl 0806.90036
[5] Golden, B. L.; Naji-Azimi, Z.; Raghavan, S.; Salari, M.; Toth, P., The generalized covering salesman problem, INFORMS J Comput, 24, 4, 534-553, (2012) · Zbl 1462.90106
[6] Salari, M.; Reihaneh, M.; Sabbagh, M. S., Combining ant colony optimization algorithm and dynamic programming technique for solving the covering salesman problem, Comput Ind Eng, 83, 244-251, (2015)
[7] Shaelaie, M. H.; Salari, M.; Naji-Azimi, Z., The generalized covering traveling salesman problem, Appl Soft Comput, 24, 867-878, (2014)
[8] Gendreau, M.; Laporte, G.; Semet, F., The covering tour problem, Oper Res, 45, 4, 568-576, (1997) · Zbl 0887.90122
[9] Hodgson, M. J.; Laporte, G.; Semet, F., A covering tour model for planning mobile health care facilities in suhum district, ghana, J Reg Sci, 38, 4, 621-638, (1998)
[10] Motta L, Ochi LS, Martinhon C. Grasp metaheuristics for the generalized covering tour problem. In: MIC2001-4th metaheuristics international conference. Porto, Portugal: Citeseer; 2001. · Zbl 1208.90177
[11] Baldacci R, Boschetti MA, Maniezzo V, Zamboni M. Scatter search methods for the covering tour problem. In: Metaheuristic optimization via memory and evolution. New York: Springer; 2005. p. 59-91. · Zbl 1072.90053
[12] Kubik P. Heuristic solution approaches for the covering tour problem [Ph.D. thesis]. Universität Wien; 2007.
[13] Hachicha, M.; Hodgson, M. J.; Laporte, G.; Semet, F., Heuristics for the multi-vehicle covering tour problem, Comput Oper Res, 27, 1, 29-42, (2000) · Zbl 0973.90019
[14] Naji-Azimi, Z.; Renaud, J.; Ruiz, A.; Salari, M., A covering tour approach to the location of satellite distribution centers to supply Humanitarian aid, Eur J Oper Res, 222, 3, 596-605, (2012)
[15] Oliveira WA, Mello MP, Moretti AC, Reis EF. The multi-vehicle covering tour problem: building routes for urban patrolling. arXiv:1309.5502.
[16] Jozefowiez, N.; Semet, F.; Talbi, E. G., The bi-objective covering tour problem, Comput Oper Res, 34, 7, 1929-1942, (2007) · Zbl 1190.90044
[17] Nolz PC, Doerner KF, Gutjahr WJ, Hartl RF. A bi-objective metaheuristic for disaster relief operation planning. In: Advances in multi-objective nature inspired computing. Berlin: Springer; 2010. p. 167-87.
[18] Tricoire, F.; Graf, A.; Gutjahr, W. J., The bi-objective stochastic covering tour problem, Comput Oper Res, 39, 7, 1582-1592, (2012) · Zbl 1251.90361
[19] Feillet, D.; Dejax, P.; Gendreau, M., Traveling salesman problems with profits, Transp Sci, 39, 2, 188-205, (2005)
[20] Golden, B. L.; Levy, L.; Vohra, R., The orienteering problem, Nav Res Logist, 34, 3, 307-318, (1987) · Zbl 0647.90099
[21] Laporte, G.; Martello, S., The selective travelling salesman problem, Discret Appl Math, 26, 2-3, 193-207, (1990) · Zbl 0695.90098
[22] Kataoka, S.; Morito, S., An algorithm for single constraint maximum collection problem, J Oper Res Soc Jpn, 31, 4, 515-530, (1988) · Zbl 0665.90092
[23] Vansteenwegen, P.; Souffriau, W.; Van Oudheusden, D., The orienteering problema survey, Eur J Oper Res, 209, 1, 1-10, (2011) · Zbl 1205.90253
[24] Fouilhoux, P.; Karasan, O. E.; Mahjoub, A. R.; Özkök, O.; Yaman, H., Survivability in hierarchical telecommunications networks, Networks, 59, 1, 37-58, (2012) · Zbl 1241.90023
[25] Stoer, M.; Wagner, F., A simple MIN-cut algorithm, J Assoc Comput Mach, 44, 4, 585-591, (1997) · Zbl 0891.68071
[26] Edmonds, J.; Karp, R. M., Theoretical improvements in algorithmic efficiency for network flow problems, J Assoc Comput Mach, 19, 2, 248-264, (1972) · Zbl 0318.90024
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.