Customer case · NS
NS: Why Replanning Trains Is NP-Hard
Every day NS plans the maintenance of its trains to the minute. One late train can break that plan. Repairing it sounds simple, but it belongs to one of the hardest classes of problems in computing. Here is why, and how you solve it anyway.
The case is real. The cities, trains and plans in the interactive examples are illustrative: they show how the problem behaves, not NS's actual planning.
One salesman, too many routes
Start with the most famous puzzle in planning. A salesman has to visit a number of cities, each exactly once, and end where he started. Which order gives the shortest trip? It is called the travelling salesman problem, and it sounds like something for a rainy afternoon.
With five cities there are 12 different round trips, easy to check by hand. With ten there are 181,440. Every city you add multiplies the number of routes by the number of cities already on the map. Move the slider and watch what that does.
This is called combinatorial explosion, and a faster computer barely dents it. A machine a thousand times faster buys you two or three extra cities, not a thousand.
Checking every route, or thinking smarter
The obvious approach is brute force: try every route, keep the shortest. It is guaranteed to find the perfect answer, and for a handful of cities it is fine. Past that it never finishes.
The smarter approach starts with a quick, reasonable route and then improves it. Nearest neighbour simply goes to the closest city it has not visited yet. It is fast, but it paints itself into corners and leaves long jumps at the end. 2-opt then looks for two legs of the route that cross, or that could be shorter the other way round, and reconnects them. Repeat until nothing improves.
Try all three on the same map. Brute force checks thousands of routes to be certain. The smarter pair usually lands on the same route, or within a few percent of it, after a few dozen steps. Then pick 30 cities and try brute force again.
- Route being tried
- Quick first route
- Best route so far
The real question
In practice nobody asks for the perfect plan. The question is: what is the best plan we can find before the next train arrives? That changes the problem from finding the optimum to finding a very good answer, fast, and knowing how good it is.
What NP-hard actually means
The travelling salesman has a strange property. If someone hands you a route, checking how long it is takes a moment. Finding the shortest route yourself has no known shortcut: every method that is guaranteed to find it slows down explosively as the problem grows.
Problems like this are called NP-hard. They are at least as hard as a whole family of problems that are easy to check but, as far as anyone knows, hard to solve. Find a fast exact method for one of them and you have found one for all of them. Whether that is possible at all, the P versus NP question, is one of the seven Millennium Prize Problems, with a million dollars for whoever settles it. Nobody has.
So for NP-hard problems you stop looking for a trick that makes them easy. You look for a smart way to get a very good answer in the time you have.
From salesmen to maintenance tracks
NS has extensive and tightly scheduled maintenance plans for its trains every day. Each train that comes in has its slot, its track and its team. When a train arrives late, the plan can no longer be followed, and it has to be repaired with a replanning algorithm.
The link with the salesman is direct. The cities become the trains to be serviced, the route becomes the order and the track for each train, and the distance becomes the minutes of delay. On top of that come rules the salesman never had: which work fits on which track, which team is free, which train has to leave in time for the evening rush.
Make one train late below and try three ways to repair the day. The catch: a track holds one train at a time, and each crew has prepared for the train the plan sends it. Wait for your own track, and every train behind the late one inherits the delay. Improvise, and each train takes the first free track: trains end up where nobody expected them, crews have to search for parts or a train, and while they are busy with one they are not ready for the next. Within an hour the whole board is reshuffled. A smart replanner looks ahead and moves only what pays off.
- On time
- Late
- Moved: crew not prepared
- Where the plan had it
SLT 2617 is late, and track 1 holds one train at a time. Every train behind it waits for its own track, so the delay rolls down the whole line.
Even this small board, eleven trains on three tracks, can be arranged in 3,113,510,400 ways. The illustration has three tracks, but a real depot has ten or more. With ten tracks and forty trains a day, the number of possible plans grows to 1.7 × 1057, far more than the routes on the 30-city map that made brute force give up. And a new plan is needed within minutes.
That is the travelling salesman problem we started with, in another form. The trains are the cities, the order on each track is the route, and every extra train multiplies the possibilities. Brute force gets stuck here just as it did on the map, and only a smarter approach finds a good plan in time.
Why these problems are so interesting
This is what makes planning problems fascinating rather than tedious. Raw computing power does not win. You win by understanding the problem well enough to know which shortcuts are safe: which parts of the plan can stay as they are, which choices can be ruled out early, where a good answer is likely to be.
And no two are the same. A depot, a delivery fleet, a hospital roster and a production line all look like the salesman from a distance, but each has its own rules, its own goal and its own time limit. An off-the-shelf solver rarely fits. Every one asks for its own, creative solution.
- Start from what you have: repairing a disrupted plan is a different problem from planning from scratch, and often a much smaller one.
- Use the structure: rules that rule out large parts of the search are worth more than a faster computer.
- Trade quality for time on purpose: a method that is within one percent in a minute beats a perfect one that finishes tomorrow.
- Keep more than one method: a quiet morning and a chaotic rush hour call for different approaches.
What we built for NS
Instead of one fixed rule for every disruption, we proposed and applied a new replanning framework, with a total of four solution methods.
- A framework that takes the disrupted plan as its starting point, rather than planning the day from scratch.
- Four solution methods within that framework, each with its own balance between the quality of the new plan and the time it takes to find it.
- A comparison of the methods, so the right one can be chosen for the situation at hand.
Have a planning problem that looks impossible?
Those are the ones we like most. Every one is different, and every one has a smarter way in.