Finding empty berths on 'fully booked' Indian trains: reservation charts as intervals

On Indian Railways, a train can show "waiting list" for days and still leave with empty berths. People cancel late, don't turn up, or book only part of the route. Once the railway prepares the reservation chart, the berth-level picture is public, but it's spread across dozens of coaches and station pairs. Almost nobody can use it by hand.

I built GapSeat to answer one question: is there a berth I can use between my two stations? And if no single berth covers the trip, what's the fewest number of berth changes that does? This post is about the model and the search behind that second answer, which I call seat hopping.

The data: a berth is a list of segments

After the chart is prepared, each berth comes with segments along the train's route: booked from station A to station D, vacant from D to F, booked again from F onwards, and so on. Stations have an order along the route, so the first step is to replace station codes with their index in the schedule.

Two rules matter more than anything else:

1. Segments are half-open intervals. A booking from A to D occupies the legs A→B, B→C and C→D. It does not occupy D→E. The passenger gets off at D, and the berth is free from there.
2. Occupied always wins, and unknown is never vacant. If the data says a leg is both vacant and occupied (it happens when charts overlap), treat it as occupied. If a station isn't in the schedule, ignore that segment instead of guessing.

With stations indexed, a berth becomes a set of vacant legs (leg i is the stretch from station i to station i + 1). Consecutive legs merge into ranges:

List<VacantSeatRange> vacantSeatRanges(SeatResult seat, Map<String, int> index) {
  final vacant = <int>{}, occupied = <int>{};
  for (final s in seat.segments) {
    final from = index[s.from], to = index[s.to];
    if (from == null || to == null || from >= to) continue; // unknown never counts
    for (var i = from; i < to; i++) {
      (s.occupied ? occupied : vacant).add(i);              // half-open: [from, to)
    }
  }
  vacant.removeAll(occupied);                               // occupied wins
  // ...merge sorted consecutive legs into [from, to) ranges
}

Checking whether one berth covers a trip is now a range check: is there a vacant range with from <= boarding and to >= destination?

Seat hopping: a shortest path, built backwards

When no single berth covers the trip, we want a sequence of berths: berth A from your station to Kanpur, then berth B from Kanpur to your destination. We want the fewest changes, because every change means moving your luggage at a station, sometimes into another coach.

Think of each station as a node. Any vacant range that covers station s gives an edge from s to every later station it reaches. The problem is a shortest path, where "shortest" means fewest edges.

The planner works backwards from the destination. For each station, from the last one before the destination back to the boarding station, it keeps the best few ways to finish the trip from there:

final best = <int, List<List<JourneyStep>>>{ to: [[]] };   // at the destination, nothing left to do

for (var start = to - 1; start >= from; start--) {
  // edges: every station reachable from `start` on one berth
  // candidates: one step to `next`, then the best ways on from `next`
  // keep the top `limit`, ranked by number of steps
  best[start] = rank(candidates).take(limit).toList();
}
return best[from];

A few details make the results feel right to a passenger:

• No branch cutoff. Every station is considered as a possible change point. A pruning heuristic would be faster, but it could hide a direct berth or a one-change route, and that's the one result a user must never miss.
• One representative berth per reachable station. When ten berths all go from station 4 to station 9, the path only needs one of them. The results screen still offers the other berths that cover the same stretch, so the user can pick a lower berth or the same coach.
• Staying on the same berth is one step. If the best way on from station 5 starts on the very berth you're already on, the two steps merge. A berth that is vacant across two separate data segments shouldn't look like a change.
• Ranking ties: travel farther first. Between two paths with the same number of changes, prefer the one that keeps you on the first berth longer. People would rather change once near the end than early.
• Deduplicate by station pattern. Two paths that change at the same stations are the same plan for the passenger, so we keep only one.
• Bounds. At most 5 paths, and at most 8 steps per path. Beyond that it isn't a plan anyone would follow.

Each station looks at the vacant ranges that cover it, and each range reaches at most every later station, so the work is roughly proportional to stations × ranges × stations. A long-distance train has well under a hundred halts and fewer than two thousand berths, which runs comfortably on a phone.

Testing the edge cases

Most of the planner's tests are named after a way it could mislead a passenger:

• adjacent legs on the same berth require no seat change
• occupied overlap overrides vacancy, and unknown stations can't prove vacancy
• it doesn't bridge a vacancy gap on the same berth
• it can return to a berth after using another berth through that berth's gap
• it considers transfer stations inside a larger vacant interval
• it finds the direct seat even after many shorter candidate ranges
• it rejects disconnected paths even when the endpoints match

The one I trust most is a property test. It generates 100 seeded random trains and, for each, computes the true minimum number of berths with a separate, deliberately simple search over every station pair. Then it checks three things: the planner's best path uses exactly that many berths, every step of every path really is vacant on its berth, and the planner returns nothing when no path exists. Hand-picked cases catch the bugs you thought of; that test catches the ones you didn't.

The app around it

GapSeat is a Flutter app (with flutter_bloc for state and get_it for dependency injection) plus a static website. A few things that turned out to matter for this audience:

• An offline timetable. The app downloads a compact binary timetable once and queries it in a long-lived worker isolate. Station search and train lists work on a weak connection. Chart and vacancy data always come live, because occupancy can't be cached.
• Hindi, Marathi and Tamil, alongside English, because a lot of the demand comes from Hindi and Hinglish searches.
• TalkBack support across the main vacancy-search journey, so screen-reader users can search a train and read the results.

Limits, honestly

A vacancy result is a snapshot of the published chart. Berths can be booked through current booking or allotted by the TTE after you check. GapSeat doesn't book or allot anything. You still book through IRCTC current booking or a counter, or ask the TTE with a valid ticket. And GapSeat isn't affiliated with IRCTC or Indian Railways.

If you're curious, try the web checker at gapseat.in/chart-vacancy, or get the Android app. I'd love feedback on the planner. Is there a ranking you'd pick differently?