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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：10

、訪客IP：18.216.227.76

姓名

林瑜芳(Yu-fang Lin) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

小汽車共乘公平性配對模式暨求解演算法之研究
(Matching Model and Heuristic Algorithm for Fairness in the Carpool Problem)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

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

論文目次

摘要 I
ABSTRACT II
目錄 III
圖目錄 VI
表目錄 VII
第一章　緒論 1
1.1研究背景與動機 1
1.2研究目的與範圍 2
1.3研究方法與流程 2
第二章　文獻回顧 4
2.1共乘定義 4
2.2小汽車共乘相關文獻 6
2.3撥召共乘相關文獻 8
2.4時空網路的相關文獻 11
2.5分解式演算法的相關文獻 14
2.6文獻評析 17
第三章　模式構建 18
3.1模式基本條件或已知資訊 18
3.2成本最小化及公平性之小汽車共乘配對模式 20
3.2.1時空網路 20
3.2.1.1車流時空網路 21
3.2.1.2人流時空網路 23
3.2.2模式符號說明 24
3.2.3數學定式 26
3.3模式應用 28
3.4小結 29
第四章　求解演算法設計 30
4.1目標值下限 32
4.1.1鬆弛公平性及車容量限制式(F1) 32
4.1.2鬆弛車容量限制式(F2) 35
4.1.3鬆弛公平性限制式(F3) 35
4.1.4混合整數問題(MIP) 36
4.2目標值上限 36
4.3收斂機制及求解步驟 41
4.4人車配對 43
4.5小結 44
第五章　範例測試 45
5.1輸入資料 45
5.1.1車輛規劃資料 45
5.1.2共乘旅次資料 47
5.1.3基準距離(T) 47
5.2模式發展 47
5.2.1問題規模 47
5.2.2模式輸入資料 48
5.3電腦演算環境及設定 49
5.3.1電腦演算環境 49
5.3.2相關程式設定 49
5.3.3模式輸出資料 50
5.4測試結果與分析 50
5.5敏感度分析 54
5.5.1基準距離(T)之敏感度分析 54
5.5.2旅行時間成本之敏感度分析 57
5.6方案分析 59
5.6.1不同路網型態分析 59
5.6.2不同目標式之分析 61
5.6.3虛擬規劃日數量之分析 63
5.7演算法求解績效分析 65
5.8小結 67
第六章　結論與建議 68
6.1結論 68
6.2建議 69
6.3貢獻 70
參考文獻 71
附錄 78
附錄一 CPLEX Callable Library Code 78
附錄二範例測試之輸入資料 79
附錄三公平性模式與最小成本模式輸出結果 82

參考文獻

