Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem
Publication Type
Journal Article
Publication Date
9-2021
Abstract
Existing deep reinforcement learning (DRL)-based methods for solving the capacitated vehicle routing problem (CVRP) intrinsically cope with a homogeneous vehicle fleet, in which the fleet is assumed as repetitions of a single vehicle. Hence, their key to construct a solution solely lies in the selection of the next node (customer) to visit excluding the selection of vehicle. However, vehicles in real-world scenarios are likely to be heterogeneous with different characteristics that affect their capacity (or travel speed), rendering existing DRL methods less effective. In this article, we tackle heterogeneous CVRP (HCVRP), where vehicles are mainly characterized by different capacities. We consider both min-max and min-sum objectives for HCVRP, which aim to minimize the longest or total travel time of the vehicle(s) in the fleet. To solve those problems, we propose a DRL method based on the attention mechanism with a vehicle selection decoder accounting for the heterogeneous fleet constraint and a node selection decoder accounting for the route construction, which learns to construct a solution by automatically selecting both a vehicle and a node for this vehicle at each step. Experimental results based on randomly generated instances show that, with desirable generalization to various problem sizes, our method outperforms the state-of-the-art DRL method and most of the conventional heuristics, and also delivers competitive performance against the state-of-the-art heuristic method, that is, slack induction by string removal. In addition, the results of extended experiments demonstrate that our method is also able to solve CVRPLib instances with satisfactory performance.
Keywords
Decoding, Search problems, Reinforcement learning, Computer architecture, Vehicle routing, Routing, Optimization, Deep reinforcement learning (DRL), heterogeneous CVRP (HCVRP), min-max objective, min-sum objective
Discipline
Management Information Systems
Research Areas
Intelligent Systems and Optimization
Publication
IEEE Transactions on Cybernetics
Volume
52
Issue
12
First Page
13572
Last Page
13585
ISSN
2168-2267
Identifier
10.1109/TCYB.2021.3111082
Publisher
Institute of Electrical and Electronics Engineers
Citation
LI, Jingwen; MA, Yining; GAO, Ruize; CAO, Zhiguang; LIM, Andrew; SONG, Wen; and ZHANG, Jie.
Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem. (2021). IEEE Transactions on Cybernetics. 52, (12), 13572-13585.
Available at: https://ink.library.smu.edu.sg/sis_research/8204