From chains to journeys

This page describes the output step of a public transport component: how it puts a pre-transport leg before and a post-transport leg after the chains of the chain cache, per origin block and departure moment, and keeps the Pareto front of the journeys per origin-destination pair. The walking and cycling legs come from Walking and cycling legs, the chains from Public transport. The direct trips (WW, CC, Car) are components of their own and do not take part in a public transport component; see Components and merging.

The step is in NetworkSetup.dms (impl), NetworkSetup/PublicTransport.dms and NetworkSetup/PublicTransport/PerDepartureMoment_T.dms.

Contents

Step 1: the legs of the component

A public transport component has one pre-transport type and one post-transport type, which follow from its name (Impl/ComponentName): C_RM_PT_OVf_C, for example, cycles to a rail or metro stop and takes the OV-fiets after the last stop. Impl/PT_PreTransport_Types and Impl/PT_PostTransport_Types hold the two types. Their legs are prepared once for all origin blocks, in NetworkSetup/impl:

  • V_org holds the pre-transport legs of all origins, from PublicTransport_Prep/Legs/<type>/ODMatrix, with the origin block and the part (step 3) of each leg.
  • N holds the post-transport legs to all destinations.
  • IsVStop marks the places where a pre-transport leg of the component ends.

Per leg these hold:

  • impedance, the time of the leg including the start and parking times of a cycling leg (Duration_seconds_ext);
  • impedance_net, the network time without those, which the maximum times are tested against;
  • Distance and Price;
  • the mode, walking or cycling, and the code of the type in ModeUsed (ModeClass_rel): W, C, C_RM, C_RMT or C_Ric before, and W, C, RM_C, RMT_C or OVf_C after the chain.

How the legs are computed, with their extra time and their price, is on Walking and cycling legs.

Step 2: the chains of the component

The chain cache holds the chains from every stop. The component reads only the chains that board at a stop where one of its pre-transport legs ends (PublicTransport_Prep/PT_V, selected with uq_c_FromTime_Stop/IsVBoarding). A component that cycles to a rail or metro stop, for example, reads only the chains that board at such a stop. PT_V reads the cache per stop block with collect_by_cond, which reads only the tiles that hold such chains.

Step 3: origin blocks and parts

The output step computes the origins in blocks, to limit its memory:

  1. The origins get a random order (NetworkSetup/impl/OrgBlockSelections/rnd_rel) and are cut into Advanced/NumberOfOrgBlocks (450) blocks of at most Advanced/MaxOrgBlockSize origins: 33 for a neighbourhood set of its own CBS year, such as Buurt2025, and 200 for other origin sets.
  2. One ConfigurationPerOrgBlock_T per block (NetworkSetup/ConfigurationPerBlock/<block>) computes the journeys from the origins of that block.
  3. A component whose estimated memory peak per block is above Advanced/MaxMemoryPerProcess_GB computes every block in Impl/OrgBlockParts parts, each a contiguous range of the random order (OrgBlockSelections/OrgPart_rel); see MaxMemoryPerProcess_GB. With one part, the default for most components, the part is the whole block.

Every part (PublicTransport/PerPart/Part<k>of<K>, template BlockPart_T) has:

  • V, the pre-transport legs of the origins of the part;
  • PT_InBlock, the chains of PT_V that board at a stop where one of these legs ends; a stop that several origins reach counts once;
  • N, all post-transport legs, the same for every block.

batch\WriteOutputBlocks.ps1 computes the blocks in portions, one GeoDmsRun per portion of Classifications/Components/BlocksPerPortion blocks, so that the memory is freed between the portions; see The output step.

Step 4: the chains in the window of a departure moment

For every departure moment of the run (Impl/MeasureMoments), PerDepartureMoment_T (PerPart/<part>/PerDepartureMoment/<moment>) selects the chains of PT_InBlock that a traveller who leaves at that moment can catch (Within_VW_Window):

inTime <= From_Time_rel <= inTime + Max_V_Time + MaxWaitingTimeAtOrigin

