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

1、 動(dòng)態(tài)規(guī)劃法在服裝運(yùn)輸車輛路徑優(yōu)化中的應(yīng)用研究 鄭飛摘 要：連鎖服裝配送中路徑的優(yōu)化對(duì)提高連鎖服裝企業(yè)的服務(wù)水平、降低成本、提高企業(yè)效益具有重要意義。根據(jù)動(dòng)態(tài)規(guī)劃的基本思想，結(jié)合連鎖服裝物流配送過(guò)程中的路徑選擇問(wèn)題以及時(shí)變因素，引入突發(fā)事件影響因子，提出了適合連鎖服裝物流配送過(guò)程中改進(jìn)的路徑優(yōu)化算法。通過(guò)具體實(shí)例，驗(yàn)證了該方法在連鎖服裝物流配送的路徑隨機(jī)選擇中的實(shí)用性和可行性，并可將此算法推廣到其他物流配送的路徑選擇中。Key：動(dòng)態(tài)規(guī)劃法；服裝連鎖；配送；路徑優(yōu)化：U116.2 ：AAbstract： It is very important for the routing optimizat

2、ion 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

3、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 feas

4、ibility 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 optimization0 引 言近年來(lái)，隨著市場(chǎng)經(jīng)濟(jì)的不斷深入以及人們生活水平的不斷提高，服裝連鎖經(jīng)營(yíng)在我國(guó)有了很大的發(fā)展，品牌服裝的銷售量日益增加，連鎖門店市場(chǎng)

5、的競(jìng)爭(zhēng)越來(lái)越激烈1。在電子商務(wù)出現(xiàn)以后，由于電子商務(wù)突破了時(shí)空限制、新媒體對(duì)服裝全方位的展示、低的交易成本與低庫(kù)存、較少的中間環(huán)節(jié)所帶來(lái)的交易費(fèi)用的優(yōu)勢(shì)等，給連鎖服裝門店的經(jīng)營(yíng)帶來(lái)了新的挑戰(zhàn)2-3。在人們?nèi)找孀非蠓b個(gè)性化、高增值服務(wù)的時(shí)代，在原材料與人力資源成本挖掘的空間越來(lái)越小的情況下，服裝連鎖企業(yè)越來(lái)越關(guān)注作為企業(yè)第三利潤(rùn)源泉的物流的作用3，通過(guò)降低物流成本、加快配送速度、優(yōu)化配送路徑等措施來(lái)提高企業(yè)的競(jìng)爭(zhēng)力。在優(yōu)化配送路徑方面，人們做了很多工作。20世紀(jì)50年代，美國(guó)數(shù)學(xué)家Bellman等人在研究多階段決策過(guò)程的優(yōu)化問(wèn)題時(shí)提出了動(dòng)態(tài)規(guī)劃法。動(dòng)態(tài)規(guī)劃法解決了線性規(guī)劃和非線性規(guī)劃無(wú)法處理的

6、多階段決策問(wèn)題4。后來(lái)，試圖將圖的廣度優(yōu)先搜索算法、蟻群算法與動(dòng)態(tài)規(guī)劃法結(jié)合求解關(guān)鍵路徑問(wèn)題5-9，或者簡(jiǎn)單使用動(dòng)態(tài)規(guī)劃法研究物流配送的最短路徑10-11，但所有這些方法都無(wú)法對(duì)時(shí)變環(huán)境下的路徑進(jìn)行隨機(jī)選擇。本文根據(jù)動(dòng)態(tài)規(guī)劃的基本思想，通過(guò)對(duì)傳統(tǒng)動(dòng)態(tài)規(guī)劃模型的改進(jìn)，將服裝物流配送過(guò)程中因道路、天氣、車輛狀況等引起的突發(fā)事件考慮到模型中，提出了一類高效實(shí)用的服裝物流配送路徑優(yōu)化方法。通過(guò)該模型的應(yīng)用，服裝連鎖企業(yè)可以得到盡量?jī)?yōu)化的配送路徑，對(duì)降低配送成本、提高服務(wù)質(zhì)量、提高企業(yè)經(jīng)濟(jì)效益具有重要的意義。1 動(dòng)態(tài)規(guī)劃法簡(jiǎn)介1.1 動(dòng)態(tài)規(guī)劃法的基本思想4美國(guó)數(shù)學(xué)家Bellman等人在研究多階段決策過(guò)程

7、的優(yōu)化問(wèn)題時(shí)，通過(guò)將多階段過(guò)程轉(zhuǎn)化為一系列單階段問(wèn)題，然后逐一求解，創(chuàng)立了解決多階段過(guò)程的動(dòng)態(tài)規(guī)劃方法，即通常所說(shuō)的Bellman最優(yōu)性原理。動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解為若干子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。因此，為了運(yùn)用動(dòng)態(tài)規(guī)劃法，所考慮的問(wèn)題：（1）必須能夠分解為相互重疊的子問(wèn)題；（2）滿足最優(yōu)子結(jié)構(gòu)的特性子問(wèn)題的局部最優(yōu)將導(dǎo)致整個(gè)問(wèn)題的全局最優(yōu)；（3）無(wú)后效性當(dāng)前狀態(tài)是此前歷史的總結(jié)，此前的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響未來(lái)的決策。1.2 動(dòng)態(tài)規(guī)劃法的求解過(guò)程各個(gè)子問(wèn)題之間的重疊關(guān)系通過(guò)狀態(tài)轉(zhuǎn)移方程（或動(dòng)態(tài)規(guī)劃函數(shù)）來(lái)表現(xiàn)。為了避免重復(fù)計(jì)算，將子問(wèn)題的解填入表中。動(dòng)態(tài)規(guī)劃法利用最優(yōu)性原理，采用自底向上的方式，先求出子問(wèn)題的最優(yōu)解，然后逐步求得整個(gè)問(wèn)題的最優(yōu)解，其求解思路如圖2所示。因此，使用動(dòng)態(tài)規(guī)劃法進(jìn)行決策，需要將原問(wèn)題分解為若干個(gè)相互重疊的子問(wèn)題，進(jìn)行分段決策；然后根據(jù)最優(yōu)性原理，分析