網路模式分析
Network Modeling Analysis
| 節 | 週二 |
|---|---|
2 09:00–09:50 | 網路模式分析 A904 3 節連堂 |
3 10:10–11:00 | |
4 11:10–12:00 |
* 根據陽明交大上課時間表所列
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 |
| 第 2 週 | Quantitative/Network Models/Presentation/ Algorithmic Concerns/Formulation and Applications |
| 第 3 週 | Shortest Path Problem (I): Label Setting SPP (II): Label Correcting Algorithm |
| 第 4 週 | SPP (III): Floyd's Algorithm Review of LP Simplex |
| 第 5 週 | 國慶日 National Holiday |
| 第 6 週 | Minimum Cost Flow Problems: Network Simplex |
| 第 7 週 | Traffic Assignment; User Equilibrium Assignment Beckmann Transformation; UE Equivalent MP Model Review of Optimization Techniques |
| 第 8 週 | Application of Frank-Wolfe Algorithm to UE Assignment |
| 第 9 週 | **** First Examination **** |
| 第 10 週 | Arc Covering Problem Chinese Postman Problem (CPP) on undirected network |
| 第 11 週 | CPP on directed networks Facility Location: Median and Center Problem |
| 第 12 週 | Node Covering: Traveling Salesman Problem (TSP) --Problem Complexity: NP-Completeness TSP Exact Solution: Branch & Bound Algorithm TSP Heuristics, Euclidean TSP |
| 第 13 週 | TSP(II): TSP for Directed Graphs, M-TSP VRP(I): Formulation; C-W Savings Algorithm |
| 第 14 週 | VRP(II): VRP Heuristic Methods VRP Variants |
| 第 15 週 | **** Second Examination **** |
| 第 16 週 | More of VRP Heuristics/Metaheuristics Neighborhood Search VND/RVND; Tabu Search; SA/TA/RRT; Evolutionary Methods: GA/MA/PSO |
| 第 17 週 | Application Examples: (PSO) VRP & MCVRP; (ILS) VRP-IRF & PLRP; (Multi-Start) SDVRP & Variants |
| 第 18 週 | Final Presentation (in groups) |
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.