動態規劃法在服裝運輸車輛路徑優化中的應用研究

鄭飛

摘 要：連鎖服裝配送中路徑的優化對提高連鎖服裝企業的服務水平、降低成本、提高企業效益具有重要意義。根據動態規劃的基本思想，結合連鎖服裝物流配送過程中的路徑選擇問題以及時變因素，引入突發事件影響因子，提出了適合連鎖服裝物流配送過程中改進的路徑優化算法。通過具體實例，驗證了該方法在連鎖服裝物流配送的路徑隨機選擇中的實用性和可行性，并可將此算法推廣到其他物流配送的路徑選擇中。

關鍵詞：動態規劃法；服裝連鎖；配送；路徑優化

中圖分類號：U116.2 文獻標識碼：A

Abstract： It is very important for the routing optimization of the apparel chain distribution to raise the service level， reduce the product costs and improve the enterprise benefit of the apparel chain enterprise. According to the basic thought of the dynamic programming， and in combination with the problem of the routing selection and the time-varying factor in the apparel chain distribution logistics process， the impact factor of the unexpected events is introduced and the improved routing optimization algorithm suitable for the apparel chain logistics distribution process. In conjunction with the specific example， the effectiveness and the feasibility of the routing optimization algorithm is validated and the method is too extended to the touting selection of another logistics distribution.

Key words： dynamic programming； apparel chain； distribution； routing optimization

0 引 言

近年來，隨著市場經濟的不斷深入以及人們生活水平的不斷提高，服裝連鎖經營在我國有了很大的發展，品牌服裝的銷售量日益增加，連鎖門店市場的競爭越來越激烈[1]。在電子商務出現以后，由于電子商務突破了時空限制、新媒體對服裝全方位的展示、低的交易成本與低庫存、較少的中間環節所帶來的交易費用的優勢等，給連鎖服裝門店的經營帶來了新的挑戰[2-3]。在人們日益追求服裝個性化、高增值服務的時代，在原材料與人力資源成本挖掘的空間越來越小的情況下，服裝連鎖企業越來越關注作為企業第三利潤源泉的物流的作用[3]，通過降低物流成本、加快配送速度、優化配送路徑等措施來提高企業的競爭力。

在優化配送路徑方面，人們做了很多工作。20世紀50年代，美國數學家Bellman等人在研究多階段決策過程的優化問題時提出了動態規劃法。動態規劃法解決了線性規劃和非線性規劃無法處理的多階段決策問題[4]。后來，試圖將圖的廣度優先搜索算法、蟻群算法與動態規劃法結合求解關鍵路徑問題[5-9]，或者簡單使用動態規劃法研究物流配送的最短路徑[10-11]，但所有這些方法都無法對時變環境下的路徑進行隨機選擇。

本文根據動態規劃的基本思想，通過對傳統動態規劃模型的改進，將服裝物流配送過程中因道路、天氣、車輛狀況等引起的突發事件考慮到模型中，提出了一類高效實用的服裝物流配送路徑優化方法。通過該模型的應用，服裝連鎖企業可以得到盡量優化的配送路徑，對降低配送成本、提高服務質量、提高企業經濟效益具有重要的意義。

1 動態規劃法簡介

1.1 動態規劃法的基本思想[4]

美國數學家Bellman等人在研究多階段決策過程的優化問題時，通過將多階段過程轉化為一系列單階段問題，然后逐一求解，創立了解決多階段過程的動態規劃方法，即通常所說的Bellman最優性原理。動態規劃算法的基本思想是將待求解問題分解為若干子問題，先求解子問題，然后從這些子問題的解得到原問題的解。因此，為了運用動態規劃法，所考慮的問題：（1）必須能夠分解為相互重疊的子問題；（2）滿足最優子結構的特性——子問題的局部最優將導致整個問題的全局最優；（3）無后效性——當前狀態是此前歷史的總結，此前的歷史只能通過當前的狀態去影響未來的決策。

1.2 動態規劃法的求解過程

各個子問題之間的重疊關系通過狀態轉移方程（或動態規劃函數）來表現。為了避免重復計算，將子問題的解填入表中。

動態規劃法利用最優性原理，采用自底向上的方式，先求出子問題的最優解，然后逐步求得整個問題的最優解，其求解思路如圖2所示。

因此，使用動態規劃法進行決策，需要將原問題分解為若干個相互重疊的子問題，進行分段決策；然后根據最優性原理，分析問題，建立狀態轉移方程（或動態規劃函數）；最后采用自底向上的求解方法，求出問題的解，從而實現動態規劃過程。

為了構建簡單實用的服裝運輸車輛配送路徑選擇的數學模型，假設：

（1）配送車輛滿足一次配送要求；

（2）配送點是可達的；