動(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é)合連鎖服裝物流配送過程中的路徑選擇問題以及時(shí)變因素，引入突發(fā)事件影響因子，提出了適合連鎖服裝物流配送過程中改進(jìn)的路徑優(yōu)化算法。通過具體實(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 引 言近年來，隨著市場(chǎng)經(jīng)濟(jì)的不斷深入以及人們生活水平的不斷提高，服裝連鎖經(jīng)營在我國有了很大的發(fā)展，品牌服裝的銷售量日益增加，連鎖門店市場(chǎng)

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

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

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