×

zbMATH — the first resource for mathematics

The clustered orienteering problem. (English) Zbl 1338.90421
Summary: In this paper we study a generalization of the Orienteering Problem (OP) which we call the Clustered Orienteering Problem (COP). The OP, also known as the Selective Traveling Salesman Problem, is a problem where a set of potential customers is given and a profit is associated with the service of each customer. A single vehicle is available to serve the customers. The objective is to find the vehicle route that maximizes the total collected profit in such a way that the duration of the route does not exceed a given threshold. In the COP, customers are grouped in clusters. A profit is associated with each cluster and is gained only if all customers belonging to the cluster are served. We propose two solution approaches for the COP: an exact and a heuristic one. The exact approach is a branch-and-cut while the heuristic approach is a tabu search. Computational results on a set of randomly generated instances are provided to show the efficiency and effectiveness of both approaches.

MSC:
90C35 Programming involving graphs or networks
90B06 Transportation, logistics and supply chain management
90C10 Integer programming
Software:
Concorde
PDF BibTeX Cite
Full Text: DOI
References:
[1] Archetti, C., Speranza, M. G., & Vigo, D. (2013). Vehicle routing problems with profits, Working paper WPDEM 2013/3. Dipartimento di Economia e Management, Università degli Studi di Brescia.
[2] Chao, I.; Golden, B.; Wasil, E., Theory and methodology - A fast and effective heuristic for the orienteering problem, European Journal of Operational Research, 88, 475-489, (1996) · Zbl 0911.90146
[3] Chekuri, C.; Korula, N.; Pál, M., Improved algorithms for orienteering and related problems, ACM Transactions on Algorithms, 8, 661-670, (2012) · Zbl 1192.90162
[4] Cook, W. (2010). Concorde TSP solver <http://www.tsp.gatech.edu/concorde.html>.
[5] Feillet, D.; Dejax, P.; Gendreau, M., Traveling salesman problems with profits, Transportation Science, 39, 188-205, (2005)
[6] Fischetti, M.; Salazar-González, J. J.; Toth, P., Solving the orienteering problem through branch-and-cut, INFORMS Journal on Computing, 10, 133-148, (1998) · Zbl 1034.90523
[7] Gendreau, M.; Laporte, G.; Semet, F., A tabu search heuristic for the undirected selective travelling salesman problem, European Journal of Operational Research, 106, 539-545, (1998) · Zbl 0991.90103
[8] Gendreau, M.; Laporte, G.; Semet, F., A branch-and-cut algorithm for the undirected selective travelling salesman problem, Networks, 32, 263-273, (1998) · Zbl 1002.90044
[9] Golden, B.; Levy, L.; Vohra, R., The orienteering problem, Naval Research Logistics, 34, 307-318, (1987) · Zbl 0647.90099
[10] Golden, B.; Wang, Q.; Liu, L., A multifaceted heuristic for the orienteering problem, Naval Research Logistics, 35, 359-366, (1988) · Zbl 0649.90089
[11] Keller, C., Algorithms to solve the orienteering problem: A comparison, European Journal of Operational Research, 41, 224-231, (1989) · Zbl 0671.90091
[12] Laporte, G.; Martello, S., The selective travelling salesman problem, Discrete Applied Mathematics, 26, 193-207, (1990) · Zbl 0695.90098
[13] Liang, Y.-C., Kulturel-Konak, S., Smith, A. E. (2002), Meta heuristics for the orienteering problem. In Proceedings of the 2002 congress on evolutionary computation (pp. 384-389).
[14] Lin, S.; Kernighan, B. W., An effective heuristic algorithm for the traveling-salesman problem, Operations Research, 21, 498-516, 197, (1973) · Zbl 0256.90038
[15] Padberg, M.; Rinaldi, G., A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems, SIAM Review, 33, 60-100, (1991) · Zbl 0734.90060
[16] Ramesh, R.; Yoon, Y.; Karwan, M., An optimal algorithm for the orienteering tour problem, ORSA Journal on Computing, 4, 155-165, (1992) · Zbl 0782.90093
[17] Tsiligirides, T., Heuristic methods applied to orienteering, Journal of the Operational Research Society, 35, 797-809, (1984)
[18] Vansteenwegen, P.; Souffriau, W.; Van Oudheusden, D., The orienteering problem: A survey, European Journal of Operational Research, 209, 1-10, (2011) · Zbl 1205.90253
[19] Wang, Q.; Sun, X.; Golden, B.; Jia, J., Using artificial neural networks to solve the orienteering problem, Annals of Operations Research, 61, 111-120, (1995) · Zbl 0839.90041
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.