Key Definitions:

Here are some definitions and concepts that will be helpful when trying to understand Highway Assignment:

Zone: Portion of the study area with homogenous land use, socio-economic and demographic characteristics
Zone Centroid: Assumed point in a zone that represents the origin or destination of all trips to or from that zone
Centroid Connector: Imaginary link representing the local streets within a zone. Linking the zone to the network loading point.
Network: Contains the transport network of the study area. Represented by links and nodes.
OD Demand Matrix: Demand for travel between all zones in a study area. (N x N)
Skim Matrix: Indicator matrix containing zone to zone statistics.
Generalized cost: Generalized costs (GC) are the costs perceived by the traveler as they decide which mode to use. These sum time and monetary costs and use the Value of Time to convert to a single unit.

• Car generalized costs: In vehicle time (generally no waiting time), Vehicle operating costs (fuel), Tolls, Parking charges
• PT generalized costs: walk time, waiting time, in vehicle time, fare, interchange penalties.

Highway Assignment Overview:

Highway assignment deals with finding the least generalized cost path between each origin and destination in a network.

It is an iterated procedure looking for convergence or equilibrium, which means that every user in the system reaches the path with the best general cost, there is no possible further reduction. For example, in the case that travel time is the only factor being accounted, equilibrium is reached when all users achieve the best travel time available for their trips.

Inputs for a Highway program include (among others):

• Highway Network:

        Can be built from (by conversion tools):

         -Shape Files

         -Dbf files

         -ASCII files

       Cube format network formats (no conversion):

         - Geodatabase Networks (.mdb/ .gdb)

         - Binary .NET Networks (no associated geometry to links (straight lines only)). True shape of the links can be activated with an underlying shapefile

• Zonal Matrices:

         - Matrices for Highway Assignment must be SQUARE matrices. Where rows represent the Origins and columns represent Destinations.

         - In CUBE you can have several tables/ matrices inside one Matrix file which are accommodated in tabs at the top.

         - A single CUBE Format Matrix file (.mat) can hold up to 255 matrices/ tables.

         - Matrices can come originally in a csv, dbf or fixed format and with the help of CUBE tools can be converted into a CUBE Format Matrix file.

• Zonal data files
• Turn Penalties

Outputs for a Highway program include (among others):

• Loaded network
• Matrices
• Junction Output Data

Highway Assignment Process in Voyager:

The Highway program in CUBE has as its primary function to Build Paths between all origin destination pairs. After paths are built it is possible to skim network variables and assign trips to the network.

The method used to assign the OD matrix to the network uses an iterative approach:

1. Shortest paths are determined by minimizing link cost
2. A supplied matrix of trips is assigned to the paths
3. Link costs are updated based on the link congestion equations
4. New ‘shortest’ paths are determined
5. The matrix of trips is optimally spread over all available paths.

Steps 3 to 5 are repeated until some criteria for termination is reached.

The highway program applies the above-mentioned method by dividing the process in 5 phases, which are all coded/scripted with control statements:

• SETUP phase: Initialize certain variables and/ or arrays and lookup tables
• LINKREAD phase: Loop across all links. Obtain required initial values from input network data and compute link values referenced elsewhere.
• ILOOP phase: Loop across all zones, building and loading minimum paths as requested
• ADJUST phase: Loop across all links. Revise the link variable values to be used in the next iteration (congested time TC and COST) and/or for output processes
• CONVERGE phase: For every iteration check to determine whether additional iterations are necessary.

In the Highway Program Script we would write the following control statements:

SETUP Phase, which is an implicit phase (it does not have a header)

• Specify the Assignment Algorithm  after the Parameter Combine:
• Deterministic Assignment:
  • EQUI: search for ‘optimal’ LAMBDA
  • ENHANCE = 0 ; ‘Normal’ Frank-Wolf Algorithm (default)
  • ENHANCE = 1 ; Conjugate Frank-Wolf Algorithm
  • ENHANCE = 2 ; Bi-Conjugate Frank-Wolf Algorithm
  • AVE: LAMBDA = 1/ITERATION ‘method of successive averages’ (MSA). Used when costs may not be separable and independent (i.e. cost on a link is not due entirely to its own volume and characteristics)
  • WTD (weighted average), ITER (only last iteration), SUM (incremental loading)
