MINT: Proposition of a New Transit Assignment Algorithm for Frequency Based Networks

MINT: Proposition of a New Transit Assignment Algorithm for Frequency Based Networks


P Palmier, CETE Nord-Picardie, FR


MINT, base on optimal strategies algorithm, is an adaptation to overcome its limits. It is based on the concept of the 'MInimum maximum Time'. A tool is developing. Tests are encouraging, and evaluation on the Greater Paris network is planned.


The concept of optimal strategies was introduced by Spiess - Florian in 1989. The principle is based on the assumption that users of public transport which have a choice of attractive strategies to go to their destination will board into the first vehicle that will arrive, if it belongs to an attractive line.

This algorithm applies to frequency based networks.

The implementation of the algorithm consists of two parts:

· First, start from the destination and determine recursively attractive lines

· Then, distributes the travel demand from the origin to destination successively in proportion of the frequency of attractive lines starting from each node.

The proposed MINT algorithm, while keeping the basic principles of optimal strategies algorithm, propose an adaptation to overcome these limits:

· to take into account travel time in the computation of flows between attractive lines.

· to assign a proportion of the demand in all attractive lines, including transit segments and pedestrian links. (problems of infinite frequency links)

· to split the proportion of the demand between the line in which the user stands and another quicker line that starts at a further node (the problem of infinite frequency of successive segments of the same line)

· to deal with pedestrian only strategies, without assigning 100% of the flows

The Mint algorithm is based on the concept of the ?MInimum maximum Time? which is defined for a node by the minimum sum of travel time and headway for all attractive lines.

If two transit lines have the same travel times but different frequencies, the global expected travel time and the flow results along lines will be strictly identical as those provided by the optimal strategies algorithm.

But if travel times are different, the MINT algorithm will assign a little more traffic on the fastest line to reflect the fact that users prefer to wait for a bus faster if the travel time saved is more important that the additional wait.

In this case, Mint also offers an overall expected travel time slightly lower than in optimal strategies.

The overall expected travel time which are evaluated by either optimal strategies or Mint procedures are based on implicit associated timetables. Optimal strategies suppose that the arrival of the vehicles of all attractive lines are regularly spaced at intervals equal to the headway of the combined frequencies. Mint procedure suppose that the inter-vehicles intervals preserve the sum of headway and travel time.

We can easily prove, considering a uniform arrival of passengers, that Mint algorithm give the minimum expected travel time given a set of attractive lines, building an implicit corresponding timetable.

At first, the algorithm has been tested on basic networks in order to evaluate the concept. Now, CETE Nord-Picardie is developing an experimental software prototype, to adapt the basic concept to more complex networks, in order to evaluate its behaviour, applicability to real and large networks.

First tests are encouraging and it is planned to test further the algorithm on the Greater Paris network, computing performance, and to compare results in terms of flows and travel times with those from optimal strategies.

Later, it is planned to add a congestion module based either on effective headways or not, to analyze whether the continuous nature of the flow repartition along lines as a function of travel time and frequency implies a better convergence. Moreover, as flows repartition is not only based on the frequency proportion of attractive lines, effective headways procedure may be no longer essential.


Association for European Transport