Team Orienteering Problem with Time Windows and Variable Profit

• Autorzy: Marzal Eliseo , Sebastia Laura

Identyfikatory

DOI

10.15439/2022F158

• Konferencja: Federated Conference on Computer Science and Information Systems (17 ; 04-07.09.2022 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

computer science; reactive power; benchmark testing; mathematical model; optimization

PL

informatyka; moc bierna; testy porównawcze; model matematyczny; optymalizacja

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2022
• Tom: Vol. 30
• Strony: 347--350
• Opis fizyczny: Bibliogr. 12 poz., tab., wz.

Twórcy

autor

Marzal Eliseo

• Valencian Research Institute for Artificial Intelligence Universitat Politècnica de València Camino de Vera s/n - Valencia (Spain)

autor

Sebastia Laura

• Valencian Research Institute for Artificial Intelligence Universitat Politècnica de València Camino de Vera s/n - Valencia (Spain)

Bibliografia

• 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.

Uwagi

1. Short article

2. Track 6: 15th International Workshop on Computational Optimization

3. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).