時窗限制下貨物配送問題求解方法之研究--時空雙準則平行節省啟發法之研擬

Abstract

近年來，企業界的行銷通路系統發生許多變革。其中，由於通路階層的縮減，使得貨 物配送問題益形重要。 貨物配送問題的關鍵要素有三：巡行、排程與裝載問題。其中巡行問題的處理旨在降 低運輸成本；滿足顧客對特定配送時間的要求或配合道路系統的行駛時間限制，則屬 於排程問題；對配送者而言，車輛的裝載限制，即構成裝載問題。包含上述三個關鍵 要素的貨物配送問題，稱為時窗限制車輛巡迴問題。 目前有關時窗限制車輛巡迴問題之研究，大多採用路線循序構建法處理，其缺失為對 路線的安排無法做整體性的考量；並且未對三大關鍵同時提出因應之道。本研究即針 對上述缺點，提出時空雙準則平行節省法，除了採用路線同時構建法，並應用配對問 題的處理技巧，使路線安排具整體性的考量；另外，本研究分別以修正節省指標、排 程彈性及加入虛擬點集合的技巧，同時求解巡行、排程及裝載三個關鍵問題。 為評估時空雙準則平行節省啟發法的績效，本研究以亂數隨機產生的方式，分為寬時 窗及窄時窗兩組，每組產生30次50個顧客點的測試簡例，在路線數、總巡行距離、總 排程時間等評估準則下，其結果顯示，不論是求解結果精確度或其穩定性，都比插入 法的表現為佳。 另外，本研究以一實例進行分析的結果顯示，本研究所評提之啟發式解法，不但求解 結果精確度較高，且可提供更多排程的資訊，對場站內外作業介面的建立具有實質貢 獻。