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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：35

、訪客IP：18.117.107.78

姓名

吳權哲(Chuan-che Wu) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

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

相關論文

★ 橋梁檢測人力機具排班最佳化之研究	★ 勤業務專責分工下消防人員每日勤務排班最佳模式之研究
★ 司機員排班作業最佳化模式之研究	★ 科學園區廢水場實驗室檢驗員任務指派最佳化模式之研究
★ 倉儲地坪粉光工程之最佳化模式研究	★ 生下水道工程工作井佈設作業機組指派最佳化之研究
★ 急診室臨時性短期護理人力指派最佳化之探討	★ 專案監造人力調派最佳化模式研究
★ 地質鑽探工程人機作業管理最佳化研究	★ 職業棒球球隊球員組合最佳化之研究
★ 鑽堡於卵礫石層施作機具調派最佳化模式之研究	★ 職業安全衛生查核人員人力指派最佳化研究
★ 救災機具預置最佳化之探討	★ 水電工程出工數最佳化之研究
★ 石門水庫服務台及票站人員排班最佳化之研究	★ 空調附屬設備機組維護保養排程最佳化之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

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

論文目次

摘要 I
ABSTRACT II
誌謝 III
目錄 IV
圖目錄 VI
表目錄 VII
第一章緒論 1
1.1研究背景與動機 1
1.2研究目的與範圍 2
1.3研究方法與流程 2
第二章計程車共乘現況概述與文獻回顧 4
2.1計程車共乘之定義 4
2.2國內外計程車共乘現況 7
2.3 共乘及撥召的相關文獻 9
2.4時空網路的相關文獻 11
2.5分解式演算法的相關文獻 14
2.6 小結 16
第三章模式構建 18
3.1模式基本假設 19
3.2車隊共乘配對模式 21
3.2.1時空網路 21
3.2.2模式符號說明 24
3.2.3數學定式 26
3.3單一車輛定線及乘客配對模式 27
3.3.1時空網路 28
3.3.2模式符號說明 31
3.3.3數學定式 32
3.4模式應用 35
第四章求解演算法設計 37
4.1演算法一(SL) 39
4.1.1目標值下限 39
4.1.2目標值上限 41
4.2演算法二(FL) 45
4.2.1目標值下限 45
4.2.2目標值上限 48
4.3收斂機制及求解步驟 49
4.4 小結 50
第五章範例測試 52
5.1 輸入資料 52
5.1.1車隊規劃資料 52
5.1.2共乘旅次資料 53
5.2 模式發展 54
5.2.1問題規模 54
5.2.2模式輸入資料 55
5.3 電腦演算環境及設定 56
5.3.1電腦演算環境 56
5.3.2相關程式設定 56
5.3.3模式輸出資料 57
5.4測試結果與分析 57
5.5敏感度分析 61
5.5.1單一車輛規劃車容量之敏感度分析 61
5.5.2乘客旅行時間價值成本之敏感度分析 62
5.6方案分析 64
5.6.1配對組織之立場分析 64
5.6.2系統服務人數及派車數分析 67
5.7演算法求解績效分析 68
5.8小結 70
第六章結論與建議 71
6.1結論 71
6.2建議 72
6.3貢獻 73
參考文獻 74
附錄 78
附錄一都會區計程車共乘配對模式 78
附錄二 CPLEX Callable Library Code 85
附錄三範例測試之輸入資料 86
附錄四測試範例求解結果 88

參考文獻

