跳到主要內容

臺灣博碩士論文加值系統

(44.210.85.190) 您好!臺灣時間:2022/12/10 13:52
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:邱柏學
研究生(外文):Po-Hsueh Chiu
論文名稱:考慮不確定性分析之車輛途程問題
論文名稱(外文):Uncertainty analysis on Dial-a-Ride Problem
指導教授:楊康宏楊康宏引用關係
指導教授(外文):Kang-Hung Yang
學位類別:碩士
校院名稱:中原大學
系所名稱:工業與系統工程研究所
學門:工程學門
學類:工業工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:中文
論文頁數:55
中文關鍵詞:車輛途程問題復康巴士撥召問題啟發式演算法不確定性分析
外文關鍵詞:Heuristic AlgorithmUncertainty AnalysisVehicle Routing ProblemDial-a-Ride ProblemFu-kang Bus
相關次數:
  • 被引用被引用:0
  • 點閱點閱:194
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
台灣的社會服務中,身障者服務早已經成為一個健全社會不可或缺的項目之一,隨著法案的頒布以及大眾對於平等生活權之重視,對於身障人士在交通運輸需求上,可利用復康巴士作為身障者達成遠距旅程戶到戶的交通需求。
復康巴士屬於撥召問題(Dial-a-Ride Problem),在問題定義中,有多台復康巴士,由同一場站去接送多組的乘客需求,每位乘客需求皆有時間窗限制,而問題定義與車輛途程問題含時間窗限制(Vehicle Routing Problem with Time window)相似,復康巴士需於時間窗限制內抵達乘客需求點進行服務。本研究透過了解撥召問題之特性,編寫符合此特性之車輛排程演算法;接著,利用演算法求解之結果去探究撥召問題之服務時間、車輛速度以及時間窗長度在考慮不確定性狀況下,對求解結果之影響。結果顯示,車輛總等待時間的部分在服務時間遞增時呈現上升趨勢,在車輛速度遞增時呈現下降趨勢,在時間窗長度遞增時呈現下降趨勢;接著,車輛總旅程時間的部分在服務時間與時間窗長度遞增時無明顯變動趨勢,在車輛速度遞增時呈現下降趨勢;最後,車輛使用數量部分在服務時間遞增時無明顯變動,在車輛速度遞增時呈現下降趨勢,在時間窗長度遞增時呈現下降趨勢。


Social services in Taiwan already become an integral part of a complete society, especially service of disablement. With the promulgation of the bill and noticing about importance of equal rights of life, in the aspect of transporting disabled persons, Dial-a-Ride service is the best way to satisfy a long-distance request for disabilities and let them to reach the destination from door to door.
Fu-kang Bus are classified to Dial-a-Ride Problem(DARP), in the definition of the problem, more than one vehicles from a certain station to pick a group of passengers, each demand has a time window constrain. DARP is similar to the Vehicle Routing Problem with Time Windows, all of the services need to be hell within the time window. Through this study, we want to understand the characteristics of the DARP, and then propose a vehicle routing heuristic algorithm. Using this algorithm to analyse three parameters concluding service time, speed of vehicle and time window period under uncertainty condition. And then we discuss the effect of solution results. The results showed that the total waiting time of vehicles showing a upward trend when service time is increasing, showing a downward trend when the vehicle speed is increasing, showing a downward trend when the time window length increments; on the other part, the total traveling time of vehicles have no significant change while increasing the service time and length of time windows, however, when the vehicle speed is increasing it showing a downward trend; Finally, when the service time in increments , the number of vehicles using have no significant change, when the vehicle speed is increasing, it showing a downward trend, when the time window length increments it showing dropped.


目錄
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的與問題定義 4
1.3 研究架構與章節概要 6
第二章 撥召問題文獻回顧 7
第三章 數學模式與啟發式演算法 11
3.1 基本假設 11
3.2 符號說明 12
3.3 撥召問題模式與啟發式演算法 13
3.3.1 數學模式 14
3.3.2 演算法介紹 16
3.3.3 演算法步驟說明 18
第四章 參數分析與探討 20
4.1 演算法範例測試與比較 20
4.2 變動服務時間對於求解結果之影響分析 22
4.3 變動車輛速度對於求解結果之影響分析 27
4.4 變動時間窗長度變動對於求解結果之影響分析 31
第五章 結論與建議 36
5.1 結論 36
5.2建議 38
參考文獻 40
附錄A 43
附錄B 44

