- Titel
- An Improvement Heuristic Based on Variable Neighborhood Search for Dynamic Orienteering Problems with Changing Node Values and Changing Budgets
- Zitierfähige Url:
- https://nbn-resolving.org/urn:nbn:de:bsz:15-qucosa2-1036058
- Quellenangabe
- SN Computer Science
Erscheinungsjahr: 2022
Jahrgang: 3
Heft: 4
E-ISSN: 2661-8907
Artikelnummer: 326 - Erstveröffentlichung
- 2022
- Abstract (EN)
- We study the Dynamic Orienteering Problem (DOP) with changing node values and changing budgets. It is a complex com- binatorial optimization problem with many applications, e.g., in tour planning. To solve the DOP, an improvement heuristic based on Variable Neighborhood Search VNSDOP is proposed. In addition, three methods for handling solutions that became invalid by budget changes are presented. Heuristic VNSDOP is experimentally compared with two improvement heuristics based on state-of-the-art algorithms for the static Orienteering Problem. In addition, the influence of the three invalid solution handling methods on the algorithms’ optimization behavior is evaluated experimentally. For the experiments, benchmark instances as well as instances generated from existing road networks are used. As a quality measure for the algorithms, their performance over time is used. The results show that both types of dynamic changes, i.e., changes in the node values and changes in the budget, lead to higher volatility in the results for all compared algorithms. However, the latter type has a more negative effect on the performance. Out of the compared algorithms, the proposed heuristic VNSDOP obtains the best results in most cases on a variety of problem instances with dynamic node values and dynamic budgets, showing that it has a high performance over time in dynamic environments and is able to deal with different levels of dynamic changes. For DOPs with changing budgets, the invalid solution handling method that repairs solutions by fixing the violation of the budget constraint as fast as possible performs best for the considered algorithms.
- Andere Ausgabe
- Erstveröffentlichung
DOI: 10.1007/s42979-022-01205-x - Freie Schlagwörter (EN)
- Dynamic optimization, Neighborhood search, Metaheuristics, Routing problems
- Klassifikation (DDC)
- 000
- Verlag
- Springer Nature, Singapore
- Förder- / Projektangaben
- Deutsche Forschungsgemeinschaft (DFG)
Dynamische evolutionäre Optimierung von Netzwerkproblemen
ID: 392050753 - Version / Begutachtungsstatus
- publizierte Version / Verlagsversion
- URN Qucosa
- urn:nbn:de:bsz:15-qucosa2-1036058
- Veröffentlichungsdatum Qucosa
- 02.04.2026
- Dokumenttyp
- Artikel
- Sprache des Dokumentes
- Englisch
- Lizenz / Rechtehinweis
CC BY 4.0