Abstract
We address a special TSP in which the set of cities is partitioned into two subsets: mandatory cities and selective cities. All mandatory cities should be visited once within one of the corresponding predefined multiple time windows. A subset of the selective cities, whose cardinality depends on the tour completion time, should be visited within one of the associated multiple time windows. The objective is to plan a tour, not exceeding a predefined number of days, that minimizes a linear combination of the total traveled distance as well as the total waiting time. We present a mixed integer linear programming (MILP) model for the problem and propose a heuristic approach to solve it. Computational experiments address two real world problems that arise in different practical contexts.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Fischetti, M., Salazar-González, J.-J., Toth, P.: The generalized traveling salesman and orienteering problems. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and its Variants, pp. 609–662. Kluwer (2002)
Gendreau, M., Laporte, G., Semet, F.: A branch-and-cut algorithm for the undirected selective traveling salesman problem. Networks 32(4), 263–273 (1998)
Kaufman, L., Rousseeuw, P.J.: Finding groups in data: an introduction to cluster analysis. Wiley, New York (1990)
Labadie, N., Mansini, R., Melechovsky, J., Calvo, R.W.: The team orienteering problem with time windows: An LP-based granular variable neighborhood search. European Journal of Operational Research 220, 15–27 (2012)
Pisinger, D., Ropke, S.: A general heuristic for vehicle routing problems. Computers & Operations Research 34, 2403–2435 (2007)
Ropke, S., Pisinger, D.: An adaptative large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science 40(4), 455–472 (2006)
Tricoire, F., Romauch, M., Doerner, K.F., Hartl, R.F.: Heuristics for the multi-period orienteering problem with multiple time windows. Computers & Operations Research 37, 351–367 (2010)
Vansteenwegen, P., Souffriau, W., Berghe, G.V., Oudheusden, D.V.: Iterated local search for the team orienteering problem with time windows. Computers & Operations Research 36, 3281–3290 (2009)
Vansteenwegen, P., Souffriau, W., Oudheusden, D.V.: The orienteering problem: A survey. European Journal of Operational Research 209, 1–10 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mesquita, M., Murta, A., Paias, A., Wise, L. (2013). TSP with Multiple Time-Windows and Selective Cities. In: Pacino, D., Voß, S., Jensen, R.M. (eds) Computational Logistics. ICCL 2013. Lecture Notes in Computer Science, vol 8197. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41019-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-41019-2_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41018-5
Online ISBN: 978-3-642-41019-2
eBook Packages: Computer ScienceComputer Science (R0)