帶外包的服飾運(yùn)輸調(diào)度問(wèn)題的優(yōu)化

楊 軍 蔡延光 湯雅連 江澤東

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006）

帶外包的服飾運(yùn)輸調(diào)度問(wèn)題的優(yōu)化

楊 軍 蔡延光 湯雅連 江澤東

（廣東工業(yè)大學(xué) 自動(dòng)化學(xué)院，廣州 510006）

由于服飾產(chǎn)品是一種時(shí)效性很強(qiáng)的商品，而且服飾產(chǎn)品在配送過(guò)程中可以外包給快遞公司進(jìn)行配送，對(duì)帶外包和硬時(shí)間窗的服飾運(yùn)輸調(diào)度問(wèn)題（Apparel products Vehicle Routing Rroblem with Hard Time Windows and Outsourcing，AVRRHTWO）進(jìn)行分析，并構(gòu)建了AVRRHTWO、一般性VRR（Vehicle Routing Rroblem）和VRRSTW（Vehicle Routing Rroblem with Soft Time Windows）的數(shù)學(xué)模型，通過(guò)對(duì)基本的人工魚群算法（artificial fish swarm algorithm，AFSA）進(jìn)行改進(jìn)，混沌搜索被引入人工魚群算法來(lái)提高算法的全局收斂性，反饋策略用來(lái)指導(dǎo)人工魚的移動(dòng)，以此來(lái)提高收斂精度。應(yīng)用混沌人工魚群算法（chaotic artificial fish swarm algorithm，CAFSA）及遺傳算法（genetic algorithm，GA）對(duì)所建立的三種模型求解，通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行處理，證明了AVRRHTWO模型和混沌人工魚群算法求解此類模型的有效性，進(jìn)一步證明了問(wèn)題模型的復(fù)雜程度影響算法尋優(yōu)能力，問(wèn)題模型簡(jiǎn)單時(shí)，遺傳算法更優(yōu)；問(wèn)題模型復(fù)雜時(shí)，混沌人工魚群算法更優(yōu)。

硬時(shí)間窗；軟時(shí)間窗；外包；服飾運(yùn)輸調(diào)度問(wèn)題；混沌人工魚群算法；遺傳算法

服飾產(chǎn)品是一種時(shí)效性很強(qiáng)的商品，流行周期短，季節(jié)性強(qiáng)，一旦過(guò)了季節(jié)或者流行期，銷售轉(zhuǎn)弱，價(jià)格會(huì)大幅下降，且具有變化快、多品種，以及強(qiáng)烈的地域性消費(fèi)差異等特點(diǎn)，這就要求服飾企業(yè)的物流配送必須做到及時(shí)、準(zhǔn)確，能夠盡快縮短交貨周期，也就是要求企業(yè)擁有較強(qiáng)的過(guò)程控制能力和供貨時(shí)效性，能夠準(zhǔn)確按照客戶需求準(zhǔn)時(shí)準(zhǔn)確地做到物流服務(wù)。由于地域性消費(fèi)差異，不同門店的需求也不一樣，所以企業(yè)在配送過(guò)程中，對(duì)大批量的服飾可以采用廠家直銷直接配送的方式，對(duì)小批量的服飾可以外包給快遞公司配送的方式，最終目的就是最小化成本。