何依栖 (1989)，「都會區計程車共乘制度實施及管理之探討」，運輸計畫季刊，第十八卷，第四期，第507-518頁。
余秀梅 (1994)，「多元商品模式應用在動態貨櫃調度問題之研究」，國立成功大學交通管理科學研究所碩士論文。
辛孟鑫 (2005)，「撥召運輸系統路線規劃問題之研究－以台北市復康巴士為例」，碩士論文，國立成功大學交通管理科學研究所。
林士鈞 (2005)，「定期貨櫃運輸船舶排程暨船期表建立之研究」，碩士論文，國立中央大學土木工程學系
周文生、黃台生、黃慧娟、王裕民、詹彥倫、許采蘋 (2004)，「九十三年度臺北地區計程車營運情形調查」，台北縣市政府交通局委託中華民國運輸學會辦理。
邱明琦，陳春益，林佐鼎 (2002)，「海運貨櫃排程模式之研究」，運輸計劃季刊，第三十一卷，第三期，第495-522頁。
許采蘋 (2005)，「計程車共乘與撥召計程車可行條件之研究」，碩士論文，國立交通大學交通運輸研究所。
陳妙珍、顏上堯、張珮璇 (2000)，「航空公司資產與負債管理模式之建立」，第四屆海峽兩岸會計與管理學術研討會論文集，武漢。
陳春益，邱明琦 (2002)，「貨櫃航線網路設計模式之研究」，運輸計劃季刊，第三十一卷，第二期，第267-298頁。
陶治中 (2005)，「智慧型運輸系統應用於高乘載計畫之示範與建置-都會區共乘系統之示範與建置(1/2)」，交通部科技顧問室。
陶治中 (2006)，「智慧型運輸系統應用於高乘載計畫之示範與建置-都會區共乘系統之示範與建置(2/2)」，交通部科技顧問室。
郭瑜堅 (2003)，「都市旅次成本之研究」，碩士論文，國立臺灣大學土木工程學研究所。
龍天立 (1976)，「戶到戶公共運輸系統在台北市可行性之初步研究」，運輸計畫季刊，第五卷，第一期，第29~63頁。
顏上堯、何淑萍 (1994)，「飛航排程暨班次表之建立」，運輸計劃季刊，第二十三卷，第一期，第73-90 頁。
顏上堯、翁綵穗 (2001)，「季節轉換間緩衝期飛航排程之研究」，運輸計劃季刊，第三十卷，第四期，第891- 922頁。
Abara, J. (1989). “Applying Integer Linear Programming to the Fleet Assignment Problem,” Interfaces, Vol. 19, pp. 20-28.
Agin, N., and Cullen, D. (1975). “An Algorithm for Transportation Routing and Vehicle Loading,” Logistics, pp.1-20, North Holland, Amsterdam.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P. and Vance, P. H. (1998). “Branch-and-Price: Column Generation for Solving Huge Integer Programs,” Operations Research, Vol. 46, pp. 316-329.
Benders J. F. (1962). “Partitioning procedures for solving mixed-variables programming problems,” Numerische Mathematik, Vol.4, pp. 238-252.
Camerini, P. K., Fratta, L. and Maffioli, F. (1975). “On Improving Relaxation Methods by Modified Gradient Techniques,” Mathematical Programming Study, Vol. 3, pp. 6-25.
Chen, C. Y. and Kornhauser, A. L. (1990). “Decomposition of Convex Mulitcommodity Network Flow Problem,” Report SOR-90-19, Dept. of Civil Engineering and Operations Research, Princeton University, Princeton, NJ.
Chih, K. C. K. (1986). “A Real Time Dynamic Optimal Freight Car Management Simulation Model of Multiple Railroad, Mulitcommodity Temporal Spatial Flow Problem,” Ph.D. Dissertation, Princeton University, Princeton, NJ.
Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M.M. and Soumis, F. (1997). “Daily Aircraft Routing and Scheduling,” Management Science, Vol. 43, pp. 841-855.
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, pp. 539-557.
Fisher, M. L. (1981). “The Lagrangian Relaxation Method for Solving Integer Programming Problem,” Management Science, Vol. 27, pp. 1-18.
Fu L. (2002a). “A Simulation Model for Evaluating Advanced Dial-a-Ride Paratransit systems,” Transportation Research, Vol. 36A, pp. 291-307.
Fu, L. (2002b). “Scheduling Dial-a-Ride Paratransit under Time-Varying, Stochastic Congestion,” Transportation Research, Vol. 36B, pp. 485-506.
Hane, C. A., Barnhart, C., Johnson, E. L., Marsten, R., Nemhauser, G. L. and Sigismondi, G. (1995). “The Fleet Assignment Problem: Solving a Large-Scale Integer Program,” Mathematical Programming Study, Vol. 70, pp. 211-232.
Horn, M. E. T. (2002). “Fleet Scheduling and Dispatching for Demand-Responsive Passenger Services,” Transportation Research, 10C, pp. 35-63.
Hunsaker, B. and Savelsbergh, M. (2002). “Efficient Feasibility Testing for Dial-a-Ride Problems,” Operations Research Letters, Vol. 30, pp. 169-173.
Kennington, J. L. and Shalby, M. (1977). “An Effective Subgradient Procedure for Minimum Cost Multicommodity Flow Problem,” Management Science, Vol.23, pp. 994-1004.
Lee, K.T., Wu, P.J. and Wang, S.H. (2004). “The Planning and Design of Taxipooling on Feeder System,” Networking, Sensing and Control, 2004 IEEE International Conference, Taipei, Taiwan.
Lamatsch, A. (1992). “An Approach to Vehicle Scheduling with Depot Capacity Constraints,” in Desrochers, M. and Rousseau, J. M.（eds.）, Computer Aided Transit Scheduling, Lecture Notes in Economics and Mathematical System 386, Springer Verlag, Berlin, Heidelberg, pp. 181-195.
Lee, B. C. (1986). “Routing Problem With Service Choices, Flight Transportation Laboratory,” Report R86-4, Massachusetts Institute of Technology, MA.
Levin, A. (1971). “Scheduling and Fleet Routing Models for Transportation Systems,” Transportation Science, Vol. 5, pp. 232-255.
Levin, A. (1969). “Some Fleet Routing and Scheduling Problems for Air Transportation Systems,” Flight Transportation Laboratory Report R68-5, Massachusetts Institute of Technology, MA.
Mesquita, M. and Paixao, J. (1992). “Multiple Depot Vehicle Scheduling Problem: a New Heuristic Based on Quasi-Assignment Algorithm,” in Desrochers, M. and Rousseau, J. M.(eds.), Computer Aided Transit Scheduling, Lecture Notes in Economics and Mathematical System 386, Springer Verlag, Berlin, Heidelberg, pp. 181-195.
Powell, W. B. and Ioannis, A. K. (1992). “Shipment Routing Algorithms with Tree Constraints,” Transportation Science, Vol. 26, pp. 230-245.
Samuel, W. L. (1998). “Autonomous dial-a-ride transit Benefit-Cost Evaluation,” Volpe National Transportation Systems Center, August, 1998.
Shan, Y. S. (1985). “A Dynamic Mulitcommodity Network Flow Model for Real Time Optimal Real Freight Car Management,” Ph.D. Dissertation, Princeton University, Princeton, NJ.
Simpson, R.W. (1969). “A Review of Scheduling and Routing Model for Airline Scheduling,” IX AGIFORS Symposium, Broadway, England.
Subramanian, R., Scheff, R. P., Quillinan, J. D., Wiper, D. S. and Marsten, R. E. (1994). “Coldstart: Fleet Assignment at Delta Air Lines,” Interface, Vol. 24, pp. 104-120.
Teodorovic, D. (1988).,Airline Operations Research, Gordon and Breach Science Publishers, New York.
Teodorovic, D. and Guberinic, S. (1984). “Optimal Dispatching Strategy on an Airline Network after a Schedule Perturbation,” European Journal of Operational Research 15, pp. 178-182.
Vuchic, V. R. (1981). Urban Public Transportation Systems and Technology. Englewood Cliffs, NJ: Prentice-Hall.
Yan, S. (1996). “Approximating reduced costs under degeneracy in a network flow problem with side constraints,” Networks, Vol. 27, pp. 267-278.
Yan, S. and Chen, H.L. (2002). “A Scheduling Model and a Solution Algorithm for Inter-city Bus Carriers,” Transportation Research, Vol. 36A, pp. 805-825.
Yan, S. and Chen, C.H. (2007), “Coordinated Scheduling Models for Allied Airlines,” Transportation Research, Part C. (forthcoming).
Yan, S., and Tseng, C.H. (2002). “A Passenger Demand Based Model for Airline Flight Scheduling and Fleet Routing,” Computers and Operations Research, Vol. 29, pp. 1559-1581.
Yan, S. and Shih, Y.L. (2007). “A Time-Space Network Model for Work Team Scheduling after a Major Disaster”, Journal of the Chinese Institute of Engineers, Vol. 30, No. 1, pp. 63-75.
Yan, S. and Young, H.F. (1996). “A Decision Support Framework for Multi-Fleet Routing and Multi-Stop Flight Scheduling,” Transportation Research, Vol. 30A, pp. 379-398.
Yan, S., Tang, C.H. and Shieh, C.N. (2005). “A Simulation Framework for Evaluating Airline Temporary Schedule Adjustments Following Incidents,” Transportation Planning and Technology, Vol. 28, No. 3, pp. 189-211.
Yan, S., Chi, C.J. and Tang, C.H. (2006b). “Inter-city Bus Routing and Timetable Setting under Stochastic Demands,” Transportation Research, Vol. 40A, pp. 572-586.
Yan, S., Chen, S.C. and Chen, C.H. (2006a), “Air Cargo Fleet Routing and Timetable Setting with Multiple On-Time Demands,” Transportation Research Part E, Vol. 42, Issue 5, pp. 409-430.

指導教授

顏上堯(Shangyao Yan)

審核日期

2007-7-16

推文