Learning to handle complex constraints for vehicle routing problems

Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. While recent neural methods excel in constructing solutions based on feasibility masking, they struggle with handling complex constraints, especially when obtaining the masking itself is NP-har...

Full description

Saved in:
Bibliographic Details
Main Authors: BI, Jieyi, MA, Yining, ZHOU, Jianan, SONG, Wen, CAO, Zhiguang, WU, Yaoxin, ZHANG, Jie
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2024
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/9814
https://ink.library.smu.edu.sg/context/sis_research/article/10814/viewcontent/2410.21066v1.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-10814
record_format dspace
spelling sg-smu-ink.sis_research-108142024-12-24T03:46:15Z Learning to handle complex constraints for vehicle routing problems BI, Jieyi MA, Yining ZHOU, Jianan SONG, Wen CAO, Zhiguang WU, Yaoxin ZHANG, Jie Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. While recent neural methods excel in constructing solutions based on feasibility masking, they struggle with handling complex constraints, especially when obtaining the masking itself is NP-hard. In this paper, we propose a novel Proactive Infeasibility Prevention (PIP) framework to advance the capabilities of neural methods towards more complex VRPs. Our PIP integrates the Lagrangian multiplier as a basis to enhance constraint awareness and introduces preventative infeasibility masking to proactively steer the solution construction process. Moreover, we present PIP-D, which employs an auxiliary decoder and two adaptive strategies to learn and predict these tailored masks, potentially enhancing performance while significantly reducing computational costs during training. To verify our PIP designs, we conduct extensive experiments on the highly challenging Traveling Salesman Problem with Time Window (TSPTW), and TSP with Draft Limit (TSPDL) variants under different constraint hardness levels. Notably, our PIP is generic to boost many neural methods, and exhibits both a significant reduction in infeasible rate and a substantial improvement in solution quality. 2024-12-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9814 https://ink.library.smu.edu.sg/context/sis_research/article/10814/viewcontent/2410.21066v1.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Artificial Intelligence and Robotics
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Artificial Intelligence and Robotics
spellingShingle Artificial Intelligence and Robotics
BI, Jieyi
MA, Yining
ZHOU, Jianan
SONG, Wen
CAO, Zhiguang
WU, Yaoxin
ZHANG, Jie
Learning to handle complex constraints for vehicle routing problems
description Vehicle Routing Problems (VRPs) can model many real-world scenarios and often involve complex constraints. While recent neural methods excel in constructing solutions based on feasibility masking, they struggle with handling complex constraints, especially when obtaining the masking itself is NP-hard. In this paper, we propose a novel Proactive Infeasibility Prevention (PIP) framework to advance the capabilities of neural methods towards more complex VRPs. Our PIP integrates the Lagrangian multiplier as a basis to enhance constraint awareness and introduces preventative infeasibility masking to proactively steer the solution construction process. Moreover, we present PIP-D, which employs an auxiliary decoder and two adaptive strategies to learn and predict these tailored masks, potentially enhancing performance while significantly reducing computational costs during training. To verify our PIP designs, we conduct extensive experiments on the highly challenging Traveling Salesman Problem with Time Window (TSPTW), and TSP with Draft Limit (TSPDL) variants under different constraint hardness levels. Notably, our PIP is generic to boost many neural methods, and exhibits both a significant reduction in infeasible rate and a substantial improvement in solution quality.
format text
author BI, Jieyi
MA, Yining
ZHOU, Jianan
SONG, Wen
CAO, Zhiguang
WU, Yaoxin
ZHANG, Jie
author_facet BI, Jieyi
MA, Yining
ZHOU, Jianan
SONG, Wen
CAO, Zhiguang
WU, Yaoxin
ZHANG, Jie
author_sort BI, Jieyi
title Learning to handle complex constraints for vehicle routing problems
title_short Learning to handle complex constraints for vehicle routing problems
title_full Learning to handle complex constraints for vehicle routing problems
title_fullStr Learning to handle complex constraints for vehicle routing problems
title_full_unstemmed Learning to handle complex constraints for vehicle routing problems
title_sort learning to handle complex constraints for vehicle routing problems
publisher Institutional Knowledge at Singapore Management University
publishDate 2024
url https://ink.library.smu.edu.sg/sis_research/9814
https://ink.library.smu.edu.sg/context/sis_research/article/10814/viewcontent/2410.21066v1.pdf
_version_ 1820027789380681728