動態規劃在物流企業中的配送與運輸問題分析

李靜強

摘要：動態規劃作為運籌學的一個分支，是求解決策過程最優化的數學方法。隨著現在電子商務的迅猛發展，全國物流企業的業務也保持著較快速度的增加，因此這對物流企業也產生了新的問題——即最優化問題，這種要求已經成為物流企業發展的重要組成部分和推動國民經濟發展的新動力。所以動態規劃在物流企業的應用具有重大的意義。

關鍵詞：動態規劃;多階段決策;最短路徑;配送裝箱

如何做到對物流企業中的配送與運輸問題的最優化，針對這類問題，可以應用動態規劃的基本思想，將需要求解的問題分解成若干個子問題，通過先求解子問題，以達到幫助物流企業在生產和經菅管理中，合理安排生產與庫存的問題， 有效的降低成本費用，提高生產和經營管理的整體效率的目的。

1 動態規劃方法的簡介

動態規劃方法是用來求解最優化一類問題的一種數學方法，對解決最優化問題非常有效。“分而治之”是該方法的主要思想，即把一個較為復雜的問題進行分割，將其分割成為一個一個的子問題，并且這些子問題必須與母問題有關，如果這個問題還不能得到解決，那么可再對各子問題進行進一步的分割，直到可以求解出相關的每個子問題為止，達到解決母問題的目的。

動態規劃方法的特點是可以大幅度節約計算時間，減少求解問題的時間，即在對問題不斷分割的過程中遇到重復出現或及其相似的子問題時，只在第一次時便加以求解，得到相應的解決方法，同時將該解決方法進行保存，這種方法可以用于整個過程中該類子問題，如果再次遇到則可以直接引用或者簡單修改，不必重新求解，大大縮減了時間。

采用動態現劃方法進行求解，需要同時滿足以幾個下條件：

（1）最優子結構：在求出的問題的最優解中，那么如果由這個問題分割出來的子問題有最優解，將其稱為最優子結構。

（2）存在重疊子問題：根據前面提出的動態規劃方法的特點可以看出，在動態規劃過程中會重復遇到相同的問題，這時，保存下來的解決方法就可以被再次使用。雖然動態規劃對此沒有強制要求，但是如果可以滿足這個條件，那么就有很大的優勢。

（3）無后效性：無后效性是指如果在某個階段上過程的狀態已知，則從此階段以后過程的發展變化僅與此階段的狀態有關，而與過程在此階段以前的階段所經歷過的狀態無關。

建立動態規劃數學模型的一般步驟：①劃分階段;②選擇變量;③確定允許決策集合;④確定決策變量;⑤確定狀態轉移方程;⑥確定指標函數;⑦選出最優指標函數;⑧列出基本方程。

動態規劃模型可被應用在多個方面，沒有統一的形式，所以在建模時只能根據具體問題具體分析，在不斷實踐中進行總結，才能準確掌握建模的方法與技巧。

2 動態規劃對物流企業中的配送與運輸問題分析

2.1 在物流配送中最短路徑問題的應用

給定一個線路網絡，兩點之間連線上的數字表示兩點間的費用（或距離），A、B、C、D、E代表企業的配送中心。在此基礎上提出如何找出從A經B、C、D到達E的線路使費用最少（或長度最短）。從A到E的整個過程可以分為四個階段，每一個階段都有一個起始點——我們稱之為初始狀態，同時也有一個終點狀態，每一階段都需做一個選擇——稱之為決策，決策本階段由初始狀態應演變到終點狀態（也是下一階段的那一個起始點）。過程中每一個階段的決策不僅會影響到本階段，還關系到下一階段的具體情況，對此后所有階段的決策都會產生一定的影響。因此，在對某一階段進行決策時，需要將它看成整體中的一部分，不能僅僅從該階段本身去考慮，這樣才能讓整個過程達到最優效果，保證問題的最優解。

常見的兩種求解最短路徑問題的方法：順序遞推法、逆序遞推法。從字面上就可以看出兩種方法異同，結果相同，只是解決問題的順序恰好相反。例如從A到E的最短路徑與從E到A的最短路徑是相同的，所以采用順序遞推法與逆序遞推法這兩種解法得出的結果是也是相同的，并且是唯一確定的，不僅如此，如果其中某一路徑為最短路徑，則它的任一子路徑也一定是最短路徑。

2.2 對物流配送中裝箱問題的應用

對于配送裝箱問題的子問題如下：求解一種方案，對于一個固定容量的箱子，在保證貨物完好無損即該箱子裝或不裝貨物的前提下如何分配貨物使得到的總價值最大。對于此類問題可以將其簡單理解為動態規劃中0-1背包問題，即向背包中裝入物品，求解能裝入最大價值物品的最優解決方案，這樣就能很好地解決此類問題。對于此類問題的求解過程相當于在不斷地做決策，對問題中的每一個過程都需要做類似決策，即決策所給定的物品是否能完整放入背包。

在物流企業運輸成本不斷增加的今天，對于各大物流企業來說解決裝箱問題可以大大增加經濟效益，所以需要合理的完成物流貨物的裝箱配送。通過采用動態規劃方法進行相關求解，得出相應的最優裝箱算法，可以有效解決類似的物流配送裝箱問題中的子問題，以達到解決物流企業配送運輸的目的。

使用動態規劃解決多階段決策和物流裝配與運輸等方面的問題對于在提高效率方面有很大的幫助，不僅有簡便、清晰的思路，而且很容易達到想要的目的。從我們對實際應用做的各方面實踐反映，動態規劃在實用性方面的優勢是毋庸置疑的，雖然在某些方面也可能存在一定的不足，但是也可以看出其作用范圍還是挺廣的，可以解決實踐應用中大部分較困難的問題，為物流企業的配送與應用問題的解決提供極大的便利。

參考文獻：

[1] 錢頌迪.運籌學[M].北京：清華大學出版社，2002.

[2] 孫曉燕，李自良，彭雄風等.利用動態規劃法求解運輸間題的最短路徑[J].機械設計與制造，2010（02）.

[3] 施成湘.動態規劃算法在物流配送裝箱問題中的應用[J].物流技術m2013（07）.

[4] 劉彥平.倉儲與配送管理[M].二版.北京：電子工業出版社，2011.

基金項目：重慶工程職業技術學院科研項目"動態規劃在物流企業中的應用研究"（編號：RWB201703）。

（作者單位：重慶工程職業技術學院）