Here inTime is the departure moment, From_Time_rel the boarding time of the chain, and Max_V_Time the longest pre-transport leg that can still be valid (Impl/PT_Max_V_Time: the largest maximum time of the pre-transport type plus the start and parking times of a cycling leg). A chain that departs before the departure moment can never be caught. A chain that departs after the upper bound cannot be caught without waiting longer than Advanced/MaxWaitingTimeAtOrigin allows.

The modes of the chains are decoded here from ModeCode into letters, once per distinct code (UqModeCode, with Classifications/GTFS_Modes/CodeDigits): BBR is two buses and then a train.

Step 5: pre-transport and chain

Add_V_to_PT joins every pre-transport leg (V) to every chain of the window that boards at the place where the leg ends (join_equal_values_uint64 on V/To_Place_rel and Within_VW_Window/From_Place_rel). A combination is valid (IsValid) when:

  • the traveller who leaves the origin at the departure moment reaches the stop no later than the chain departs (IsWaitingTimeValid); arriving exactly at the departure counts, as it does for a transfer;
  • the wait, the departure of the chain minus the arrival at the stop (WaitingTime_rel), is at most Advanced/MaxWaitingTimeAtOrigin (899 s);
  • the network time of the leg is within the maximum of its mode (IsVTimeNotTooLong: MaxWalkingTime_Org2Stops or MaxCyclingTime_Org2Stops);
  • the chain starts with a scheduled departure at that stop and time, not with a waiting link (IsPT_departureEvent_ActualPT, looked up in ScheduledLinks/c_fromTime_Stop_rel).

The model puts the wait at home: the traveller leaves the origin at the departure moment plus the wait, and reaches the stop just in time. The combination gets:

  • Traveltime: the time of the leg (V_time, with start and parking time) plus the travel time of the chain (PT_time), plus the wait (W_time) only with Advanced/IncludeWaitingAtHomeInTravelTime;
  • Price: the price of the chain plus the price of the leg as far as it counts (Price_V): a cycling leg with Advanced/IncludeCyclingCostsInPrice (default TRUE), a walking leg with Advanced/IncludeWalkingCostsInPrice (default FALSE);
  • Price_augm: the augmented price of the chain, with its transfer costs, plus the full price of the leg;
  • ModeUsed: the code of the pre-transport type, an underscore and the modes of the chain, for example C_RM_R;
  • NeedsBike: whether the leg is cycled on one’s own bicycle.

