楊 軍 蔡延光 湯雅連 江澤東

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

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

楊 軍 蔡延光 湯雅連 江澤東

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

由于服飾產(chǎn)品是一種時效性很強的商品，而且服飾產(chǎn)品在配送過程中可以外包給快遞公司進(jìn)行配送，對帶外包和硬時間窗的服飾運輸調(diào)度問題（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é)模型，通過對基本的人工魚群算法（artificial fish swarm algorithm，AFSA）進(jìn)行改進(jìn)，混沌搜索被引入人工魚群算法來提高算法的全局收斂性，反饋策略用來指導(dǎo)人工魚的移動，以此來提高收斂精度。應(yīng)用混沌人工魚群算法（chaotic artificial fish swarm algorithm，CAFSA）及遺傳算法（genetic algorithm，GA）對所建立的三種模型求解，通過對實驗數(shù)據(jù)進(jìn)行處理，證明了AVRRHTWO模型和混沌人工魚群算法求解此類模型的有效性，進(jìn)一步證明了問題模型的復(fù)雜程度影響算法尋優(yōu)能力，問題模型簡單時，遺傳算法更優(yōu)；問題模型復(fù)雜時，混沌人工魚群算法更優(yōu)。

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

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

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

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

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

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

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

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

配送方式有以下兩種。

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

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

定義變量如下

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

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

約束條件

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

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

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

定義變量如下：

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

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

約束條件

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

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

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

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

2 混沌人工魚群算法

2.1 求解思路

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

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

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

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

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

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

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

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

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

（32）隨機移動一步。

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）隨機行為。隨機行為是為了在更大范圍內(nèi)尋覓食物或同伴，隨機選擇一個狀態(tài)，然后向該方向移動。

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

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

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

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

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

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

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

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

3 仿真分析

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

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

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

算例分析

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

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

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

4 結(jié)語

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

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

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

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

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

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

［6］ 朱命昊，厙向陽.求解旅行商問題的改進(jìn)人工魚群算法［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］ 湯雅連，蔡延光，郭帥，等.單車場關(guān)聯(lián)物流運輸調(diào)度問題的混沌遺傳算法［J］.廣東工業(yè)大學(xué)學(xué)報，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

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

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