7.1.2.1.2. infrarisk.src.physical.transportation package

7.1.2.1.2.1. infrarisk.src.physical.transportation.network module

exception infrarisk.src.physical.transportation.network.BadNetworkOperationException

Bases: Exception

You can raise this exception if you try a network action which is invalid (e.g., trying to find a topological order on a network with cycles.)

class infrarisk.src.physical.transportation.network.Network(networkFile='', demandFile='', nodeFile='')

Bases: object

This is the class used for transportation networks. It uses the following dictionaries to store the network; the keys are IDs for the network elements, and the values are objects of the relevant type:

node – network nodes; see node.py for description of this class link – network links; see link.py for description of this class ODpair – origin-destination pairs; see od.py path – network paths; see path.py. Paths are NOT automatically generated

when the network is initialized (you probably wouldn’t want this, the number of paths is exponential in network size.)

The network topology is expressed both in links (through the tail and head nodes) and in nodes (forwardStar and reverseStar are Node attributes storing the IDs of entering and leaving links in a list).

numNodes, numLinks, numZones – self-explanatory firstThroughNode – in the TNTP data format, transiting through nodes with

low IDs can be prohibited (typically for centroids; you may not want vehicles to use these as “shortcuts”). When implementing shortest path or other routefinding, you should prevent trips from using nodes with lower IDs than firstThroughNode, unless it is the destination.

FrankWolfeStepSize(targetFlows, precision=0.0001)

This method returns the step size lambda used by the Frank-Wolfe algorithm.

The current link flows are given in the self.link[ij].flow attributes, and the target flows are given in the targetFlows dictionary.

The precision argument dictates how close your method needs to come to finding the exact Frank-Wolfe step size: you are fine if the absolute difference between the true value, and the value returned by your method, is less than precision.

acyclicShortestPath(origin)

This method finds the shortest path in an acyclic network, from the stated origin. You can assume that a topological order has already been found, and referred to in the ‘order’ attributes of network Nodes. You can also find a list of nodes in topological order in self.topologicalList. (See the method createTopologicalList below.)

Use the ‘cost’ attribute of the Links to calculate travel times. These values are given – do not try to recalculate them based on flows, BPR functions, etc.

Be aware that both the order Node attribute and topologicalList respect the usual convention in network modeling that the topological order starts at 1, whereas Python starts numbering at 0.

The implementation in the text uses a vector of backnode labels. In this assignment, you should use back-LINK labels instead. The idea is exactly the same, except you are storing the ID of the last link in a shortest path to each node.

The backlink and cost labels are both stored in dict’s, whose keys are node IDs.

* BE SURE YOUR IMPLEMENTATION RESPECTS THE FIRST THROUGH NODE! * Travelers should not be able to use “centroid connectors” as shortcuts, *** and the shortest path tree should reflect this.

You should use the macro utils.NO_PATH_EXISTS to initialize backlink labels, and utils.INFINITY to initialize cost labels.

allOrNothing()

This method generates an all-or-nothing assignment using the current link cost values. It must do the following:

  1. Find shortest paths from all origins to all destinations

  2. For each OD pairs in the network, load its demand onto the shortest path found above. (Ties can be broken arbitrarily.)

The resulting link flows should be returned in the allOrNothing dict, whose keys are the link IDs.

Be aware that the network files are in the TNTP format, where nodes are numbered starting at 1, whereas Python starts numbering at 0.

Your code will not be scored based on efficiency, but you should think about different ways of finding an all-or-nothing loading, and how this might best be done.

averageExcessCost()

This method should calculate the average excess cost based on the current link flows, and return this value.

To do this, you will need to calculate both the total system travel time, and the shortest path travel time (you will find it useful to call some of the methods implemented in earlier assignments).

beckmannFunction()

This method evaluates the Beckmann function at the current link flows.

calculateShortestTravelTime(origin, destination)
createTopologicalList()

Takes a topological ordering of the nodes, expressed by the ‘order’ attribute of the Node objects, and creates a single list which stores the IDs of the nodes in topological order. This is essentially the inverse function of the topological order, the k-th element of this list gives you the ID of the node whose order value is k.

finalize()

Establish the forward and reverse star lists for nodes, initialize flows and costs for links and OD pairs.

This method should return the ID of the node with the least number of links entering the node. Ties can be broken arbitrarily.

findTopologicalOrder()

This method should find a topological order for the network, storing the order in the ‘order’ attribute of the nodes, i.e.:

self.node[5].order

should store the topological label for node 5.

The topological order is generally not unique, this method can return any valid order. The nodes should be labeled 1, 2, 3, … up through numNodes.

If the network has cycles, a topological order does not exist. The presence of cycles can be detected in the algorithm for finding a topological order, and you should raise an exception if this is detected.

formAdjacencyMatrix()

This method should produce an adjacency matrix, with rows and columns corresponding to each node, and entries of 1 if there is a link connecting the row node to the column node, and 0 otherwise. This matrix should be stored in self.adjacencyMatrix, which is a dictionary of dictionaries: the first key is the “row” (tail) node, and the second key is the “column” (head) node.

loadPaths()

This method should take given values of path flows (stored in the self.path[].flow attributes), and do the following:

  1. Set link flows to correspond to these values (self.link[].flow)

  2. Set link costs based on new flows (self.link[].cost), see link.py

  3. Set path costs based on new link costs (self.path[].cost), see path.py

readDemandFile(demandFileName)

Reads demand (OD matrix) data from a file in the TNTP format.

readFromFiles(networkFile, demandFile)

Reads network data from a pair of files (networkFile, containing the topology, and demandFile, containing the OD matrix), then do some basic checks on the input data (validate) and build necessary data structures (finalize).

