Title

應用VNS演算法求解撥召服務結合貨物運送之研究

Translated Titles

Solving Combined Passenger-Cargo Dial-a-Ride Problem by Variable Neighborhood Search Algorithm

DOI

10.6342/NTU202003076

Authors

蔡侑勛

Key Words

長照交通接送服務 ; 撥召運輸 ; VNS演算法 ; 客貨混載 ; 需求反應式運輸服務 ; Long-Term Care Transportation Services ; Dial-a-Ride ; VNS algorithm ; Combined Passenger-Cargo Mode ; DRTS

PublicationName

臺灣大學土木工程學研究所學位論文

Volume or Term/Year and Month of Publication

2020年

Academic Degree Category

碩士

Advisor

張學孔

Content Language

繁體中文

Chinese Abstract

隨著人口結構的改變,我國已從高齡化社會正式進入高齡社會,並將在2026年邁入超高齡社會。因此政府積極推動「長期照顧計畫2.0」以因應逐年增加的長照需求,其中長照交通接送則為提供年長者在就醫、復健之撥召運輸服務。該長照運輸服務的特色是車輛路線與班表具有一定的彈性,且需求皆有時窗的限制以確保服務品質。本研究以長照交通接送服務為研究對象,依據撥召運輸特性,並考量民眾生活日常需求,引入客貨混載營運模式,建構撥召服務結合貨物運送之途程問題模型,在最小營運成本目標並有一定服務品質條件下,求解最小派遣車輛數。 本研究在求解大規模問題時是應用VNS演算法,共設計六種鄰域結構,並加入模擬退火演算法之劣解接受機制來增加求解的廣度。研究中首先建立兩個模擬案例,用以驗證本研究VNS演算法求得的解與精確解間之誤差能控制於5%內。實例分析的部分是以台中市區與梨山偏鄉作為驗證案例,並收集實際一週需求資料進行車輛派遣的規劃,結果顯示VNS演算法多能在3分鐘內完成求解;本研究進一步比較「客貨混載」與「客貨分載」模式的績效,客貨混載模式在營運成本、共乘率與派遣車輛數等面向皆優於單一客載模式。整體而言,研究分析結果顯示本研究建立之客貨混載模型及其求解方法能夠有效協助長照車隊之途程規劃,提升車輛有限運能與營運效率,增加長照行動服務之社會福祉。

English Abstract

With the change of population structure, Taiwan has formally entered the aging society, and will enter the super-aged society in 2026. Therefore, the government has implemented Long-Term Care Plan 2.0 to respond to the increasing demand for long-term care in recent years. Long-Term Care Transportation Service provides the elderly with medical treatment or rehabilitation transportation service. Its service features consisted of flexibility on the routing and scheduling, and the service quality is ensured by the time window. This study aims on long-term care bus with considering the full functions of medicine care and daily living needs. According to the dial-a-ride characteristics and the combined passenger-cargo operation mode, a combined passenger-cargo dial-a-ride problem model is developed with the objective of minimizing fleet size under the minimum operating cost and specific service quality. In this study, VNS algorithm applied for the optimization model, a total of six neighborhood structures are designed, and the poor solution acceptance mechanism of SA algorithm is also established. Two simulation cases are established to verify the differences between VNS algorithm and exact solution can be controlled within 5%. The part of the case study, one week is used as the verification length in Taichung City and Lishan. The results show that VNS algorithm can solve the problems within 3 minutes. This study further explores the combined passenger-cargo mode, and the results show that the combined passenger-cargo mode is superior to the original mode in terms of total cost, carpooling rate, and the number of vehicles. It has been shown that combined passenger-cargo mode and the method established in this study can effectively assist the vehicle fleet planning, improve the utilization of vehicle capacity, and also increase the social welfare.

