Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem

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 selec...

Full description

Saved in:
Bibliographic Details
Main Authors: LI, Jingwen, MA, Yining, GAO, Ruize, CAO, Zhiguang, LIM, Andrew, SONG, Wen, ZHANG, Jie
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2021
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/8204
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-9207
record_format dspace
spelling sg-smu-ink.sis_research-92072023-10-04T05:06:02Z Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem LI, Jingwen MA, Yining GAO, Ruize CAO, Zhiguang LIM, Andrew SONG, Wen ZHANG, Jie 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. 2021-09-23T07:00:00Z text https://ink.library.smu.edu.sg/sis_research/8204 info:doi/10.1109/TCYB.2021.3111082 Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Decoding Search problems Reinforcement learning Computer architecture Vehicle routing Routing Optimization Deep reinforcement learning (DRL) heterogeneous CVRP (HCVRP) min-max objective min-sum objective Management Information Systems
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Decoding
Search problems
Reinforcement learning
Computer architecture
Vehicle routing
Routing
Optimization
Deep reinforcement learning (DRL)
heterogeneous CVRP (HCVRP)
min-max objective
min-sum objective
Management Information Systems
spellingShingle Decoding
Search problems
Reinforcement learning
Computer architecture
Vehicle routing
Routing
Optimization
Deep reinforcement learning (DRL)
heterogeneous CVRP (HCVRP)
min-max objective
min-sum objective
Management Information Systems
LI, Jingwen
MA, Yining
GAO, Ruize
CAO, Zhiguang
LIM, Andrew
SONG, Wen
ZHANG, Jie
Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem
description 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.
format text
author LI, Jingwen
MA, Yining
GAO, Ruize
CAO, Zhiguang
LIM, Andrew
SONG, Wen
ZHANG, Jie
author_facet LI, Jingwen
MA, Yining
GAO, Ruize
CAO, Zhiguang
LIM, Andrew
SONG, Wen
ZHANG, Jie
author_sort LI, Jingwen
title Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem
title_short Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem
title_full Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem
title_fullStr Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem
title_full_unstemmed Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem
title_sort deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem
publisher Institutional Knowledge at Singapore Management University
publishDate 2021
url https://ink.library.smu.edu.sg/sis_research/8204
_version_ 1779157224659091456