 |
|
|
|
以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：53 、訪客IP：18.222.182.191
姓名 陳俊穎(Chun-Ying Chen) 查詢紙本館藏 畢業系所 土木工程學系 論文名稱 小汽車共乘配對最佳化模式暨求解演算法之研究
(Optimization Models and Solution Algorithms for the Car Pooling Problems)相關論文 檔案 [Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
[檢視]
- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
摘要(中) 由於目前台灣都會區交通量的成長迅速，因此若能實行小客車共乘，則除可以紓解都市的交通擁塞問題外，亦可節約國家的能源。然而，以往探討小客車共乘配對問題的文獻不多，且為簡化問題，所發展的模式大多未考慮實際營運時的限制，僅考量簡單的時窗與容量限制。因此，此等模式難以直接地運用於複雜的實務問題上。至於在問題稍為相似的撥召配對文獻上，雖有較多學者曾嘗試發展數學解析模式及解法，然該問題與本研究所欲解決的小客車共乘問題存有相當的差異，因此其模式與解法亦難直接地應用於求解本研究問題。由於以往鮮有探討多對多起迄之小客車共乘配對問題，另在加入考量先前配對資訊考量的小客車共乘問題更未發現有相關的研究，因此本研究以系統最佳化觀點，針對預約式多對多起迄的旅次發展一小客車共乘配對模式與考量先前資訊之小客車共乘配對模式，期能提供決策者輔助工具，在面對不同的問題，以有效地規劃小客車共乘配對。
本研究分為兩個主題。第一主題中，本研究針對每日預約的多對多起迄旅客構建一不考量先前資訊之小客車共乘配對模式；第二主題中，針對每日預約的多對多起迄旅客構建考量先前資訊之小客車共乘配對模式。本研究利用網路流動技巧以構建所有模式。此等模式預期均可定式為特殊之整數多重貨物網路流動問題，屬NP-hard問題，預期在面對實務大型的問題時，難以在合理的時間內求得最佳解。因此，為了有效地求解實際的大型問題，在第一個主題中，我們發展一以拉氏鬆弛法暨次梯度法為基礎之求解演算法以及一個上限啟發解法；第二個主題中，我們發展一以拉氏鬆弛法為基礎之求解演算法以及一個上限啟發解法。最後，為評估各演算法之實際求解績效，本研究進行範例測試，並設計電腦隨機產生器產生多個不同的測試例，以測試各演算法在不同情況下的求解績效，結果甚佳。
摘要(英) Traffic volume has significantly grown in Taiwan. If carpool is performed, it will not only relieve traffic congestion but will also save energy. However, only a little research related with car pooling problems has been studied. Moreover, in order to simplify the studied problems, they only considered simple constraints, such as time-windows or capacity constraints. Consequently, the proposed models or methods cannot be directly applied to the complex and practical carpooling problems. Although many researchers have developed analytical models to solve the dial-a-ride problem which is rather closely related with our research, the difference in between is significant. Therefore, the proposed models and solution algorithms cannot be directly used for solving our problem. Since there has not yet research on many-to-many car pooling problem, particularly with consideration of pre-matching information, in this research, based on the system optimization perspective and a set of given advanced-order passenger trips, we develop a many-to-many car pooling model, and the many-to-many car pooling model with pre-matching information. These models are expected to be useful tools to help the planner effectively and efficiently solve these car pooling problems.
This study is divided into two essays. In the first essay, we construct a car pooling model without pre-matching information for the daily advanced-order many-to-many trips. In the second essay, we construct the car pooling model with pre-matching information for the daily advanced-order many-to-many trips. In this study, we strive to make up this lack by employing a time-space network flow technique to develop models for two essays. All the models are formulated as special integer multiple commodity network flow problems, which are characterized as NP-hard and cannot be optimally solved in a reasonable time for large-scale problems. In order to efficiently solve large-scale problems occurring in real world, in the first essay, we develop a solution algorithm based on Lagrangian relaxation, a subgradient method, and a heuristic for the upper bound solution, to solve the model; in the second essays, we develop a solution algorithm based on Lagrangian relaxation, and a heuristic for the upper bound solution, to solve the model. Finally, computerized random generators also are designed to generate different problem instances used for testing the solution algorithms. The results are good, showing that the model and heuristic algorithm could be useful.
關鍵字(中) ★ 小客車共乘
★ 多重貨物網路流動問題
★ 時空網路
★ 拉氏鬆弛法關鍵字(英) ★ time-space network
★ multiple commodity network flow problem
★ carpool
★ Lagrangian relaxation論文目次 摘要 i
Abstract ii
誌謝 iii
Contents iv
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
Chapter 2 Essay1: An Optimization Model and a Solution Algorithm for the Car Pooling Problem 5
2.1 Introduction 5
2.2 Problem description 8
2.3 The model 12
2.3.1 The CVG vehicle-flow time-space networks 12
2.3.2 CVG passenger-flow time-space networks 14
2.3.3 CNG passenger-flow time-space networks 16
2.3.4 Other relational constraints 18
2.3.5 The model formulation 19
2.4 Solution algorithm 25
2.4.1 The lower bound of the optimal solution 26
2.4.2 The upper bound of the optimal solution 27
2.4.3 Sub-gradient method and the solution process 30
2.5 Numerical tests 31
2.5.1 Test results 31
2.5.2 Case illustration with sensitivity analyses 35
2.6 Conclusion 40
Chapter 3 Essay 2: An Optimization Model and a Solution Algorithm for the Car Pooling Problem with Pre-Matching Information 42
3.1 Introduction 42
3.2 Problem description 44
3.3 The model 49
3.3.1 The pre-CG vehicle-flow time-space networks 49
3.3.2 The CVG vehicle-flow time-space networks 51
3.3.3 CVG passenger-flow time-space networks 53
3.3.4 CNG passenger-flow time-space networks 54
3.3.5 Other relational constraints 57
3.3.6 The model formulation 57
3.3.7 The flexibility of model modification 65
3.4 Solution algorithm 66
3.4.1 Stage 1: the lower bound of the optimal solution 66
3.4.2 Stage 2: the upper bound of the optimal solution 67
3.5 Numerical tests 70
3.5.1 Test results 70
3.5.2 Case illustration and sensitivity analyses 75
3.6 Conclusions 80
Chapter 4 Conclusions, Discussions, Suggestions, and Contributions 82
4.1 Conclusions 82
4.2 Discussion 84
4.3 Suggestions 86
4.4 Contributions 87
References 88
參考文獻 Baldacci, R., Maniezzo, V., Mingozzi, A., 2004, “An exact method for the car pooling problem based on Lagrangean column generation,” Operations Research, 52(3), 422-439.
Calvo, R.W., Colorni, A., 2007, “An effective and fast heuristic for the dial-a-ride problem,” 4OR: A Quarterly Journal of Operations Research, 5, 61-73.
Calvo, R.W., Luigi, F.L., Haastrup, P., Maniezzo, V., 2004, “A distributed geographic information system for the daily car pooling problem,” Computers and Operations Research, 31, 2263-2278.
Colorni, A., Righini, G., 2001, “Modeling and optimizing dynamic dial-a-ride problems,” International Transactions in Operational Research, 8, 155-166.
Coppersmith, D., Nowicki, T.J., Paleologo, G.A., Tresser, C., Wu, C.W., 2005, “The optimality of the on-line greedy algorithm in carpool and chairman assignment problems,” IBM Research Report, RC23721.
Cordeau, J-F., 2006, “A Branch-and-cut algorithm for the dial-a-ride problem,” Operations Research, 54, 573-586.
Cordeau, J-F., Laporte, G., 2003a, “A tabu search heuristic for the static multi-vehicle dial-a-ride problem,” Transportation Research B, 37, 579-594.
Cordeau, J-F., Laporte, G., 2003b, “The dial-a-ride problem (DARP): variants, modeling issues and algorithms,” 4OR: A Quarterly Journal of Operations Research, 1, 89-101.
Cordeau, J-F., Laporte, G., 2007, “The dial-a-ride problem : models and algorithms,” Annals of Operations Research, 153, 29-46.
Coslovich, L., Pesenti, R., Ukovich, W., 2006, “A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem,” European Journal of Operational Research, 175, 1605-1615.
Diana, M., Dessouky, M.M., 2004, “A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows,” Transportation Research Part B, 38, 539-557.
Fagin, R., Williams, J.H., 1983, “A fair carpool scheduling algorithm,” IBM Journal of Research & Development, 27(2), 133-139.
Ferrari E, Manzini R, Pareschi A, Persona A, Regattieri A, 2003, “The car pooling problem: Heuristic algorithms based on savings functions,” Journal of Advanced Transportation, 37, 243-272.
Fisher M.L., 1981, “The Lagrangian relaxation method for solving integer programming problem,” Management Science 27, 1-18.
Garey, M.R., Johnson, D.S., 1979, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman & Company, San Francisco, CA.
Guo, Y.J, 2003, Trip cost urban transportation, Master’s thesis, National Taiwan University, Department of Civil engineering.
Jørgensen, R.M., Larsen, J., Bergvinsdottir, K.B., 2007, “Solving the dial-a-ride problem using genetic algorithms,” Journal of the Operational Research Society, 58, 1321-1331.
Melachrinoudis, E., Ilhan, A.B., Min, H., 2007, “A dial-a-ride problem for client transportation in a healthcare organization,” Computers & Operations Research, 34, 742-759.
Naor M., 2005, “On fairness in the carpool problem,” Journal of Algorithms, 55, 93-98.
Rekiek, B., Delchambre, A., Saleh, H.A., 2006, “Handicapped person transportation: an application of the grouping genetic algorithm,” Engineering Application of Artificial Intelligence, 19, 511-520.
Ropke, S., Cordeau, J-F., Laporte, G., 2007, “Models and branch-and-cut algorithms for pickup and delivery problems with time windows,” Networks, 49, 258-272.
Teodorovic, D., Radivojevic, G., 2000, “A fuzzy logic approach to dynamic dial-a-ride problem,” Fuzzy Sets and Systems, 116, 23-33.
Wong, K.I., Bell, M.G.H., 2006, “Solution of the dial-a-ride problem with multi-dimensional capacity constraints,” International Transactions in Operational Research, 13, 195-208.
Xiang, Z., Chu, C., Chen, H., 2006, “A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints,” European Journal of Operational Research, 174, 1117-1139.
Yan, S, Young H.F., 1996, “A decision support framework for multi-fleet routing and multi-stop flight scheduling,” Transportation Research Part A, 30(5), 379-398.
Yan, S., Chen, S.C., Chen, C.H., 2006, “Air cargo fleet routing and timetable setting with multiple on-time demands,” Transportation Research Part E, 42(5), 409-430.
Yan, S., Shih, Y.L., 2009, “Optimal scheduling of emergency roadway repair and subsequent relief distribution,” Computers & Operations Research, 36(6), 2049-2065.
指導教授 顏上堯(Shangyao Yan) 審核日期 2010-7-21 推文 plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
網路書籤 Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit