Routing

Routing#

This section is a brief documentation to routing in the Polaris project. The project utilizes multiple routing algorithms for different purposes:

Multimodal Network Representation#

For multimodal network representation, see Multimodal Routing, Assignment, and Simulation Documentation.

Point-to-Point Routing Algorithms#

The routing algorithm in POLARIS is point-to-point, time-dependent, and intermodal. For detials, please refer to Interested readers are encouraged to read the following Time-Dependent Intermodal A* Algorithm: Methodology and Implementation on a Large-Scale Network paper for modeling and this unpublished paper for its use in the overal POLARIS framework.

The algorithm finds routes for the following modes:

  • Driving:

    • Passenger cars,

    • Taxis and TNCs.

  • Active:

    • Walking,

    • Micromobility with personally owned bikes/scooters,

    • Shared micromobility with docked vehicles,

    • Shared micromobility with non-docked vehicles.

  • Transit:

    • Walk and transit,

    • Drive to transit (park-and-ride or kiss-and-ride),

    • Drive after transit (Return transit trip to the parked car and drive to the destination),

    • Walk and rail only,

    • Drive to rail only,

    • Drive after rail only,

    • TNC and transit (TNC as a FMLM service or as a connector between transit legs),

    • Micromobility and transit (Micromobility as a FMLM service or as a connector between transit legs).

The point-to-point algorithm calculates paths between two activity locations, which can be considered as nano-zones connected to various walking, biking, and driving links. Depending on the mode of transportation, the algorithm begins with a specific set of links. For example, if the mode is passenger car, it starts with driving links, and it doesn’t switch to other link types during the process. The algorithm focuses on a subset of destination driving links related to the destination activity location, identifying the optimal starting link and destination link. The algorithm calculates the shortest path for a given departure time in seconds.

For walking and walk-and-transit, only walking links are considered at both the origin and destination. In park-and-ride, the origin uses driving links, while the destination uses walking links, with transfers possible only at transit facilities with parking. For drive-after-transit, the algorithm starts with walking links, finds a walk-and-transit path to the parked car, and then calls a driving query to the destination. In the case of TNC-and-transit, both walking and driving links are considered, as the best path may involve different combinations of TNC, walking, driving, and transit. The algorithm optimizes the sequence and combination of these modes for the best path.

Below is the list of origin and destination link types based on the queried trip’s travel mode:

  • Roadway routing:

    • Origin links: roadway network

    • Destination links: roadway network

    • Intermediate links: roadway network

  • Walk routing:

    • Origin links: walk network

    • Destination links: walk network

    • Intermediate links: walk network

  • Bike routing:

    • Origin links: bike network

    • Destination links: bike network

    • Intermediate links: bike network

  • Shared bike/scooter routing:

    • Origin links: walk network

    • Destination links: walk network

    • Intermediate links: walk and bike network

  • Walk-to-transit routing:

    • Origin links: walk network

    • Destination links: walk network

    • Intermediate links: walk and transit network

  • Drive-to-transit routing:

    • Origin links: roadway network

    • Destination links: walk network

    • Intermediate links: roadway, walk and transit network.

    • No transfer is possible from the walk or transit network back to the roadway network

  • Drive-after-transit routing:

    • Origin links: walk network

    • Destination links: roadway network

    • Intermediate links: roadway, walk and transit network.

    • This algorithm is performed in two stages. In the first stage, a walk-to-transit algorithm is called. At this stage, the origin links are the actual origin links, whereas the destination links are the walking links, that are closest to the roadway link where the car is parked. In the second stage, a roadway routing algorthm is called. At this stage, the origin links are the roadway link where the car is parked and potentially its opposite-direction link. The destination links are the actual destination links.

  • TNC-and-transit routing:

    • Origin links: roadway and walk network

    • Destination links: roadway and walk network

    • Intermediate links: roadway, walk and transit network.

    • This algorithm allows the use of TNC vehicles as the first-mile, last-mile, or middle-mile leg. As a result, the origin and destination link sets are flexible.

Below are sample parameter values for multimodal routing.

A sample excerpt out of the main scenario.json file:

"time_dependent_routing": true,
"multimodal_routing": true,
"multimodal_routing_model_file": "MultiModalRoutingModel.json",
"time_dependent_routing_weight_shape": 1.5,
"time_dependent_routing_weight_scale": 1800.0,
"time_dependent_routing_weight_factor": 1.0,
"time_dependent_routing_gap_cap": 3.0,
"time_dependent_routing_link_based_gap": true,
"time_dependent_routing_weight_factor_affects_choice": true,
"time_dependent_routing_weight_factor_affects_calculation": false,
"time_dependent_routing_gap_calculation_strategy": "use_max",
"use_person_gaps": true,
"use_heterogenous_VOT": true,

