Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
SQL-o1: Automatic Text-to-SQL Program Synthesis via Self-Reward Heuristic Search
A Survey on Mathematical Reasoning and Optimization with Large Language Models
KBQA-o1: Agentic Knowledge Base Question Answering with Monte Carlo Tree Search
On Parallel External-Memory Bidirectional Search
LLM-Virus: Evolutionary Jailbreak Attack on Large Language Models
HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs
토론
이 논문과 연결된 포럼 글이 아직 없습니다.