paper-with-me

홈 › Papers

Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation

2022-07-20 · Qiaoyue Tang, Yangzhe Kong, Lemeng Pan, Choonmeng Lee

Vehicle Routing Problems (VRPs) in real-world applications often come with various constraints, therefore bring additional computational challenges to exact solution methods or heuristic search approaches. The recent idea to learn heuristic move patterns from sample data has become increasingly promising to reduce solution developing costs. However, using learning-based approaches to address more types of constrained VRP remains a challenge. The difficulty lies in controlling for constraint violations while searching for optimal solutions. To overcome this challenge, we propose a Reinforcement Learning based method to solve soft-constrained VRPs by incorporating the Lagrangian relaxation technique and using constrained policy optimization. We apply the method on three common types of VRPs, the Travelling Salesman Problem with Time Windows (TSPTW), the Capacitated VRP (CVRP) and the Capacitated VRP with Time Windows (CVRPTW), to show the generalizability of the proposed method. After comparing to existing RL-based methods and open-source heuristic solvers, we demonstrate its competitive performance in finding solutions with a good balance in travel distance, constraint violations and inference speed.

📄 PDF Abstract BibTeX arXiv:2207.09860

Code (0)

등록된 구현이 없습니다.

Tasks

Heuristic Search

Methods 이 논문이 사용한 방법론

Travel 설명 없음

Similar Papers 제목 키워드 기반

Learning a Transferable Scheduling Policy for Various Vehicle Routing Problems based on Graph-centric Representation Learning

2021-01-01 · Inwook Kim, Jinkyoo Park

Reinforcement learning has been used to learn to solve various routing problems. however, most of the algorithm is restricted to finding an optimal routing strategy for only a single vehicle. In addition, the trained pol…

Graph Neural Networkreinforcement-learningReinforcement LearningReinforcement Learning (RL)+2

Learn to Solve Vehicle Routing Problems ASAP: A Neural Optimization Approach for Time-Constrained Vehicle Routing Problems with Finite Vehicle Fleet

2024-11-07 · Elija Deineko, Carina Kehrt

Finding a feasible and prompt solution to the Vehicle Routing Problem (VRP) is a prerequisite for efficient freight transportation, seamless logistics, and sustainable mobility. Traditional optimization methods reach the…

BenchmarkingCombinatorial OptimizationDecoder

Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach

2020-02-13 · Ke Zhang, Meng Li, Zhengchao Zhang, Xi Lin 외

Multi-vehicle routing problem with soft time windows (MVRPSTW) is an indispensable constituent in urban logistics distribution systems. Over the past decade, numerous methods for MVRPSTW have been proposed, but most are …

Computational EfficiencyDecoderMulti-agent Reinforcement Learningreinforcement-learning+2

Enhancing Column Generation by Reinforcement Learning-Based Hyper-Heuristic for Vehicle Routing and Scheduling Problems

2023-10-15 · Kuan Xu, Li Shen, Lindong Liu

Column generation (CG) is a vital method to solve large-scale problems by dynamically generating variables. It has extensive applications in common combinatorial optimization, such as vehicle routing and scheduling probl…

Combinatorial OptimizationScheduling

C. H. Robinson Uses Heuristics to Solve Rich Vehicle Routing Problems

2019-12-31 · Ehsan Khodabandeh, Lawrence V. Snyder, John Dennis, Joshua Hammond 외

We consider a wide family of vehicle routing problem variants with many complex and practical constraints, known as rich vehicle routing problems, which are faced on a daily basis by C.H. Robinson (CHR). Since CHR has ma…