Title

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

Translated Titles

Matching Models and Solution Algorithms for Urban Taxipool.

Authors

吳權哲

Key Words

計程車共乘 ; 時空網路 ; 拉氏鬆弛法 ; Lagrangian relaxation ; time-space network ; taxipool

PublicationName

中央大學土木工程學系學位論文

Volume or Term/Year and Month of Publication

2007年

Academic Degree Category

碩士

Advisor

顏上堯

Content Language

繁體中文

Chinese Abstract

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

English Abstract

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.

Topic Category 工學院 > 土木工程學系
工程學 > 土木與建築工程
Reference
  1. 辛孟鑫 (2005),「撥召運輸系統路線規劃問題之研究-以台北市復康巴士為例」,碩士論文,國立成功大學交通管理科學研究所。
    連結:
  2. 林士鈞 (2005),「定期貨櫃運輸船舶排程暨船期表建立之研究」,碩士論文,國立中央大學土木工程學系
    連結:
  3. 邱明琦,陳春益,林佐鼎 (2002),「海運貨櫃排程模式之研究」,運輸計劃季刊,第三十一卷,第三期,第495-522頁。
    連結:
  4. 陳春益,邱明琦 (2002),「貨櫃航線網路設計模式之研究」,運輸計劃季刊,第三十一卷,第二期,第267-298頁。
    連結:
  5. 郭瑜堅 (2003),「都市旅次成本之研究」,碩士論文,國立臺灣大學土木工程學研究所。
    連結:
  6. 顏上堯、翁綵穗 (2001),「季節轉換間緩衝期飛航排程之研究」,運輸計劃季刊,第三十卷,第四期,第891- 922頁。
    連結:
  7. Abara, J. (1989). “Applying Integer Linear Programming to the Fleet Assignment Problem,” Interfaces, Vol. 19, pp. 20-28.
    連結:
  8. 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.
    連結:
  9. Benders J. F. (1962). “Partitioning procedures for solving mixed-variables programming problems,” Numerische Mathematik, Vol.4, pp. 238-252.
    連結:
  10. 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.
    連結:
  11. 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.
    連結:
  12. Fisher, M. L. (1981). “The Lagrangian Relaxation Method for Solving Integer Programming Problem,” Management Science, Vol. 27, pp. 1-18.
    連結:
  13. Fu L. (2002a). “A Simulation Model for Evaluating Advanced Dial-a-Ride Paratransit systems,” Transportation Research, Vol. 36A, pp. 291-307.
    連結:
  14. Fu, L. (2002b). “Scheduling Dial-a-Ride Paratransit under Time-Varying, Stochastic Congestion,” Transportation Research, Vol. 36B, pp. 485-506.
    連結:
  15. 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.
    連結:
  16. Horn, M. E. T. (2002). “Fleet Scheduling and Dispatching for Demand-Responsive Passenger Services,” Transportation Research, 10C, pp. 35-63.
    連結:
  17. Hunsaker, B. and Savelsbergh, M. (2002). “Efficient Feasibility Testing for Dial-a-Ride Problems,” Operations Research Letters, Vol. 30, pp. 169-173.
    連結:
  18. Kennington, J. L. and Shalby, M. (1977). “An Effective Subgradient Procedure for Minimum Cost Multicommodity Flow Problem,” Management Science, Vol.23, pp. 994-1004.
    連結:
  19. 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.
    連結:
  20. Lee, B. C. (1986). “Routing Problem With Service Choices, Flight Transportation Laboratory,” Report R86-4, Massachusetts Institute of Technology, MA.
    連結:
  21. Levin, A. (1971). “Scheduling and Fleet Routing Models for Transportation Systems,” Transportation Science, Vol. 5, pp. 232-255.
    連結:
  22. Levin, A. (1969). “Some Fleet Routing and Scheduling Problems for Air Transportation Systems,” Flight Transportation Laboratory Report R68-5, Massachusetts Institute of Technology, MA.
    連結:
  23. 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.
    連結:
  24. Powell, W. B. and Ioannis, A. K. (1992). “Shipment Routing Algorithms with Tree Constraints,” Transportation Science, Vol. 26, pp. 230-245.
    連結:
  25. 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.
    連結:
  26. Teodorovic, D. (1988).,Airline Operations Research, Gordon and Breach Science Publishers, New York.
    連結:
  27. 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.
    連結:
  28. Yan, S. (1996). “Approximating reduced costs under degeneracy in a network flow problem with side constraints,” Networks, Vol. 27, pp. 267-278.
    連結:
  29. 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.
    連結:
  30. Yan, S. and Chen, C.H. (2007), “Coordinated Scheduling Models for Allied Airlines,” Transportation Research, Part C. (forthcoming).
    連結:
  31. 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.
    連結:
  32. 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.
    連結:
  33. 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.
    連結:
  34. 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.
    連結:
  35. 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.
    連結:
  36. 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.
    連結:
  37. 何依栖 (1989),「都會區計程車共乘制度實施及管理之探討」,運輸計畫季刊,第十八卷,第四期,第507-518頁。
  38. 余秀梅 (1994),「多元商品模式應用在動態貨櫃調度問題之研究」,國立成功大學交通管理科學研究所碩士論文。
  39. 周文生、黃台生、黃慧娟、王裕民、詹彥倫、許采蘋 (2004),「九十三年度臺北地區計程車營運情形調查」,台北縣市政府交通局委託中華民國運輸學會辦理。
  40. 許采蘋 (2005),「計程車共乘與撥召計程車可行條件之研究」,碩士論文,國立交通大學交通運輸研究所。
  41. 陳妙珍、顏上堯、張珮璇 (2000),「航空公司資產與負債管理模式之建立」,第四屆海峽兩岸會計與管理學術研討會論文集,武漢。
  42. 陶治中 (2005),「智慧型運輸系統應用於高乘載計畫之示範與建置-都會區共乘系統之示範與建置(1/2)」,交通部科技顧問室。
  43. 陶治中 (2006),「智慧型運輸系統應用於高乘載計畫之示範與建置-都會區共乘系統之示範與建置(2/2)」,交通部科技顧問室。
  44. 龍天立 (1976),「戶到戶公共運輸系統在台北市可行性之初步研究」,運輸計畫季刊,第五卷,第一期,第29~63頁。
  45. 顏上堯、何淑萍 (1994),「飛航排程暨班次表之建立」,運輸計劃季刊,第二十三卷,第一期,第73-90 頁。
  46. Agin, N., and Cullen, D. (1975). “An Algorithm for Transportation Routing and Vehicle Loading,” Logistics, pp.1-20, North Holland, Amsterdam.
  47. 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.
  48. 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.
  49. 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.
  50. 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.
  51. Samuel, W. L. (1998). “Autonomous dial-a-ride transit Benefit-Cost Evaluation,” Volpe National Transportation Systems Center, August, 1998.
  52. 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.
  53. Simpson, R.W. (1969). “A Review of Scheduling and Routing Model for Airline Scheduling,” IX AGIFORS Symposium, Broadway, England.
  54. Vuchic, V. R. (1981). Urban Public Transportation Systems and Technology. Englewood Cliffs, NJ: Prentice-Hall.
Times Cited
  1. 張毓倫(2016)。考量鄰近與順路之一對多 計程車共乘媒合演算法。逢甲大學都市計畫與空間資訊學系學位論文。2016。1-69。 
  2. 李昀蓁(2015)。計程車共乘願付價格之研究-以台中地區為例。逢甲大學運輸科技與管理學系學位論文。2015。1-90。 
  3. 洪羽佑(2008)。災後工程搶修物料補給排程之研究。中央大學土木工程學系學位論文。2008。1-75。
  4. 陳信諺(2008)。計程車共乘及旅客配對整合模式暨求解演算法之研究。中央大學土木工程學系學位論文。2008。1-84。
  5. 劉映岑(2008)。因應拌合廠臨時故障下即時性拌合車派遣規劃之研究。中央大學土木工程學系學位論文。2008。1-97。
  6. 張佑璿(2011)。隨機旅行時間下保全公司運鈔車護運作業排程規劃之研究。中央大學土木工程學系學位論文。2011。1-91。
  7. 王領(2012)。初期通勤型自行車道規劃模式暨求解演算法之研究。中央大學土木工程學系學位論文。2012。1-88。