Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Evolution-inspired local improvement algorithm solving orienteering problem

  • Original Paper
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The orienteering problem (OP) is defined on a graph with scores assigned to the vertices and weights attached to the links. The objective of solutions to the OP is to find a route over a subset of vertices, limited in length, that maximizes the collective score of the vertices visited. In this paper we present a new, efficient method for solving the OP, called the evolution-inspired local improvement algorithm (EILIA). First, a multi-stage, hill climbing-based method is used to improve an initial random population of routes. During the evolutionary phase, both feasible and infeasible (routes that are too long) parts of the solution space are explored and exploited by the algorithm operators. Finally, infeasible routes are repaired by a repairing method. Computer testing of EILIA is conducted on popular data sets, as well as on a real transport network with 908 nodes proposed by the authors. The results are compared to an exact method (branch and cut) and to the best existing algorithms for OP. The results clearly show that EILIA outperforms existing heuristic methods in terms of the quality of its solutions. In many cases, EILIA produces the same results as the exact method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  • Bunglowala, A., & Singhi, B. M. (2008). A solution to combinatorial optimization problem using memetic algorithms. International Journal of Computer Science and Applications, 1(3), 164–167.

    Google Scholar 

  • Campbell, A. M., Gendreau, M., & Barrett, T. W. (2011). The orienteering problem with stochastic travel and service times. Annals of Operations Research, 186(1), 61–81.

    Article  Google Scholar 

  • Campos, V., Marti, R., Sanchez-Oro, J., & Duarte, A. (2014). Grasp with path relinking for the orienteering problem. Journal of the Operational Research Society, 65(12), 1800–1813.

  • Caserta, M., & Vo, S. (2010). A math-heuristic algorithm for the DNA sequencing problem. Learning and intelligent optimization. Lecture notes in computer science (pp. 25–36). Berlin: Springer

  • Chao, I. M., Golden, B. L., & Wasil, E. A. (1996). A fast and effective heuristic for the orienteering. European Journal of Operational Research, 88, 475–489.

    Article  Google Scholar 

  • Christofides, N., Mingozzi, A., & Toth, P. (2014). VRP instances. http://www.bernabe.dorronsoro.es/vrp/. Last. accessed 24 June 2014.

  • Croes, G. A. (1958). A method for solving traveling salesman problems. Operations Research, 6, 791–812.

    Article  Google Scholar 

  • Feillet, D., Dejax, P., & Gendreau, M. (2001). Traveling salesman problems with profits. An Overview Transportation Science, 38, 188–205.

    Google Scholar 

  • Feo, T. A., & Resende, M. G. C. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8, 67–71.

    Article  Google Scholar 

  • Fischetti, M., Salazar, J. J., & Toth, P. (1998). Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing, 10, 133–148.

    Article  Google Scholar 

  • Fischetti, M., & Toth, P. (1988). An additive approach for the optimal solution of the prize-collecting traveling salesman problem, vehicle routing: Methods and Studies. Amsterdam: Elsevier.

    Google Scholar 

  • Garcia, A., Arbelaitz, O., Vansteenwegen, P., Souffriau, W., & Linaza, M. T. (2010). Hybrid approach for the public transportation time dependent orienteering problem with time windows. Lecture Notes in Computer Science, 6077, 151–158.

    Article  Google Scholar 

  • Gavalas, D., Konstantopoulos, Ch., Mastakas, K., & Pantziou, G. (2014). A survey on algorithmic approaches for solving tourist trip design problems. Journal of Heuristics, 20(3), 291–328.

    Article  Google Scholar 

  • Gendreau, M., Laporte, G., & Semet, F. (1998a). A branch-and-cut algorithm for the undirected selective traveling salesman problem. Networks, 32(4), 263–273.

    Article  Google Scholar 

  • Gendreau, M., Laporte, G., & Semet, F. (1998b). A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research, 106(2–3), 539–545.

    Article  Google Scholar 

  • Golden, B., Levy, L., & Vohra, R. (1987). The orienteering problem. Naval Research Logistics, 34, 307–318.

    Article  Google Scholar 

  • Golden, B., Wang, Q., & Liu, L. (1988). A multifaceted heuristic for the orienteering problem. Naval Research Logistics, 35, 359–366.

    Article  Google Scholar 

  • Hutter, F., Hoos, H. H., Leyton-Brown, K., & Stutzle, T. (2009). ParamILS: An automatic algorithm configuration framework. Journal of Artificial Intelligence Research, 36, 267–306.

    Google Scholar 

  • Jaen, J., Mocholi, J. A., & Catala, A. (2011). Digital ants as the best cicerones for museum visitors. Applied Soft Computing, 11, 111–119.

    Article  Google Scholar 

  • Jozefowiez, N., Glover, F., & Laguna, M. (2008). Multi-objective meta-heuristics for the traveling salesman problem with profit. Journal of Mathematical Modelling and Algorithms, 7, 177–195.

    Article  Google Scholar 

  • Karbowska-Chilinska, J., Koszelew, J., Ostrowski, K., & Zabielski, P. (2012). Genetic algorithm solving orienteering problem in large networks. Frontiers in Artificial Intelligence and Applications, 243, 28–38.

    Google Scholar 

  • Kataoka, S., & Morito, S. (1988). An algorithm for single constraint maximum collection problem. Journal of the Operations Research Society of Japan, 31(4), 515–531.

    Google Scholar 

  • Koszelew, J., & Ostrowski, K. (2013). A genetic algorithm with multiple mutation which solves orienteering problem in large networks. Computational Collective Intelligence Technologies and Applications LNCS, 8083, 356–366.

    Article  Google Scholar 

  • Koszelew, J., Piwonska, A., & Zabielski, P. (2010). Official tourist website of the Podlasie region. http://wycieczka.wrotapodlasia.pl//GenerateWays.aspx. Accessed 24 June 2014

  • Laporte, G., & Martello, S. (1990). The selective travelling salesman problem. Discrete Applied Matheuristics, 26, 20–193.

    Google Scholar 

  • Mansini, R., Pelizzari, M. Wolfler Calvo, R. (2006). The tour orienteering problem with time windows. In Third international workshop on freight transportation and logistics, Altea (Spagna) (pp. 244–246).

  • Ostrowski K. (2013). Dataset network of 908 cities of Poland. http://p.wi.pb.edu.pl/sites/default/files/krzysztof-ostrowski/files/polska908.txt. Accessed 24 June 2014.

  • Ostrowski, K. (2014). Comparison of different graph weights representations used to solve the time-dependent orienteering problem. In Trends in contemporary computer science, Podlasie 2014 (pp. 144–154). Bialystok University of Technology Publishing Office.

  • Ostrowski, K., & Koszelew, J. (2011). The comparison of genetic algorithm which solve orienteering problem using complete and incomplete graph, Zeszyty Naukowe. Politechnika Bialostocka Informatyka, 8, 61–77.

    Google Scholar 

  • Piwonska, A, Koszelew, J. (2011). A memetic algorithm for a tour planning in the selective travelling salesman. In Foundations of Intelligent System. LNCS (Vol. 6804, pp. 684–694). Springer.

  • Potvin, J.-Y. (1996). Genetic algorithms for the traveling salesman problem. Annals of Operations Research, 63(3), 337–370.

    Article  Google Scholar 

  • Prins, C., Prodhon, C., Woler Calvo, R., & Woler Calvo R. (2006). Solving the capacitated location-routing problem by a grasp complemented by a learning process and a path relinking. Journal of Operational Research, 4, 221–238.

    Google Scholar 

  • Ramesh, R., & Brown, K. M. (1991). An efficient four-phase heuristic for the generalized orienteering problem. Computer Operational Research, 18(2), 151165.

    Article  Google Scholar 

  • Ramesh, R., Yoon, Y., & Karwan, M. H. (1992). An optimal algorithm for the orienteering tour problem. INFORMS Journal on Computing, 4(2), 155–165.

    Article  Google Scholar 

  • Reghioui, M., Prins, C., & Labadi, N. (2007). Grasp with path relinking for the capacitated arc routing problem with time windows. In Lecture Notes of Computer Science (Vol. 4448, pp. 722–731).

  • Reinelt, G. (2014). TSPLIB: Library of sample instances for the TSP (and related problems), 1995. http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/. Accessed 24 June 2014.

  • Resende, M. G. C., & Ribeiro, C. C. (2003). Greedy randomized adaptive search procedures. Berlin: Kluwer Academic Publishers.

    Book  Google Scholar 

  • Salhi, S., & Nagy, G. (2007). Local improvement in planar facility location using vehicle routing. Annals of Operations Research, 167(1), 287–296.

    Article  Google Scholar 

  • Schilde, M., Doerner, K., Hartl, R., & Kiechle, G. (2009). Metaheuristics for the biobjective orienteering problem. Swarm Intelligence, 3, 179–201.

    Article  Google Scholar 

  • Sevkli, Z., Sevilgen, E. (2010). Discrete particle swarm optimization for the orienteering problem, Evolutionary Computation (CEC) IEEE Congress (pp. 1–8).

  • Souffriau, W. (2010). Automated tourist decision support. PhD Thesis. Katholieke Universiteit Leuven.

  • Souffriau, W., Vansteenwegen, P., Vanden Berghe, G., & Van Oudheusden, D. (2010). A path relinking approach for the team orienteering problem. Computers and Operational Research, 37, 1853–1859.

    Article  Google Scholar 

  • Tang, H., & Miller-Hooks, E. (2005). A tabu search heuristic for the team orienteering problem. Computers and Operational Research, 32(6), 1379–1407.

    Article  Google Scholar 

  • Tasgetiren, M. F. (2002). A genetic algorithm with an adaptive penalty function for the orienteering problem. Journal of Economic and Social Research, 4(2), 20–40.

    Google Scholar 

  • Tasgetiren, M. F., & Smith, A. E. (2000). A genetic algorithm for the orienteering problem. Proceedings of the 2000 Congress on Evolutionary Computation San Diego, 2, 1190–1195.

    Article  Google Scholar 

  • Tsiligirides, T. (1984). Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9), 797–809.

    Article  Google Scholar 

  • Vansteenwegen, P., & Van Oudheusden, D. (2007). The mobile tourist guide: An or opportunity. Operational Research Insight, 20(3), 21–27.

    Google Scholar 

  • Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2009a). A guided local search metaheuristic for the team orienteering problem. European Journal of Operational Research, 196, 118–127.

    Article  Google Scholar 

  • Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2009b). Iterated local search for the team orienteering problem with time windows. Computers and Operational Research, 36, 3281–3290.

    Article  Google Scholar 

  • Vansteenwegen, P., Souffriau, W., & Van Oudheusden, D. (2011a). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1–10.

    Article  Google Scholar 

  • Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2011b). The city trip planner: An expert system for tourists. Expert Systems with Applications, 38(6), 6540–6546.

    Article  Google Scholar 

  • Verbeeck, C., Aghezzafa, E. H., Srensenb, K., & Vansteenwegena, P. (2014). A fast solution method for the time-dependent orienteering problem. European Journal of Operational Research, 236(2), 419–432.

    Article  Google Scholar 

  • Wang, Q., Sun, X., Golden, B. L., & Jia, J. (2008). Using artificial neural networks to solve the orienteering problem. Annals of Operations Research, 61, 111120.

    Google Scholar 

  • Zhu, Ch., Hu, J. Q., Xu, Y., & Cao, R. (2010). On the tour planning problem. Annals of Operations Research, 192(1), 67–86.

    Article  Google Scholar 

Download references

Acknowledgments

The authors would like to thank Vicente Campos, Rafael Marti, Jess Snchez-Oro and Abraham Duarte for executing their algorithms (Campos et al. 2014) on our network (908 cities of Poland) and sharing the results with us. The authors gratefully acknowledge support from the Polish Ministry of Science and Higher Education at the Bialystok University of Technology (Grant S/WI/1/2014, W/WI/2/2013 and W/WI/4/2014).

Author information

Authors and Affiliations

  1. Faculty of Computer Science, Bialystok University of Technology, Poland Wiejska 45 A, 15-351, Bialystok, Poland

    Krzysztof Ostrowski, Joanna Karbowska-Chilinska, Jolanta Koszelew & Pawel Zabielski

Authors
  1. Krzysztof Ostrowski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joanna Karbowska-Chilinska
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jolanta Koszelew
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pawel Zabielski
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Krzysztof Ostrowski.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ostrowski, K., Karbowska-Chilinska, J., Koszelew, J. et al. Evolution-inspired local improvement algorithm solving orienteering problem. Ann Oper Res 253, 519–543 (2017). https://doi.org/10.1007/s10479-016-2278-1

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-016-2278-1

Keywords

Search

Navigation