圖目錄
圖1 撥召問題示意圖 5
圖2 演算法排班示意圖 17
圖3 本研究演算法之流程圖 19
圖4 服務時間對於目標函數之影響狀況圖 24
圖5 服務時間對於車輛使用數關係圖 26
圖6 車輛速度對於目標函數之影響狀況圖 29
圖7 車輛速度對於車輛使用數關係圖 30
圖8 時間窗長度對於目標函數之影響狀況圖 32
圖9 時間窗增加示意圖 34
圖10 車輛速度對於車輛使用數關係圖 35

表目錄
表1 身心障礙類別 2
表2 撥召問題比較 9
表3 範例基本假設 20
表4 本研究演算法與(Cordeau et al., 2007)之求解結果比較 21
表5 遞增服務時間 22
表6 遞減服務時間 23
表7 服務時間變動對於目標函數數據 23
表8 服務時間變動對於旅程時間影響分析值 24
表9 服務時間變動對於等待時間影響分析值 25
表10 服務時間變動對於車輛使用數影響之分析值 27
表11 調整車輛速度 28
表12 車輛速度變動對於目標函數數據 29
表13 調整時間窗長度 31
表14 時間窗長度變動對於目標函數數據 32
表15 服務時間變動對於旅程時間影響分析值 33


參考文獻
蘇昭銘, 楊琮平. (2000). 先進撥召公車營運管理系統之研究. 中華管理學報, 1, 89-114.
陳百傑. (2002). 以啟發式演算法求解時窗限制車輛塗成問題. (碩士), 中原大學.
張凱勝. (2004). 台北市復康巴士與捷運整合服務之研究. (碩士), 國立台灣大學.
辛孟鑫. (2005). 撥召運輸系統路線規劃問題之研究-以台北市復康巴士為例. (碩士), 國立成功大學.
陳家和, 丁慶榮. (2005). 應用螞蟻演算法於時窗限制車輛途程問題之研究. 運輸學刊, 3, 261-280.
李國村. (2006). 以群蟻演算法求解動態車輛途程規劃. 朝陽科技大學.
魏建宏, 王穆衡, 蔡欽同, 辛孟鑫. (2007). 台北市復康巴士路線規劃問題之研究. 運輸學刊, 19, 301-332.
詹火生. (2011). 一甲子以來台灣社會福利政策的演變:從理念政策到制度實踐. 社會福利論壇研討會論文
林奕隆. (2011). 應用蜂群最佳化演算法求解撥召問題-以復康巴士為例. (碩士), 中央大學.

