動態規劃方法在配送線路優化中的應用研究

[摘要] 應用圖論的方法對配送線路進行優化的缺點是，當線路復雜時計算較為煩瑣，而應用動態規劃的方法能有效解決這個問題。本文從理論上應用動態規劃的方法對共同配送線路進行優化，并應用此方法對實際問題進行計算。

[關鍵詞] 動態規則 方法 配送線路

配送中心貨物配送的線路直接影響到配送的效率、成本，進而影響到顧客的滿意度，因此，如何使配送線路最優即路程最短，一直是理論及企業關心的問題。以前解決此問題的方法主要是應用圖論的方法，但該方法的缺點是，當線路復雜時計算較為煩瑣，而應用動態規劃的方法能有效解決這個問題。

一、模型建立

設n個頂點，每兩個項點之間有邊連接，現要求從某一個結點出發，經過每一個結點一次且僅一次，最后回到出發時結點，要求路徑最短，這就是最優哈密頓回路問題。這個問題用圖論語言敘述為：考慮n個頂點無向完全圖，為頂點集合，E為邊集合，為兩結點之間距離。

采用動態規劃法計算。考慮頂點1為始點（為了書寫方便，把頂點等簡化為123）和終點的一條周游路線。每條這樣的路線均可表示為形式:對于某個路線包含了一條邊<1，k>和頂點k到1的一條通路，這條通路必須經過V－{1，k}的每個頂點各一次。不難看出，如果以頂點1為始點和終點的某條周游路線是最佳的，那么，這條路徑上從頂點k到頂點1的部分路徑（經過V－{1－k}的每個頂點各一次），必須是從k到1的一條最短路徑。因此，最佳原理是適用的。設(i，S)是從頂點i出發，經過S中除去頂點1之外的其它頂點各一次并回到頂點1的一條最短路徑的長。于是g(1，V－{1})就是一條最佳旅游路線的長。根據最佳原理，我們有

一般地，當時，有

.

如果對所有選定的k，已知，則可以求得。各的值可逐步求得。令，這是初始狀態。往后，依次對元素個數為1的集合S，求得所有的。然后求和絕對值S=2的所有的等等。當時，對任何必須滿足。最后可求得問題的最佳解，我們稱這種方法為圖論中的動態規劃方法。

二、算法實例

集中存儲統一配送是現代化連鎖經營的典型物流模式。以一個配送中心為10家門店進行配送服務的業務流程為例進行線路優化設計，連鎖經營集團在門店不設有倉儲設施，由各供應商集貨到配送中心，由配送中心統一配貨和保管。配送中心以技術為支撐，它是各門店供貨樞紐，配送中心建立了有效的信息處理系統如 POS 系統通過運輸車隊按照各門店的需求進行配送，門店由于沒有設置倉儲設施增加了營業面積，降低了各門店倉儲人力資源成本。對各門店配送路線的優化選擇是典型的最短路徑求解方法。由 POS 系統把各門店的全部需求信息后反饋給配送中心， 由配送中心根據商品需求信息制定配送計劃并對配送路線做出最佳選擇，對各門店進行多品種、小批次、多頻率的配送，路線優化設計從配送中心開始，車輛經過 10 家門店且只經過一次，最終完成配送任務返回配送中心使總路程最短。

配送中心采取共同配送方式為各門店配貨，共同配送是為了提高物流效率，通過配送中心集中運輸貨物的一種方式。可以把多種貨類集貨于一輛車，既提高了車輛的滿載率又提高了配送效率。減少了運輸自身行為帶來的外部不經濟如破環生態環境、噪聲污染、交通擁擠，即有利于企業經濟利潤最大化又使整個社會經濟的可持續發展。

某配送中心與各連鎖店之間的距離用矩陣表示，矩陣中的元素aij表示第i個超市與第 j 個超市之間的距離：

約束條件：為各門店實行配送服務的車輛從配送中心出發最終回到配送中心，各門店的配送業務由一輛貨車完成；每個門店都必須有貨物需求量，所有門店的貨物需求量總和不超過配送車輛的載重量。

要研究的問題是一輛非滿載車輛從配送中心出發經過各個門店配貨僅一次并且返回配送中心，約束條件是每個配送任務都需要完成而且貨物不能超載，要求配送運輸路徑最短，這是一個最短的哈密頓回路問題。為了找到由0至10的最短線路，可以將該問題成為0—1—2…10 11 個階段，在每個階段都需要作出決策，即在0點需決策下一步到哪個門店;同樣，若到達第二階段某個狀態，比如1，需決定走向1還是2;依次類推，可以看到：各個階段的決策不同，由0至10的線路就不同，當從某個階段的某個狀態出發作出一個決策，則這個決策不僅影響到下一個階段的距離而且直接影響后面階段的配送線路。所以這類問題要求在各個階段選擇一個恰當的決策，使由這些決策序列所決定的一條路線對應的配送線路最短。

下面用無向圖來表示各門店之間的連通情況。說明如下：節點j表示第j個門店，連接兩個門店的邊上注明的數字表示兩個門店之間的距離。顯然這個圖是有11個節點的完全加權圖，此圖共有邊條邊，為了清楚起見我們不畫出所有的邊。

按照前面圖論動態規劃方法，找出最短路徑的配送方案為：0→1→3→2→5→4→6→7→8→9→10→0

采用動態規劃方法計算量比較小，因而節省時間。例如結點系數為n時，一般情況下找出最短哈密頓回路第一個結點到第二個結點n-1種走法，第二個結點到第三個結點有n-2種走法……，共有1/2（n-1）!，不同哈密頓回路為了比較權大小，對每條回路要做n-1次加法，當n較大時，浪費時間是很多的，如果按動態規劃算法，設N是未計算g(1，-{1})前需要計算g(i，s)的個數，對于每一個{S}，i有n-1種取法，又包括1和i取大小為k的不同集合個數是，因此，顯然計算量要比較其他算法要小的多。

參考文獻:

[1]胡運權:運籌學基礎及應用[M].哈爾濱工業大學出版社，1998年2月版

[2]李軍郭耀煌:物流配送車輛優化調度理論與方法[M]. 中國物資出版社，2001年3月版

[3]毛薇:物流園區規劃及運營關鍵技術研究[D].天津大學.2005年

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。