A method for building at least one optimal itinerary for use by a user to plan a trip travelling in a multimodal transportation network according to the earliest arrival time and the number of transfers in the multimodal transportation network or the latest departure time and the number of transfers in the multimodal transportation network by creating a set of feasible transfers T (t, L′) for a trip t of line L, for each target line L′ from a set of all transfers from line L to all other lines to determine an itinerary from an origin to a destination, comprising:
- (a) electronically computing, using an electronic processor and electronic memory, for each origin line L, a set of feasible transfers between stations of the origin line L and a destination line L′ such that when ΔTfp(L@i,L′@j) is defined, (i, L′@j, ΔTfp(L@i,L′@j) is added to the set of feasible transfers for L, i being an index in a stop sequence, L@i being a stop along destination line L, L′@j being a stop along destination line L′, ΔTfp(L@i,L′@j) being a transfer duration between stop L@i and stop L′@i,
- (b) electronically sorting such that a previously added transfer is prevented from being dominated by a later added transfer, using an electronic processor and electronic memory, by destination line L′, the computed set of feasible transfers to create an ordered transfer set T (L), the computed set of feasible transfers being electronically sorted by decreasing origin line index;
- (c) electronically determining, using an electronic processor and electronic memory, for each trip t of the origin line L, and for each transfer in the ordered transfer set T (L), an earliest trip t′ of L′ wherein the transfer is feasible;
- (d) electronically adding, using an electronic processor and electronic memory, for each trip t of the origin line L, the determined transfer from t to t′ to the set of feasible transfers T (t, L′) (i) when trip t′ is an only destination trip of the transfers in the set of feasible transfers T (t, L′) passing at a destination station and (ii) when trip t′ is earlier than all previous destination trips of the transfers in the set of feasible transfers T (t, L′) passing by the destination station;
- (e) electronically determining, using an electronic processor, electronic memory, and the set of feasible transfers T (t, L′), a set of possible initial trips as a function of a departure location, and a set of possible final trips as a function of an arrival location, in a multimodal transportation network;
- and
- (f) electronically performing, using an electronic processor and electronic memory, a routing optimization algorithm to electronically compute a Pareto front, said routing optimization algorithm, using the computed Pareto front, building, among itineraries having a main part from an initial trip belonging to the set of possible initial trips to a final trip belonging to the set of possible final trips, at least one optimal itinerary according to the earliest arrival time and the number of transfers or the latest departure time and the number of transfers, when considering only trips from the set of possible trips using selected transportation modes, and only transfers from the set of feasible transfers between considered trips;
- wherein said electronically computing, for each origin line L, feasible transfers between stations of the origin line L and a destination line L′ and said electronically sorting the computed feasible transfers to prevent a previously added transfer from being dominated by a later added transfer minimizes a number of electronic computations needed for determining the set of feasible transfers T (t, L′).