Baldacci, R., Bartolini, E., &; Mingozzi, A. (2011). An Exact Algorithm for the Pickup and Delivery Problem with Time Windows. Operations Research, 59(2), 414-426. doi: 10.1287/opre.1100.0881
Baugh, J. W., Kakivaya, G. K. R., &; Stone, J. R. (1998). Intractability of the Dial-a-Ride Problem and a Multiobjective Solution Using Simulated Annealing. Engineering Optimization, 30(2), 91-123. doi: 10.1080/03052159808941240
Chevrier, R., Liefooghe, A., Jourdan, L., &; Dhaenens, C. Solving a Dial-a-Ride Problem with a Hybrid Multi-objective Evolutionary Approach: Application to Demand Responsive Transport. Applied Soft Computing, 12(4), 1247-1258.
Cordeau, J.-F. (2006). A Branch-and-Cut Algorithm for the Dial-a-Ride Problem. Operations Research, 54(3), 573-586. doi: 10.1287/opre.1060.0283
Cordeau, J.-F., &; Laporte, G. (2003). A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological, 37(6), 579-594. doi: http://dx.doi.org/10.1016/S0191-2615(02)00045-0
Cordeau, J.-F., &; Laporte, G. (2007). The dial-a-ride problem: models and algorithms. Annals of Operations Research, 153(1), 29-46. doi: 10.1007/s10479-007-0170-8
Ho, S., &; Haugland, D. (2011). Local search heuristics for the probabilistic dial-a-ride problem. OR Spectrum, 33(4), 961-988. doi: 10.1007/s00291-009-0175-6
Hunsaker, B., &; Savelsbergh, M. (2002). Efficient feasibility testing for dial-a-ride problems. Operations Research Letters, 30(3), 169-173. doi: http://dx.doi.org/10.1016/S0167-6377(02)00120-7
Issam, Z., Khaled, M., Kamel, Z., &; Khaled, G. (2012). A multi-objective simulated annealing for the multi-criteria dial a ride problem. Eng. Appl. Artif. Intell., 25(6), 1121-1131. doi: 10.1016/j.engappai.2012.03.012
Jorgensen, R. M., Larsen, J., &; Bergvinsdottir, K. B. (2007). Solving the Dial-a-Ride problem using genetic algorithms. Journal of the Operational Research Society, 58, 1321–1331.
Kirchler, D., &; Wolfler Calvo, R. (2013). A Granular Tabu Search algorithm for the Dial-a-Ride Problem. Transportation Research Part B: Methodological, 56(0), 120-135. doi: http://dx.doi.org/10.1016/j.trb.2013.07.014
Lin, C. K. Y., Chow, C. K., &; Chen, A. (2002). A location-routing-loading problem for bill delivery services. computers &; Industrial Engineering, 43(1–2), 5-25. doi: http://dx.doi.org/10.1016/S0360-8352(02)00060-8
Luo, Y., &; Schonfeld, P. (2007). A rejected-reinsertion heuristic for the static Dial-A-Ride Problem. Transportation Research Part B: Methodological, 41(7), 736-755. doi: http://dx.doi.org/10.1016/j.trb.2007.02.003
Masson, R., Lehuédé, F., &; Péton, O. (2014). The Dial-A-Ride Problem with Transfers. Computers &; Operations Research, 41(0), 12-23. doi: http://dx.doi.org/10.1016/j.cor.2013.07.020
Muelas, S., LaTorre, A., &; Peña, J.-M. (2013). A variable neighborhood search algorithm for the optimization of a dial-a-ride problem in a large city. Expert Systems with Applications, 40(14), 5516-5531. doi: http://dx.doi.org/10.1016/j.eswa.2013.04.015
Parragh, S. N., Doerner, K. F., &; Hartl, R. F. (2010). Variable neighborhood search for the dial-a-ride problem. Computers &; Operations Research, 37(6), 1129-1138. doi: http://dx.doi.org/10.1016/j.cor.2009.10.003
Prins, C., Prodhon, C., Ruiz, A., Soriano, P., &; Wolfler Calvo, R. (2007). Solving the Capacitated Location-Routing Problem by a Cooperative Lagrangean Relaxation-Granular Tabu Search Heuristic. Transportation Science, 41(4), 470-483. doi: 10.1287/trsc.1060.0187
Psaraftis, H. N. (1980). A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem. Transportation Science, 14(2), 130-154. doi: doi:10.1287/trsc.14.2.130
Schilde, M., Doerner, K. F., &; Hartl, R. F. Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem. European Journal of Operational Research(0). doi: http://dx.doi.org/10.1016/j.ejor.2014.03.005
Schilde, M., Doerner, K. F., &; Hartl, R. F. (2011). Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports. Computers &; Operations Research, 38(12), 1719-1730. doi: http://dx.doi.org/10.1016/j.cor.2011.02.006
Schilde, M., Doerner, K. F., &; Hartl, R. F. (2014). Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem. European Journal of Operational Research, 238(1), 18-30. doi: http://dx.doi.org/10.1016/j.ejor.2014.03.005
Sophie N. Parragh, K. F. D., Richard F. Hartl. (2009). Variable Neighborhood Search for the Dial-a-Ride Problem.
Tang, J., Kong, Y., Lau, H., &; Ip, A. W. H. (2010). A note on “Efficient feasibility testing for dial-a-ride problems”. Operations Research Letters, 38(5), 405-407. doi: http://dx.doi.org/10.1016/j.orl.2010.05.002
Xiang, Z., Chu, C., &; Chen, H. (2006). A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints. European Journal of Operational Research, 174(2), 1117-1139. doi: http://dx.doi.org/10.1016/j.ejor.2004.09.060
Xiang, Z., Chu, C., &; Chen, H. (2008). The study of a dynamic dial-a-ride problem under time-dependent and stochastic environments. European Journal of Operational Research, 185(2), 534-551. doi: http://dx.doi.org/10.1016/j.ejor.2007.01.007
Yu, B., Yang, Z.-Z., &; Yao, B. (2009). An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 196(1), 171-176. doi: http://dx.doi.org/10.1016/j.ejor.2008.02.028
Yu, V. F., Lin, S.-W., Lee, W., &; Ting, C.-J. (2010). A simulated annealing heuristic for the capacitated location routing problem. computers &; Industrial Engineering, 58(2), 288-299. doi: http://dx.doi.org/10.1016/j.cie.2009.10.007
Zidi, I., Zidi, K., Mesghouni, K., &; Ghedira, K. (2012). A contribution to the modelling and the resolution of a multi–objective dial a ride problem. International Journal of Engineering Management and Economics, 3(1), 95-116. doi: 10.1504/IJEME.2012.048607

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top