多場站多車型-車輛規劃問題(MDMV-VSP)在連結式網路架構與時空網路架構下的比較

簡易檢索 / 詳目顯示

回結果列表

研究生：	陳智元 Zhi-Yuan Chen
論文名稱：	多場站多車型-車輛規劃問題(MDMV-VSP)在連結式網路架構與時空網路架構下的比較 The comparison between connection-based network and time-space network on multiple-depot multiple-vehicle-type scheduling problem
指導教授：	陳正綱 Cheng-Kang Chen
口試委員:	洪政煌 Cheng-Huang Hung 洪大為 Ta-Wei Hung
學位類別：	碩士 Master
系所名稱：	管理學院 - 資訊管理系 Department of Information Management
論文出版年：	2006
畢業學年度：	94
語文別：	英文
論文頁數：	49
中文關鍵詞：	連結式網路、時空網路、車輛規劃問題
外文關鍵詞：	connection-based network, time-space network, vehicle scheduling problem
相關次數：	點閱：346 下載：11
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

上一筆

本論文考慮了多場站、多車型的車輛規劃問題 (multiple-depot multiple-vehicle-type scheduling problem)，此類問題包含了一份任務的時間表(timetabled task)，每一個任務(task)被限制只能被某場站的某些車行所服務。而本論文最大的不同在於我們考慮了每一個任務是具有成本的，而且成本會因為服務其任務的車型而改變。我們為此類問題建立了兩種不同模式的公式，分別為連結式網路(connection-based network) 與時空網路(time-space network)的數學公式。我們使用最佳化數學軟體CPLEX分析我們為此兩類模式的數學公式運算成果，發現了此兩模式的差異。再小型的此類車輛規劃問題中，連結式網路的整數規劃問題規模比時空網路還要小；而在中型或大型的此類車輛規劃問題，時空網路具有明顯的優勢。

In this paper, we consider the multiple-depot multiple-vehicle-type scheduling problem (MDMV-VSP) where a given set of timetabled trips (or tasks) are assigned to appropriate vehicles from appropriate depots. A key feature differentiating our paper from extant literature is that the task cost is considered to be dependent on the vehicle type assigned to the task. Two different formulations, which are time-space network (TSN) and connection-based network (CBN), are constructed and analyzed for the MDMV-VSP. By utilizing the optimization software CPLEX to compare TSN and CBN formulations, several interesting observations are obtained. For example, our computational results show the connection-based network (CBN) formulation is better than time-space network (TSN) formulation in small size of MDMV-VSP problems. However, time-space network (TSN) formulation obviously outperforms connection-based network (CBN) formulation in medium and large sizes of problems.

致  謝............................................................I
摘  要............................................................II
Abstract..........................................................III
TABLE OF CONTENTS.................................................IV
LIST OF FIGURES...................................................VI
LIST OF TABLES....................................................VII
Chapter 1. Introduction...........................................1
1.1 Investigate background and motive.............................1
1.2 Investigate objective.........................................2
1.3 Investigate scope and restriction.............................3
1.4 Investigate method and procedure..............................4
Chapter 2. Literature review......................................5
Chapter 3. Description of Connection-based network (CBN) flow model for MDMV-VSP...............................................................7
3.1 Mathematically formulation....................................7
3.1.1 Network structure...........................................8
3.1.2 Nodes.......................................................9
3.1.3 Arcs........................................................10
3.1.4 Arc costs...................................................11
3.1.5 Variables...................................................11
3.2 Model formulation.............................................12
3.3 A example of CBN formulation for MDMV-VSP.....................13
Chapter 4. Dscription of Time-space network (TSN) flow model for MDMV-VSP	15
4.1 Mathematically formulation....................................15
4.1.2 Nodes.......................................................17
4.1.3 Arcs........................................................18
4.1.4 Arc costs...................................................19
4.1.5 Variables...................................................19
4.2 Model formulation.............................................20
4.3 A example of TSN formulation for MDMV-VSP.....................21
Chapter 5. Computational result...................................25
5.1 Computation result with connection-based network..............27
5.2 Computation result with time-space network....................33
5.3 Comparison with two models....................................39
Chapter 6. Concluding Remarks.....................................45
References........................................................46

                                