華銓平等人［1］分析服裝具有時(shí)效性強(qiáng)等特點(diǎn)，建立了服裝時(shí)效性的模糊數(shù)學(xué)模型，提出的改進(jìn)的蟻群算法，證明了改進(jìn)算法對(duì)具有時(shí)效性服裝VRR模型求解的合理性與有效性；王赟等人［2］研究了服裝配送網(wǎng)絡(luò)中的車輛路徑優(yōu)化問(wèn)題，驗(yàn)證了遺傳算法求解該問(wèn)題模型的可行性和優(yōu)越性；賈祥素等人［3］提出了改進(jìn)的蟻群算法求解服裝運(yùn)輸車輛路徑規(guī)劃問(wèn)題，取得了良好成果；王昕等人［4］研究了一種適合服裝供應(yīng)鏈VRR成本模型的獎(jiǎng)懲蟻群算法，證明了該模型與求解算法的有效性；王培崇等人［5］對(duì)一般的VRR進(jìn)行分析，在初期階段應(yīng)用人工魚群算法迅速獲得階段最優(yōu)解，后期應(yīng)用遺傳算法尋優(yōu)，證明了算法具有求解速度快、性能穩(wěn)定等優(yōu)點(diǎn)；朱命昊等人［6］采用隨機(jī)鍵表達(dá)編碼的改進(jìn)人工魚群算法對(duì)旅行商問(wèn)題求解，算法測(cè)試表明改進(jìn)的算法提高了收斂速度，增強(qiáng)了全局搜索能力。通過(guò)混沌人工魚群算法求解AVRRHTWO的文獻(xiàn)不多，所以本文重點(diǎn)是通過(guò)混沌人工魚群算法求解AVRRHTWO模型，并比較該算法和遺傳算法求解該模型和其他兩種模型的效果。

1 問(wèn)題描述及數(shù)學(xué)模型的建立

1.1 問(wèn)題描述及假設(shè)

帶外包的硬時(shí)間窗服飾運(yùn)輸調(diào)度問(wèn)題是指對(duì)于一系列需求點(diǎn)，給定車場(chǎng)位置以及客戶的數(shù)量、位置和需求量，組織適當(dāng)?shù)倪\(yùn)輸路線，使服飾配送在滿足一定的約束條件（運(yùn)輸容量、硬時(shí)間窗、里程約束及載重約束等）下，達(dá)到運(yùn)輸成本最少的目的。本節(jié)研究的問(wèn)題基于以下假設(shè)：1）1個(gè)工廠，1個(gè)快遞公司，l個(gè)門店（i，j=1，2，…，l），門店需求確定；2）車輛有最大里程約束、載重約束，同種車型；3）硬時(shí)間窗約束；4）車輛的配送任務(wù)完成后必須回到車場(chǎng)。

1.2 建立AVRPHTWO的數(shù)學(xué)模型

有l(wèi)個(gè)門店，第i個(gè)門店的需求量為gi，從工廠將服飾配送給各門店，門店要求送貨時(shí)間窗為［Ai，Bi］，門店i與j之間的距離為dij。Ti表示車輛到達(dá)i的時(shí)間。可以按照式（1）估算車輛數(shù)。式中，［］表示不大于括號(hào)內(nèi)數(shù)字的最大整數(shù)；0＜α＜1，是對(duì)裝車（或卸車）的復(fù)雜程度及約束多少的估計(jì)。tij表示從i到j(luò)的行駛時(shí)間，T總表示行駛總時(shí)間。

配送方式有以下兩種。

1）工廠配送。假設(shè)工廠由貨車配送，貨車載重為qc，速度為vc，有m輛貨車，已知gi＜qc，cijk表示為車輛k將服飾從點(diǎn)i送到點(diǎn)j的單位運(yùn)價(jià)，nk表示第k輛車服務(wù)的門店個(gè)數(shù)，ck為啟用車輛的固定成本，Dmax為貨車的里程約束。

2）快遞配送。假設(shè)快遞公司由摩托車配送，摩托車載重為qd，有s輛貨車，c1為起價(jià)，c2為續(xù)價(jià)，ph表示第h輛車服務(wù)的門店個(gè)數(shù)，Dh為摩托車的里程約束。

定義變量如下

建立數(shù)學(xué)模型：

目標(biāo)函數(shù)

約束條件

