Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Transfer Learning Approach in Classification of BCI Motor Imagery Signal Read chapter Read first chapter

2020 | OriginalPaper | Chapter

An Efficient Metaheuristic for the Time-Dependent Team Orienteering Problem with Time Windows

Author : Krzysztof Ostrowski

Published in: Computer Information Systems and Industrial Management

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The Time-Dependent Team Orienteering Problem with Time Windows (TDTOPTW) is a combinatorial optimization problem defined on graphs. The goal is to find most profitable set of paths in time-dependent graphs, where travel times (weights) between vertices varies with time. Its real life applications include tourist trip planning in transport networks. The paper presents an evolutionary algorithm with local search operators solving the problem. The algorithm was tested on public transport network of Athens and clearly outperformed other published methods achieving results close to optimal in short execution times.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Intraday Patterns in Trading Volume. Evidence from High Frequency Data on the Polish Stock Market
next chapter Measurement and Optimization Models of Risk Management System Usability
Literature
1.
Campbell, A.M., Gendreau, M., Barrett, W.T.: The orienteering problem with stochastic travel and service times. Ann. Oper. Res. 186(1), 61–81 (2011)MathSciNetMATHCrossRef
2.
Campos, V., Marti, R., Sanchez-Oro, J., Duarte, A.: Grasp with path relinking for the orienteering problem. J. Oper. Res. Soc. 156, 1–14 (2013)
3.
4.
Chao, I., Golden, B., Wasil, E.: Theory and methodology - a fast and effective heuristic for the orienteering problem. Eur. J. Oper. Res. 88, 475–489 (1996)MATHCrossRef
5.
Divsalar, A., Sorensen, K., Vansteenwegen, P., Cattrysse, D.: A memetic algorithm for the orienteering problem with hotel selection. Eur. J. Oper. Res. 237(1), 29–49 (2014)MATHCrossRef
6.
Garcia, A., Vansteenwegen, P., Arbelaitz, O., Souffriau, W., Linaza, M.T.: Integrating public transportation in personalised electronic tourist guides. Comput. Oper. Res. 40(3), 758–774 (2013)CrossRef
7.
Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., Vathis, N.: Heuristics for the time dependent team orienteering problem: application to tourist route planning. Comput. Oper. Res. 62, 36–50 (2015)MathSciNetMATHCrossRef
8.
Gendreau, M., Laporte, G., Semet, F.: A tabu search heuristic for the undirected selective travelling salesman problem. Eur. J. Oper. Res. 106, 539–545 (1998)MATHCrossRef
9.
Golden, B., Levy, L., Vohra, R.: The orienteering problem. Naval Res. Logist. 34, 307–318 (1987)MATHCrossRef
10.
Gunawan, A., Yuan, Z., Lau, H.C.: A Mathematical Model and Metaheuristics for Time Dependent Orienteering Problem. Angewandte Mathematik und Optimierung Schriftenreihe AMOS 14 (2014)
11.
Hutter, F., Hoos, H.H., Leyton-Brown, K., Stutzle, T.: ParamILS: an automatic algorithm configuration framework. J. Artif. Intell. Res. 36, 267–306 (2009)MATHCrossRef
12.
Li, J.: Model and algorithm for Time-Dependent Team Orienteering Problem. Commun. Comput. Inf. Sci. 175, 1–7 (2011)
13.
Mahfoud, S.W.: Crowding and preselection revisited. In: Proceedings of the 2nd International Conference on Parallel Problem Solving from Nature (PPSN II), Brussels, Belgium, pp. 27–36. Elsevier, Amsterdam (1992)
14.
Ostrowski, K.: Parameters tuning of evolutionary algorithm for the orienteering problem. Adv. Comput. Sci. Res. 12, 53–78 (2015)
15.
Ostrowski, K., Karbowska-Chilinska, J., Koszelew, J., Zabielski, P.: Evolution-inspired local improvement algorithm solving orienteering problem. Ann. Oper. Res. 253(1), 519–543 (2017)MathSciNetMATHCrossRef
16.
Ostrowski, K.: Evolutionary algorithm for the Time-Dependent Orienteering Problem. Lect. Notes Comput. Sci. 10244, 50–62 (2017)CrossRef
17.
Ostrowski, K.: An effective metaheuristic for tourist trip planning in public transport networks. Appl. Comput. Sci. 12(2) (2018)
18.
Schilde, M., Doerner, K., Hartl, R., Kiechle, G.: Metaheuristics for the biobjective orienteering problem. Swarm Intell. 3, 179–201 (2009)CrossRef
19.
Tasgetiren, M.: A genetic algorithm with an adaptive penalty function for the orienteering problem. J. Econ. Soc. Res. 4(2), 1–26 (2001)
20.
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., Oudheusden, D.V.: A guided local search metaheuristic for the team orienteering problem. Eur. J. Oper. Res. 196(1), 118–127 (2009)MATHCrossRef
21.
Verbeeck, C., Sorensen, K., Aghezzaf, E.H., Vansteenwegena, P.: A fast solution method for the time-dependent orienteering problem. Eur. J. Oper. Res. 236(2), 419–432 (2014)MathSciNetMATHCrossRef
22.
Yu, Q., Fang, K., Zhu, N., Ma, S.: A matheuristic approach to the orienteering problem with service time dependent profits. Eur. J. Oper. Res. 273(2), 488–503 (2019)MathSciNetMATHCrossRef
Metadata
Title
An Efficient Metaheuristic for the Time-Dependent Team Orienteering Problem with Time Windows
Author
Krzysztof Ostrowski
Copyright Year
2020
Book
Computer Information Systems and Industrial Management

Print ISBN: 978-3-030-47678-6

Electronic ISBN: 978-3-030-47679-3

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-47679-3_34

Premium Partner

    Image Credits