Topic Category 工學院 > 土木工程學研究所
工程學 > 土木與建築工程
Reference
  1. 1. Attanasio, A., Cordeau, J. F., Ghiani, G. Laporte, G. (2004). Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem. Parallel Computing, 30(3), 377-387.
  2. 2. Awad, H. Elshaer, R. (2019). A Taxonomic Review of Metaheuristic Algorithms for Solving the Vehicle Routing Problem and Its Variants. Computers Industrial Engineering, 140, 106242.
  3. 3. Beaudry, A., Laporte, G., Melo, T. Nickel, S. (2010). Dynamic transportation of patients in hospitals. OR spectrum, 32(1), 77-107.
  4. 4. Birim, Ş. (2016). Vehicle routing problem with cross docking: A simulated annealing approach. Procedia-Social and Behavioral Sciences, 235(Supplement C), 149-158.
  5. 5. BoussaïD, I., Lepagnot, J. Siarry, P. (2013). A survey on optimization metaheuristics. Information sciences, 237, 82-117.
  6. 6. Braekers, K. Kovacs, A. A. (2016). A multi-period dial-a-ride problem with driver consistency. Transportation Research Part B: Methodological, 94, 355-377.
  7. 7. Cattaruzza, D., Absi, N., Feillet, D. Vigo, D. (2014). An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows. Computers Operations Research, 51, 257-267.
  8. 8. Cordeau, J. F. Laporte, G. (2003). The dial-a-ride problem (DARP): Variants, modeling issues and algorithms. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1(2), 89-101.
  9. 9. Cordeau, J. F. Laporte, G. (2007). The dial-a-ride problem: models and algorithms. Annals of operations research, 153(1), 29-46.
  10. 10. Dantzig, G. B. Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91.
  11. 11. Dorigo, M., Maniezzo, V. Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29-41.
  12. 12. Dueck, G. Scheuer, T. (1990). Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing. Journal of computational physics, 90(1), 161-175.
  13. 13. Dumas, Y., Desrosiers, J. and Soumis, F. (1989). Large scale multi-vehicle dial-a-ride problems. Les Cahiers du GERAD, G-89-30, Ecole des Hautes Etudes Commercials, Montreal.
  14. 14. Ferreira, H. S., Bogue, E. T., Noronha, T. F., Belhaiza, S. Prins, C. (2018). Variable neighborhood search for vehicle routing problem with multiple time windows. Electronic Notes in Discrete Mathematics, 66, 207-214.
  15. 15. Fu, L. Teply, S. (1999). On-line and off-line routing and scheduling of dial-a-ride paratransit vehicles. Computer-Aided Civil and Infrastructure Engineering, 14(5), 309-319.
  16. 16. Gianessi, P., Ceselli, A., Létocart, L. Calvo, R. W. (2016). A Branch Price Cut algorithm for the Vehicle Routing Problem with Intermediate Replenishment Facilities. Electronic Notes in Discrete Mathematics, 55, 93-96.
  17. 17. Glover, F. (1986). Future paths for integer programming and links to artificial intelligence. Computers operations research, 13(5), 533-549.
  18. 18. Gutierrez, A., Dieulle, L., Labadie, N. Velasco, N. (2016). A multi population memetic algorithm for the vehicle routing problem with time windows and stochastic travel and service times. IFAC-PapersOnLine, 49(12), 1204-1209.
  19. 19. Hansen, P. Mladenović, N. (2003). Variable neighborhood search. In Handbook of metaheuristics (pp. 145-184). Springer, Boston, MA.
  20. 20. Hemmelmayr, V. C., Doerner, K. F. Hartl, R. F. (2009). A variable neighborhood search heuristic for periodic routing problems. European Journal of Operational Research, 195(3), 791-802.
  21. 21. Ho, S. C., Szeto, W. Y., Kuo, Y. H., Leung, J. M., Petering, M. Tou, T. W. (2018). A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological, 111, 395-421.
  22. 22. Holland, J. (1975). Adaptation in natural and artificial systems: an introductory analysis with application to biology. Control and artificial intelligence.
  23. 23. Hoos, H. H. Tsang, E. (2006). Local search methods. Foundations of Artificial Intelligence, 2, 135-167, Elsevier.
  24. 24. 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(10), 1321-1331.
  25. 25. Kirkpatrick, S., Gelatt, C. D. Vecchi, M. P. (1983). Optimization by simulated annealing. science, 220(4598), 671-680.
  26. 26. Kulachenko, I. N., Kononova, P. A., Kochetov, Y. A. Kurochkin, A. A. (2019). The variable neighborhood search for a consistent vehicle routing problem under the shift length constraints. IFAC-PapersOnLine, 52(13), 2314-2319.
  27. 27. Kuo, Y. Wang, C. (2012). A variable neighborhood search for the multi-depot vehicle routing problem with loading cost. Expert Systems with Applications, 39(8), 6949-6954.
  28. 28. Laporte, G., Gendreau, M., Potvin, J-Y and Semet, F. (2000), “Classical and Modern Heuristics for the Vehicle Routing Problem,” International Transactions in Operational Research, 7(4-5), 285-300.
  29. 29. Lin, S. W., Vincent, F. Y. Lu, C. C. (2011). A simulated annealing heuristic for the truck and trailer routing problem with time windows. Expert Systems with Applications, 38(12), 15244-15252.
  30. 30. Lucic, P. Teodorovic, D. (2001). Bee system: modeling combinatorial optimization transportation engineering problems by swarm intelligence. Preprints of the TRISTAN IV triennial symposium on transportation analysis, 441-445.
  31. 31. Madsen, O. B., Ravn, H. F. Rygaard, J. M. (1995). A heuristic algorithm for a dial-a-ride problem with time windows, multiple capacities, and multiple objectives. Annals of operations Research, 60(1), 193-208.
  32. 32. Melachrinoudis, E., Ilhan, A. B. Min, H. (2007). A dial-a-ride problem for client transportation in a health-care organization. Computers Operations Research, 34(3), 742-759.
  33. 33. Mitrovic-Minic, S., Krishnamurti, R. and Laporte, G. (2004). Double-horizon Based Heuristics for the Dynamic Pickup and Delivery Problem with Time Windows. Transportation Research Part B, 38, 669-685.
  34. 34. Mladenović, N. Hansen, P. (1997). Variable neighborhood search. Computers Operations Research, 24(11), 1097-1100.
  35. 35. Moshref-Javadi, M. Lee, S. (2016). The customer-centric, multi-commodity vehicle routing problem with split delivery. Expert Systems with Applications, 56, 335-348.
  36. 36. Or, I. (1976). Traveling salesman-type combinatorial problems and their relation to the logistics of regional blood banking. Northwestern University, PhD. Dissertation.
  37. 37. 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.
  38. 38. Ropke, S. Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4), 455-472.
  39. 39. Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In International conference on principles and practice of constraint programming, 417-431.
  40. 40. Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2), 254-265.
  41. 41. Solomon, M. M. Desrosiers, J. (1988). Survey paper—time window constrained routing and scheduling problems. Transportation science, 22(1), 1-13.
  42. 42. 張學孔、蘇雄義(1993),網枝途程問題之設定與求解,運輸計劃季刊,22(2),139-166。
  43. 43. 魏健宏、王穆衡、蔡欽同、辛孟鑫(2007),台北市復康巴士路線規劃問題之研究,運輸學刊,19(3),301-332。
  44. 44. 陳惠國、林奕隆、王宣(2013),應用修正式蜂群最佳化演算法求解撥召問題-以復康巴士問題為例,運輸學刊,25(3),279-308。
  45. 45. 辛孟鑫(2005),撥召運輸系統路線規劃問題之研究-以台北市復康巴士為例,成功大學交通管理科學系碩士論文。
  46. 46. 郭佳林(2005),求解具時間窗之多趟次車輛途程問題,交通大學運輸科技與管理學系碩士論文。
  47. 47. 林志鴻、許晉嘉(2006),宅配業車輛路線問題之研究,運輸計劃季刊,35(4),443-474。
  48. 48. 傅宣維(2019),應用ALNS演算法求解多場站撥召問題之研究,臺灣大學土木工程學研究所碩士論文。
  49. 49. 陳俊穎、蘇昭銘(2014),以接駁型需求反應式公車服務模型解決偏遠地區運輸問題之初探,都市交通半年刊,29(1),32-41。
  50. 50. 蔡孟儒(2013),求解動態撥召問題 : 以復康巴士為例,淡江大學資訊管理學系碩士論文。
  51. 51. 林依潔(2002),整合模糊理論與螞蟻演算法於含時窗限制之車輛途程問題,台北科技大學生產系統工程與管理系碩士論文。
  52. 52. 張廷吉(2000),考慮派車時段與載重均衡之車輛途程規劃問題,逢甲大學工業工程研究所碩士論文。
  53. 53. 林孝禹(2014),以變動鄰域搜尋法求解可調式多載具之車輛途程問題,臺灣科技大學工業管理系碩士論文。
  54. 54. 卓裕仁、朱佑旌(2008),兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究,運輸計劃季刊,37(4),405-430。
  55. 55. 廖彩雲(2011),以混合啟發式方法求解多場站動態車輛巡迴路線問題研究成果報告,行政院國家科學委員會專題研究計畫。
  56. 56. 邱裕鈞(2009),巨集演算法之發展與應用,國防管理學報,30(2),49-67。
  57. 57. 張學孔、張朝能、陳雅雯、洪鈞澤、史習平、洪勝宇(2019),無障礙小客車多元運輸服務系統平台之建立,運輸計劃季刊,48(3),179-221。
  58. 58. 張學孔、王穆衡等人(2011),「需求反應式公共運輸系統之整合研究(3/3)」,交通部運輸研究所與中華智慧型運輸系統協會合作研究報告。
  59. 59. 侯勝宗、張學孔、唐玄輝等人(2019),從共享經濟邁向共善社會:公私協力的王道實踐,中華民國科技部補助逢甲大學服務創新與行動設計中心研究計畫報告。
  60. 60. 衛生福利部統計處,https://dep.mohw.gov.tw/dos/mp-113.html。
  61. 61. 中華民國內政部戶政司全球資訊網,https://www.ris.gov.tw/app/portal/346。