Online Vehicle Routing With Neural Combinatorial Optimization and Deep Reinforcement Learning

• Published in: IEEE transactions on intelligent transportation systems 2019-10, Vol.20 (10), p.3806-3817
• Main Authors: Yu, James J. Q., Yu, Wen, Gu, Jiatao
• Format: Article
• Language: English
• Subjects: Algorithms; Combinatorial analysis; Complexity; Computational modeling; Computer simulation; Computing time; deep reinforcement learning; Green products; intelligent transportation; logistic system; Logistics; Machine learning; Mathematical programming; neural combinatorial optimization; Neural networks; Online vehicle routing; Optimization; Process parameters; Production scheduling; Route planning; Routing; Strategy; Training; Transportation; Transportation networks; Transportation services; Transportation systems; Vehicle routing
• ISSN: 1524-9050; 1558-0016
• DOI: 10.1109/TITS.2019.2909109

Online vehicle routing is an important task of the modern transportation service provider. Contributed by the ever-increasing real-time demand on the transportation system, especially small-parcel last-mile delivery requests, vehicle route generation is becoming more computationally complex than before. The existing routing algorithms are mostly based on mathematical programming, which requires huge computation time in city-size transportation networks. To develop routes with minimal time, in this paper, we propose a novel deep reinforcement learning-based neural combinatorial optimization strategy. Specifically, we transform the online routing problem to a vehicle tour generation problem, and propose a structural graph embedded pointer network to develop these tours iteratively. Furthermore, since constructing supervised training data for the neural network is impractical due to the high computation complexity, we propose a deep reinforcement learning mechanism with an unsupervised auxiliary network to train the model parameters. A multisampling scheme is also devised to further improve the system performance. Since the parameter training process is offline, the proposed strategy can achieve a superior online route generation speed. To assess the proposed strategy, we conduct comprehensive case studies with a real-world transportation network. The simulation results show that the proposed strategy can significantly outperform conventional strategies with limited computation time in both static and dynamic logistic systems. In addition, the influence of control parameters on the system performance is investigated.