An implementation of an algorithm based on SPOT using Viriato's Algorithm Platform.

SPOT [1] is a mathematical model for strategic passenger railway planning building on the well-known PESP (Periodic Event Scheduling Problem [2]). The goal of the SPOT model is to obtain an automatically generated and workable timetable during the strategic planning phase as it aims to provide a passenger-centric timetable.

We want to provide an implementation based on SPOT using Viriato's Algorithm Platform to deliver a software prototype that can be actually used by a subject-matter expert in practice so that the model's results can be assessed by them without any mathematical or programming background. We demonstrate the benefits that come with our Algorithm Platform to the researcher.

We want to highlight the benefits that come with our Algorithm Platform to the researcher:

• Data Acquisition and Provision. The Algorithm Platform retrieves all data requested by the algorithm from Viriato's database and provides it via an interoperable REST interface. There is no need to write database queries.
• Rapid Development. The input data provision and the simple way of passing parameters in combination with the predefined domain data model (AIDM) reduce the development effort considerably.
• Prevention from Misuse. Relying on the Algorithm Platform reduces the chance for the algorithm developer to make errors, and also protects them from erroneous data due to the enforced invariants in Algorithm Platform's Algorithm Interface.
• Visualisation of Results and Reports. The user can easily explore the solution which was written back to Viriato, allowing them to inspect the structure of the results in the available modules and assess their correctness and quality. In addition, reports in form of Excel sheets are generated to present the parameters used and a summary of the solution to the user giving them insights.

Note that our implementation of SPOT deliberately deviates in some aspects from the original model in [1] in order to enhance the applicability in practice. The main goal was to demonstrate the use of the Viriato Algorithm Platform rather than an analysis of the model.

As the input for SPOT we are given a list of origin-destination ("OD") relations describing the travel wishes of a set of passengers, and a set of trains that have a list of defined commercial stop locations and minimum travelling times between these node pairs.

The SPOT model routes passengers through a train network from their origin to their destination by modifying the arrival and departure times of the trains, therefore impacting the total travel times (consisting of transfer times at stations and travel times on trains) of the passengers being routed. The objective is to minimise the total travel time for all passengers of all OD relations.

Figure 1 provides an example timetable generated with SPOT. In our small example, let there be only one OD relation with origin A and destination D. The given trains travel only from A to B, B to C and C to D. Therefore, passengers have to change twice, once in B and again in C. In this simple case where the only relation is for demand from A to D, SPOT has optimised the arrival and departure at both changes, such that the transfer time is minimal.

Figure 1: A graphic timetable for the example with two transfers. (Viriato screenshot).

For this example, we defined five minutes as the required minimum transfer time. The connection clock in Figure 2 allows us to verify that the transfer time at B is minimal, since the train to C departs exactly five minutes after the arrival of the train from A.

Figure 2: A connection clock for station B. (Viriato screenshot).

Our SPOT implementation deviates from the original in [1] in several places for sake of practical applicability.

The SPOT model optimises travel times only for those parts of a train run which are used on a passenger's route. Depending on the input data, it may happen that parts of a train run are not used by any passenger in a SPOT solution, and this implies that the travel time on these parts are not necessarily optimised. Therefore it can happen that a train runs with an unrealistically slow speed on some track section in the solution. In practice, a train often spends a large part of this "idle" time stationary at a station. For sake of simplicity, we cancel these sub-parts in a solution if they occur at the beginning or at the end of a train run, and completely cancel and remove trains which not used at all by the algorithm. Figure 3 shows a timetable, where irrelevant parts of scheduled trains have been cancelled.

Through using the Algorithm Platform's C# API wrapper methods CancelTrain(...), CancelTrainBefore(...) and CancelTrainAfter(...) this is a straightforward operation.

Figure 3: A graphic timetable where all commercially irrelevant parts of trains have been cancelled. (Viriato screenshot).

See 'Cancelling a Train' for a code example.

