月旦知識庫
 
  1. 熱門:
 
首頁 臺灣期刊   法律   公行政治   醫事相關   財經   社會學   教育   其他 大陸期刊   核心   重要期刊 DOI文章
運輸學刊 本站僅提供期刊文獻檢索。
  【月旦知識庫】是否收錄該篇全文,敬請【登入】查詢為準。
最新【購點活動】


篇名
應用時窗離散策略與可回溯式門檻接受法求解VRPBTW問題之研究
並列篇名
Time Window Discretization and BATA Heuristics for Solving the VRPBTW Problems
作者 韓復華陳仲豪
中文摘要
本研究應用時窗離散(Time Window Discretization)策略與可回溯式門檻接受(BATA)法求解具時窗限制之回程取貨車輛路線問題(VRPBTW)。研究方法分為兩階段進行:第一階段採取時間窗離散化的方法,將VRPBTW問題中的時間窗限制消除,轉換成無時間窗的VRPB問題,並設計問題規模精簡策略,縮小問題規模;第二階段求解轉換後的VRPB問題,應用可回溯式門檻接受法作為巨集啟發式解法架構。在求解績效評估方面,本研究以Gelinas et al.(1995)的國際標竿題庫進行測試。結果發現與目前已知最佳結果在車輛數上的平均誤差為0.87輛,且有5題找到文獻已知最佳結果;旅行成本的平均誤差為5.32%。本研究亦發現,對時窗離散所提出的精簡策略可有效地簡化轉換後無時窗的VRPB問題規模。此外,不同題型之測試結果則顯示,本研究提出的結合時窗離散策略與可回溯式門檻接受法的求解架構,對於原作業點時間窗寬度較小且均勻的問題效果較佳。
英文摘要
Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW), an extension of the classical Vehicle Routing Problem, is a very complicated NP-Hard problem. In this paper, we proposed a two-phase approach to solve the VRPBTW. First, using a time window discretization approach, we removed the time window constraints from the original VRPBTW and transformed it to an approximate VRPB. The second phase was focused on solving the transformed VRPB using a BATA meta-heuristic approach. We also proposed some discretization strategies which can effectively reduce the problem size of the transformed VRPB. The 15 benchmark instances defined by Gelinas et al. (1995) were selected for the evaluation of our proposed meta-heuristics. Results showed that the average deviation from the best known solutions are 0.87 in fleet size and 5.32% in total distance, respectively. We also found five best known solutions of the 15 benchmark instances. In addition, our results imply that our proposed time window discretization approach is most effective for those problems which have uniform and relatively small time windows.
起訖頁 285-306
關鍵詞 時窗離散化門檻接受法可回溯式門檻接受法回程取貨車輛路線問題具時窗限制之回程取貨車輛路線問題Time window discretizationThreshold accepting(TA)Backtrack adaptive threshold accepting(BATA)Vehicle routing problem with backhauls(VRPB)Vehicle routing problem with backhauls and time windows(VRPBTW)
刊名 運輸學刊  
期數 201009 (22:3期)
出版單位 中華民國運輸學會
該期刊-上一篇 以車流狀態為基礎之高速公路旅行時間預測模式
該期刊-下一篇 利用資料填補概念探討車輛偵測器佈設間距
 

新書閱讀



最新影音


優惠活動




讀者服務專線:+886-2-23756688 傳真:+886-2-23318496
地址:臺北市館前路28 號 7 樓 客服信箱
Copyright © 元照出版 All rights reserved. 版權所有,禁止轉貼節錄