Analysis of Service Options

• You can find the code repo here, it has an unlicense.
• Go here to skip straight to the statistical data for each algorithm.

General overview

If you are reading this and are technically inclined you’ll know from your algorithm book of choice that scheduling is one of the canonical examples of an NP hard problem.

In the wild, if your research this, common approaches include the following:

• Using Mathematical programming, for example ILP as demonstrated in this job shop scheduling problem project
• Heuristics, for example genetic algorithms, as demonstrated in this python example
• Simulation, as used by SBB’s Opentrack library.

The particular genus of the scheduling problem that Maytró presents, Single track scheduling, is solved with algorithms that feature common inputs like blocks (spaces between stations upon which only one train can be scheduled) and certain assumptions, such as that trains can cross at stations (not the case in our specific example unfortunately).

Below is an example space time diagram that is typically used to help visualize the problem 1.

• The nodes, S_n, are stations
• The vertices, F_(x,y), are blocks (think a single track stretch between two stations)
• The vertical axis represents time moving forward.
• Each sloping line is a train occupying a block in time.

In order to create a valid schedule, sloping lines within a block can’t intersect.

Scheduling Maytró

The particular problem my code seeks to solve is the scheduling of as many trains as feasible given normal domain constraints (blocks, rolling stock) on three intersecting routes:

• The Nephin: Ballina - Westport
• The Covey: Westport - Ballyhaunis
• The Costello: Ballyhaunis - Ballina

Scenario specific constraints also apply (there are four different scenarios, the baseline being the current service).

The most obvious brute force approach is simply to cycle through every scheduling option, something like (pseudocode)

   schedule = []
   blocks = single_track_sections
   current_station = stations.first
   trains = ordered_trains_waiting_to_enter_first_block

   while trains.any? do
      train = trains.shift
      block = next_block(current_station, blocks)
      if block && block.empty?
         block.train = train
         schedule << train
         current_station = stations[stations.index(current_station) + 1]
      else
         trains.unshift(train)
      end
   end
   return schedule

The former example is superficially similar to the algorithmic approach I take but instead of trying to schedule all trains per open block I optimize for connections, applying practical shortcuts (heuristics) to avoid unnecessary cycles. This is a typical way to tackle a problem like this and produces what are referred to as ‘greedy’ algorithms:

A greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum. – [from Wikipedia]

My goal is to demonstrate that using available resources, given a certain scenario, trains could be scheduled a lot better. The goal is not to find the absolute optimum scheduling possible or indeed to verify that. I have accepted the general constraint that rescheduling existing trains (excepting in a very limited way for option 2) would render any putative solution infeasible.

The heuristic ‘shortcut’ I adopt is to start with existing connections and work back, as opposed to starting from scratch and scheduling every train anew. I then pick the locally optimal scheduling choice for the current connection, fitting in as many new trains as practicable around it before moving on. This trade off makes finding an optimal solution ‘hopeful’ rather than likely but it does generates valid timetables that are a marked improvement on the current one.

Scenarios

The baseline is just the current service and I look that up directly from Iarnród Éireann’s public (but not published) api, that serves their website. This means of course my implementation could and probably will break in the future but given the time I was willing to give this, the easiest thing was to query directly. I coded this initially as a basic cli, you can look up any route.

   $rescue models/scenarios/option_3.rb 20221222 Claremorris Castlebar
   +-------------------------------------------------------------------+
   |                            An Maytró                            |
   +-------------+-----------+-------+-------+---------------+---------+
   | from        | to        | dep   | arr   | info          | trip_id |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 06:09 | 06:28 |               | LCX-0   |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 08:18 | 08:38 | to Westport   | C-0     |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 10:19 | 10:39 | to Westport;  | C-1     |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 12:04 | 12:23 |               | LCX-2   |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 14:04 | 14:23 |               | LCX-4   |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 15:20 | 15:40 | to Westport   | C-2     |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 17:19 | 17:39 | to Westport   | C-3     |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 19:13 | 19:32 |               | LCX-6   |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 20:49 | 21:09 | to Westport   | C-4     |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 22:34 | 22:53 |               | LCX-8   |
   +-------------+-----------+-------+-------+---------------+---------+
   | Claremorris | Castlebar | 23:59 | 00:18 |               | LCL-10  |
   +-------------+-----------+-------+-------+---------------+---------+

