Ricardo Saldanha, Head of Innovation, @SISCOG | 5 min read
___________
THE CHALLENGE
Months before the day of operations railroad operators produce detailed plans specifying how their resources are going to be deployed in order to provide the transportation service they want to offer. The plan that defines how rolling stock is going to be utilized in network operations is called the rolling stock rotation plan. It is composed of a set of rotations, where each rotation defines in the form of a repetitive pattern the sequence of operations to be performed by rolling stock units of the same type over a limited or unlimited number of calendar weeks. These operations include providing transportation and traction capacity for scheduled train trips as well as periodic maintenance opportunities according to the business rules.
Because railroad operators want to use their resources in the most efficient way, they look for tools that are capable of producing operational plans such as rolling stock rotations (hereafter rotations) automatically and in an optimized way. This is why VIA Rail Canada (VIA) and SISCOG developed a project some years ago. The challenge was to provide to VIA algorithmic support for producing rotations that bring increased profit by adjusting, in a smart way, seat capacity to passenger demand on each train trip.
SISCOG's algorithmics team was chosen to face this challenge. The starting point was a set of legacy algorithms previously developed by the team and the literature on optimization of rolling stock. Both addressed this problem as a cost minimization problem with the passenger demand being modelled as a hard or soft constraint. This approach was not suitable for railroad operators, like VIA, that run trains with reserved seats because in this context the maximization of profit cannot be achieved just by minimizing costs, it should also consider revenue. On the other hand, revenue management approaches described in the literature tend to ignore or oversimplify operational costs.
SISCOG's algorithmics team developed a new hybrid approach for solving approximately the Maximum Profit Rolling Stock Rotation Planning problem.
______________________
In order to overcome these limitations, our team developed a new hybrid approach for solving approximately the Maximum Profit Rolling Stock Rotation Planning (MPRSRP) problem with maintenance constraints assuming fixed ticket prices.
We describe the approach and how it is successfully being used in practice by VIA to plan their intercity locomotive-hauled operation along a corridor that connects Toronto, Montreal and Quebec City.
The MPRSRP problem can be stated in the following way: given a set of train trips each one with its own passenger demand (for business and economy class), find, from scratch, for a standard week, the most profitable rotations that assign a vehicle composition (hereafter composition) to each trip that covers all or part of the demand and that satisfy all operational constraints, namely maintenance constraints and many others. The overall profit is equal to the revenue minus the operational cost, where revenue is derived from the expected tickets sold (obtained by matching demand with train capacity for economy and business class), and cost includes aspects like track occupation, fleet depreciation, maintenance and energy consumption, and crew utilization.
In the context of VIA every rotation must comply with the following maintenance constraints: a maintenance of type B must be performed every week, and type C every two weeks, with the particularity that maintenance C includes B.
In the context of VIA rotations comply also with a special requirement. The composition assigned to each trip has two parts: one, called the "base composition", formed with vehicles that always circulate together as shown in Figure 1; and a second part formed with vehicles that don't have this restriction. The base composition is usually formed by a locomotive, a business and an economy carriage, but it can also include more economy carriages and a second locomotive in the rear.
Figure 1: Locomotive rotation showing the base composition where it belongs to (inside the red dotted rectangle).
THE SOLUTION
Since the problem cannot be solved exactly, due to the size of the VIA's problem instances, we developed an optimizer that uses an approximate solution method that is inspired on the concept of base composition described earlier. This optimizer is part of FLEET, a software product for scheduling and managing the network operations of rolling stock which is being used by VIA.
The solution method solves the problem in two stages:
- Produce rotations for the base composition,
- Produce rotations for the extra carriages used to form compositions that are extensions of the base compositions obtained in the first stage.
The first stage is solved by an adapted version of the heuristic used by CREWS(1), based on Lagrangian relaxation and column generation, which solves a minimum cost set covering problem with additional constraints where:
- set elements represent trips,
- sets represent rotations defined for specific composition types,
- cost represents loss (cost minus revenue) of rotations,
- additional constraints model fleet size restrictions for each vehicle type.
Apart from making this mapping, we also adapted the pricing procedure (which explores paths in a trip graph) to solve a resource constrained shortest path problem with a dynamic programming algorithm where resources were set up properly to rule out paths in the trip graph that correspond to rotations violating maintenance or any other relevant constraint. We also made adjustments in the trip graph to accommodate the concept of rotation.
The new and hybrid fleet optimization solution can be applied to any railroad operator.
______________________
The second stage is solved with an approach that uses an hypergraph network model. In our case the hypergraph only contains hyperarcs related with the extra carriages that are used to enlarge the compositions obtained in the first stage. This reduces considerably the overall number of hyperarcs to a number that makes the problem tractable. In order to maximise profit this model favors (avoids) the assignment of extra carriages to trips with lack (excess) of seats.
REMARK: Although the presented solution method was inspired in the concept of base composition, specific to VIA, it can be applied to any railroad operator. It is just a matter of reducing the base composition to a single vehicle, e.g. a locomotive.
IMPACT
The performance of our approach was benchmarked against human planners. As a direct result of using FLEET in production environment VIA reported the following gains with respect to previous rotations (produced manually by human planners):
- 10,000,000 CAD of annual savings due to being able to operate all trips with one less composition,
- 3% to 5% increase in revenue,
- 3% to 4% increase in available seats per mile.
CONCLUSION
We addressed a fleet optimization problem that is relevant for train operations with reserved seats. Because practical problem instances cannot be solved exactly we proposed an approximate solution method that combines existing techniques in a new way. By using this approach in production environment, VIA Rail Canada obtained significant revenue growths and cost savings.
(1) CREWS is an award-winning software product for the optimized planning and management of staff.