應用時窗離散策略與可回溯式門檻接受法求解VRPBTW問題之研究

FU-WHA HAN

Research output: Contribution to journalArticle

Abstract

本研究應用時窗離散(Time Window Discretization)策略與可回溯式門檻接受(BATA)法求解具時窗限制之回程取貨車輛路線問題(VRPBTW)。研究方法分為兩階段進行:第一階段採取時間窗離散化的方法,將VRPBTW問題中的時間窗限制消除,轉換成無時間窗的VRPB問題,並設計問題規模精簡策略,縮小問題規模;第二階段求解轉換後的VRPB問題,應用可回溯式門檻接受法作為巨集啟發式解法架構。在求解績效評估方面,本研究以Gelinas et al.(1995)的國際標竿題庫進行測試。結果發現與目前已知最佳結果在車輛數上的平均誤差為0.87輛,且有5題找到文獻已知最佳結果;旅行成本的平均誤差為5.32%。本研究亦發現,對時窗離散所提出的精簡策略可有效地簡化轉換後無時窗的VRPB問題規模。此外,不同題型之測試結果則顯示,本研究提出的結合時窗離散策略與可回溯式門檻接受法的求解架構,對於原作業點時間窗寬度較小且均勻的問題效果較佳。
Original languageChinese (Traditional)
Pages (from-to)285 - 306
Number of pages22
Journal運輸學刊
Volume22
Issue number3
DOIs
StatePublished - 2010

Cite this