SpringerLink
Log in

Efficiently solving the thief orienteering problem with a max–min ant colony optimization approach

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

We tackle the thief orienteering problem (ThOP), an academic multi-component problem that combines two classical combinatorial problems, namely the Knapsack Problem and the Orienteering Problem. In the ThOP, a thief has a time limit to steal items that distributed in a given set of cities. While traveling, the thief collects items by storing them in their knapsack, which in turn reduces the travel speed. The thief has as the objective to maximize the total profit of the stolen items. In this article, we present an approach that combines swarm-intelligence with a randomized packing heuristic. Our solution approach outperforms existing works on almost all the 432 benchmarking instances, with significant improvements.

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
EUR 32.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 includes VAT (Thailand)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. In addition to the code of our mathematical model, it also contains some experiments and results on smaller instances that we have created in order to solve the model and establish a benchmarking with exact results. However, the experiments have shown that even for instances with 15 cities and 1 item per city, our model cannot be solved, and it also is not able to find tight mathematical bounds within a reasonable computational time.

  2. Publicly available online at http://www.aco-metaheuristic.org/aco-code

  3. As stated by Polyakovskiy and Neumann [22], determining the optimal packing plan is \({{\mathcal {N}}}{{\mathcal {P}}}\)-hard, even when the route of the thief is kept fixed.