A sample MultiModalRoutingModel.json file:

"transferPenalty" 		: 1020.0,
"waitWeight" 			: 3.00,
"walkWeight" 			: 4.00,
"bikeWeight" 			: 3.00,
"ivtWeight" 			: 1.00,
"rail_waitWeight" 		: 2.00,
"rail_walkWeight" 		: 2.66,
"rail_bikeWeight" 		: 2.00,
"rail_ivtWeight" 		: 0.80,
"rail_ivtWeight_ampeak"	: 0.80,
"rail_ivtWeight_pmpeak"	: 0.80,
"standWeight" 			: 0.50,
"capacityAlpha" 		: 80.00,
"capacityBeta" 			: 0.60,
"carWeight" 			: 15.0,
"tncWeight" 			: 15.0,
"scanThreshold"			: 75000.0,
"costThreshold"			: 28800.0,
"commuter_rail_costThreshold"	: 43200.0,
"waitThreshold"			: 1800.0,
"walkThreshold"			: 2500.0,
"rail_waitThreshold"	: 2700.0,
"rail_walkThreshold"	: 3750.0,
"walkSpeed"				: 5.0,		
"bikeThreshold"			: 10000.0,
"rail_bikeThreshold"	: 15000.0,
"bikeSpeed"				: 16.0,
"VOT"					: 18.0,
"debug_route"			: false,
"multimodal_dijkstra"	: true,
"tncWaitCountThreshold" : 3.0,
"transitWaitCountThreshold" : 5.0,
"fmlmMinDriveTimeSeconds" : 1800.0,
"fmlmProportion" : 0.5

Skim Routing Algorithms#

Skim routing algorithms are tree-based algorithms, i.e. they find the shortest path from a source to all nodes/links in the network. The goal of this module in POLARIS is to generate TAZ-to-TAZ (TAZ: Traffic Analysis Zone) route level-of-service (LOS) metrics. These metrics are then used in Mode Choice, Destination Choice, and other travleer decision making modules.

The TAZ-to-TAZ tables of metrics are generated for different time inetrvals, such as 0-4 am, 4-6 am, 6-7 am, and so on. It is advised to use low precision (large interval durations) for times of the day such as midnight to 4 am, since traffic conditions are not very dynamic and close to free flow. On the other hand, for peak periods, generating skims at a higher precision (every half hour, every hour, or every two hours) is suggested to capture the changing dynamics in the network.

The time intervals are determined in the scenario JSON file using the interval endpoints in minutes from midnight. It is implied that the beginning of the first time interval is 0, and the endpoint of each time interval is the beginning of the next interval. See the sample below.

"read_skim_tables": true,
"skim_averaging_factor": 0.8,
"write_skim_tables": true,
"generate_transit_skims": false,
"skim_nodes_per_zone": 4,
"skim_interval_endpoint_minutes": [
        240,
        360,
        420,
        480,
        540,
        600,
        720,
        840,
        900,
        960,
        1020,
        1080,
        1140,
        1200,
        1320,
        1440
    ],

If read_skim_tables is true, the intervals should not be entered because POLARIS will read the existing skim tables and derive the interval enpodints from those skims. If both read_skim_tables and write_skim_tables ae true, POLARIS will generate new skims but when writing the skims, it will write the average of the old and new LOS values. The skim_averaging_factor determines the weight on the new LOS and [1-skim_averaging_factor] on the old LOS.

The highway skims are generated by selecting random activity locations in each zone. The skim_nodes_per_zone determines how many activity locations are selected per zone. POLARIS also determines a random depature time for each activity location. A shortest oath tree is generated rooted at each location. For a given origin-destination (OD) pair, the TAZ-to-TAZ level LOS values are the average of the [skim_nodes_per_zone times skim_nodes_per_zone] LOS values resulting from the [skim_nodes_per_zone many] shortest path calculations. If one selected all the links in the zone, the router would return zero values for any intrazonal trip, and very small values for neighboring zones. As a result, we chose to randomize the starting locations and departure times for highway skims. Each routing query builds a full tree where one could potentially generate a trajectory from the origin to anywhere in the network, these trees are not stored. The reason is that those paths will not be used. For individual travel starting and ending at specific activity locations and departing at a certain time (in seconds), the point-to-point algorithm is utilized. Here, the objective is store TAZ-to-TAZ level LOS values. The values for highway skims are:

  • Travel time in minutes,

  • Travel distance in meters,

  • Monetary cost in dollars,

