網路模式分析

Network Modeling Analysis

學期

106-1

學分

0 學分

當期課號

5499

永久課號

ITS5111

開課單位

運輸與物流管理學系交通運輸碩博士班

授課教師

韓復華

校區

光復

類別

選修

上課時間表

節	週二
A 18:30–19:20	網路模式分析 A905（光復） 3 節連堂
B 19:30–20:20
C 20:30–21:20

* 根據陽明交大上課時間表所列

概述

This course will cover the modeling techniques, solution methods and application considerations of those widely applied network models that include Shortest Path Problems, (LP) Minimum-Cost Flow Problems, (NLP) User Equilibrium Traffic Assignment, (Node Covering) Traveling Salesman Problems, (Arc Covering) Chinese Postman Problem, Vehicle Routing Problem, and Facility Location Problems. Recent development of meta-heuristics applications will be discussed as well. Students will find these models most useful in application areas such as Supply Chain Planning, Distribution Network Design, Logistics System Design, Transportation Planning, Transportation System Analysis, Vehicle Routing and Scheduling, and Service Facility Planning.

先修科目

微積分、作業研究

備註

無備註

教學方式

教師未提供此項資料

評分方式

Class Participation 25% Homework and Group Assignment 25% Midterm Examination 25% Final Presentation 25%

課程大綱

教師未提供此項資料

週次計畫

週次	主題
第 1 週	Course Overview; Konigsburg Seven-Bridge Problem 9/12
第 2 週	Quantitative/Network Models/Presentation/ Algorithmic Concerns/Formulation and Applications 9/19
第 3 週	Shortest Path Problem (I): Label Setting SPP (II): Label Correcting Algorithm 9/26
第 4 週	SPP (III): Floyd's Algorithm Review of LP Simplex 10/3
第 5 週	國慶日 National Holiday 10/10
第 6 週	Minimum Cost Flow Problems: Network Simplex 10/17
第 7 週	Traffic Assignment; User Equilibrium Assignment Beckmann Transformation; UE Equivalent MP Model Review of Optimization Techniques 10/24
第 8 週	Application of Frank-Wolfe Algorithm to UE Assignment 10/31
第 9 週	** First Examination ** 11/7
第 10 週	Arc Covering Problem Chinese Postman Problem (CPP) on undirected network 11/14
第 11 週	CPP on directed networks Facility Location: Median and Center Problem 11/21
第 12 週	Node Covering: Traveling Salesman Problem (TSP) --Problem Complexity: NP-Completeness TSP Exact Solution: Branch & Bound Algorithm TSP Heuristics, Euclidean TSP 11/28
第 13 週	TSP(II): TSP for Directed Graphs, M-TSP VRP(I): Formulation; C-W Savings Algorithm 12/5
第 14 週	VRP(II): VRP Heuristic Methods VRP Variants 12/12
第 15 週	** Second Examination ** 12/19
第 16 週	More of VRP Heuristics/Metaheuristics Neighborhood Search VND/RVND; Tabu Search; SA/TA/RRT; Evolutionary Methods: GA/MA/PSO 12/26
第 17 週	Application Examples: (PSO) VRP & MCVRP; (ILS) VRP-IRF & PLRP; (Multi-Start) SDVRP & Variants 1/2
第 18 週	Final Presentation (in groups) 1/9

教科書

Text Materials: 1. Evans, James and Edward Minieka, Optimization Algorithms for Networks and Graphs, 2nd ed., Marcel Dekker, 1992. 2. Christofides, N., Graph Theory: An Algorithmic Approach, Academic Press, 1975. 3. Larson, R. and A. Odoni, Urban Operations Research, Prentice Hall, 1981. 4. Bradley, S., A. Hax and T. Magnanti, Applied Mathematical Programming, Addison-Wesley, 1977. 5. Sheffi, Y., Urban Transportation Networks, Prentice Hall, 1985. 6. Williams, H.P., Model Building in Mathematical Programming, 4th ed., John Wiley & Sons, 1999. 7. Teodorovic, D., Transportation Networks: A Quantitative Treatment, Gordon and Breach Science Publisher, 1986. 8. Bodin, Lawrence, Bruce Golden, Arjang Assad and Michael Ball, "Routing and Scheduling of Vehicles and Crews," Special Issue of Computers and Operations Research, 1983. 9. Golden, Bruce, S. Raghavan and Edward Wasil (eds.), The Vehicle Routing Problem: Latest Advances and New Challenges, Springer, 2008 References Books: 1. Ahuja, R.K., T. Magnanti and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993. 2. Ball, M., T. Magnanti, C. Monma and G. Nemhauser (eds.), Network Models, Handbooks in Operations Research and Management Science, Volume 7, INFORMS, Elsevier, 1995. 3. Ball, M., T. Magnanti, C. Monma and G. Nemhauser (eds.), Network Routing, Handbooks in Operations Research and Management Science, Volume 8, INFORMS, Elsevier, 1995. 4. Golden, Bruce, S. Raghavan and Edward Wasil (eds.), The Vehicle Routing Problem: Latest Advances and New Challenges, Springer, 2008. 5. Williams, H.P., Logic and Integer Programming, Springer, 2009.

Office Hours

地點: 教師未提供此項資料
時間: 教師未提供此項資料
聯絡方式: 教師未提供此項資料