都會區計程車共乘配對模式暨求解演算法之研究

Matching Models and Solution Algorithms for Urban Taxipool.

吳權哲(Chuan-che Wu)

指導教授 ： 顏上堯

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

摘要

鑑於目前台灣都會區交通量的成長迅速，計程車之使用亦日益普遍，因此有效的透過共乘以提高計程車之服務能量，除可以紓解都市交通雍塞外，亦可節約能源。目前實務在計程車共乘的配對上，多採用人工經驗排班方式，缺乏系統分析，故其求解除缺乏效率外，亦難以確保效果。至於學術上，以往文獻大多僅考慮單一起迄(單一起點或單一迄點)方式，與現行實務的運作之多起迄的配對問題不同，故難以應用至實際多起迄的配對問題。緣此，本研究針對預約式旅次，以共乘配對系統規劃者的角度，建立一系統最佳化之配對架構，其中包含車隊共乘配對及單一車輛定線暨乘客配對等兩階段模式，期能提供一有效的規劃輔助工具，幫助決策者有效地同時規劃乘客配對及計程車排程。
本研究構建一多起迄對車輛共乘配對之架構。此共乘配對架構可區分為兩個階段，第一階段為車隊共乘配對模式，係針對系統中每日接收之所有預約旅次進行人車共乘配對；第二階段含二個單一車輛定線暨乘客配對模式，針對第一階段模式之車隊解進行流量分解，以得各計程車之排程暨乘客之配對。三模式均將利用網路流動技巧，其中包含多重車流時空網路及多重人流時空網路，以定式車輛及旅次每日在時空中流動之情況。另外在車流與人流網路之間，加上一些額外的限制，以滿足實務的營運條件。此三模式可定式為整數多重網路流動問題，屬NP-hard問題，因此本研究將針對問題規模較大之第一階段模式，以拉氏鬆弛法暨次梯度法為基礎配合數學規劃軟體CPLEX，發展有效的求解演算法。最後為評估本研究中模式與演算法之實用績效，設計一電腦隨機產生器產生不同的測試例，進行本研究之範例測試與分析，進而提出結論與建議。

關鍵字

計程車共乘 ； 時空網路 ； 拉氏鬆弛法

並列摘要

Traffic volume has significantly grown and taxi becomes more popular than before in Taiwan. Therefore, taxipool that enhances the taxi utilization can not only relieve traffic congestion, but can also save energy. However, in Taiwan taxipool matching is manually performed by planning personnel 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. Although single origin or single destination matching problems have been researched in literature, they are different from the multiple origin-destination (OD) pairing matching problems that mostly occur in real word. As a result, the proposed models or methods cannot be directly applied to the practical multiple origin/destination matching problems. Therefore, in this research, based on the system planner perspective and focusing on advanced-order passenger trips, we develop a system optimization matching framework that contains several matching models in two stages: 1. fleet scheduling with passenger matching and 2. single taxi scheduling with passenger matching. The matching models are expected to be an effective tool for the planner to help simultaneously solve passenger matching and fleet scheduling.
We construct a multiple OD pair matching framework that is divided into two stages. In the first stage, we construct a fleet scheduling with passenger matching model which matches the daily advanced-order passenger trips with taxis. In the second phase, we construct two single taxi scheduling with passenger matching models, in order to decompose the fleet-flow solution from the first stage and to get each taxi schedule with matched passengers. We employ network flow techniques to develop these three models, each including multiple fleet-flow networks and multiple passenger-flow networks to formulate the daily flows of taxis and passengers in the dimensions of time and space. Some side constraints between the fleet- and passenger-flow networks are set to comply with real operating requirements. The three models are formulated as 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. Therefore, to efficiently solve large-scale problems occurring in real world, we develop a solution algorithm for each model, based on Lagrangian relaxation with subgradient methods. To evaluate the matching framework and solution algorithm in practice, we perform a case study. A computerized random generator is designed to generate different problem instances used for testing. Finally, conclusions and suggestions are given.

並列關鍵字

Lagrangian relaxation ； time-space network ； taxipool

參考文獻

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

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

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

林士鈞 (2005)，「定期貨櫃運輸船舶排程暨船期表建立之研究」，碩士論文，國立中央大學土木工程學系

辛孟鑫 (2005)，「撥召運輸系統路線規劃問題之研究－以台北市復康巴士為例」，碩士論文，國立成功大學交通管理科學研究所。