CREW SCHEDULING : Past and Future

CREW SCHEDULING : Past and Future

Canadian Mathematical Society Montral, December 11 -13, 1999 Jacques Desrosiers cole des Hautes tudes Commerciales & GERAD Montral, Canada H3T 2A7 [email protected] The Mathematics behind Vehicle Routing and Crew Scheduling This presentation describes the significant advances made in time-constrained routing and scheduling. Helped by continuously better insights into problem structures and rapid advances in computer technology, the optimization methods are becoming a viable tool for solving practical size problems. SUCCESSFUL APPLICATIONS

Vehicle Routing with Time Windows Dial-a-Ride for Physically Disabled Persons Urban Transit Crew Scheduling Multiple Depot Vehicle Scheduling Aircraft Routing Crew Pairing

Crew Rostering (Pilots & Flight Attendants) Locomotive and Car Assignment The GENCOL Optimizer at the Core of Various Software Systems CREW-OPT BUS-OPT ALTITUDE-Pairings

ALTITUDE-Rosters ALTITUDE-PBS RAIL-WAYS 60 installations around the world RESEARCH TRENDS Accelerating Techniques

Primal - Dual Stabilization Constraint Aggregation Sub-Problem Speed-up Two-level Problems Solved with Benders Decomposition Integer Column Generation with Interior Point Algorithm Acceleration Techniques Column Generator Master Problem Global Formulation

Heuristics Re-Optimizers Pre-Processors to obtain Primal & Dual Solutions Acceleration Techniques ... Multiple Columns: selected subset close to expected optimal solution Early & Multiple Branching & Cutting: quickly gets local optima

Partial Pricing in case of many Sub-Problems Branching & Cutting: on integer variables ! Primal - Dual Stabilization min cx Ax y1 y2 b x 0 0 y1 1 ,0 y2 2 Perturbed Primal

min cx Ax b x 0 max b A c max b A c d1 d 2 Restricted Dual min cx d1 y1 d 2 y 2

Ax y1 y 2 b 0 y1 1 , x 0 0 y 2 2 Stabilized Primal Primal - Dual Stabilization ... Dual Solution Primal Solution Primal Solution Dual Solution Approximate Primal & Dual

Primal & Dual Solutions Constraint Aggregation Massive Degeneracy on Set Partitioning Problems A pilot covers consecutive flights on the same aircraft A driver covers consecutive legs on the same bus line Aggregate Identical Constraints on Non-zero Variables Aggregation Algorithm Initial Constraint Aggregation Consider only Compatible Variables Solve Aggregated Master Problem

Primal & Aggregated Dual Solutions Dual Variables Split-up Solve Sub-Problem Modify Constraint Aggregation Sub-Problem Speed-up Resource Constrained Shortest Path Labels at each node : cost, time, load, n A Resource Projection R R m

Adjust A dynamically Generalized Lagrangian Relaxation 4 Results on R R 2 Sub-Problem cpu time divided by 5 to 10 mn Two-Level Problems Benders Decomposition Algorithm

for Simultaneous Assignment of Buses and Drivers Aircraft and Pilots Pairings and Rosters Locomotives and Cars IP(X, Y) for Two-Level Scheduling B&B(Y) with MIP(X, y) at each node MIP(X, y) solved using Benders Decomposition Master Sub-Problem IP(X) Simplex and B&B(X) solved by Column Generation

MP LP(y) of Set Partitioning SP DP for Constrained Paths Benders MP CG MP LP CG SP DP B&B

Benders SP IP Column Generation with Interior Point Algorithm ACCPM Algorithm (Goffin & Vial) Applications Linear Programming Non-Linear Programming Stochastic Programming Variational Inequalities

Integer Column Generation with Interior Point Algorithm Strategic Grant in Geneva J.-P. Vial et al. Strategic Grant in Montral J.-L. Goffin et al. Design of a Commercial Software System CONCLUSIONS

Larger Problems to Solve Mixing of Decomposition Methods Strong Exact and Heuristic Algorithms Faster Computers Parallel Implementations Still a lot of work to do !!

Recently Viewed Presentations

  • Industry, Urbanization, Immigration and the Gilded Age

    Industry, Urbanization, Immigration and the Gilded Age

    Horatio Alger "Myth of the Self Made Man" ... Alger's book, Sink or Swim helped . Also Supporter of capitalism. Acres of Diamonds. Conwell. Social Darwinism. Based on the scientific studies of Charles Darwin-Natural Selection. Ideas are applied to society...
  • Performance and Overhead in a Hybrid Reconfigurable Computer

    Performance and Overhead in a Hybrid Reconfigurable Computer

    K1 K2 K3 KN Generated by the DES breaker L2 MIOC L2 PCI Slot SNAP Private Memory mP Board Xeon mP L2 PCI Slot MIOC Private Memory SNAP L2 mP Board Control Chip On-Board Memory (24 MB) (6x) User Chip...
  • Chapter 3 Convective Dynamics - University of Oklahoma

    Chapter 3 Convective Dynamics - University of Oklahoma

    Convective Dynamics ... environments in which they form, and weather produced. The most basic classification includes: Single-cell or air-mass storm Typically last 20-30 minutes. ... NSSL Life cycle of a non-severe single cell storm in weak wind shear Radar history...
  • Thach Ha Women Union

    Thach Ha Women Union

    HLHPN huyện Thạch Hà - Hà Tĩnh THACH HA WOMEN UNION Chia sẻ một số hoạt động của HPN liên quan đến dự án mỏ sắt Thạch Khê
  • AMERICAS ARMY: THE STRENGTH OF THE NATION CBA

    AMERICAS ARMY: THE STRENGTH OF THE NATION CBA

    The CBA problem statement (from Step 1) usually states or implies a desired benefit (the primary benefit). Ask the question: How well does this COA achieve the benefit implied in the problem statement? CBA problem statement: Identify the optimum process...
  • Cost Management Certificate Course (CMCC) Naval Postgraduate School

    Cost Management Certificate Course (CMCC) Naval Postgraduate School

    Toward this end, we have fielded the General Fund Enterprise Business System (GFEBS) to more than 11,000 users at 14 major installations. As reported by the Government Accountability Office, GFEBS development is on schedule and on budget. Much more than...
  • Bad PowerPoint Presentations And How To Avoid Them

    Bad PowerPoint Presentations And How To Avoid Them

    Bad PowerPoint Presentations And How To Avoid Them The addition of visual aids to a presentation provide the presenter with many advantages. Recent studies from the University of Minnesota indicate that the benefits are immense: 43% increase in action being...
  • Advancement Flap for Recalcitrant Posterior Leg Ulceration Nisha

    Advancement Flap for Recalcitrant Posterior Leg Ulceration Nisha

    Angiosomes were first described by Taylor and Palmer in 1987 in which they defined three-dimensional vascular territories supplied by source arteries and veins to each tissue layer between the skin and bone.6 The leg has arterial supply from the popliteal,...