透過您的圖書館登入
IP:52.23.231.207
  • 學位論文

運用禁忌搜尋裝箱演算法探討考量碳排放之具時窗限制車輛途程問題

Tabu Search and a Bin Packing Algorithm for the Vehicle Routing Problem with Time Windows and Carbon Emission Reduction

指導教授 : 林耘竹

摘要


車輛途程問題中最重要的規劃內容包含了車輛的運用,而近年來,對車輛途程問題(VRP)的研究常試圖將所謂的“綠色”概念與經典的車輛途程問題模型進行結合。隨著我國《溫室氣體減量與管理法》的頒布,物流業者更需要一個新的工具來評估不同碳政策下對減少排放的影響。鑑此,本研究提出一個能夠考量車輛排放係數會依時、依地變化之具時窗限制車輛途程規劃問題,探討使用租賃車隊服務一群具有特定時窗客戶之需求配送計畫,以最小化車輛使用、最小化旅行距離和最小化總碳排放量為目標。由於模型較為複雜且難以求解,我們參考Lodi et al. (2004) 所提出之原本用以求解裝箱問題的禁忌搜尋裝箱演算法以及Baltzersen (2010) 修正以Solomon (1987) 之循序節省插入法建構初始解的流程架構,本研究另提出新的填充函數定義,發展適用於本問題之啟發式演算法加以求解。最後,修改Solomon(1987)所設計之56題具時窗限制之車輛途程問題國際標竿測試例題以進行測試,並與Lodi et al. (2004) 、Baltzersen (2010) 等人所提出之填充函數求解結果進行比較分析。研究結果顯示,本研究所提出之填充函數在求解時窗較為寬鬆之車輛途程規劃問題上,其求解結果之總車輛數、總旅行距離與總碳排放量較佳。

並列摘要


Vehicle routing comprises the most important operational planning problems related to the deployment of freight carrier vehicles. Recent research on the vehicle routing problem (VRP) attempts to integrate so-called “green” aspects into classical planning models. Freight carriers need a tool to evaluate properly impacts of different carbon tax policy on emission reduction in advanced. In this research, we explore a vehicle routing problem with time windows and carbon emission reduction which consists of routing a number of vehicles to serve a set of customers within preset time windows, so as to minimize the vehicle used, total distance and total carbon emission. It is worthy to note that we consider business situations of private fleet and rental fleet and region-dependent carbon emission rates in this study. Because of the computational intractability of the new VRP, we modify the algorithm called “TSPack Algorithm” from Lodi et al. (2004), which naturally used in the bin packing problems to minimize the number of bins, to develop suitable heuristics. We also used Solomon’s heuristic to get the initial solution and tabu search to improve the solution quality, as Baltzersen (2010) did before, but we proposed a new filling function. We redesigned the benchmark problem sets of Solomon's VRPTW instances. Comparisons of numerical experiments were performed to estimate the effectiveness of different filling functions among Lodi et al. (2004), Baltzersen (2010), and this study. The total number of vehicle used, total distance and total carbon emissions achieved by the proposed algorithm is superior only for the VRP with wide time windows.

參考文獻


44. 陳百傑 (2002),以啟發式演算法求解時窗限制車輛途程問題,中原大學工業工程學系碩士論文。
42. 張潔穎 (2015),考量碳排放量的城市物流計劃方法之發展,國立中央大學企業管理研究所碩士論文。
48. 賴怡儒 (2014),考慮碳排成本的二階車輛路線規劃問題之研究,國立交通大學運輸與物流管理學系碩士論文。
47. 楊明仁 (2011),模擬退火法結合禁忌搜尋法求解車輛回程途徑問題,華梵大學資訊管理學系碩士論文。
43. 莊凱智 (2011),應用改良式粒子群演算法於旅行銷售員問題,國立高雄應用科技大學工業工程與管理學系碩士論文。

延伸閱讀