×

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.

MSC:

90B06 Transportation, logistics and supply chain management
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Naji-Azimi, Z.; Salari, M., The time constrained maximal covering salesman problem, Appl Math Model, 38, 15, 3945-3957 (2014) · Zbl 1428.90173
[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)
[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)
[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
[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. 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.