An Improvement Heuristic Based on Variable Neighborhood Search for a Dynamic Orienteering Problem

Le，Hoang Thanh1; Middendorf，Martin1; Shi，Yuhui2

10.1007/978-3-030-72904-2_5

2021

0302-9743

1611-3349

LECT NOTES ARTIF INT

12692 LNCS

68-83

The Dynamic Orienteering Problem (DOP) is studied where nodes change their value over time. An improvement heuristic that is based on Variable Neighborhood Search is proposed for the DOP. The new heuristic is experimentally compared with two heuristics that are based on state-of-the-art algorithms for the static Orienteering Problem. For the experiments several benchmark instances are used as well as instances that are generated from existing road networks. The results show that the new heuristic outperforms the other heuristics with respect to several evaluation criteria and different measures for run time. An additional experiment shows that the new heuristic can be easily adapted to become a standalone algorithm that does not need given initial solutions. The standalone version obtains better results than two state-of-the-art algorithms.

Anytime algorithms Dynamic optimization Neighborhood search Routing problems

其他

英语

EI

20212310475020

Benchmarking ; Combinatorial optimization ; Evolutionary algorithms ; Heuristic algorithms ; Heuristic methods

Computer Programming:723.1 ; Optimization Techniques:921.5

2-s2.0-85107362477

Scopus

1.Swarm Intelligence and Complex Systems Group,Institute of Computer Science,Leipzig University,Leipzig,Germany
2.Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,China

Le，Hoang Thanh,Middendorf，Martin,Shi，Yuhui. An Improvement Heuristic Based on Variable Neighborhood Search for a Dynamic Orienteering Problem[C],2021:68-83.