Machine learning based simulation optimisation for urban routing problems

Bayliss, Christopher ORCID: 0000-0003-0031-5937 (2021) Machine learning based simulation optimisation for urban routing problems. APPLIED SOFT COMPUTING, 105. p. 107269.

Text Traffic_VRP_LH (2).pdf - Author Accepted Manuscript Download (1MB) | Preview

Abstract

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.

Item Type:	Article
Uncontrolled Keywords:	Team orienteering problem, Learnheuristic, Traffic simulation, Machine learning, Metaheuristics
Divisions:	Faculty of Humanities and Social Sciences > School of Management
Depositing User:	Symplectic Admin
Date Deposited:	12 Mar 2021 16:59
Last Modified:	18 Jan 2023 22:56
DOI:	10.1016/j.asoc.2021.107269
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3117120