References

  1. Aarts, E., Aarts, E.H., Lenstra, J.K.: Local Search in Combinatorial Optimization. Princeton University Press, Princeton (2003)

    Book  Google Scholar 

  2. Birattari, M., Yuan, Z., Balaprakash, P., Stützle, T.: F-race and iterated f-race: An overview. In: Bartz-Beielstein, T., Chiarandini, M., Paquete, L., Preuss M. (eds) Experimental Methods for the Analysis of Optimization Algorithms, pp. 311–336. Springer, Berlin, Heidelberg (2010). https://doi.org/10.1007/978-3-642-02538-9_13

  3. Bonyadi, M.R., Michalewicz, Z., Barone, L.: The travelling thief problem: the first step in the transition from theoretical problems to realistic problems. In: IEEE Congress on Evolutionary Computation, pp. 1037–1044. IEEE, Cancun, Mexico (2013). https://doi.org/10.1109/CEC.2013.6557681

  4. Bonyadi, M.R., Michalewicz, Z., Wagner, M., Neumann, F.: Evolutionary computation for multicomponent problems: opportunities and future directions. In: Datta, S., Davim, J. (eds) Optimization in Industry, pp. 13–30. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-01641-8_2

  5. Chagas, J.B., Wagner, M.: Ants can orienteer a thief in their robbery. Oper. Res. Lett. 48(6), 708–714 (2020)

    Article  MathSciNet  Google Scholar 

  6. Chand, S., Wagner, M.: Fast heuristics for the multiple traveling thieves problem. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 293–300. ACM (2016)

  7. Chen, C., Cheng, S.F., Gunawan, A., Misra, A., Dasgupta, K., Chander, D.: Traccs: a framework for trajectory-aware coordinated urban crowd-sourcing. In: Bigham, J.P., Parkes, D.C. (eds.) Second AAAI Conference on Human Computation and Crowdsourcing (HCOMP). AAAI (2014). http://www.aaai.org/Library/HCOMP/hcomp14contents.php

  8. Dorigo, M., Di Caro, G.: Ant colony optimization: a new meta-heuristic. In: IEEE Congress on Evolutionary Computation (CEC), vol. 2, pp. 1470–1477. IEEE (1999)

  9. Faêda, L.M., Santos, A.G.: A genetic algorithm for the thief orienteering problem. In: 2020 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE (2020)

  10. Faulkner, H., Polyakovskiy, S., Schultz, T., Wagner, M.: Approximate approaches to the traveling thief problem. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 385–392. ACM (2015)

  11. Fischetti, M., Gonzalez, J.J.S., Toth, P.: Solving the orienteering problem through branch-and-cut. INFORMS J. Comput. 10(2), 133–148 (1998)

    Article  MathSciNet  Google Scholar 

  12. Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., Hendel, G., Hojny, C., Koch, T., Le Bodic, P., Maher, S.J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M.E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., Witzig, J.: The SCIP Optimization Suite 7.0. ZIB-Report 20-10, Zuse Institute Berlin (2020). http://nbn-resolving.de/urn:nbn:de:0297-zib-78023

  13. Golden, B.L., Levy, L., Vohra, R.: The orienteering problem. Naval Res. Logist. 34, 307–318 (1987)

    Article  Google Scholar 

  14. Gunawan, A., Lau, H.C., Vansteenwegen, P.: Orienteering problem: a survey of recent variants, solution approaches and applications. Eur. J. Oper. Res. 255(2), 315–332 (2016)

    Article  MathSciNet  Google Scholar 

  15. Iori, M., Martello, S.: Routing problems with loading constraints. Top 18(1), 4–27 (2010)

    Article  MathSciNet  Google Scholar 

  16. Kim, H., Kim, B.I., ** Noh, D.: The multi-profit orienteering problem. Comput. Ind. Eng. 149, 106808 (2020)

    Article  Google Scholar 

  17. López-Ibáñez, M., Dubois-Lacoste, J., Cáceres, L.P., Birattari, M., Stützle, T.: The irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect. 3, 43–58 (2016)

    MathSciNet  Google Scholar 

  18. Maher, S., Miltenberger, M., Pedroso, J.P., Rehfeldt, D., Schwarz, R., Serrano, F.: PySCIPOpt: mathematical programming in python with the SCIP optimization suite. In: Mathematical Software—ICMS 2016, pp. 301–307. Springer International Publishing (2016). https://doi.org/10.1007/978-3-319-42432-3_37

  19. Neumann, F., Polyakovskiy, S., Skutella, M., Stougie, L., Wu, J.: A fully polynomial time approximation scheme for packing while traveling. In: Disser, Y., Verykios, V.S. (eds.) Algorithmic Aspects of Cloud Computing, pp. 59–72. Springer, Berlin (2019)

    Chapter  Google Scholar 

  20. Orlis, C., Bianchessi, N., Roberti, R., Dullaert, W.: The team orienteering problem with overlaps: an application in cash logistics. Transp. Sci. 54(2), 470–487 (2020)

    Article  Google Scholar 

  21. Polyakovskiy, S., Bonyadi, M.R., Wagner, M., Michalewicz, Z., Neumann, F.: A comprehensive benchmark set and heuristics for the traveling thief problem. In: Genetic and Evolutionary Computation Conference (GECCO), pp. 477–484. ACM (2014)

  22. Polyakovskiy, S., Neumann, F.: Packing while traveling: mixed integer programming for a class of nonlinear knapsack problems. In: International Conference on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems (CPAIOR), pp. 332–346. Springer (2015)

  23. Santos, A.G., Chagas, J.B.: The thief orienteering problem: formulation and heuristic approaches. In: IEEE Congress on Evolutionary Computation (CEC), pp. 1191–1199. IEEE (2018)

  24. Stützle, T., Hoos, H.H.: Max–min ant system. Fut. Gener. Comput. Syst. 16(8), 889–914 (2000)

    Article  Google Scholar 

  25. Toth, P., Martello, S.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Hoboken (1990)

    MATH  Google Scholar 

  26. Trachanatzi, D., Rigakis, M., Marinaki, M., Marinakis, Y.: A firefly algorithm for the environmental prize-collecting vehicle routing problem. Swarm Evol. Comput. 57, 100712 (2020)

    Article  Google Scholar 

  27. Wagner, M.: Stealing items more efficiently with ants: a swarm intelligence approach to the travelling thief problem. In: International Conference on Swarm Intelligence (ANTS), pp. 273–281. Springer (2016)

  28. Wagner, M., Lindauer, M., Mısır, M., Nallaperuma, S., Hutter, F.: A case study of algorithm selection for the traveling thief problem. J. Heuristics 24(3), 295–320 (2018)

    Article  Google Scholar 

  29. Wu, J., Wagner, M., Polyakovskiy, S., Neumann, F.: Exact approaches for the travelling thief problem. In: Asia-Pacific Conference on Simulated Evolution and Learning, pp. 110–121. Springer (2017)

Download references

Acknowledgements

The authors would like to thank the following institutions and funding bodies: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brazil (CAPES) - Finance code 001; Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG); Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq); Universidade Federal de Ouro Preto (UFOP); Universidade Federal de Viçosa (UFV); and Australian Research Council Project DP200102364.

Author information

Authors and Affiliations

  1. Departamento de Computação, Universidade Federal de Ouro Preto, Ouro Preto, Brazil

    Jonatas B. C. Chagas

  2. Departamento de Informática, Universidade Federal de Viçosa, Viçosa, Brazil

    Jonatas B. C. Chagas

  3. School of Computer Science, The University of Adelaide, Adelaide, Australia

    Markus Wagner

Authors
  1. Jonatas B. C. Chagas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Markus Wagner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jonatas B. C. Chagas.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chagas, J.B.C., Wagner, M. Efficiently solving the thief orienteering problem with a max–min ant colony optimization approach. Optim Lett 16, 2313–2331 (2022). https://doi.org/10.1007/s11590-021-01824-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-021-01824-y

Keywords

Search

Navigation