都會區計程車共乘配對模式暨求解演算法之研究; Matching Models and Solution Algorithms for Urban Taxipool.

NCUIR > Engineering College > Graduate Institute of Civil Engineering > Electronic Thesis & Dissertation > Item 987654321/1225

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/1225

Title:	都會區計程車共乘配對模式暨求解演算法之研究;Matching Models and Solution Algorithms for Urban Taxipool.
Authors:	吳權哲;Chuan-che Wu
Contributors:	土木工程研究所
Keywords:	計程車共乘;時空網路;拉氏鬆弛法;Lagrangian relaxation;time-space network;taxipool
Date:	2007-06-18
Issue Date:	2009-09-18 17:23:59 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	鑑於目前台灣都會區交通量的成長迅速，計程車之使用亦日益普遍，因此有效的透過共乘以提高計程車之服務能量，除可以紓解都市交通雍塞外，亦可節約能源。目前實務在計程車共乘的配對上，多採用人工經驗排班方式，缺乏系統分析，故其求解除缺乏效率外，亦難以確保效果。至於學術上，以往文獻大多僅考慮單一起迄(單一起點或單一迄點)方式，與現行實務的運作之多起迄的配對問題不同，故難以應用至實際多起迄的配對問題。緣此，本研究針對預約式旅次，以共乘配對系統規劃者的角度，建立一系統最佳化之配對架構，其中包含車隊共乘配對及單一車輛定線暨乘客配對等兩階段模式，期能提供一有效的規劃輔助工具，幫助決策者有效地同時規劃乘客配對及計程車排程。本研究構建一多起迄對車輛共乘配對之架構。此共乘配對架構可區分為兩個階段，第一階段為車隊共乘配對模式，係針對系統中每日接收之所有預約旅次進行人車共乘配對；第二階段含二個單一車輛定線暨乘客配對模式，針對第一階段模式之車隊解進行流量分解，以得各計程車之排程暨乘客之配對。三模式均將利用網路流動技巧，其中包含多重車流時空網路及多重人流時空網路，以定式車輛及旅次每日在時空中流動之情況。另外在車流與人流網路之間，加上一些額外的限制，以滿足實務的營運條件。此三模式可定式為整數多重網路流動問題，屬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.
Appears in Collections:	[Graduate Institute of Civil Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...