A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem

Ahmed Hadjar
Ahmed Hadjar
[email protected]
Département de mathématiques et génie industriel, École Polytechnique de Montréal, C.P. 6079, succursale Centre-ville, Montréal, Québec, Canada H3C 3A7
Search for more papers by this author
,
Odile Marcotte
Odile Marcotte
[email protected]
Département d’informatique, Université du Québec à Montréal, C.P. 8888, succursale Centre-ville, Montréal, Québec, Canada H3C 3P8
Search for more papers by this author
,
François Soumis
François Soumis
[email protected]
Département de mathématiques et génie industriel, École Polytechnique de Montréal, C.P. 6079, succursale Centre-ville, Montréal, Québec, Canada H3C 3A7
Search for more papers by this author

Département de mathématiques et génie industriel, École Polytechnique de Montréal, C.P. 6079, succursale Centre-ville, Montréal, Québec, Canada H3C 3A7

Search for more papers by this author

Odile Marcotte

[email protected]

Département d’informatique, Université du Québec à Montréal, C.P. 8888, succursale Centre-ville, Montréal, Québec, Canada H3C 3P8

Search for more papers by this author

François Soumis

[email protected]

Département de mathématiques et génie industriel, École Polytechnique de Montréal, C.P. 6079, succursale Centre-ville, Montréal, Québec, Canada H3C 3A7

Search for more papers by this author

Published Online:1 Feb 2006https://doi.org/10.1287/opre.1050.0240

Supplemental Material

opre.54.1.130-sm.pdf (140 KB)

Cited by
- Agricultural robots task allocation via learning-enhanced memetic optimization
  Applied Soft Computing, Vol. 201
- Chance-constrained battery management for electric bus scheduling
  European Journal of Operational Research, Vol. 96
- Optimizing battery electric bus allocations: an integrated approach to cost minimization and evolutionary game theory
  10 December 2025 | Transportation Letters, Vol. 9
- Optimizing Bus Driver Scheduling: A Set Covering Approach for Reducing Transportation Costs
  25 August 2025 | Applied System Innovation, Vol. 8, No. 5
- Dynamic Discretization Discovery for the Multidepot Vehicle Scheduling Problem with Trip Shifting
  Rolf Nelson van Lieshout,
  Thomas van der Schaft
  1 August 2025 | INFORMS Journal on Computing, Vol. 0, No. 0
- Electric vehicle scheduling problem considering time-of-use electricity price
  20 June 2025 | International Journal of Production Research, Vol. 217
- Integrated multi-plant collaborative production, inventory, and hub–spoke delivery of make-to-order products
  30 November 2023 | IISE Transactions, Vol. 57, No. 1
- Optimizing electric bus charging infrastructure deployment under two charging modes considering seasonal differences
  6 November 2023 | Transportation Letters, Vol. 16, No. 9
- Aggregation formulation for on‐site multidepot vehicle scheduling scenario
  26 April 2024 | Computer-Aided Civil and Infrastructure Engineering, Vol. 39, No. 20
- Increasing schedule reliability in the multiple depot vehicle scheduling problem with stochastic travel time
  Omega, Vol. 127
- Millisecond-Scale Real-Time Scheduling of Buses: A Controller-Based Approach
  IEEE Transactions on Intelligent Transportation Systems, Vol. 25, No. 7
- A mixed-integer programming-based Q-learning approach for electric bus scheduling with multiple termini and service routes
  Transportation Research Part C: Emerging Technologies, Vol. 162
- Electric bus charging scheduling on a bus network
  Transportation Research Part C: Emerging Technologies, Vol. 161
- Vehicle Scheduling
  23 May 2024
- Modeling and Solution Approaches for Resource Assignment with Deployment Restrictions
  29 December 2024
- Optimizing Autonomous Transfer Hub Networks: Quantifying the potential impact of self-driving trucks
  EURO Journal on Transportation and Logistics, Vol. 13
- Scheduling of Software Test to Minimize the Total Completion Time
  20 November 2023 | Mathematics, Vol. 11, No. 22
- Branch-and-Price Based Heuristic Algorithm for Fuzzy Multi-Depot Bus Scheduling Problem
  30 October 2023 | International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, Vol. 31, No. 05
- Vehicle and Charging Scheduling of Electric Bus Fleets: A Comprehensive Review
  Journal of Intelligent and Connected Vehicles, Vol. 6, No. 3
- An exact approach for the multi-depot electric bus scheduling problem with time windows
  European Journal of Operational Research, Vol. 306, No. 1
- Exact solution of network flow models with strong relaxations
  7 March 2022 | Mathematical Programming, Vol. 197, No. 2
- A column generation approach for the driver scheduling problem with staff cars
  27 September 2021 | Public Transport, Vol. 14, No. 3
- Electric bus planning & scheduling: A review of related problems and methodologies
  European Journal of Operational Research, Vol. 301, No. 2