For sake of simplicity, in this case we chose to neglect the waiting time at a passenger's origin station. Moreover, at present we assume that all passengers of an OD relation select the same travel route. This assumption contrasts with the implementation in [1], where the waiting time at the origin is considered. Therefore, not all passengers of an OD relation travel via the same route. The difference between these two cases can be seen in Figure 4.

Figure 4: Simplified passenger routing (left), original SPOT implementation (right).

A solution of our implementation is shown on the left of Figure 4, where because waiting at A is disregarded, all passengers on the relation A-B use the faster 2nd train. In contrast, on the right hand side we can observe the solution that would be achieved given the full implementation of the SPOT algorithm as defined in [1]. As the waiting time at A is taken into account, some passengers use the slower train since in their case it leads to an overall shorter passenger trip time than waiting for the faster train.

We will present here some features of the Algorithm Platform which assisted with the implementation of this prototype.

Trains with their basic characteristics (travel route, minimum running and dwell times, etc.) from a pool of trains can be used by our prototype to build a SPOT solution. In Viriato, these template trains can be defined conveniently, as shown in Figure 5, and our prototype queries them directly from the Algorithm Platform.

Figure 5: A train run (data anonymised) that can be used as a template train in SPOT. (Viriato screenshot).

See 'Reading Line Characteristics' for a code example.

The Algorithm Platform and the C# API wrapper provide a convenient way to pass user-defined parameters to SPOT. For example, our implementation allows the setting of a bound on the number of allowed transfers for any passenger on their route. Before the algorithm is started, the user enters the desired value using a dialog, as shown in Figure 6.

Figure 6: The dialog to enter the parameters before starting the algorithm. (Viriato screenshot).

See Section 'Passing Parameters' for a code example.

If a template train defined in the section 'Reading Line Characteristics' is selected by the algorithm as forming part of the the solution of the SPOT model, then the external algorithm will write it back to the Algorithm Platform. This consists of two steps. First, the template train is declared to be in the solution set. Then its arrival and departure times, including reserves, are updated and written back to the Algorithm Platform. The resulting timetable can be inspected with Viriato's graphic timetable functionality, see Figure 7.

Figure 7: A resulting graphic timetable. (Viriato screenshot).

See the section 'Writing Trains Back to Viriato' for a code example.

In addition to the persisted timetable results, we also provide Excel sheets that our implementation populates with KPIs, allowing subsequent evaluation and comparison of different solutions. See Figure 8 and Figure 9 for a sample of this output. Generating these reports programmatically is straightforward using the CreateTable(...) and related methods with the C# API wrapper.

Figure 8: Travel time composition per relation generated by Viriato and exported to Excel.

Figure 9: A summary sheet generated by Viriato and exported to Excel.

Our implementation of SPOT uses Viriato's Algorithm Platform through the C# API wrapper. In this section, we highlight some of the methods and demonstrate their application. In addition, we give references to the actual use in our prototype's code.

As the AlgorithmInterface is part of the C# API wrapper for the Algorithm Platform, there is little development effort required to read the line characteristics discussed in the section 'Reading Line Characteristics'.

The following code piece reads a list of IAlgorithmTrain trains from a template train scenario selected by the user with the parameter mask GUI shown in Figure 6.

var spotLines = _algorithmInterface
.GetAlgorithmTrainsParameter("templateTrainsFromScenario")
.Select(t => t.ToSpotLine())
.ToImmutableList();

Link to use in the code.

The previous section showed how to read a parameter from the parameter mask GUI depicted in Figure 6. Here is another example showing how we read out the maximum allowed number of transfers.

var maximalNumberOfTransfers = _algorithmInterface.GetIntParameter("maximalNumberOfTransfersParameterKey");

Link to use in the code.

In order to cancel a train that is not meant to be written back to the solution (see 'Writing Back Planned Trains') we have to specify its ID and request the Algorithm Platform to cancel this train:

_algorithmInterface.CancelTrain(spotTrainToCancel.ID)

Link to use in the code.

