Self-adaptive heuristic algorithms for the dynamic and stochastic orienteering problem in autonomous transportation system

Bijun Wang, Zheyong Bian () and Mo Mansouri
Additional contact information
Bijun Wang: Stevens Institute of Technology
Zheyong Bian: University of Houston
Mo Mansouri: Stevens Institute of Technology

Journal of Heuristics, 2023, vol. 29, issue 1, No 3, 77-137

Abstract: Abstract This paper studies a task execution and routing problem in the autonomous transportation system that maps to the famous orienteering problem (OP) in operations research. By extending the classical OP to stochastic and dynamic OP with stochastic travel time and service time, an investigation is conducted that aims to optimize the selection of travel routes with the objective of maximizing the total collected rewards in accordance with the time availability of self-adaptive agent (e.g., unmanned aircraft vehicles and unmanned ground vehicle). Three self-adaptive multi-stage heuristics-based adjustment strategies (i.e., Insertion-and-Removal Heuristics, Hybrid Simulated Annealing-Tabu Search-based Re-Optimization, and Threshold-based Re-Optimization) are proposed to equip the autonomous agent with the ability of real-time routing adjustment in the context of the dynamic and stochastic orienteering problem. Finally, benchmark simulation experiments are used to test the effectiveness of all the three proposed adjustment strategies. The experimental results show that, compared with a priori solutions acquired by a static meta-heuristic algorithm (Hybrid Simulated Annealing-Tabu Search algorithm), the three strategies can improve the solution qualities at different levels.

Keywords: Heuristics; Stochastic and dynamic orienteering problem; Adaptive optimization strategies; Hybrid simulated annealing-tabu search algorithm; Autonomous transportation system (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-022-09507-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:29:y:2023:i:1:d:10.1007_s10732-022-09507-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-022-09507-2

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().