Logo PTI Logo FedCSIS

Proceedings of the 17th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 30

Team Orienteering Problem with Time Windows and Variable Profit

,

DOI: http://dx.doi.org/10.15439/2022F158

Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 347–350 ()

Full text

Abstract. The Orienteering Problem (OP) is a combinatorial optimization and integer programming problem whose goal is to obtain the optimal route for a vehicle to traverse to deliver to a given set of customers. The objective is to select a subset of nodes to visit to maximize the total collected score given a limited time budget. The OP has numerous applications in various fields such as logistics and tourism. Several variants have been studied, including the Team Orienteering Problem (TOP), the Orienteering Problem with Time Windows (OPTW), and the TOP with Variable Profits (TOPVP). This paper introduces the Team OP with Time Windows and Variable Profits (TOPTWVP). In this case, each node has a predefined time window in which the service must start (in case this node is visited), and the vehicle may spend an amount of time given by a predefined interval so that the profit collected at this node depends on the time spent. We first propose a mathematical model for the TOPTWVP and use OR-Tools to solve small modified benchmark instances. We then propose an algorithm based on Iterated Local Search to solve more difficult modified benchmark instances. The results show that our approach can solve difficult instances with good quality.

References

  1. P. Vansteenwegen, W. Souffriau, and D. Van Oudheusden, “The orienteering problem: A survey,” European Journal of Operational Research, vol. 209, no. 1, pp. 1–10, 2011. http://dx.doi.org/10.1016/j.ejor.2010.03.045
  2. I.-M. Chao, B. L. Golden, and E. A. Wasil, “The team orienteering problem,” European journal of operational research, vol. 88, no. 3, pp. 464–474, 1996. http://dx.doi.org/10.1016/0377-2217(94)00289-4
  3. S. Boussier, D. Feillet, and M. Gendreau, “An exact algorithm for team orienteering problems,” 4or, vol. 5, no. 3, pp. 211–230, 2007. http://dx.doi.org/10.1007/s10288-006-0009-1
  4. G. Erdogan and G. Laporte, “The orienteering problem with variable profits,” Networks, vol. 61, pp. 104–116, 2013. http://dx.doi.org/10.1002/net.21496
  5. A. Gunawan, K. M. Ng, G. Kendall, and J. Lai, “An iterated local search algorithm for the team orienteering problem with variable profits,” Engineering Optimization, vol. 50, no. 7, pp. 1148–1163, 2018. http://dx.doi.org/10.1080/0305215X.2017.1417398
  6. F. Mufalli, R. Batta, and R. Nagi, “Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans,” Computers & Operations Research, vol. 39, no. 11, pp. 2787–2799, 2012. http://dx.doi.org/10.1016/j.cor.2012.02.010
  7. P. Vansteenwegen and D. Van Oudheusden, “The mobile tourist guide: an or opportunity,” OR insight, vol. 20, no. 3, pp. 21–27, 2007. http://dx.doi.org/10.1057/ori.2007.17
  8. J. Ibañez, L. Sebastia, and E. Onaindia, “Planning tourist agendas for different travel styles,” in Proceedings of the Twenty-second European Conference on Artificial Intelligence. IOS Press, 2016. http://dx.doi.org/10.3233/978-1-61499-672-9-1818 pp. 1818–1823.
  9. J. Ibánez-Ruiz, L. Sebastiá, and E. Onaindia, “Evaluating the quality of tourist agendas customized to different travel styles,” arXiv preprint https://arxiv.org/abs/1706.05518, 2017.
  10. L. Sebastia and E. Marzal, “Extensions of the tourist travel design problem for different travel styles,” Procedia Computer Science, vol. 176, pp. 339–348, 2020. http://dx.doi.org/10.1016/j.procs.2020.08.036
  11. P. Vansteenwegen, W. Souffriau, G. V. Berghe, and D. Van Oudheusden, “Iterated local search for the team orienteering problem with time windows,” Computers & Operations Research, vol. 36, no. 12, pp. 3281–3290, 2009. http://dx.doi.org/10.1016/j.cor.2009.03.008
  12. A. Gunawan, H. C. Lau, and K. Lu, “An iterated local search algorithm for solving the orienteering problem with time windows,” in Evolutionary Computation in Combinatorial Optimization: 15th European Conference, EvoCOP 2015, Copenhagen, Denmark, April 8-10, 2015, Proceedings, 2015. http://dx.doi.org/10.1007/978-3-319-16468-7_6 pp. 61–73.