目標(biāo)函數(shù)式（6）表示總運(yùn)輸成本最低，由兩部分構(gòu)成，工廠自銷配送費(fèi)用與外包給快遞公司的配送費(fèi)用之和；（7）為車輛行駛距離約束，其中dijk表示車輛k行駛了門店i到j(luò)的路程，dijh表示車輛h行駛了門店i到j(luò)的路程；（8）表示車輛完成任務(wù)后，回到原車場(chǎng)；（9）表示當(dāng)某輛車配送到門店的個(gè)數(shù)大于等于1時(shí)，則參與了配送服務(wù)，否則，沒(méi)有參與配送；（10）表示所有門店都被服務(wù)到；（11）表示不能超過(guò)車輛的載重；（12）表示保證每輛車服務(wù)的門店總數(shù)小于等于總門店數(shù)目；（13）表示到達(dá)門店i的時(shí)間必須在時(shí)間窗內(nèi)；（14）表示到達(dá)j的時(shí)間Tj為車場(chǎng)到i的時(shí)間T0i與門店i到門店j的時(shí)間tij之和。

1.3 建立VRP的數(shù)學(xué)模型

按照1.2節(jié)方法估算車輛數(shù)。本節(jié)考慮簡(jiǎn)單的VRR模型，只研究廠家直銷的配送模式。對(duì)1.2節(jié)進(jìn)行簡(jiǎn)化：不考慮外包配送模式和時(shí)間窗約束。目標(biāo)函數(shù)及約束的表述見(jiàn)1.2節(jié)。

定義變量如下：

建立數(shù)學(xué)模型：

目標(biāo)函數(shù)

約束條件

1.4 建立VRPSTW的數(shù)學(xué)模型

在1.3節(jié)的基礎(chǔ)上加上軟時(shí)間窗約束，即考慮VRRSTW模型，β為車輛早到和晚到的懲罰系數(shù)，目標(biāo)函數(shù)包含了運(yùn)輸成本和時(shí)間窗懲罰費(fèi)用。時(shí)間窗約束見(jiàn)1.2節(jié)，約束條件極其表述見(jiàn)1.2節(jié)和1.3節(jié)。

建立數(shù)學(xué)模型。

目標(biāo)函數(shù)：

2 混沌人工魚群算法

2.1 求解思路

人工魚群算法［7］是模擬魚群的行為進(jìn)行隨機(jī)的搜索，主要利用人工魚的覓食、聚群、追尾等行為，利用局部最優(yōu)信息逐步達(dá)到全局尋優(yōu)的目的。為了提高人工魚群算法的全局搜索能力，克服基本人工魚群算法精度低、后期收斂慢、復(fù)雜度較高等特點(diǎn)，本文主要是采用基于混沌搜索和反饋策略的混沌人工魚群算法解決服飾物流運(yùn)輸調(diào)度問(wèn)題。

2.2 混沌人工魚群算法求解步驟

魚群中，每個(gè)個(gè)體的位置向量X=（x1，x2，…，xn），X為尋優(yōu)決策變量；人工魚個(gè)體i與個(gè)體j間的距離表示為di，j=Xj-Xi；人工魚當(dāng)前所在位置的食物濃度為Y=f（X），即為目標(biāo)函數(shù)值；Visual表示人工魚的感知距離；step表示人工魚的感知距離；δ為擁擠度因子；α為衰減因子，Pf為反饋概率；Try-num表示人工魚每次移動(dòng)的最大試探次數(shù)。在尋優(yōu)過(guò)程中，X中元素的順序表示配送的訪問(wèn)順序，也就是一個(gè)潛在的解，其適應(yīng)值可以衡量解X的優(yōu)劣程度。由于混沌搜索具有隨機(jī)性、遍歷性和確定性，所以混沌搜索要比隨機(jī)搜索好。

1）混沌搜索。文中選用Logistic映射［8-10］，如式（28）所示。式中，i表示混沌變量的序號(hào)，i=1，2，…，r；u表示種群序號(hào)，u=0，1，…，n=0；βi表示混沌變量，0≤βi≤1；μi表示吸引子。當(dāng)μi=4時(shí)，Logistic映射完全處于混沌的狀態(tài)，此時(shí)產(chǎn)生的混沌變量βi具有很好的遍歷性。假設(shè)迭代次數(shù)為300，初值為0.6，得到Logistic映射的概率分布圖，如圖1所示。

