Transportation Network Analysis Often Useful in Applications far from Transportation! Outline null Background and Definitions null Shortest path null Minimum spanning tree null Introduction to Travelling Salesman Problem and Chinese Postman Problem Recall Continuum of Chapter 3 null Then we add discrete streets, adding at most 1/3 of a block length in mean travel distance null What about shifting to a directed network, i.e., alternating one-way streets? null With transportation networks, we discretize geography Illustrative Network A B CD E Network with Terminology A B CD E Nodes B and D Directed Arc Undirected Arc Examples of Nodes & Arcs Nodes null Street intersections null Towns null Cities null Electrical junctions null Project milestones Arcs null Street segments null Country roads null Airplane travel time null Circuit components null Project tasks Arcs Can Have “Lengths” A B CD E 4 2 11 5 3 17 6 Arc Lengths Nodes Can Have “Weights” A B CD E 100 200 50 50 100 Node Weights Examples of Node Weights? null Town population null % of certain population by zone null % of electricity use by zone We Can Travel Along PATHS A B CD E Path: A C D E A Special Path is a CYCLE A B CD E Cycle: C D E C Some Examples of Networks Boston Subway null Seattle Network of Major Highways Seattle Ferry Boat Network Telecommunications Networks Network Terminology null N = sets of nodes null A = set of arcs null G(N,A) null Incident arc null Adjacent nodes null Adjacent arcs null Path null Degree-ness of a node null In-degree null Out-degree null Cycle or circuit null Connected nodes null Connected undirected graph null Strongly connected directed graph null Subgraph Network Terminology - con't. null Tree of an undirected network is a connected subgraph having no cycles null A tree having t nodes contains (t-1) edges null Spanning tree of G(N,A) is a tree containing all n nodes of N null Length of a path S null d(x,y), d(i,j) L(S) = l(i, j) (i, j)∈S ∑ Now to Some Network Decision Problems Issues of design or deployment on a network Routing Problems null Shortest path problem null Traveling salesman problem null Chinese postman problem Shortest Path Problem null Find the shortest path between two nodes, starting at Node O and ending at Node D. – O: Origin node – D: Destination node Node Labeling Algorithm: Dijkstra null Shortest path from a node null k=1, start at origin node null At the end of iteration k, the set of k CLOSED NODES consists of the k closest nodes to the origin. null Each OPEN NODE adjacent to one or more closed nodes has our current 'best guess' of the minimal distance to that node. Dijkstra Algorithm, Con't null Each best guess represents a feasible perhaps optimal path null Next step: Close the closest of the BEST GUESSES. null Loop on updating best guesses. null Repeat by replacing k with k+1. 53 6 2 2 3 4 1 5 4 O D (1,0) 8 10 (k,d)=(iteration k, min distance to node O) Computational Complexity Network with n nodes null Each iteration: up to n checks null Up to n iterations null Implies O(n 2 ) complexity null For the entire graph: O(n 3 ) complexity Minimum Spanning Tree (MST) Problem null Assume an undirected graph null Why is this an important problem? null Problem: Find a shortest length spanning tree of G(N, A). null If |N|=n, then each spanning tree contains (n-1) links. null MST may not be unique MST null Algorithm: Start at an arbitrary node. Keep connecting to the growing sub- tree the closest unattached node. Proof by contradiction T 1 Proof by contradiction T 1 T 2 MST = T 1 + T 2 + (one connecting link) Proof by contradiction T 1 T 2 67 9 5 11 MST = T 1 + T 2 + (one connecting link) Corollary null In an undirected network G, the link of shortest length out of any node is part of the MST. Another MST Algorithm null Rank order arcs by length and add them to tree's incumbent solution (a group of sub-trees), making sure that we do not create cycles. null This is a good manual algorithm but more difficult to automate on the computer. Computational Complexity of the MST null Assume a fully connected G null Iteration #1: (n-1) comparisons to find minimum. Label each node with distance to start node. Computational Complexity of the MST null Iteration #2: – Find distances from newly added node to each node not in the tree & replace labels where necessary. Requires (n-2) comparisons – Find the minimum of the labels. Requires an additional (n-2) comparisons. Computational Complexity of the MST null Iteration #j: – Find distances from newly added node to each node not in the tree & replace labels where necessary. Requires (n-j) comparisons – Find the minimum of the labels. Requires an additional (n-j) comparisons. # computations = (n ? 1) + 2(n ? j) j = 2 n ∑ = 2(n ?1) + 2(n ? 2) + ... + 2 ? (n ? 1) = 2 n(n ? 1) 2 ? (n ? 1) ?O(n 2 ) Traveling Salesman Problem null Find the shortest cycle starting and ending at node O and visiting each specified node A, B, C, etc. at least once. CD E 2 11 5 3 17 6 2 11 3 6 H I J 7 7 2 Traveling Salesman Example: Make a Best Cycle Joining the Blue Nodes A B 4 F G 5 14 Chinese Postman Problem null Find the minimum length tour or cycle that “covers” each link at least once. A Famous Problem Island A Island B N = North Side S = South Side The Seven Bridges of Konigsberg Reduced to a Network N S AB Seven Bridges of Konigsberg as a Network Chinese Postman: Easy An Easy Chinese Postman Problem Chinese Postman: Matching DE 8 A B C 6 6 8 55 55 Match #2 DE 8 A B C 6 6 8 55 55 Match #3 DE 8 A B C 6 6 8 55 55 null Each of these problem types has been greatly refined and expanded over the years null Each can be implemented via computer in complex operating environments null The Post office, FEDX, truckers, even bicycled couriers use these techniques