小汽車共乘公平性配對模式暨求解演算法之研究

Matching Model and Heuristic Algorithm for Fairness in the Carpool Problem

林瑜芳(Yu-fang Lin)

指導教授 ： 顏上堯

國立中央大學/工學院/土木工程學系/碩士(2008年)

摘要

近年來交通量成長迅速，小汽車之使用亦日益普遍，透過共乘除可提高小汽車之乘載率，亦可紓解都市交通雍塞；且有鑑於目前全球油價上漲，實施共乘可減低旅行成本以及節約能源。推行小汽車共乘的優點甚多，但共乘是否具公平性會影響民眾參與共乘的意願。在目前實務小汽車共乘的配對上，多採用人工經驗排班方式缺乏系統分析，故求解除缺乏效率外，亦難以確保效果。在學術上，以往文獻討論共乘公平性問題僅以駕駛次數考量，並無將駕駛距離納入考量。緣此，本研究將距離納入考量範圍內，並針對城際間長期(例如一週每日)通勤旅次，以共乘配對系統規劃者的角度，建立一系統最佳化之配對模式，期能提供有效的規劃輔助工具，幫助決策者有效地進行規劃。
本研究使用網路流動技巧與數學規劃方法建立一多起迄之小汽車共乘配對模式，同時考量成本最小化以及公平性。而在網路設計上，加上一些額外的限制，以滿足實務的營運條件。此模式可定式為整數多重網路流動問題，屬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.

並列關鍵字

Lagrangian relaxation ； multiple commodity network flow problem ； time-space network ； fairness ； carpool

參考文獻

黃漢瑄，「撥召服務最佳化指派作業之研究」，碩士論文，淡江大學運輸管理研究所 (2006)。

楊淑芳，「以巨集啟發式演算法求解即時資訊下之中型車共乘問題」，碩士論文，淡江大學運輸管理研究所 (2006)。

邱明琦，陳春益，林佐鼎，「海運貨櫃排程模式之研究」，運輸計劃季刊，第三十一卷，第三期，第495-522頁 (2002)。

陳春益，邱明琦，「貨櫃航線網路設計模式之研究」，運輸計劃季刊，第三十一卷，第二期，第267-298頁 (2002)。

顏上堯、翁綵穗，「季節轉換間緩衝期飛航排程之研究」，運輸計劃季刊，第三十卷，第四期，第891- 922頁 (2001)。