2）反饋策略。每條人工魚執(zhí)行完移動(dòng)操作后會(huì)檢驗(yàn)自身狀態(tài)與公告牌的狀態(tài)，若自身狀態(tài)優(yōu)于公告牌狀態(tài)，則用自身狀態(tài)代替原公告牌狀態(tài)，這樣公告牌就可以記錄下歷史最優(yōu)狀態(tài)?；谶@一思路，為人工魚定義一個(gè)新行為——反饋行為，即人工魚向公告牌記錄的最優(yōu)狀態(tài)移動(dòng)，人工魚以一定的概率執(zhí)行該行為。

對(duì)人工魚群算法進(jìn)行改進(jìn)，設(shè)置反饋概率Pf，人工魚以概率Pf執(zhí)行隨機(jī)行為，以概率1-Pf執(zhí)行反饋行為。優(yōu)化過(guò)程開始時(shí)賦予Pf一個(gè)較大的數(shù)，隨著優(yōu)化過(guò)程的進(jìn)行Pf按式（29）逐漸減小，α為反饋概率的衰減因子。

3）覓食行為。設(shè)人工魚i當(dāng)前狀態(tài)為Xi，在其感知范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，如式（30）。

其中，rand（）是一個(gè)介于0和1之間的隨機(jī)數(shù)，若Yi＞Yj，則向該位置和全局最優(yōu)位置Xbest-af的向量和方向前進(jìn)一步；反之，再重新隨機(jī)選擇狀態(tài)Xj，判斷是否滿足前進(jìn)條件，若滿足，則按式

（31）前進(jìn)一步；若不滿足則繼續(xù)試探，反復(fù)嘗試Try-num次后，如果仍不滿足前進(jìn)條件，則按式

（32）隨機(jī)移動(dòng)一步。

4）聚群行為。人工魚探索當(dāng)前鄰域內(nèi)（即dij＜Visual）伙伴數(shù)目nf及中心位置Xc。如果Yc·nf＜δ·Yi，表明伙伴中心有較多食物且不太擁擠，那么按式（33）朝伙伴的中心位置和全局最優(yōu)位置Xbest-af的向量和方向前進(jìn)一步，否則執(zhí)行覓食行為。

5）追尾行為。人工魚探索當(dāng)前鄰域內(nèi)（即dij＜Visual）的伙伴中Yj為最小的伙伴Xj。如果Yj·nf＜δ·Yi，表明伙伴Xj具有較高的食物濃度并且其周圍不太擁擠，那么式（34）朝Xj的方向和全局最優(yōu)位置Xbest-af的向量和方向前進(jìn)一步，否則執(zhí)行覓食行為。

6）隨機(jī)行為。隨機(jī)行為是為了在更大范圍內(nèi)尋覓食物或同伴，隨機(jī)選擇一個(gè)狀態(tài)，然后向該方向移動(dòng)。

混沌人工魚群算法的步驟如下：

Step1：進(jìn)行初始化設(shè)置：人工魚的感知距離Visual、人工魚的感知距離Step、擁擠度因子δ、衰減因子α、反饋概率Pf、人工魚每次移動(dòng)的最大試探次數(shù)Try-num和最大迭代次數(shù)MAXGEN。

Step2：計(jì)算每條人工魚的適應(yīng)度值，將最優(yōu)的人工魚狀態(tài)記入公告牌。

Step3：對(duì)每條人工魚進(jìn)行評(píng)價(jià)，對(duì)其要執(zhí)行的行為進(jìn)行選擇，包括覓食行為、群聚行為、追尾行為。若執(zhí)行后的狀態(tài)優(yōu)于當(dāng)前狀態(tài)，則向更優(yōu)狀態(tài)的方向前移一步，然后轉(zhuǎn)至Step5。

Step4：隨機(jī)產(chǎn)生一個(gè)數(shù)，若rand（）＜Pf，則執(zhí)行隨機(jī)行為，否則執(zhí)行反饋行為。

