期刊
APPLIED SOFT COMPUTING
卷 105, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.asoc.2021.107269
关键词
Team orienteering problem; Learnheuristic; Traffic simulation; Machine learning; Metaheuristics
资金
- Erasmus+ programme [2017-1-ES01-KA103-036672]
- Spanish Ministry of Science, Innovation, and Universities [RED2018102642T]
This study explores the application of team orienteering problems in a traffic simulation environment and proposes a learnheuristic solution approach that integrates machine learning and optimization. Experiments show that different combinations produce solutions with varying characteristics in terms of total reward and reliability, with local search combined with a neural network proving effective in multiple instances. The study also addresses the optimal use of runtime for learnheuristic algorithms.
Many real world routing problems, including those in tourism and surveillance, can be formulated as team orienteering problems. The goal in such problems is to maximise the rewards collected by a fleet of vehicles whose routes must be completed within a time limit. This work considers a team orienteering problem set within a traffic simulation. In the stochastic environment of a road network, travel times depend on network structure, the demands of road users, driver behaviour and the congestion that arises from these. As a result travel times are difficult to predict. In this work a learnheuristic solution approach is proposed. Learnheuristics integrate machine learning and optimisation for solving combinatorial problems with inherent parameter learning problems-in this case travel times. The machine learning component is used to predict travel times based on data obtained from a limited budget of traffic simulation runs, a budget that is used within the run-time learnheuristic algorithm. In each iteration of the learnheuristic, the optimisation component utilises the travel time predictions of the machine learning algorithm to rapidly generate candidate solutions. The strongest candidate is tested in the traffic simulator, and the results of which are used to train the machine learning component. In a range of test instances, the effectiveness of different combinations of machine learning and optimisation components are tested. Experiments reveal that different combinations of machine learning and optimisation components produce solutions with different characteristics in terms of total reward and reliability. Local search followed by biased randomisation combined with a neural network was found to be effective in multiple instances. The question of how best to use the run-time of a learnheuristic is also addressed. (C) 2021 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据