readNetworkFile(networkFileName)

Reads network topology data from the TNTP data format. In keeping with this format, the zones/centroids are assumed to have the lowest node IDs (1, 2, …, numZones).

relativeGap()

This method should calculate the relative gap (as defined in the course text) based on the current link flows, and return this value.

To do this, you will need to calculate both the total system travel time, and the shortest path travel time (you will find it useful to call some of the methods implemented in earlier assignments).

shiftFlows(targetFlows, stepSize)

This method should update the flow on each link, by taking a weighted average of the current link flows (self.link[ij].flow) and the flows given in the targetFlows dictionary (targetFlows[ij]). stepSize indicates the weight to place on the target flows (so the weight on the current flows is 1 - stepSize).

* IMPORTANT: After updating the flow on a link, you should call its updateCost method, so that the travel time is updated to reflect the new flow value. *

This method does not need to return a value.

shortestPath(origin)

This method finds the shortest path in a network which may or may not have cycles; thus you cannot assume that a topological order exists.

The implementation in the text uses a vector of backnode labels. In this assignment, you should use back-LINK labels instead. The idea is exactly the same, except you are storing the ID of the last link in a shortest path to each node.

Use the ‘cost’ attribute of the Links to calculate travel times. These values are given – do not try to recalculate them based on flows, BPR functions, etc.

The backlink and cost labels are both stored in dict’s, whose keys are node IDs.

* BE SURE YOUR IMPLEMENTATION RESPECTS THE FIRST THROUGH NODE! * Travelers should not be able to use “centroid connectors” as shortcuts, *** and the shortest path tree should reflect this.

You should use the macro utils.NO_PATH_EXISTS to initialize backlink labels, and utils.INFINITY to initialize cost labels.

userEquilibrium(stepSizeRule='MSA', maxIterations=100, targetGap=1e-06, gapFunction=<function Network.relativeGap>)

This method uses the (link-based) convex combinations algorithm to solve for user equilibrium. Arguments are the following:

stepSizeRule – a string specifying how the step size lambda is

to be chosen. Currently ‘FW’ and ‘MSA’ are the available choices, but you can implement more if you want.

maxIterations – stop after this many iterations have been performed targetGap – stop once the gap is below this level gapFunction – pointer to the function used to calculate gap. After

finishing this assignment, you should be able to choose either relativeGap or averageExcessCost.

validate()

Perform some basic validation checking of network, link, and node data to ensure reasonableness and consistency.

7.1.2.1.2.2. infrarisk.src.physical.transportation.tests module

infrarisk.src.physical.transportation.tests.approxEqual(value, target, tolerance)
infrarisk.src.physical.transportation.tests.averageExcessCost(testFileName)
infrarisk.src.physical.transportation.tests.check(name, value, target, tolerance)
infrarisk.src.physical.transportation.tests.convexCombination(testFileName)
infrarisk.src.physical.transportation.tests.frankWolfe(testFileName)
infrarisk.src.physical.transportation.tests.readFlowsFile(flowsFileName)
infrarisk.src.physical.transportation.tests.relativeGap(testFileName)

7.1.2.1.2.3. infrarisk.src.physical.transportation.transpo_compons module

Bases: object

Class for network links. As currently written, assumes costs are calculated as the sum of three factors:

  1. Travel time, computed via the BPR function

  2. Toll cost, the product of toll and network.tollFactor

  3. Distance-related costs, the product of length and network.distanceFactor

calculateBeckmannComponent()

Calculates the integral of the BPR function for the link, for its contribution to the sum in the Beckmann function.

calculateCost()

Calculates the cost of the link using the BPR relation, adding in toll and distance-related costs. This cost is returned by the method and NOT stored in the cost attribute.

updateCost()

Same as calculateCost, except that the link.cost attribute is updated as well.

class infrarisk.src.physical.transportation.transpo_compons.Node(isZone=False)

Bases: object

class infrarisk.src.physical.transportation.transpo_compons.OD(origin, destination, demand=0)

Bases: object

class infrarisk.src.physical.transportation.transpo_compons.Path(links, network, flow=0)

Bases: object

A Path is an ordered sequence of adjacent links; these are expressed in the attribute ‘links’, which is a tuple of link IDs. Other attributes are as follows:

network points to the parent Network class (needed for calculating costs) flow is the number of vehicles using this path cost is the total cost of the path

calculateCost()

Calculates the cost of the path by summing the cost of its constituent links. This cost is returned by the method and NOT stored in the cost attribute.

updateCost()

Same as calculateCost, except that the path.cost attribute is updated as well.

infrarisk.src.physical.transportation.transpo_compons.get_transpo_dict()

7.1.2.1.2.4. infrarisk.src.physical.transportation.utils module

exception infrarisk.src.physical.transportation.utils.BadFileFormatException

Bases: Exception

This exception is raised if a network or demand file is in the wrong format or expresses an invalid network.

exception infrarisk.src.physical.transportation.utils.NotYetAttemptedException

Bases: Exception

This exception is used as a placeholder for code you should fill in.

infrarisk.src.physical.transportation.utils.path2linkTuple(pathString)

Converts a path expressed as a sequence of nodes, e.g. [1,2,3,4] into a tuple of link IDs for use with the Path object (see path.py), in this case ((1,2),(2,3),(3,4))

infrarisk.src.physical.transportation.utils.readMetadata(lines)

Read metadata tags and values from a TNTP file, returning a dictionary whose keys are the tags (strings between the <> characters) and corresponding values. The last metadata line (reading <END OF METADATA>) is stored with a value giving the line number this tag was found in. You can use this to proceed with reading the rest of the file after the metadata.