Transit skims are computationally more costly. And the transit network conditions do not necessarily change drastically over iterations. The parameter generate_transit_skims determines if transit skims are to be generated. It is advised to turn on these parameter whenever there is a change in the transit network such as frequency or speed updates or changes in the route design. As opoosed to the highway skim routing, all walking (or driving depending on the mode) links in a zone go into the set of starting links. As a result, there is one query per origin zone, and the departure time is set to be the midpoint of the time interval. The LOS values for a given OD pair are calculated by averaging the LOS values at all destination links in the destination zone which are non-infinity. In other words, the best possible starting link from the origin is selected automatically, and the portions of the destination zone that are ot reachable by the selected transit mode are disregarded. This is definitely a bias but it is one by design. This method ensures to provide the best possible LOS between two TAZs. As a result, the transit mode is not omitted from a specific mode choice set, as long as one can go from a portion of the origin TAZ to a portion of the destination TAZ in that time interval. If in turn, the point-to-point transit routing algorithm fails for a traveler who ended up choosing transit, their mode choice can be reevaluated by taking out that mode from the choice set. Transit skimming is computationally expensive, and doing one query per origin zone mitigates the computational burden. The transit skim calculation is performed for the following modes:

  • Walk to transit (any transit mode including bus, rail etc.), called BUS,

  • Walk to rail only, called RAIL,

  • Drive to transit (any transit mode including bus, rail etc.), called PARK_AND_RIDE,

  • Drive to rail only, called PARK_AND_RAIL,

  • Drive after transit, called RIDE_AND_UNPARK,

  • TNC and transit, called TNC_AND_RIDE.

For each OD pair, departure time, and mode, the following LOS values are stored:

  • Auto access time in minutes,

  • Walk access time in minutes,

  • Total waiting time in minutes,

  • Total travel time in minutes,

  • Fare in dollars,

  • Number of transfers.

Purpose-Built and Assisting Algorithms#

Multimodal Dijkstra Tree#

For the theoretical foundations of this module, please read the work by Khani et al., 2015. For its use in POLARIS, please refer to Verbas et al., 2018 and Verbas et al., 2025.

Point-to-point algorithms utilize heuristic cost estimations. The algorithm is exact from the origin to a given link that is scanned. Once a link is updated, its generalized cost from the origin and to the link itself are stored. Next, the generalized cost from that link to the destination is estimated. When the routing algorithm determines which link to scan next, it orders the links not by their generalized cost -doing so would be equivalent to doing a label setting algorithm- but by their total cost: generalized cost from the origin to the link + estimated cost from the link to the destination. Most point-to-point algorithms use a Euclidean-based heuristic. POLARIS, on the other hand, uses a heuristic cost calculated by the Multimodal Dijkstra Tree algorithm. This algorithm yields static, all-to-all labels. No waiting or transfer times are considered on transit links. The transit link travel time is the minimum observed travel time on the link throughout the simulation horizon. For walking links, the travel time is static already. This all-to-all set of values provide a theoretical minimum transit travel time between any two points in the network, as long as the two points are connected by a series of walking and transit links. Otherwise, the value is infinity. In either case, this is a more efficient way of guiding the multimodal router to the destination than the Euclidean-based estimator.

The user only needs to turn on the multimodal_dijkstra parameter in the Multimodal JSON file.

Walk to Drive Tree#

This algorithm is utilized by the corner-to-corner TNC module. For each walking link, it generates a vector of pairs. Each pair includes the ID of the driving link and the shortest path distance from the walking link to the driving link. The vector size is truncated by the number of driving links that are within the walking threshold, determined by the walkThreshold variable.

Key articles by the team#

Important

Please refer to the the following papers for more details:

  • Auld, J., Hope, M., Ley, H., Sokolov, V., Xu, B., Zhang, K. (2016). Polaris: Agent- based modeling framework development and implementation for integrated travel demand and network and operations simulations. Transportation Research Part C: Emerging Technologies 64, 101–116. DOI: 10.1016/j.trc.2015.07.017.

  • Verbas, O., Auld, J., Ley, H., Weimer, R., Driscoll, S. (2018). Time-dependent inter- modal a* algorithm: Methodology and implementation on a large-scale network. Transportation Research Record 2672, 219–230. DOI: 10.1177/0361198118796402.

  • Auld, J., Verbas, O., Stinson, M. (2019). Agent-based dynamic traffic assign- ment with information mixing. Procedia Computer Science 151, 864–869. DOI: 10.1016/j.procs.2019.04.119.

  • Verbas, O., Cokyasar , T. , Camargo, P. V. d., Gurumurthy, K. M., Zuniga-Garcia, N., & Auld, J. (2025). Modeling transit in a fully integrated agent-based framework: Methodology and large-scale application. Available at https://arxiv.org/abs/2408.05176.

References#

  • Khani, A., Hickman, M., Noh, H. (2015). Trip-Based Path Algorithms Using the Transit Network Hierarchy. Networks and Spatial Economics 15-3, 635–653. DOI: 10.1007/s11067-014-9249-3.