Step5：最優(yōu)人工魚執(zhí)行混沌搜索。

Step6：更新公告牌和反饋概率。

Step7：若滿足循環(huán)結(jié)束的條件則輸出結(jié)果，否則轉(zhuǎn)至步驟（3）。

3 仿真分析

某市的服飾廠家向市內(nèi)各區(qū)門店供應(yīng)服飾。所有門店的信息如表1所示。

工廠配有車場(chǎng)，工廠位置為（50，50），貨車的最大配送里程為300 km，貨車速度為50 km/h，載重為15 t，工廠送貨最早出發(fā)時(shí)間為5:00，貨車運(yùn)費(fèi)為1元/km，起步價(jià)為40元/輛，不考慮卸貨時(shí)間，有同類型的貨車若干。軟時(shí)間窗VRR中，早到和晚到的懲罰β為10元/h。

快遞公司位置為（50，80），摩托車的最大配送里程為250 km，摩托車車速60 km/h，載重為300 kg，快遞公司起價(jià)為0.01元/t，續(xù)價(jià)為0.001元/t，不考慮卸貨時(shí)間，快遞公司最早出發(fā)時(shí)間為6:00，有同類型的摩托車若干。

算例分析

AVRRHTWO模型的求解結(jié)果見(jiàn)表2。廠家派出4輛車配送，外包給快遞公司的配送任務(wù)由2輛車配送，總配送距離為758.29 km，總配送費(fèi)用為823元，最優(yōu)配送網(wǎng)絡(luò)如圖2，應(yīng)用兩種算法的收斂情況如圖3，可見(jiàn)CAFSA在第10代就收斂到最優(yōu)解，而GA在40代才收斂到最優(yōu)解，CAFSA優(yōu)于GA。

VRR模型的求解結(jié)果見(jiàn)表3，由4輛車配送，最優(yōu)配送距離為650.71 km，總配送費(fèi)用為810.71元，最優(yōu)配送網(wǎng)絡(luò)如圖4，應(yīng)用兩種算法求解VRR問(wèn)題模型的收斂情況如圖5所示，GA在第8代收斂，CAFSA在第30代收斂，GA優(yōu)于CAFSA。VRRSTW模型的總配送費(fèi)用為903.71元，最優(yōu)配送方案如表4，最優(yōu)配送網(wǎng)絡(luò)與VRR的一致，應(yīng)用兩種算法求解VRRSTW的收斂情況如圖6所示，GA在第20代收斂，CAFSA在第15代收斂，CAFSA略優(yōu)于GA。

可見(jiàn)問(wèn)題模型簡(jiǎn)化后，最優(yōu)結(jié)果發(fā)生變化。當(dāng)不考慮時(shí)間窗時(shí)，送貨時(shí)間相對(duì)寬松，無(wú)需外包給快遞公司，所以總配送費(fèi)用略有降低。當(dāng)加上軟時(shí)間窗后，由于送貨早到或者晚到的懲罰成本，總配送費(fèi)用也相應(yīng)增加。

4 結(jié)語(yǔ)

本文通過(guò)對(duì)帶外包和硬時(shí)間窗的服飾運(yùn)輸調(diào)度問(wèn)題進(jìn)行分析，構(gòu)建了AVRRHTWO和一般性VRR的數(shù)學(xué)模型?；煦缢阉鞅灰肴斯~群算法來(lái)提高算法的全局收斂性，反饋策略用來(lái)指導(dǎo)人工魚的移動(dòng)，這樣就形成了混沌人工魚群算法，應(yīng)用該算法及標(biāo)準(zhǔn)的遺傳算法對(duì)所建立的兩種模型求解，比較不同算法求解不同模型的結(jié)果，證明了AVRRHTWO模型和CAFSA求解此類模型的有效性，也表明了問(wèn)題模型的復(fù)雜程度影響求解結(jié)果。

［1］ 華銓平，王昕.時(shí)效性服裝配送模型與改進(jìn)蟻群算法的研究［J］.紡織學(xué)報(bào)，2012，33（6）：139-133.

