Groupe d’études et de recherche en analyse des décisions

G-2018-98

Distributed integral column generation

, et

The Integral Simplex Using Decomposition (ISUD) algorithm has been developed recently to solve large set partitioning problems (SPPs) in a primal way, i.e., moving from an integer solution to an improved adjacent one until optimality is reached. More recent works intended to enlarge its applications and to increase its performances. We cite namely the distribution version of ISUD called DISUD which implements the multi-agent system approach. In this work, we develop a distributed integral column generation (DICG) algorithm that extends DISUD to the column generation context in order to solve practical vehicle and crew scheduling problems. The computational tests on large bus drivers scheduling and aircrew pairing problems show that DICG gets good results and outperforms a distributed version of the well-known restricted master heuristic (RMH). DICG yields optimal or near optimal solutions in less than one hour.

, 21 pages