Text

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.

Ketersediaan

Informasi Detail

Judul Seri

INFORMS JOURNAL ON OPTIMIZATION, Vol. 5, No. 2, Spring 2023

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 191-210

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

MACHINE LEARNING
COLUMN GENERATION
ARC SELECTION
HEURISTIC PRICING
VEHICLE ROUTING AND CREW SCHEDULING

Info Detail Spesifik

https://doi.org/10.1287/ijoo.2022.0082

Pernyataan Tanggungjawab

Mouad Morabit, Guy Desaulniers, Andrea Lodi

Versi lain/terkait

Lampiran Berkas

Komentar