Cross-problem learning for solving vehicle routing problems

Existing neural heuristics often train a deep architecture from scratch for each specific vehicle routing problem (VRP), ignoring the transferable knowledge across different VRP variants. This paper proposes the cross-problem learning to assist heuristics training for different downstream VRP varian...

Full description

Saved in:
Bibliographic Details
Main Authors: LIN, Zhuoyi, WU, Yaoxin, ZHOU, Bangjian, CAO, Zhiguang, SONG, Wen, ZHANG, Yingqian, JAYAVELU, Senthilnath
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2024
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/9330
https://ink.library.smu.edu.sg/context/sis_research/article/10330/viewcontent/2404.11677v3.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-10330
record_format dspace
spelling sg-smu-ink.sis_research-103302024-09-26T07:39:00Z Cross-problem learning for solving vehicle routing problems LIN, Zhuoyi WU, Yaoxin ZHOU, Bangjian CAO, Zhiguang SONG, Wen ZHANG, Yingqian JAYAVELU, Senthilnath Existing neural heuristics often train a deep architecture from scratch for each specific vehicle routing problem (VRP), ignoring the transferable knowledge across different VRP variants. This paper proposes the cross-problem learning to assist heuristics training for different downstream VRP variants. Particularly, we modularize neural architectures for complex VRPs into 1) the backbone Transformer for tackling the travelling salesman problem (TSP), and 2) the additional lightweight modules for processing problem-specific features in complex VRPs. Accordingly, we propose to pre-train the backbone Transformer for TSP, and then apply it in the process of fine-tuning the Transformer models for each target VRP variant. On the one hand, we fully fine-tune the trained backbone Transformer and problem-specific modules simultaneously. On the other hand, we only fine-tune small adapter networks along with the modules, keeping the backbone Transformer still. Extensive experiments on typical VRPs substantiate that 1) the full fine-tuning achieves significantly better performance than the one trained from scratch, and 2) the adapter-based fine-tuning also delivers comparable performance while being notably parameter-efficient. Furthermore, we empirically demonstrate the favorable effect of our method in terms of cross-distribution application and versatility. 2024-08-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/9330 info:doi/10.24963/ijcai.2024/769 https://ink.library.smu.edu.sg/context/sis_research/article/10330/viewcontent/2404.11677v3.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
LIN, Zhuoyi
WU, Yaoxin
ZHOU, Bangjian
CAO, Zhiguang
SONG, Wen
ZHANG, Yingqian
JAYAVELU, Senthilnath
Cross-problem learning for solving vehicle routing problems
description Existing neural heuristics often train a deep architecture from scratch for each specific vehicle routing problem (VRP), ignoring the transferable knowledge across different VRP variants. This paper proposes the cross-problem learning to assist heuristics training for different downstream VRP variants. Particularly, we modularize neural architectures for complex VRPs into 1) the backbone Transformer for tackling the travelling salesman problem (TSP), and 2) the additional lightweight modules for processing problem-specific features in complex VRPs. Accordingly, we propose to pre-train the backbone Transformer for TSP, and then apply it in the process of fine-tuning the Transformer models for each target VRP variant. On the one hand, we fully fine-tune the trained backbone Transformer and problem-specific modules simultaneously. On the other hand, we only fine-tune small adapter networks along with the modules, keeping the backbone Transformer still. Extensive experiments on typical VRPs substantiate that 1) the full fine-tuning achieves significantly better performance than the one trained from scratch, and 2) the adapter-based fine-tuning also delivers comparable performance while being notably parameter-efficient. Furthermore, we empirically demonstrate the favorable effect of our method in terms of cross-distribution application and versatility.
format text
author LIN, Zhuoyi
WU, Yaoxin
ZHOU, Bangjian
CAO, Zhiguang
SONG, Wen
ZHANG, Yingqian
JAYAVELU, Senthilnath
author_facet LIN, Zhuoyi
WU, Yaoxin
ZHOU, Bangjian
CAO, Zhiguang
SONG, Wen
ZHANG, Yingqian
JAYAVELU, Senthilnath
author_sort LIN, Zhuoyi
title Cross-problem learning for solving vehicle routing problems
title_short Cross-problem learning for solving vehicle routing problems
title_full Cross-problem learning for solving vehicle routing problems
title_fullStr Cross-problem learning for solving vehicle routing problems
title_full_unstemmed Cross-problem learning for solving vehicle routing problems
title_sort cross-problem learning for solving vehicle routing problems
publisher Institutional Knowledge at Singapore Management University
publishDate 2024
url https://ink.library.smu.edu.sg/sis_research/9330
https://ink.library.smu.edu.sg/context/sis_research/article/10330/viewcontent/2404.11677v3.pdf
_version_ 1814047911446577152