交通部全球資訊網，網址http://www.motc.gov.tw/，(2008)。
共乘網，http://www.carpool.com.tw/，(2008)。
向美田，「公車動態資訊與撥召系統之研究與建立-以金門縣為例」，碩士論文，國立交通大學交通運輸研究所 (1997)。
何依栖，「都會區計程車共乘制度實施及管理之探討」，運輸計畫季刊，第十八卷，第四期，頁507-518 (1989)。
余秀梅，「多元商品模式應用在動態貨櫃調度問題之研究」，碩士論文，國立成功大學交通管理科學研究所 (1994)。
吳沛儒，「任務型共乘接駁計程車之規劃與設計」，碩士論文，逢甲大學交通工程與管理研究所 (2005)。
辛孟鑫，「撥召運輸系統路線規劃問題之研究－以台北市復康巴士為例」，碩士論文，國立成功大學交通管理科學研究所 (2005)。
林明德，「供給導向之都會區最適運具組合研究」，碩士論文，淡江大學土木工程學系 (1995)。
邱明琦，陳春益，林佐鼎，「海運貨櫃排程模式之研究」，運輸計劃季刊，第三十一卷，第三期，第495-522頁 (2002)。
寇世傑，「以習慣領域理論探討推動通勤者共乘行為之契機」，碩士論文，國立交通大學交通運輸研究所 (1998)。
張有恆，都市公共運輸，華泰書局 (1994)。
許采蘋，「計程車共乘與撥召計程車可行條件之研究」，碩士論文，國立交通大學交通運輸研究所 (2005)。
郭瑜堅，「都市旅次成本之研究」，碩士論文，國立台灣大學土木工程研究所交通組 (2003)。
陳妙珍、顏上堯、張珮璇，「航空公司資產與負債管理模式之建立」，第四屆海峽兩岸會計與管理學術研討會論文集，武漢 (2000)。
陳春益，邱明琦，「貨櫃航線網路設計模式之研究」，運輸計劃季刊，第三十一卷，第二期，第267-298頁 (2002)。
陶治中、張勝雄等人，智慧型運輸系統應用於高乘載計畫之示範與建置-都會區共乘系統之示範與建置(2/2)，交通部科技顧問室 (2005)。
曾國雄，「合車用乘(Car pool)在臺灣地區之可行性」，能源季刊，第十二卷，第三期，第13-19頁 (1982a)。
曾國雄，「合租用乘(Van pool)在臺灣地區之可行性」，能源季刊，第十二卷，第三期，第20-29頁 (1982b)。
黃漢瑄，「撥召服務最佳化指派作業之研究」，碩士論文，淡江大學運輸管理研究所 (2006)。
楊淑芳，「以巨集啟發式演算法求解即時資訊下之中型車共乘問題」，碩士論文，淡江大學運輸管理研究所 (2006)。
賴淑芬，「工業區實施車輛共乘之可行性研究與規劃-以高雄市楠梓加工出口區為例」，碩士論文，國立成功大學交通管理學系 (1990)。
顏上堯、何淑萍，「飛航排程暨班次表之建立」，運輸計劃季刊，第二十三卷，第一期，第73-90頁 (1994)。
顏上堯、翁綵穗，「季節轉換間緩衝期飛航排程之研究」，運輸計劃季刊，第三十卷，第四期，第891- 922頁 (2001)。
Abara, J., “Applying integer linear programming to the fleet assignment problem,” Interfaces, Vol. 19, pp. 20-28 (1989).
Agin, N. and Cullen, D., “An algorithm for transportation routing and vehicle loading,” Logistics, pp. 1-20, North Holland, Amsterdam (1975).
Ajtai, M., Aspnes, J., Naor, M., Rabani, Y., Schulman, L. J., and Waarts, O., “Fairness in scheduling,” Journal of Algorithm, Vol. 29, pp. 306-357 (1998).
Aldaihani, M. and Dessouky, M. M., “Hybrid scheduling methods for paratransit operations,” Computers and Industrial Engineering, Vol. 45, pp. 75-96 (2003).
Attanasio, A., Cordeau, J. F., Ghiani, G., and Laporte, G., “Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem,” Parallel Computing, Vol. 30, pp. 377-387 (2004).
Baldacci, R., Maniezzo, V., and Mingozzi, A., “An exact method for the car pooling problem based on Lagrangean column generation,” Operations Research, Vol. 52(3), pp. 422-439 (2004).
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., and Vance, P. H., “Branch-and-price: column generation for solving huge integer programs,” Operations Research, Vol. 46, pp. 316-329 (1998).
Benders, J. F., “Partitioning procedures for solving mixed-variables programming problems,” Numerische Mathematik, Vol. 4, pp. 238-252 (1962).
Boavida, J. P., Kamat, V., Nakum, D., Nong, R., Wu, C. W., and Zhang, X., “Algorithms for the carpool problem,” IBM Research, Yorktown Heights, NY (2006).
Bodin, L. D. and Sexton, T., “The multi-vehicle subscriber dial-a-ride problem,” TIMS Studies in Management Science, Vol. 2, pp. 73-86 (1986).
Calvo, R. W., Luigi, F. L., Haastrup, P., and Maniezzo, V., “A distributed geographic information system for the daily car pooling problem,” Computers and Operations Research, Vol. 31, pp 2263-2278 (2004).
Camerini, P. K., Fratta, L., and Maffioli, F., “On improving relaxation methods by modified gradient techniques,” Mathematical Programming Study, Vol. 3, pp. 6-25 (1975).
Chen, C. Y. and Kornhauser, A. L., “Decomposition of convex mulitcommodity network flow problem,” Report SOR-90-19, Dept. of Civil Engineering and Operations Research, Princeton University, Princeton, NJ (1990).
Chih, K. C. K., “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 (1986).
Clarke, L. W., Hane, C. A., Johnson, E. L., and Nemhauser, G. L., “Maintenance and crew considerations in fleet assignment, ” Transportation Science, Vol. 30, pp. 249-260 (1996).
Coppersmith, D., Nowicki, T. J., Paleologo, G. A., Tresser, C., Wu, C.W., “The optimality of the on-line greedy algorithm in carpool and chairman assignment problems,” IBM Research Report (2005).
Cordeau, J. F. and Laporte, G., “A tabu search heuristic for the static multi-vehicle dial-a-ride problem,” Transportation Research Part B, Vol. 37, pp. 579-594 (2003a).
Cordeau, J. F. and Laporte, G., “The dial-a-ride Problem (DARP): variants, modeling issues and algorithms,” 4OR: A Quarterly Journal of Operations Research, Vol. 1, pp. 89–101 (2003b).
Cordeau, J. F. and Laporte, G., “The dial-a-ride problem: models and algorithms,” Annals of Operations Research, Vol. 153, pp. 29-46 (2007).
Cordeau, J. F., “A branch-and-cut algorithm for the dial-a-ride problem,” Operations Research, Vol. 54, pp. 573-586 (2006).
Coslovich, L., Pesenti, R., and Ukovich, W., “A two-phase insertion technique of unexpected customers for a dynamic dial-a-ride problem,” European Journal of Operational Research, Vol. 175, pp. 1605-1615 (2006).
Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M., and Soumis, F., “Daily aircraft routing and scheduling,” Management Science, Vol. 43, pp. 841-855 (1997).
Desrosiers, J., Dumas, Y., and Soumis, F., “A dynamic programming solution of the large-scale single vehicle dial-a-ride problem with time windows,” American Journal of Mathematical and Management Sciences, Vol. 6, pp. 301-325 (1986).
Diana, M. and Dessouky, M. M., “A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows,” Transportation Research Part B, Vol. 38, pp. 539-557 (2004).
Fagin, R. and Williams, J. H., “A fair carpool scheduling algorithm,” IBM J. Res. Development, Vol. 27(2), pp. 133-139 (1983).
Ferrari, E., Manzini, R., Pareschi, A., Persona, A., and Regattieri, A., “The car pooling problem: heuristic algorithms based on savings functions,” Journal of Advanced Transportation, Vol. 37, pp. 243-272 (2003).
Fisher, M. L., “The Lagrangian relaxation method for solving integer programming problem,” Management Science, Vol. 27, pp. 1-18 (1981).
Gendreau, M., Laporte, G., and Semet, F., “A dynamic model and parallel tabu search algorithm for real-time ambulance relocation,” Parallel Computing, Vol. 27, pp. 1641-1653 (2001).
Hane, C. A., Barnhart, C., Johnson, E. L., Marsten, R., Nemhauser, G. L., and Sigismondi, G., “The fleet assignment problem: solving a large-scale integer program,” Mathematical Programming Study, Vol. 70, pp. 211-232 (1995).
Hart, S.M., “The modeling and solution of a class of dial-a-ride problems using sumulated annealing,” Control and Cybernetics, Vol. 25(1), pp. 1-27 (1996).
Horn, M. E. T., “Fleet scheduling and dispatching for demand-responsive passenger services,” Transportation Research Part C, Vol. 10, pp. 35-63 (2002).
Jaw, J. J., Odoni, A. R., Psaraftis, H. N., and Wilson, N. H. M., “A heuristic algorithm for the multi-vehicle advance-request dial-a-ride problem with time windows,” Transportation Research Part B, Vol. 20, pp. 243-257 (1986).
Jørgensen, R. M., Larsen, J., and Bergvinsdottir, K. B., “Solving the dial-a-ride problem using genetic algorithms,” Journal of the Operational Research Society, Vol.58, pp.1321-1331 (2007).
Kennington, J. L. and Shalby, M., “An effective subgradient procedure for minimum cost multicommodity flow problem,” Management Science, Vol.23, pp.994-1004 (1977).
Lamatsch, A., “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 (1992).
Lee, B. C., “Routing problem with service choices, flight transportation laboratory,” Report R86-4, Massachusetts Institute of Technology, MA (1986).
Levin, A., “Scheduling and fleet routing models for transportation systems,” Transportation Science, Vol. 5, pp. 232-255 (1971).
Levin, A., “Some fleet routing and scheduling problems for air transportation systems,” Flight Transportation Laboratory Report R68-5, Massachusetts Institute of Technology, MA (1969).
Madsen, O. B. G., Ravn, H. F., and Rygaard, J. M., “A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives,” Annals of Operations Research, Vol. 60, pp. 193-208 (1995).
Melachrinoudis, E., Ilhan, A. B., and Min, H., “A dial-a-ride problem for client transportation in a healthcare organization,” Computers and Operations Research, Vol. 34, pp. 742-759 (2007).
Mesquita, M. and Paixao, J., “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 (1992).
Naor M., “On fairness in the carpool problem”, Journal of Algorithm, Vol. 55(1), pp. 93-98 (2005).
Pearlstein, A., “A study of staff and fraculty commuters at the university of California, Los Angeles”, Transportation Research Record, No. 1082, pp. 26-33 (1986).
Powell, W. B. and Ioannis, A. K., “Shipment routing algorithms with tree constraints,” Transportation Science, Vol. 26, pp. 230-245 (1992).
Psaraftis, H. N., “A dynamic programming approach to the single-vehicle, many-to-many immediate request dial-a-ride problem,” Transportation Science, Vol. 14, pp. 130-154 (1980).
Psaraftis, H. N., “An exact algorithm for the single-vehicle many-to-many dial-a-ride problem with time windows,” Transportation Science, Vol. 17, pp. 351-357 (1983).
Rekiek, B., Delchambre, A., and Saleh, H. A., “Handicapped person transportation: an application of the grouping genetic algorithm,” Engineering Application of Artificial Intelligence, Vol. 19, pp. 511-520 (2006).
Ropke, S., Cordeau, J. F., and Laporte, G., “Models and branch-and-cut algorithms for pickup and delivery problems with time windows,” Networks, Vol. 49, pp. 258-272 (2007).
Rose G., “Providing premium carpool parking using a low-tech ITS initiative,” ITE Journal Institute of Transportation Engineers, Vol.72, pp.32-36 (2002).
Samuel, W. L., “Autonomous dial-a-ride transit benefit-cost evaluation,” Volpe National Transportation Systems Center, August (1998).
Sexton, T. and Bodin, L. D., “Optimizing single vehicle many-to-many operations with desired delivery times: I. scheduling,” Transportation Science, Vol. 19, pp. 378-410 (1985a).
Sexton, T. and Bodin, L. D., “Optimizing single vehicle many-to-many operations with desired delivery times: II. routing,” Transportation Science, Vol. 19, pp. 411-435 (1985b).
Sexton, T., “The single vehicle many-to-many routing and scheduling problem,” Ph.D. dissertation, SUNY at Stony Brook (1979).
Shan, Y. S., “A dynamic mulitcommodity network flow model for real time optimal real freight car management,” Ph.D. Dissertation, Princeton University, Princeton, NJ (1985).
Simpson, R.W., “A review of scheduling and routing model for airline scheduling,” IX AGIFORS Symposium, Broadway, England (1969).
Subramanian, R., Scheff, R. P., Quillinan, J. D., Wiper, D. S., and Marsten, R. E., “Coldstart: fleet assignment at Delta Air Lines,” Interface, Vol. 24, pp. 104-120 (1994).
Teodorovic, D. and Guberinic, S., “Optimal dispatching strategy on an airline network after a schedule perturbation,” European Journal of Operational Research, Vol. 15, pp. 178-182 (1984).
Teodorovic, D., “Airline operations research,” Gordon and Breach Science Publishers, New York (1988).
Toth, P. and Vigo, D., “Fast local search algorithms for the handicapped persons transportation problem,” In I. H. Osman and J. P. Kelly (Eds.), Meta-heuristics: Theory and Applications, Kluwer Academic Publishers, Boston, pp. 677-690 (1996).
Toth, P. and Vigo, D., “Heuristic algorithms for the handicapped persons transportation problem,” Transportation Science, Vol. 31, pp. 60-71 (1997).
Wong, K. I. and Bell, M. G. H., “Solution of the dial-a-ride problem with multi-dimensional capacity constraints,” International Transactions in Operational Research, Vol. 13, pp. 195-208 (2006).
Xiang, Z., Chu, C., and Chen, H., “A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints,” European Journal of Operational Research, Vol. 174, pp. 1117-1139 (2006).
Yan, S. and Chen, C.H., “Coordinated flight scheduling models for allied airlines,” Transportation Research Part C, Vol. 15, pp. 246-264 (2007).
Yan, S. and Chen, H. L., “A scheduling model and a solution algorithm for inter-city bus carriers,” Transportation Research Part A, Vol. 36, pp. 805-825 (2002).
Yan, S. and Shih, Y. L. “A time-space network model for work team scheduling after a major disaster,” Journal of Chinese Institute of Engineers, Vol. 30(1), pp. 63-75 (2007).
Yan, S. and Tseng, C. H., “A passenger demand based model for airline flight scheduling and fleet routing,” Computers and Operations Research, Vol. 29, pp. 1559-1581 (2002).
Yan, S. and Young, H. F., “A decision support framework for multi-fleet routing and multi-stop flight scheduling,” Transportation Research Part A, Vol. 30, pp. 379-398 (1996).
Yan, S., Chen, S. C., and Chen, C. H., “Air cargo fleet routing and timetable setting with multiple on-time demands,” Transportation Research Part E, Vol. 42(5), pp. 409-430 (2006a).
Yan, S., Chi, C. J., and Tang, C. H., “Inter-city bus routing and timetable setting under stochastic demands,” Transportation Research Part A, Vol. 40, pp. 572-586 (2006b).
Yan, S., Lai, W. and Chen, M., “Production Scheduling and Truck Dispatching of Ready Mixed Concrete,” Transportation Research, Part E, Vol. 44, Issue 1, pp. 164-179 (2008b).
Yan, S., Tang, C. H., and Shieh, C. N., “A simulation framework for evaluating airline temporary schedule adjustments following incidents,” Transportation Planning and Technology, Vol. 28(3), pp. 189-211 (2005).
Yan, S., Tang, C.H. and Fu, T.C., “An Airline Scheduling Model and Solution Algorithms under Stochastic Demands,” European Journal of Operational Research, Vol. 190, pp. 22-39 (2008a).

指導教授

顏上堯(Shang-yao Yan)

審核日期

2008-7-11

推文