1.
Bodin, L., Golden, B., and Assad, A., (1983) "Routing and scheduling of vehicles and crews: the state of the art", Computers & Operations Research 10 pp. 63-211.

2.
Daduna, J.R., Mojsilovic, M. (1988) “Computer-aided vehicle and duty scheduling using HOT programme system” Computer-aided transit scheduling, Springer, Berlin Heidelberg New York pp. 133–146.

3.
Carpaneto, G., Dell'Amico, M., Fischetti, M., and Toth, P., (1989) “A branch and bound algorithm for the multiple depot vehicle scheduling problem”, Networks 19 pp. 531-548.

4.
Mesquita, M., Paixao, J. (1992) “Multiple depot vehicle scheduling problem: A new heuristic based on quasi-assignment algorithms” Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems 386, Springer, Berlin, pp. 167-180.

5.
Dell'Amico, M., Fischetti, M., Toth, P., (1993) “Heuristic algorithms for the multiple depot vehicle scheduling problem“, Management Science 39 pp. 115-125.

6.
M.A. Forbes, J.N. Holt and A.M. Watts, (1994) “An exact algorithm for multiple depot bus scheduling”, European Journal of Operational Research 72 pp. 115-124

7.
Ribeiro, C., Soumis, F., (1994) “A column generation approach to the multiple depot vehicle scheduling problem” Operations Rresearch 42 41-52.

8.
Bianco, L., Mingozzi, A., Ricciardelli, S., (1994) “A set partitioning approach to the multiple depot vehicle scheduling problem” Optimization Methods and Software 3 pp. 163-194.

9.
Daduna, J.R., Paixao, J.M.P. (1995) “Vehicle scheduling for public mass transit – an overview“ Computer-aided transit scheduling, Springer, Berlin Heidelberg New York pp. 76–90.

10.
Friberg, C., Haase, K. (1999)” An exact branch and cut algorithm for the vehicle and crewscheduling problem” Computer-aided transit scheduling, Springer, Berlin Heidelberg New York pp. 63–80.

11.
Lobel, A. (1999) “Solving large-scale multiple-depot vehicle scheduling problems” Computer-aided transit scheduling, Springer, Berlin Heidelberg New York pp. 193–220.

12.
Haase, K., Desaulniers, G., Desrosiers, J. (2001) “Simultaneous vehicle and crew scheduling in urban mass transit systems” Transportation Science 35 286–303

13.
Kliewer, N., Mellouli, T., Suhl, L. (2002)” A new solution model for multi-depot multivehicle-type vehicle scheduling in suburban public transport”, In: Proceedings of the 13th Mini-EURO Conference and the 9th Meeting of the EUROWoring Group on Transportation, Bari, Italy

14.
Freling, R., Huisman, D.,Wagelmans, A.P.M. (2003) “Models and algorithms for integration of vehicle and crew scheduling” Journal of Scheduling 6 pp. 59–81

15.
Kang, K.H., Lee, Y.H., Lee, B.K., (2005)"An exact algorithm for multi depot and multi period vehicle scheduling problem" Lecture Notes in Computer Science 3483 (IV) pp. 350-359

16.
Natalia Kliewer *, Taieb Mellouli, Leena Suhl,(2005) “A time–space network based exact optimization model for multi-depot bus scheduling”, European Journal of Operational Research, In Press, Corrected Proof, Available online 6 April 2005,

17.
Vitali Gintner, Natalia Kliewer, and Leena Suhl, (2005) “Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice”, OR Spectrum 27 pp. 507–523.

18.
Hadjar. A., Marcotte. O., Soumis. F., (2006) "A branch-and-cut algorithm for the multiple depot vehicle scheduling problem", Operations Research 54 pp.130-149

簡易檢索 / 詳目顯示

相關論文