Transportation Network A nalysIs Often Useful in Applications far from Transportation
Transportation Network Transportation Network Analysis Analysis Often Useful in Applications far from Transportation!
Outline o Background and definitions ● Shortest path ● Minimum spanning tree e Introduction to Travelling salesman Problem and chinese postman problem
Outline Outline z Background and Definitions z Shortest path z Minimum spanning tree z Introduction to Travelling Salesman Problem and Chinese Postman Problem
Recall Continuum of Chapter 3 o Then we add discrete streets, adding at most 1/3 of a block length in mean travel distance o What about shifting to a directed network, 1. e, alternating one-way streets? o ith transportation networks, we discretize geography
Recall Continuum of Recall Continuum of Chapter 3 Chapter 3 z Then we add discrete streets, adding at most 1/3 of a block length in mean travel distance z What about shifting to a directed network, i.e., alternating one-way streets? z With transportation networks, we discretize geography
Illustrative Network
Illustrative Network Illustrative Network A B C D E
Network with Terminology B Nodes b and D Directed arc E Undirected arc
Network with Terminology Network with Terminology A B C D E Nodes B and D Directed Arc Undirected Arc
Examples of Nodes Arcs Nodes Arcs Street ● Street segments intersections ● Country roads ● Towns ● Airplane trave o Cities time Electrical junctions Circuit o Project milestones components ● Project tasks
Examples of Nodes & Arcs Examples of Nodes & Arcs Nodes z Street intersections z Towns z Cities z Electrical junctions z Project milestones Arcs z Street segments z Country roads z Airplane travel time z Circuit components z Project tasks
Arcs Can Have Lengths B C >Arc Lengths 6 E
Arcs Can Have “Lengths” Arcs Can Have “Lengths” A B C D E 4 2 1 1 5 3 17 6 Arc Lengths
Nodes Can Have Weights 100(A B)200 50(C D)100 dNode weights E 50
Nodes Can Have “Weights” Nodes Can Have “Weights” A B C D E 100 200 50 50 100 Node Weights
Examples of Node Weights? ● Town population of certain population by zone o of electricity use by zone
Examples of Node Weights? Examples of Node Weights? z Town population z % of certain population by zone z % of electricity use by zone
We Can Travel Along PATHS A B Path:A-C-D→E C D E
We Can Travel Along PATHS We Can Travel Along PATHS A B C D E Path: A C D E
