物流配送中心货车路线问题之研究.doc

《物流配送中心货车路线问题之研究.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、物流配送中心貨車路線問題之硏究硏究生：邱志鴻指導教授：謝尙賢陳俊杉一'緒論1.1硏究動機與目的由於資訊產業與Internet的蓬勃發展，帶動商業電子化的潮流，而網路商店的興起更是帶給民眾購物上的便利，於是物流公司配合網路商店將貨品配送到府的服務便漸漸崛起，此外，物流公司亦捉供貨物寄送的服務，將物品送到顧客指定的地點。可知，物流業者處理貨物配送的過程將會日漸複雜，因此發展一個捉供物流中心配送路線規劃的模組實有其必要。本硏究的冃的在於建立一個物流配送中心車輛路線規劃的模組，捉供物流配送中心一個成本最小的貨車行馭路線，進而取代傳統人工規劃路線的

2、方式，最後導入地理資訊系統，考慮真實路網的情形，進行途程規劃。1.2硏究假設與限制由於車輛路線問題爲一複雜難解之問題，爲了簡化問題的複雜度並兼顧物流配送中心的實際情形，本硏究做了以下之假設：(1)物流配送中心的位置爲已知且唯一。(2)需求點的位置及需求量爲已知。(3)需求點與需求點間的路線與距離爲已知且確定。(4)貨車經過需求點時只有卸貨而無裝貨，貨物配送完畢以空車返回配送中心。(5)物流中心只有一種貨車。本硏究所求之目標函數爲：使貨車配送路線之總成本最小。根據上述之假設，並達成所求的冃標，本硏究需滿足之限制如下：(1)每個需求點只能由一

3、部車服務一次。(2)每輛車皆須由配送中心出發，最後又回到配送中心。(3)每輛車服務之總載貨容量不能超過該車之容量。(4)必須滿足每個需求點的需求。2.1車輛路線問題車輛路線問題的定義就是用來決定車輛行'駛之路線，一物流配送中心之貨車車隊由物流配送中心出發，循特定之路線經過各配送點，最後回到配送中心，所有的配送點均必須被服務一次，而且此路線必須使物流業者所考量之目標函數(如距離、成本、時間等)最小。一般而言車輛路線問題大致可以分爲以下三種類型(Ballou，1992)：(1)相異的單一起點和單一終點(2)相同的單一起點和終點(3)多個起點和

4、終點本硏究探討的主題爲物流配送中心之貨車路線，所考量的情形爲單一貨物配送中心對其所負責之配送區域，作貨車行駛路線之規劃，屬於上述單一起點與終點之類型。關於車輛路線問題之學術硏究文獻眾多，亦提出了相當多的求解策略與方法，BodinandGolden(1981)將眾多之求解方法歸納成以下七種：(1)數學解析法(ExactProcedure)(2)人機互動法(Interactive)(3)先分群再排路線(ClusterFirst-RouteSecond)(4)先排路線冉分群(RouteFirst-ClusterSecond)(5)節省法或插入法

5、(SavingorInsertion)(6)改善或交換法(ImprovementorExchanges)(7)數學規劃近似法(Mdthemjticalprogramming)本硏究採舟「先分群再排路線」的二階段求解方法，進行配送路線的安排，也就是先將所有的配送點進行分群，然後再對每一群集中的配送點做最佳化路線的處理，換句話說，本硏究是將車輛路線問題(VRP)轉換成多個推銷員旅行問題(TSP)進行求解。2.2禁忌搜尋法禁忌搜尋法與其他萬用啓發式演算法一樣，目的在於求解人型組合的最佳化問題，禁忌搜尋法的槪念首先由Glover於1977年提出，

6、當時是將其應用於整數規劃的求解問題上(Glover，1977)，直到1989、1990年Glover在ORSAJournalonComputing上才將禁忌搜尋法的架構與方法完整提出(Glover，1989,1990)。其架構主要是使舟移步(Move)的方式，運用具有彈性的記憶架構，以疊代的方式對目前的解(CmrentSolution)展開鄰近解(NeighborhoodSolution)的搜尋°禁忌搜尋法之主要組成因素有以下五點：(1)起始解(InitialSolution)如無特殊限制條件，可以任選一可行解作爲該問題之起始解，以本硏究

7、之車輛路線問題，起始解的限制條件爲「車輛之載重」，因此必須考量滿足所有配送點及車輛載重之限制，並建立適當的起始解。⑵移步(Move)每次疊代的過程中，在所有合法的鄰近解裡，選擇其一進行變動的行爲，稱之爲移步。⑶禁忌名單(TabuList)爲了避免重複選取已選取過的解(即避免Cycle的情形)，禁忌搜尋法會將最近幾次移步的屬性記錄在禁忌名單中，作爲禁忌限制的參考指標，來防止重複搜尋的現象。禁忌名單長度會影響到求解尋優過程的結果，當禁忌名單長度太短時，搜尋的過程可能會冋到相同的區域中，造成落入區域解的囿限；若禁忌名單長度太長，除了要花費較多的

8、時間檢查移步是否被禁忌外，還可能導致搜尋過程遠離最佳解位置的可能性。因此本硏究將會對選取適當的禁忌名單長度進行探討。(1)免禁準則(AspirationCriterion)當一個移步爲禁忌'但