- Exact algorithms for the multiple depot vehicle scheduling problem with heterogeneous vehicles, split loads and toll-by-weight scheme
  Computers & Industrial Engineering, Vol. 168
- Crew Assignment with Duty Time Limits for Transport Services: Tight Multicommodity Models
  Anantaram Balakrishnan,
  Prakash Mirchandani,
  Sifeng Lin
  13 December 2021 | Operations Research, Vol. 70, No. 2
- Scheduling the vehicles of bus rapid transit systems: a case study
  2 January 2020 | International Transactions in Operational Research, Vol. 29, No. 1
- The multi-depot electric vehicle scheduling problem with power grid characteristics
  Transportation Research Part B: Methodological, Vol. 155
- Optimization of electric bus scheduling considering stochastic volatilities in trip travel time and energy consumption
  4 May 2021 | Computer-Aided Civil and Infrastructure Engineering, Vol. 36, No. 12
- Solving multi-depot electric vehicle scheduling problem by column generation and genetic algorithm
  Applied Soft Computing, Vol. 112
- Solution approaches for integrated vehicle and crew scheduling with electric buses
  Computers & Operations Research, Vol. 132
- Modeling and solving the multimodal car- and ride-sharing problem
  European Journal of Operational Research, Vol. 293, No. 1
- A column generation-based approach for integrated vehicle and crew scheduling on a single metro line with the fully automatic operation system by partial supervision
  Transportation Research Part E: Logistics and Transportation Review, Vol. 152
- Research on Distribution Strategy of Charging Piles for Electric Vehicles
  IOP Conference Series: Earth and Environmental Science, Vol. 781, No. 4
- Variable fixing heuristics for solving multiple depot vehicle scheduling problem with heterogeneous fleet and time windows
  6 April 2020 | Optimization Letters, Vol. 15, No. 1
- Avoiding redundant columns by adding classical Benders cuts to column generation subproblems
  Discrete Optimization, Vol. 39
- New Exact Techniques Applied to a Class of Network Flow Formulations
  5 May 2021
- An Exact Method for the Multi-Depot Electric Bus Scheduling Problem in Time Windows
  SSRN Electronic Journal, Vol. 54
- Resilience modeling concepts in transportation systems: a comprehensive review based on mode, and modeling techniques
  22 June 2020 | Journal of Infrastructure Preservation and Resilience, Vol. 1, No. 1
- State-of-the-Art Auction Algorithms for Multi-depot Bus Scheduling Problem Considering Depot Workload Balancing Constraints
  30 June 2021 | Fuzzy Information and Engineering, Vol. 12, No. 2
- Collaborative Optimization of Vehicle and Charging Scheduling for a Bus Fleet Mixed With Electric and Traditional Buses
  IEEE Access, Vol. 8
- Exact Branch-Price-and-Cut Algorithms for Vehicle Routing
  Luciano Costa,
  Claudio Contardo,
  Guy Desaulniers
  28 June 2019 | Transportation Science, Vol. 53, No. 4
- A column generation algorithm for vehicle scheduling and routing problems
  Computers & Industrial Engineering, Vol. 130
- Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price Approach
  Journal of Advanced Transportation, Vol. 2019
- A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem
  Transportation Research Part B: Methodological, Vol. 118
- Multiple depot vehicle scheduling with controlled trip shifting
  Transportation Research Part B: Methodological, Vol. 113
- Dantzig–Wolfe decomposition approach to the vehicle assignment problem with demand uncertainty in a hybrid hub-and-spoke network
  13 December 2017 | Annals of Operations Research, Vol. 264, No. 1-2
- A matheuristic for transfer synchronization through integrated timetabling and vehicle scheduling
  Transportation Research Part B: Methodological, Vol. 109
- Managing disruptions in the multi-depot vehicle scheduling problem
  Transportation Research Part B: Methodological, Vol. 105
- Multiple depot ring star problem: a polyhedral study and an exact algorithm
  12 April 2016 | Journal of Global Optimization, Vol. 67, No. 3
- Simple and efficient heuristic approach for the multiple-depot vehicle scheduling problem
  11 September 2015 | Optimization Letters, Vol. 10, No. 7
- New variable depth local search for multiple depot vehicle scheduling problems
  30 October 2014 | Journal of Heuristics, Vol. 22, No. 4
- Coil Batching to Improve Productivity and Energy Utilization in Steel Production
  Lixin Tang,
  Ying Meng,
  Zhi-Long Chen,
  Jiyin Liu
  23 November 2015 | Manufacturing & Service Operations Management, Vol. 18, No. 2
- Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints
  31 March 2016 | Naval Research Logistics (NRL), Vol. 63, No. 2
- A probabilistic model for vehicle scheduling based on stochastic trip times
  Transportation Research Part B: Methodological, Vol. 85
