動態(tài)規(guī)劃法在服裝運輸車輛路徑優(yōu)化中的應(yīng)用研究

鄭飛

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

關(guān)鍵詞：動態(tài)規(guī)劃法；服裝連鎖；配送；路徑優(yōu)化

中圖分類號：U116.2 文獻標(biāo)識碼：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 引 言

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

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

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

1 動態(tài)規(guī)劃法簡介

1.1 動態(tài)規(guī)劃法的基本思想[4]

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

1.2 動態(tài)規(guī)劃法的求解過程

各個子問題之間的重疊關(guān)系通過狀態(tài)轉(zhuǎn)移方程（或動態(tài)規(guī)劃函數(shù)）來表現(xiàn)。為了避免重復(fù)計算，將子問題的解填入表中。

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

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

為了構(gòu)建簡單實用的服裝運輸車輛配送路徑選擇的數(shù)學(xué)模型，假設(shè)：

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

（2）配送點是可達的；