The realtime data is the source of all the constants - block durations, turnaround times, station dwell - used to generate schedules in the following scenarios.

Options 1a

One of the problems with the current Maytró is that about half of the trains between Westport and Ballina are unusable due to lousy connections between them. The “improved” scenario (option 1a) first schedules connecting Ballina Manulla trains (Nephin) relative to the time they connect to Dublin - Westport Intercity trains (Covey hereafter). Then next part of the algorithm checks for block conflicts between the current and next schedule trains and attempts to reschedule the next train.

This scenario has one major limitation. Ideally when rescheduling, a check would be run to make sure a suitable path is available for all affected blocks, in this case I haven’t done it for the following reasons:

• Covey trains feed into the busiest section of the rail network (Portarlington - Dublin) and various shared tributaries of single track. Checking the rescheduled train can pass existing trains would be non-trivial
• It turns out the algorithm only needs to reschedule a single Covey train to achieve acceptable results
• This option is not my preferred solution, it’s inferior to Option 2.

Incidentally I did supply an approximation of the results of this exercise as a submission to the new timetable consultation without success or acknowledgement.

Option 2

This is essentially the original “Mayolink” proposal reheated. The approach is to start with the earliest Covey connection and schedule as many Nephin trains as possible until midnight, making sure to keep current connections to and from Dublin. The main difference is that the Nephin railcar runs through to Westport, as opposed to requiring a change. It’s well documented that changing mode extracts a significant penalty in terms of public transport usage, so avoiding it if possible is key to providing a good service.

The scheduling optimizations applied are as follows:

• Add train if time to schedule a full trip from current point to end point and still hit next connection
• If full trip not feasible, try shortened trip (i.e. stop at Castlebar)
• If through trip not possible, return to destination (same service as baseline)

One limitation is that the station layout at Manulla, the junction of the lines, doesn’t have proper crossover facilities. In other words trains can pass each other but depending on the direction travelled an awkward maneuver is required. Could be easily fixed by the installation of a points. Not a deal-breaker either way but worth mentioning.

Option 3

This introduces 15 minute Westport’s Eastern line, referred to here as the Costello.

The approach is to schedule as many trips as are feasible using a newly introduced railcar (the Costello) to run between Claremorris and Westport, connecting with Nephin trains, thus creating unified Maytró service with optimal connections to all towns.

The scheduling optimizations applied are as follows:

• if railcar is in the wrong place (for next connection) run it back
• if connection possible, make the connection
• otherwise just schedule an extra Costello service with no connection.

Option 3b

For option3b the Costello is extended all the way to the border, Ballyhaunis town.

The only optimization here (if you can call it that) is to check if the extension causes a scheduling clash and to remove the train if it does.

A proper approach would have been to introduce an extra block (Ballyhaunis - Claremorris) and schedule from scratch factoring in the passing possibilities therein. The approach here is likely not optimal but still a significant improvement on the status quo.

Option 4

The missing algorithm. This would be the optimal solution aka “Switzerland”. Sadly I haven’t, as of writing, had enough time to investigate this option and it’s worth remarking that it would involve quite a bit of change compared to the others, namely:

• Adding back route flexibility that has been removed over the years, i.e. small passing loops at Foxford, Manulla, Castlebar.
• Bringing average speeds into line with European standards for regional rail.
• Scheduling trains to optimal frequency, given the geography of the line.

Although the above alterations may not sound like particulary outrageous demands in the context of running an efficient railway service, they are nevertheless unlikely to find political favour given orthodox Irish economic thinking.

Be that as it may, just to get a rough idea of what is possible accepting that the aforementioned improvements were made, one could assume the longest block (Foxford to Castlebar) to take about 10 minutes to traverse and all blocks to be roughly equal in length. In such a scenario a headway of ~20 minutes would be theoretically possible, even on a single track.

In other words, in an alternative universe Swiss Mayo, people travelling in either direction between the major towns could expect a train every 20 minutes or so - not too bad!

Comparison of Algorithms

You can further analyse the aforementioned algorithms via an interactive table here

---

1. 1. Single Track Train Scheduling, Jonas Harbering · Abhiram Ranade · Marie Schmidt (January 2015)