小汽車共乘公平性配對模式暨求解演算法之研究; Matching Model and Heuristic Algorithm for Fairness in the Carpool Problem

NCU Institutional Repository > 工學院 > 土木工程研究所 > 博碩士論文 > Item 987654321/1278

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/1278

題名:	小汽車共乘公平性配對模式暨求解演算法之研究;Matching Model and Heuristic Algorithm for Fairness in the Carpool Problem
作者:	林瑜芳;Yu-fang Lin
貢獻者:	土木工程研究所
關鍵詞:	時空網路;多重貨物網路流動;拉氏鬆弛法;公平性;小汽車共乘;Lagrangian relaxation;multiple commodity network flow problem;time-space network;fairness;carpool
日期:	2008-06-23
上傳時間:	2009-09-18 17:25:39 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	近年來交通量成長迅速，小汽車之使用亦日益普遍，透過共乘除可提高小汽車之乘載率，亦可紓解都市交通雍塞；且有鑑於目前全球油價上漲，實施共乘可減低旅行成本以及節約能源。推行小汽車共乘的優點甚多，但共乘是否具公平性會影響民眾參與共乘的意願。在目前實務小汽車共乘的配對上，多採用人工經驗排班方式缺乏系統分析，故求解除缺乏效率外，亦難以確保效果。在學術上，以往文獻討論共乘公平性問題僅以駕駛次數考量，並無將駕駛距離納入考量。緣此，本研究將距離納入考量範圍內，並針對城際間長期(例如一週每日)通勤旅次，以共乘配對系統規劃者的角度，建立一系統最佳化之配對模式，期能提供有效的規劃輔助工具，幫助決策者有效地進行規劃。本研究使用網路流動技巧與數學規劃方法建立一多起迄之小汽車共乘配對模式，同時考量成本最小化以及公平性。而在網路設計上，加上一些額外的限制，以滿足實務的營運條件。此模式可定式為整數多重網路流動問題，屬NP-hard問題，為有效求解大規模問題，本研究利用拉氏鬆弛法暨次梯度法為基礎，發展有效的求解演算法。最後評估本研究中模式與演算法之實用績效，設計電腦隨機產生器產生不同的測試例，進行本研究之範例測試並針對不同參數進行敏感度分析，測試效果良好，最後提出結論與建議。 Respecting global petroleum price goes up, traffic volume has significantly grown and private cars become more popular than before in Taiwan. Therefore, carpool that enhances the car occupancy rate can not only relieve traffic congestion, but can also cheapen the travel cost and save energy. Introducing the carpool has a lot of advantages, but fairness would affect carpool members that join in the activity. As regards in Taiwan, carpool matching is manually performed by planning personnels with experience in current practice, without a systematic analysis. Such a manual approach is considered to be less efficient, and can possibly result in an inferior feasible solution. The carpool problems with the consideration of fairness were solved according to the frequency of being a driver in literatures, instead of the driving distances. Therefore, in this research, the travel distances in the carpool problem is considered for the long-term intercity commute trips to address the issue. Based on the system planner perspective, we develop a system-optimized matching model. The matching model is expected to be an effective tool for the planner to help solve carpool members matching. We consider many-to-many OD matching focusing on fairness in the carpool problem. Additional constraints are set to comply with real operating requirements. Model is formulated as an integer multiple commodity network flow problem, which is characterized as NP-hard and cannot be optimally solved in a reasonable time for large-scale problems. Therefore, to efficiently solve large-scale problems occurring in real world, we develop a solution algorithm for the model, based on Lagrangian relaxation with subgradient methods. To evaluate the matching model and solution algorithm in practice, we perform a case study. A computerized random generator is designed to create different problem instances used for testing. The results show the model could be useful. Finally, conclusions and suggestions are given.
顯示於類別:	[土木工程研究所] 博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....