As seen in 'Writing Back Planned Trains', the Algorithm Platform also offers methods to write trains back to Viriato. Since SPOT produces a timetable as a result, this feature comes is useful. Using the code sample below we are able to persist the scheduled trains in Viriato via the Algorithm Platform. When we write back a train to Viriato, we initially copy it before updating the times of the passed train path nodes since SPOT assigns arrival and departure times for all trains at all stations.

var copiedTemplateTrain = _algorithmInterface.CopyTrain(templateTrain.ID); // this declares the template train to be persisted.
var spotSolutionTrain = spotSolution.getTrain(templateTrain.ID) // take the train found in the solution of the SPOT Model
var updateTimesTrainPathNodes = spotSolutionTrain
                .TrainPathNodes
                .Zip(copiedTemplateTrain.TrainPathNodes) 
                .Select(e => CreateUpdateTimesTrainPathNode(e.Item1, e.Item2)) // create the node update we want to send to Viriato
                .ToImmutableList();

_algorithmInterface.UpdateTrainTimes(copiedTemplateTrain.ID, updateTimesTrainPathNodes); // save the times to Viriato

To update the train's time along the train path nodes (shown in 'updateTimesTrainPathNodes' in the code snippet above), information from the SPOT solution is combined with the corresponding original template train as shown in the snippet below.

 private static IUpdateTimesTrainPathNode CreateUpdateTimesTrainPathNode(ISpotTrainPathNode spotTpn, IAlgorithmTrainPathNode copiedTpn) {
            return new UpdateTimesTrainPathNode(
                copiedTpn.ID, // reference to the copied train path node
                spotTpn.ArrivalTime, // take the arrival time determinded by the spot solution
                spotTpn.DepartureTime, // take the departure time determinded by the spot solution
                null, // no update necessary. Take the minimum runnning time from the template train
                null, // no update necessary. Take the minimum stopping time from the template train
                spotTpn.StopStatus); // gives if we have a commerical stop or no stop in the solution
        }

For the usage in the prototype, see here. Note that if for any reason the trains in the SpotSolution would be corrupted by the action, then the Algorithm Platform prevents the algorithm from writing back this train into the database as a solution. This ensures that the validity of the solution applying the rules from the railway domain is guaranteed.

Another feature offering development convenience is the AlgorithmsUtils library. It builds an abstraction API around the Gurobi MIP solver. By using the library, we are able to easily generate the MIP that forms the core of SPOT. Below is a code sample that allows us to define a classic PESP [2] constraint enforcing the departure time at a stop t_departure to be equal or later than the arrival time t_arrival plus the minimum stop time ℓ_stop:

Stop duration constraint: t_departure ≥ t_arrival + ℓ_stop - τ * k _stop

var arrivalVar = VariableFactory.CreateArrival(lineConstraint, nodeConstraint);
var departureVar = VariableFactory.CreateDeparture(lineConstraint, nodeConstraint);
var cycleTimeShift = VariableFactory.CreateCycleTimeShift(nodeConstraint, nodeConstraint);
var consName = SpotConstraintNameFactory.CreateStoppingTimeEquationWithStop(ctx.GetCurrentConstraintIndex());
var minStopTime = scenario.TimeConverter.ToModelTime(nodeConstraint.MinStopTime);

var stopTimeConstraint = new Constraint(
    consName,
    new Term(new Monomial(departureVar)),
    ConstraintType.Geq,
    new Term(
        new Monomial(arrivalVar),
        new Monomial(minStopTime),
        new Monomial(-1 * scenario.TimeConverter.ToModelTime(scenario.CycleTime), cycleTimeShift)));

Link to use in the code.

• [1]: 2021 G. J. Polinder, M. Schmidt and D. Huisman, Timetabling for strategic passenger railway planning, Transportation Research Part B: Methodological, DOI: https://doi.org/10.1016/j.trb.2021.02.006
• [2]: 1989 P. Serafini and W. Ukovich, A mathematical model for periodic scheduling problems, SIAM Journal on Discrete Mathematics DOI: https://doi.org/10.1137/0402049