［2］ 王赟，李仁旺，倪夏靜，等.基于遺傳算法的服裝配送路徑優(yōu)化策略［J］.浙江理工大學(xué)學(xué)報(bào)，2013，30（2）：178-183.

［3］ 賈祥素，吳菁.基于改進(jìn)蟻群算法服裝運(yùn)輸車輛路徑優(yōu)化研究［J］.浙江紡織服裝職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2013（3）：67-72.

［4］ 王昕，華銓平.基于服裝供應(yīng)鏈與服裝屬性的VRR成本模型［J］.西安工程大學(xué)學(xué)報(bào)ISTIC，2012，26（6）：756-760.

［5］ 王培崇，錢旭，周玉.求解VRR問(wèn)題的混合魚群遺傳優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（24）：201-203.

［6］ 朱命昊，厙向陽(yáng).求解旅行商問(wèn)題的改進(jìn)人工魚群算法［J］.計(jì)算機(jī)應(yīng)用研究，2010，27（10），3734-3736.

［7］ 江銘炎，袁東風(fēng).人工魚群算法及其應(yīng)用［M］.北京：科學(xué)出版社，2012.

［8］ Hu W，Liang H，Reng C，etal.A Hybrid Chaos-Rarticle Swarm Optimization Algorithm for the Vehicle Routing Rroblem with TimeWindow［J］.Entropy，2013，15（4）：1247-1270.

［9］ Yue Y X，Wen Z B，Yue Q X.Chaos Optimization Algorithm for Vehicle Routing Rroblem［J］.Advanced Materials Research，2012，538：2722-2726.

［10］ 湯雅連，蔡延光，郭帥，等.單車場(chǎng)關(guān)聯(lián)物流運(yùn)輸調(diào)度問(wèn)題的混沌遺傳算法［J］.廣東工業(yè)大學(xué)學(xué)報(bào)，2013，30：53-57.

Optimization for Apparel Transportation Scheduling Problem with Outsourcing

YANG Jun CAIYan.guang TANG Ya.lian JIANG Ze.dong
（School of Automation，Guangdong University of Technology，Guangzhou 510006，China）

Apparel product，as a strong timeliness goods，can be outsourced by the Express Company in the process of delivery.This paper analyzes the Apparel products Vehicle Routing Rroblem with Hard Time Windows and Outsourcing（AVRRHTWO），and then builds the AVRRHTWO model，Vehicle Routing Rroblem with Soft Time Windows（VRRSTW）model and general mathematicalmodel of Vehicle Routing Rroblem（VRR），improving the basic artificial fish swarm algorithm（AFSA），introducing the chaotic search in order to improve the global convergence of the artificial fish swarm algorithm，using feedback strategy to guide themovement of the artificial fish，in order to improve the convergence precision.By way of chaotic artificial fish swarm algorithm（CAFSA）and genetic algorithm（GA）to solve the three kinds ofmodel，based on the experimental data processing，it can prove the validity of AVRRHTWOmodel and the chaotic artificial fish swarm algorithm to solve the kinds ofmodel；moreover，it further proves that the complexity of themodel can affect the optimization ability；the simpler the problem model is，the better genetic algorithm is；themore complex the problem model is，the better chaotic artificial fish swarm algorithm is.

hard timewindows；Soft TimeWindows；outsourcing；apparel products Vehicle Routing Rroblem；chaotic artificial fish swarm algorithm；genetic algorithm

TR301

碼：A

：1009-0312（2014）05-0034-08

2014-03-18

國(guó)家自然科學(xué)基金（61074147，61074185）；廣東省自然科學(xué)基金（S2011010005059，8351009001000002）；廣東省教育部產(chǎn)學(xué)研結(jié)合項(xiàng)目（2012B091000171，2011B090400460）；廣東省科技計(jì)劃項(xiàng)目（2012B050600028，2010B090301042）。

楊軍（1989—），男，湖南株洲人，碩士生，主要從事嵌入式軟件開發(fā)研究。