Machine-learning-based arc selection for constrained shortest path problems in column generation
Column generation is an iterative method used to solve a variety of optimization problems. It decomposes the problem into two parts: a master problem, and one or more pricing problems (PP). The total computing time taken by the method is divided between these two parts. In routing or scheduling applications, the problems are mostly defined on a network, and the PP is usually an NP-hard shortest path problem with resource constraints. In this work, we propose a new heuristic pricing algorithm based on machine learning. By taking advantage of the data collected during previous executions, the objective is to reduce the size of the network and accelerate the PP, keeping only the arcs that have a high chance to be part of the linear relaxation solution. The method has been applied to two specific problems: the vehicle and crew scheduling problem in public transit and the vehicle routing problem with time windows. Reductions in computational time of up to 40% can be obtained.
Code (0)
등록된 구현이 없습니다.
Tasks
ARCBIG-bench Machine LearningSchedulingSimilar Papers 제목 키워드 기반
Solving Constrained Stochastic Shortest Path Problems with Scalarisation
Constrained Stochastic Shortest Path Problems (CSSPs) model problems with probabilistic effects, where a primary cost is minimised subject to constraints over secondary costs, e.g., minimise time subject to monetary budg…
(Machine) Learning to Improve the Empirical Performance of Discrete Algorithms
This paper discusses a data-driven, empirically-based framework to make algorithmic decisions or recommendations without expert knowledge. We improve the performance of two algorithmic case studies: the selection of a pi…
BIG-bench Machine LearningLogic-Constrained Shortest Paths for Flight Planning
The logic-constrained shortest path problem (LCSPP) combines a one-to-one shortest path problem with satisfiability constraints imposed on the routing graph. This setting arises in flight planning, where air traffic cont…
A Constrained Randomized Shortest-Paths Framework for Optimal Exploration
The present work extends the randomized shortest-paths framework (RSP), interpolating between shortest-path and random-walk routing in a network, in three directions. First, it shows how to deal with equality constraints…
Reinforcement LearningOn an exact method for the constrained shortest path problem
The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column-generation solution methods fo…
Scheduling