MCF - A network simplex implementation: Vehicle scheduling in public transit and Lagrangean pricing This paper investigates the solution of the linear programming relaxation of the multi-commodity flow formulation of the multiple-depot vehicle scheduling problems arising in public mass transit. We develop a column generation technique that makes it possible to solve the huge linear programs that come up there. The technique, which we call Lagrangean pricing, is based on two different Lagrangean relaxations.par We describe in detail the basic ingredients of our approach and give computational results for large-scale test data (with up to 70 million variables) from three German public transportation companies. Because of these results, we propose Lagrangean pricing as one of the basic ingredients of an effective method to solve multiple-depot vehicle scheduling problems to proven optimality. (Source:

References in zbMATH (referenced in 24 articles )

Showing results 1 to 20 of 24.
Sorted by year (citations)

1 2 next

  1. Guedes, Pablo Cristini; Lopes, William Prigol; Rohde, Leonardo Rosa; Borenstein, Denis: Simple and efficient heuristic approach for the multiple-depot vehicle scheduling problem (2016)
  2. Kovács, Péter: Minimum-cost flow algorithms: an experimental evaluation (2015)
  3. Groiez, Mounira; Desaulniers, Guy; Hadjar, Ahmed; Marcotte, Odile: Separating valid odd-cycle and odd-set inequalities for the multiple depot vehicle scheduling problem (2013)
  4. Sadykov, Ruslan; Vanderbeck, François: Column generation for extended formulations (2013)
  5. Benchimol, Pascal; Desaulniers, Guy; Desrosiers, Jacques: Stabilized dynamic constraint aggregation for solving set partitioning problems (2012)
  6. Kim, Byung-In; Kim, Seongbae; Park, Junhyuk: A school bus scheduling problem (2012)
  7. Dahl, Geir; Flatberg, Truls: Reconstructing (0,1)-matrices from projections using integer programming (2009)
  8. Hadjar, Ahmed; Soumis, François: Dynamic window reduction for the multiple depot vehicle scheduling problem with time windows (2009)
  9. Oliveira, Francisco P.M.; Tavares, João Manuel R.S.: Matching contours in images through the use of curvature, distance to centroid and global optimization with order-preserving constraint (2009)
  10. Raith, Andrea; Ehrgott, Matthias: A two-phase algorithm for the biobjective integer minimum cost flow problem (2009)
  11. Raith, Andrea; Ehrgott, Matthias: A comparison of solution strategies for biobjective shortest path problems (2009)
  12. Oliveira, Francisco.P.M.; Tavares, Joao Manuel R.S.: Algorithm of dynamic programming for optimization of the global matching between two contours defined by ordered points (2008)
  13. Oukil, Amar; Ben Amor, Hatem; Desrosiers, Jacques; El Gueddari, Hicham: Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems (2007)
  14. Bastos, Luísa F.; Tavares, João Manuel R.S.: Matching of objects nodal points improvement using optimization (2006)
  15. Choi, Dae-Sik; Choi, In-Chan: On the effectiveness of the linear programming relaxation of the 0-1 multi-commodity minimum cost network flow problem (2006)
  16. Frangioni, Antonio; Manca, Antonio: A computational study of cost reoptimization for min-cost flow problems (2006)
  17. Hadjar, Ahmed; Marcotte, Odile; Soumis, François: A branch-and-cut algorithm for the multiple depot vehicle scheduling problem (2006)
  18. Geunes, Joseph (ed.); Pardalos, Panos M. (ed.): Supply chain optimization. (2005)
  19. Huisman, Dennis; Jans, Raf; Peeters, Marc; Wagelmans, Albert P.M.: Combining column generation and Lagrangian relaxation (2005)
  20. Avella, Pasquale; Boccia, Maurizio; Sforza, Antonio: Solving a fuel delivery problem by heuristic and exact approaches. (2004)

1 2 next