Only the combinations in the front of their origin and the place where the chain arrives go on to step 6 (Add_V_to_PT/Front, marked by Result/IsFront). This front is exact, on the criteria of the final front (Classifications/OutputParetoAttr, see step 7), per origin and arrival place (OrgArrival_key); of exact duplicates the first stays, as in the final front. Every post-transport leg from the arrival place adds the same time and price to each combination that arrives there, so a combination outside this front stays dominated after any post-transport leg, and coupling it would only cost memory and time. For a component that cycles on both sides, such as C_PT_C, the coupling of step 6 becomes about 21 times smaller (#140). Because the final front applies its 1% epsilon in two condensations, a combination that this front removes can still change which journeys within that epsilon the final front keeps; the cheapest journey of a pair stays the same.

Step 6: post-transport

Add_N_to_VPT joins every combination of the front of step 5 (Add_V_to_PT/Front) to every post-transport leg (N) from the place where the chain ends. A journey is valid when:

  • its travel time, with the post-transport time, is at most MaxTravelTime (90 min);
  • the network time of the post-transport leg is within the maximum of its mode (MaxWalkingTime_Stops2Dest or MaxCyclingTime_Stops2Dest).

Over all couplings the model computes only what this test needs: the travel time and the network time of the post-transport leg. The other columns follow in Add_N_to_VPT/Result, for the valid journeys only, through PT_rel (the row of Add_V_to_PT/Result) and N_rel (the post-transport leg).

The post-transport leg adds its time (N_time) to Traveltime, its price as far as it counts (Price_N, under the same rules as the pre-transport; the OV-fiets is a cycling leg with its rental price) to Price, its full price to Price_augm, and its code to ModeUsed. W_BBR_W is walking, two buses and a train, and walking; C_RM_R_OVf_C is cycling to a rail or metro stop, a train, and the OV-fiets.

A destination that no post-transport leg of the type reaches within its maximum time has no journey in this component.

Step 7: the Pareto front per origin-destination pair

The valid journeys (Add_N_to_VPT/Result) are the options of the departure moment, AllOptions. A run computes one component, so for a direct component the same template takes its direct trips as AllOptions instead (see Components and merging). The model keeps the Pareto front in two condensations:

  1. per departure from the origin and destination (uq_c_FromTime_Place_rel, To_Place_rel): the journeys that leave the origin at the same time for the same destination, through different stops or chains (Result_AfterFirstCondensation);
  2. per origin and destination (From_Place_rel, To_Place_rel), over the different departures from the origin within the window of the departure moment (Result_AfterSecondCondensation).

Both use pareto_optimal_eps on Classifications/OutputParetoAttr: the price and time criteria of the final front (FinalParetoAttr, from MinimiseCriteria, by default Price and TravelTime), and the ownership criteria NeedsCar and NeedsBike when MinimiseCriteria names them. Within one public transport component every journey has the same pre- and post-transport type, so the ownership criteria are equal for all its journeys and do not change its front; they matter in the merge. The epsilons are those of the chain joiner: the cheapest journey of a pair always stays, and a dearer one only when it is more than 1% (Advanced/ChainParetoTimeEpsilon) faster than every cheaper one that stays.

The front can hold several journeys per pair, such as a cheap and slow one next to a fast and expensive one. The public transport components keep on average 3.1 to 4.2 options per pair and departure moment (see Hardware requirements).

Step 8: the result of the block

  1. Each part computes the front of a departure moment behind its own fence (PerDepartureMoment_T/Result_Fence), so that GeoDMS frees the memory of its intermediate results before the next part starts.
  2. BlockResult unites the fronts of the parts in their order. With one part it is the front of that part, with the same rows in the same order.
  3. The writers of the first part (CreateExports) write it as one file per block and departure moment, PerBlock/tt_<moment>_<n>of<N>.parquet (or .csv), in the output folder of the component, together with the counts of the block. The columns are described under The files per block.
  4. An integrity check stops the run when a public transport journey without a ferry has price 0 (IsPTWithoutPrice); some ferries are free, such as those in Amsterdam.

The output folder is %LocalDataProjDir%/Output/<Analysis_date>_<OutputLabel>_<component>, with the settings in signature.txt; see Where the results are.

In the OD pair mode the same steps also keep, for every option, the rows it comes from (PT_InBlock_rel, VPT_rel, AllOptions_rel, First_rel). With PT_rel and N_rel of Add_N_to_VPT/Result OD_Output traces each option back to its pre-transport leg, chain and post-transport leg; see Routes of an OD pair.

Parameters

Parameter Default Description
MaxTravelTime 90 min Maximum travel time of the journey, without the wait at home by default.
Advanced/MaxWaitingTimeAtOrigin 899 s Maximum wait at home before the pre-transport leg.
Advanced/IncludeWaitingAtHomeInTravelTime FALSE Does the wait at home count in the travel time?
MaxWalkingTime_Org2Stops, MaxCyclingTime_Org2Stops, MaxWalkingTime_Stops2Dest, MaxCyclingTime_Stops2Dest 15 min Maximum network time of a pre- or post-transport leg.
Advanced/IncludeWalkingCostsInPrice, Advanced/IncludeCyclingCostsInPrice FALSE, TRUE Does the price of a walking or cycling leg count in Price? It always counts in Price_augm.
MinimiseCriteria 'Price,Time' Criteria of the front of the component.
Advanced/ChainParetoTimeEpsilon 0.01 Relative epsilon on the travel time.
Advanced/NumberOfOrgBlocks, Advanced/MaxOrgBlockSize 450; 33 or 200 Origin blocks of the output step.
Advanced/MaxMemoryPerProcess_GB 64 Memory per GeoDmsRun above which a block is computed in parts.
OutputFormat 'parquet' Format of the files per block.