- A Hybrid Heuristic Algorithm for the Intelligent Transportation Scheduling Problem of the BRT System
  17 January 2015 | Journal of Intelligent Systems, Vol. 24, No. 4
- School bus routing based on branch and bound approach
- Planning, operation, and control of bus transport systems: A literature review
  Transportation Research Part B: Methodological, Vol. 77
- Low Carbon Iron-making Supply Chain Planning in Steel Industry
  11 November 2014 | Industrial & Engineering Chemistry Research, Vol. 53, No. 47
- Transit Bus Scheduling with Limited Energy
  Jing-Quan Li
  25 June 2013 | Transportation Science, Vol. 48, No. 4
- Operation and charging scheduling of electric buses in a city bus route network
- The traveling therapist scheduling problem
  28 March 2014 | IIE Transactions, Vol. 46, No. 7
- A branch‐price‐and‐cut algorithm for the min‐max k ‐vehicle windy rural postman problem
  5 October 2013 | Networks, Vol. 63, No. 1
- The Simultaneous Vehicle Scheduling and Passenger Service Problem
  Hanne L. Petersen,
  Allan Larsen,
  Oli B. G. Madsen,
  Bjørn Petersen,
  Stefan Ropke
  2 August 2012 | Transportation Science, Vol. 47, No. 4
- Separating valid odd-cycle and odd-set inequalities for the multiple depot vehicle scheduling problem
  EURO Journal on Computational Optimization, Vol. 1, No. 3-4
- Branch-and-price algorithms for the Two-Echelon Capacitated Vehicle Routing Problem
  17 October 2012 | Optimization Letters, Vol. 7, No. 7
- Vehicle scheduling for suburban public transport
- Stabilized dynamic constraint aggregation for solving set partitioning problems
  European Journal of Operational Research, Vol. 223, No. 2
- A school bus scheduling problem
  European Journal of Operational Research, Vol. 218, No. 2
- Golf course revenue management
  6 November 2009 | Journal of Revenue and Pricing Management, Vol. 10, No. 2
- Branch and Cut
  14 January 2011
- Vehicle Scheduling for Transports in Large-Scale Sports Meeting
- Golf Course Revenue Management
- Transit network timetabling and vehicle assignment for regulating authorities
  Computers & Industrial Engineering, Vol. 59, No. 1
- Solving a real-world train-unit assignment problem
  9 May 2010 | Mathematical Programming, Vol. 124, No. 1-2
- Path-Reduced Costs for Eliminating Arcs in Routing and Scheduling
  Stefan Irnich,
  Guy Desaulniers,
  Jacques Desrosiers,
  Ahmed Hadjar,
  21 September 2009 | INFORMS Journal on Computing, Vol. 22, No. 2
- A new model and heuristic algorithms for the multiple‐depot vehicle scheduling problem
  4 March 2011 | Journal of the Chinese Institute of Engineers, Vol. 33, No. 2
- The Generation of Experimental Data for Computational Testing in Optimization
  26 October 2010
- An overview on vehicle scheduling models
  17 March 2010 | Public Transport, Vol. 1, No. 4
- Iterated local search for the multiple depot vehicle scheduling problem
  Computers & Industrial Engineering, Vol. 57, No. 1
- Optimization of Vehicle Route to Reduce Fuel Consumption Based on Genetic Algorithm
  26 April 2012
- Dynamic window reduction for the multiple depot vehicle scheduling problem with time windows
  Computers & Operations Research, Vol. 36, No. 7
- Research on a Vehicle Routing Schedule to Reduce Fuel Consumption
- On the choice of explicit stabilizing terms in column generation
  Discrete Applied Mathematics, Vol. 157, No. 6
- A Column Generation Algorithm for a Rich Vehicle-Routing Problem
  Alberto Ceselli,
  Giovanni Righini,
  Matteo Salani,
  1 February 2009 | Transportation Science, Vol. 43, No. 1
- A comparison of five heuristics for the multiple depot vehicle scheduling problem
  12 July 2008 | Journal of Scheduling, Vol. 12, No. 1
- Research on Vehicle Routing Problem with Stochastic Demand and PSO-DP Algorithm with Inver-over Operator
  Systems Engineering - Theory & Practice, Vol. 28, No. 10
- Integrated Location-Routing Problem Modeling and GA Algorithm Solving
- Constrained Local Search Method for Bus Fleet Scheduling Problem with Multi-depot with Line Change
- Chapter 2 Public Transit

Volume 54, Issue 1

January-February 2006

Pages ii-200

Article Information

Supplemental Material

Metrics

Information

Received:June 01, 2001
Accepted:October 01, 2004
Published Online:February 01, 2006

Cite as

Ahmed Hadjar, Odile Marcotte, François Soumis, (2006) A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem. Operations Research 54(1):130-149.

https://doi.org/10.1287/opre.1050.0240

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem

Supplemental Material

Volume 54, Issue 1

Article Information

Supplemental Material

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News