Monte Carlo Tree Search improved Genetic Algorithm for unmanned vehicle routing problem with path flexibility

With the gradual normalization of the COVID-19, unmanned delivery has gradually become an important contactless distribution method around China. In this paper, we study the routing problem of unmanned vehicles considering path flexibility and the number of traffic lights in the road network to redu...

Full description

Saved in:
Bibliographic Details
Published in:Advances in production engineering & management 2022-12, Vol.17 (4), p.425-438
Main Authors: Wang, Y.D., Lu, X.C., Song, Y.M., Feng, Y., Shen, J.R.
Format: Article
Language:English
Subjects:
Complexity
Coronaviruses
COVID-19
Design
Disease transmission
Electric vehicles
Flexibility
Genetic algorithms
Heuristic
Medical research
Monte Carlo simulation
Neighborhoods
Road conditions
Route planning
Search algorithms
Traffic
Traffic signals
Transportation networks
Unmanned aerial vehicles
Unmanned vehicles
Vehicle routing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:With the gradual normalization of the COVID-19, unmanned delivery has gradually become an important contactless distribution method around China. In this paper, we study the routing problem of unmanned vehicles considering path flexibility and the number of traffic lights in the road network to reduce the complexity of road conditions faced by unmanned vehicles as much as possible. We use Monte Carlo Tree Search algorithm to improve the Genetic Algorithm to solve this problem, first use Monte Carlo Tree Search Algorithm to compute the time-saving path between two nodes among multiple feasible paths and then transfer the paths results to Genetic Algorithm to obtain the final sequence of the unmanned vehicles fleet. And the hybrid algorithm was tested on the actual road network data around four hospitals in Beijing. The results showed that compared with normal vehicle routing problem, considering path flexibility can save the delivery time, the more complex the road network composition, the better results could be obtained by the algorithm.
ISSN:1854-6250
1855-6531
DOI:10.14743/apem2022.4.446