• Stochastic Assignment:
  • BURREL: Uniform Distribution
  • PROBIT: Normal Distribution

 We will set in this case: COMBINE=EQUI as well as set the iteration information (Maximum number of iterations)     MAXITERS and/or set convergence criteria. (The program will finish running once it meets either the convergence criteria or maximum number of iterations, whichever comes first).

LINKREAD Phase:

Defines required values for each link like:

• Capacity

      C=LI.CAPACITY

• Travel times

      t₀=(LI.DISTANCE/LI.SPEED)*60

• Distance:

      DISTANCE=LI.DISTANCE

ILOOP Phase:

In this phase we will be creating paths from each origin zone to every destination using command PATHLOAD.

Other keywords used are:

• PATH keyword is used to define the distance or travel time or generalized cost attribute (E.g., COST, TIME, DISTANCE,  {name}, or LW.{name}): PATH=TIME
• Keywords are added to assign Volume Sets VOL[ ]=‘Matrix’ – Assignment : VOL[x]=MI.1.1
• Once build, working matrices can also be skimmed using PATHTRACE
• PATHO writes paths from the PATHLOAD statement
  • INCLUDECOST=T à The cost through every link in every path is written.

Lets take a simple example on how Highway Assignment works.

The schematic diagram shows that we have:

• 2 ZONES N=1 (zone i) and N=2 (zone j) and 2 intermediate nodes N=100 and N=101.
• Links available between nodes are shown by the black arrows:
• 1-100
• 1-101
• 100-2
• 101-2
• 100-101

We have to assign a capacity and travel time to each link in the figure t₀ and c which is primarily done in LINKREAD phase.

In ILOOP Phase, we build shortest paths from every zonal pair or for every origin/destination. In our example, we start building all possible paths from 1 to 2 (Origin-Destination) and calculate the overall travel time. In this process, we find 3 paths as below:

Path 1 (1—100, 100-2):

t₀= 6 mins

 

Path 2: (1-100,100-101,101-2)

t₀= 12 mins

Path 3: (1-101,101-2)

t₀= 8 mins

 

After building all the possible paths we find the best path as Path 1 (1-100, 100-2) as it is the one with least travel time. On this path, we do All or Nothing (AON) assignment for Iteration 1 (t₀).

Once a AON path is found, we load the demand for that OD pair to this path. Once done, we move to ADJUST phase.

ADJUST Phase:

In Adjust phase, we define functions that will be used in the Highway Program to update the travel times on each link or update the generalized cost for each link and this will be largely dependent on congestion of the respective link.. In Adjust phase, we combine all the volumes from every OD pair on a single subject link including adding other vehicles from other user-classes. The combine is done by V as below.

• Combine Volumes from user-classes

             V=VOL[x1]+VOL[x2]

          Where V computes the total volume on a link after an iteration.

• The V and C (Capacity) is then used in a volume-delay function or a traditional BPR function where the travel times are updated like below.

             TC[n]=T₀*(1+α(V/C)^β

          Where TC stands for congested time

In our example, after ADJUST phase, the travel times are now updated as below.

Once the updated Travel Times are available, we move to ILOOP Phase again where Paths are built again and a new AON Best Path is chosen. In our example, the new AON path is  Path 3: 1-101, 101-2. Then, the  COMBINE=EQUI statement will decide how many trips will go in each path, given the new best path. Trips after both iterations are split between Iter 1 Best Path and Iter 2 Best Path using the equilibrium calculations or based on ‘lambda’ values.

After two iterations it is noticeable that the assignment will produce variation in the selection of a Best Path which is why the CONVERGE Phase is needed.

CONVERGE phase

• It decides when to stop iterative procedure by following either default convergence tests (in ADJUST) or user-defined criteria (PHASE=CONVERGE). If not converged the program will go back to ILOOP

Suggestions for HW Assignment convergence:

• Check congestion levels along the network
• Avoid large turn penalty values
• Reduce effects from large fixed values (e.g. tolls) in link performance functions
• Define generalized cost function
• Use fixed link capacity during iterations
• Check RGAP convergence evolution and final value: A Relative Gap of 0.01 % (0.0001) is required to assure that the assignment is sufficiently converged to achieve stable link flows (Boyce, et al., 2004)

For more details on CUBE’s Highway Assignment, please refer to CUBE Voyager > Highway documentation.

For examples on How to do Highway Assignment in CUBE Voyager refer to other Wiki Posts.