Machine learning based simulation optimisation for urban routing problems

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.