Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems

Amar Oukil, Hatem Ben Amor, Jacques Desrosiers*, Hicham El Gueddari

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

52 Citations (Scopus)


Column generation has proven to be efficient in solving the linear programming relaxation of large scale instances of the multiple-depot vehicle scheduling problem (MDVSP). However difficulties arise when the instances are highly degenerate. Recent research has been devoted to accelerate column generation while remaining within the linear programming framework. This paper presents an efficient approach to solve the linear relaxation of the MDVSP. It combines column generation, preprocessing variable fixing, and stabilization. The outcome shows the great potential of such an approach for degenerate instances.

Original languageEnglish
Pages (from-to)817-834
Number of pages18
JournalComputers and Operations Research
Issue number3
Publication statusPublished - Mar 2007
Externally publishedYes


  • Column generation
  • Degeneracy
  • Multiple-Depot Vehicle Scheduling Problem
  • Stabilization

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research


Dive into the research topics of 'Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems'. Together they form a unique fingerprint.

Cite this