《土木与环境工程》（英文版） Transportation Network Analysis

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