朱 偉，徐克林，佀占華，周 娜

（同濟(jì)大學(xué) 機械工程學(xué)院，上海201804）

對配裝配載及配送路線優(yōu)化問題的研究一直是運輸組織以及運籌學(xué)關(guān)注的重點，二者既相互影響，又相互制約.為提高配送系統(tǒng)運作效率及服務(wù)水平、進(jìn)一步降低成本，必須從系統(tǒng)化、集成化的角度出發(fā)，將配裝配載與運輸兩大功能進(jìn)行整合［1］.基于以上思路，本文研究并建立了單車輛配裝運輸決策模型 （decision-making model for single vehicle loading-transportation，SLTD）.

SLTD 研究是典型的組合優(yōu)化領(lǐng)域的非確定性多項式難題（NP-Hard）［2］，傳統(tǒng)的求解方法一般是優(yōu)化或啟發(fā)式算法，如Clarke和Wright提出的節(jié)約算法［3］，Gillett和Miller提 出 的Sweep算 法［4］，Lin提出的r-opt（r=2，3，…；r指改換的邊數(shù)）算法［5］，Norback和Love研究的幾何圖解算法［6］，Landrieu等運用的Tabu算法［7］等，但這些算法隨結(jié)點數(shù)的增加會出現(xiàn)組合爆炸現(xiàn)象.

遺傳算法（genetic algorithm，GA）最早由美國Michigan大學(xué)的Holland教授于1975年提出，它是受生物進(jìn)化規(guī)律啟迪的概率搜索方法［8］，極強的魯棒性和內(nèi)在的并行計算機制使它不僅在旅行商問題、背包問題、圖分割問題等組合優(yōu)化問題中取得了很多成果［9-10］，而且在配裝配載和運輸問題中也有廣泛應(yīng)用［11-12］，但遺傳算法在SLTD 中的應(yīng)用尚不多見.本文用VC++6.0語言實現(xiàn)了求解SLTD 模型的遺傳算法，實例計算表明了算法及模型的有效性.

1 SLTD 問題定義及模型建立

1.1 SLTD問題定義

SLTD 問題可定義為：有l(wèi)個客戶點，配送中心服務(wù)它們的配送需求，已知運輸車輛的載重量限制為G，容積限制為V，以總配送成本最低和車載利用率最高為目標(biāo)函數(shù)，在一定的約束條件下，確定滿足配送要求的最合適的車輛數(shù)m和最佳的車輛行程線路.本文研究SLTD 模型基于如下假設(shè)：配送中心到各需求點的距離及需求點間的距離已知；客戶數(shù)量及其需求量已知；各客戶需求均能得到滿足且每個客戶只能由同一輛車服務(wù)；需求點有且只能被服務(wù)一次；客戶i任務(wù)在時間窗［te，i，tl，i］內(nèi)完成，其中，te，i為時間窗起點，tl，i為時間窗終點；所有貨物均可配送；貨物配裝無需分類，亦無需采用隔離措施；配送車輛為單一車型；配送車輛均由配送中心出發(fā)且完成全部配送任務(wù)后返回出發(fā)點；線路總需求不大于運輸車輛的容量；配送過程無退貨產(chǎn)生；各道路均通暢，不考慮交通情況約束及車輛行程約束.

1.2 模型參數(shù)及決策變量

dhj（h∈I′，j∈I）表示中心至客戶或客戶點之間的距離；Ski表示k車服務(wù)客戶i的次序；thjk（h∈I′，j∈I）表示車輛k從中心至客戶或在客戶點之間運行的時間；設(shè)點h是同一條線路上點i的前相鄰點，車輛到達(dá)h的時間為th，車輛到達(dá)i的時間為ti，tu，h為點h的卸貨時間，則ti=th+tu，h+thik，（i∈I，h∈I′）.G為運輸車載重量，V為運輸車載的體積.

決策變量為

1.3 SLTD 數(shù)學(xué)模型

目標(biāo)函數(shù)（1）為配送成本最小，其中第1項為配送運輸成本，第2項為車輛基本運營成本，第3項和第4項分別為機會成本和懲罰成本；目標(biāo)函數(shù)（2）為車載重量利用率最大，目標(biāo)函數(shù)（3）為車輛容積資源利用率最高.令Z′g=-Zg，Z′v=-Zv，則線性加權(quán)后的單目標(biāo)函數(shù)Z可表示為：minZ=α1Zf+α2Z′g+α3Z′v，其中，α1，α2，α3是介于0～1 之間的權(quán)重系數(shù)，可用層次分析法確定，且α1+α2+α3=1.新目標(biāo)函數(shù)統(tǒng)一為追求最小化，為敘述方便，后文稱Z為服務(wù)成本.約束式（4）確保每個客戶有且僅有一個車輛為其服務(wù)；式（5）表示實際參與配送的車輛數(shù)為m；式（6）為車載重量約束，保證車輛所服務(wù)客戶的總需求重量不超過車載重量；式（7）為車載體積約束，保證車輛所服務(wù)客戶的總需求體積不超過車輛有效容積；式（8）為車輛路線連續(xù)性約束；式（9）和式（10）限定只能有一輛車從每個客戶節(jié)點進(jìn)出；式（11）為時窗約束表達(dá)式；式（12）表示客戶i只能分配給參與配送任務(wù)的車輛k；式（13）為支路消去約束，確保配送車輛在任何一個客戶中不形成回路.

2 算法設(shè)計

由于標(biāo)準(zhǔn)遺傳算法不能保證全局收斂，因此必須精心設(shè)計遺傳算法的染色體結(jié)構(gòu)、適應(yīng)度函數(shù)、初始群體、遺傳算子和控制參數(shù)，使之發(fā)揮其優(yōu)越性并以較大的概率獲得全局最優(yōu)解［13-14］.

2.1 遺傳算法應(yīng)用在模型中的適應(yīng)性分析

遺傳算法以編碼方式將搜索空間映射為遺傳空間，把可能的解編碼成一個向量，稱為染色體或個體，通過隨機方法確定起始的一群個體，稱為種群，然后以生物進(jìn)化為原型，通過復(fù)制、交叉和變異等操作，選擇最好的染色體，如此進(jìn)化下去，直至滿足期望的終止條件.

遺傳算法是一種應(yīng)用于優(yōu)化問題的啟發(fā)式算法，它尤其適用于常規(guī)算法難于求解的復(fù)雜空間，自產(chǎn)生以來，便以其魯棒性好，通用性強，并行計算等魅力吸引了無數(shù)學(xué)者和工程技術(shù)人員為之探討，但同時，它也存在 “編碼復(fù)雜”、“尋優(yōu)和收斂受算法設(shè)計影響大”、容易出現(xiàn) “早熟”和 “進(jìn)化停滯”等缺點.為此，在SLTD 模型中，算法采用了以下措施：

（1）算法中嵌入配送重量、體積及配送時窗檢驗子程序，減小了編碼的復(fù)雜程序；

（2）實驗優(yōu)化算法設(shè)計，確保其對于尋優(yōu)和收斂的 “正效應(yīng)”；

（3）通過最佳保留和自適應(yīng)交叉變異等策略改善 “早熟”和 “進(jìn)化停滯”現(xiàn)象.

2.2 染色體結(jié)構(gòu)

圖1 染色體結(jié)構(gòu)示意圖Fig.1 Diagram of chromosome structure

圖1染色體結(jié)構(gòu)中，子路徑內(nèi)部有序即調(diào)整子路徑中需求點位置，目標(biāo)函數(shù)值會發(fā)生變化；子路徑之間無序，即交換子路徑位置，目標(biāo)函數(shù)值不發(fā)生變化.

2.3 初始種群

配送中心是車輛的出發(fā)點和返回點，所以基因編碼應(yīng)始終以配送中心編號0開始；其次，生成l個需求點的隨機序列，如i1，i2，…，il，在此序列中插入虛擬配送中心點0，具體方法如下：若且，其中，gkj表示第k條路徑上第j個客戶點的需求質(zhì)量，vkj表示第k條路徑上第j個客戶點的需求體積；te，r≤tr≤tl，r，則將r至l的基因逐一向后移動1位，使r位空出，將0 插入第r位（r＜l）.接著若且且，重復(fù)如上操作，使s位空出，將0插入第s位.如此繼續(xù)，直到將m-1個0全部插入染色體為止，這樣就構(gòu)成了一條初始染色體.如此反復(fù)，直到生成滿足種群規(guī)模要求的染色體數(shù)目.

2.4 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是判斷解個體優(yōu)劣的重要手段，是解值逐步優(yōu)化的驅(qū)動力.為滿足適應(yīng)度函數(shù)的非負(fù)要求，目標(biāo)函數(shù)通過變換fi=αZbest／Zi轉(zhuǎn)化為適應(yīng)度函數(shù)，此處，fi為染色體i的適應(yīng)度，α為常數(shù)，Zbest為當(dāng)代最好染色體的服務(wù)成本，Zi為染色體i對應(yīng)的服務(wù)成本.顯然由表達(dá)式fi=αZbest／Zi得到的染色體適應(yīng)度值越大越好.

2.5 遺傳算子

選擇算子：采用最佳保留的輪盤賭法復(fù)制染色體.

交叉算子：由于基因編碼組間無序，組內(nèi)有序的特點，如果直接采用傳統(tǒng)的k值交叉方式，即隨機選取交叉點，交換父代的相應(yīng)基因片段，將可能分割已形成的優(yōu)良子路徑，甚至得到問題的不可行解.為此，本文采用文獻(xiàn)［15］中的交叉算子——最大保留交叉算子運算.具體過程為：（1）如果染色體交叉點處的2個基因都為0，直接進(jìn)行部分匹配交叉運算（PMX）；（2）如果染色體處的兩個基因不全為0，則將交叉點左移（右移），直到交叉點處的兩個基因都為0，再進(jìn)行PMX 運算.如：

父代1 0120｜345｜06780

父代2 0137｜026｜50480

｜｜內(nèi)為匹配段，經(jīng)過最大保留交叉運算后，結(jié)果為：

子代1 013402650780

子代2 017034502680

變異算子：采用2點交換作為遺傳算法的變異算子，隨機選取染色體上的兩個基因位，交換這兩個位置上的相應(yīng)基因，形成新個體.若基因串中出現(xiàn)連續(xù)0編碼，則表示參與配送任務(wù)的車輛數(shù)多，此時應(yīng)減少配送車輛，這對于優(yōu)化配送車輛數(shù)目和配送線路非常重要.

2.6 交叉變異率及終止條件

（1）自適應(yīng)調(diào)整交叉率pc和變異率pm：以fmax表示某代最優(yōu)染色體的適應(yīng)度；favg表示同代群體的平均適應(yīng)度；fm表示變異染色體的適應(yīng)度；fc表示兩交叉?zhèn)€體的較大適應(yīng)度值，得到：

其中，k1，k2為常數(shù)，且滿足0＜k1＜k2＜1.

（2）算法終止條件：設(shè)置進(jìn)化代數(shù)作為算法終止的判斷條件.

2.7 算法實現(xiàn)步驟

步驟1 輸入需求重量集N（g）=（g1，g2，…，gl），體積集N（v）=（v1，v2，…，vl），運輸車載重量G和體積V，初始車輛數(shù)m；

步驟2 構(gòu)造染色體；

步驟3 令Vms=0，Gms=0，這里Vms和Gms分別表示車輛m已裝載的貨物總體積和總重量；

步驟5 計算客戶i需求量的容重比ci=vi／gi；

步驟6 找出使得min|Rm-ci|的客戶i；

步驟7 比較客戶i貨物重量和體積與車輛剩余載重量和容積的大小，若Vi≤V-Vms且Gi≤GGms，轉(zhuǎn)步驟8，否則，刪除該染色體，轉(zhuǎn)步驟2；

步驟8 若ti∈twi，轉(zhuǎn)步驟9，否則，刪除該染色體，轉(zhuǎn)步驟2；

步驟10 若Im=Φ，轉(zhuǎn)步驟11，否則轉(zhuǎn)步驟4；

步驟11m=m-1；

步驟12 若m≥1轉(zhuǎn)步驟3，否則，確認(rèn)該染色體生成；

步驟13 重復(fù)步驟2～步驟12，直至生成滿足規(guī)模要求的染色體數(shù)目；

步驟14 設(shè)置控制參數(shù)（種群規(guī)模n、交叉率pc、變異率pm及最大迭代次數(shù)T）；

步驟15 gen=0，產(chǎn)生初始群體p（0），群體中每條染色體表示一個SLTD 方案；

步驟16i=1；

步驟17 將群體p（gen）中的第i條染色體譯成服務(wù)成本；

步驟18 計算第i條染色體的適應(yīng)度值；

步驟19i=i+1；

步驟20 若i≤n，則返回步驟17.否則，染色體復(fù)制；

步驟21 進(jìn)行最大保留交叉、2點變異；

步驟22 gen=gen+1，若滿足終止條件則停止，否則轉(zhuǎn)步驟16.

3 實例計算與分析

3.1 實例計算

某自有型配送中心服務(wù)8 個客戶的貨物配送，配送中心與客戶依次編號為0，1，…，8，各客戶的貨物需求量和需求體積、服務(wù)時窗及卸貨時間由表1給出.配送任務(wù)由載重量為8t，容積為10m3的車輛執(zhí)行，配送中心與客戶點及各客戶點之間的距離由表2給出（假設(shè)dij=dji，dii=0）.取c1=2，c2=4，車輛平均行駛速度為60km·h-1，確定完成任務(wù)的車輛數(shù)及行車路線.

表1 客戶需求特征Tab.1 Characteristics of customer demand

3.2 結(jié)果分析

配送中心用3輛車即可完成配送任務(wù)，3車輛的線路分別為0→6→7→5→0，0→3→4→0，0→1→2→8→0；其配送線路長度分別為357，318和312km；服務(wù)成本分別為946，849和834元；載重利用率分別為85%，86%和90%；容積利用率分別為85%，87%和84%.圖2為配送結(jié)果柱狀圖.

表2 網(wǎng)點間距離矩陣Tab.2 Distance matrix of node km

圖2 配送結(jié)果柱狀圖Fig.2 Column map for distribution results

4 結(jié)束語

采用遺傳算法實現(xiàn)了SLTD 模型的求解，本方法可有效地節(jié)約車輛行程，降低服務(wù)成本；使車輛的載重量和容積資源得以充分利用，減少配送車輛數(shù)目，降低配送車輛的購置費用.通過對遺傳算子的改進(jìn)及約束檢驗子程序的嵌入，算法于全局搜索，改善了局部收斂及早熟現(xiàn)象且提高了算法的速度及解的精準(zhǔn)度，較好地解決了多目標(biāo)配裝運輸決策問題.下一步將對多車配送及配送與回收集成問題進(jìn)行研究.

［1］ Tuzun D，Burke L I.Atwo-phase tabu search approach to the location routing problem［J］.European Journal of Operational Research，1999，116（1）：87.

［2］ Mosheiov G.The travelling salesman problem with pick-up and delivery［J］.European Journal of Operation Research，1994，79（2）：299.

［3］ Clarke G，Wright J W.Scheduling of vehicles froma central depot to a number of delivery points［J］.Operations Research，1964，12（4）：568.

［4］ Gillett B，Miller L.A heuristic algorithm for the vehicle dispatch problem［J］.Operations Research，1974，22（2）：340.

［5］ Lin S.Computer solutions of the traveling salesman problem［J］.Bell System Technology Journal，1965，44（10）：2245.

［6］ Norback J P，Love R F.Geometric approaches to solving the traveling salesman problem［J］.Management Science，1977，23（11）：1208.

［7］ Landrieu A，Mati Y，Binder Z.Atabu search heuristic for the single vehicle pickup and delivery problem with time windows［J］.Journal of Intelligent Manufacturing，2001，12（5-6）：497.

［8］ Holland J H.Adaptation in natural and artificial system［M］.Ann Arbor：The University of Michigan Press，1975.

［9］ Grefenstette J，Gopal R，Rosimaita B，et al.Genetic Algorithms for the traveling salesman problem［C］／／Proceedings of the 1st International Conference on Genetic Algorithmand Their Applications.Pittsburgh：Lawrence Erlbaum，1985：160-168.

［10］ 王蕾，沈庭芝，招揚.一種改進(jìn)的自適應(yīng)遺傳算法［J］.系統(tǒng)工程與電子技術(shù)，2002，24（5）：75.WANG Lei，SHEN Tingzhi，ZHAO Yang.An improved adaptive genetic algorithm ［J］.Systems Engineering and Electronics，2002，24（5）：75.

［11］ Montano B R，Anandalingam G，Zandi I.A genetic algorithmapproach to policy design for consequence minimization［J］.European Journal of Operational Research，2000，124（1）：43.

［12］ 謝秉磊，孫毅，李榮喜.求解配送＼收集旅行商問題的遺傳算法［J］.陜西工學(xué)院學(xué)報，2002，18（1）：70.XIE Binglei，SUN Yi，LI Rongxi.Genetic algorithm solving salesman problem with pickup and delivery［J］.Journal of Shaanxi Institute of Technology，2002，18（1）：70.

［13］ 周明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京：國防工業(yè)出版社，2002.ZHOU Ming，SUN Shudong.Genetic algorithm theory and application ［M］. Beijing： National Defence Industry Press，2002.

［14］ 玄光男，程潤偉.遺傳算法與工程設(shè)計［M］.北京：科學(xué)出版社，2000.XUAN Guangnan，CHEN Runwei.Genetic algorithms and engineering design［M］.Beijing：Science Press，2000.

［15］ 李軍，謝秉磊，郭耀煌.非滿載車輛調(diào)度問題的遺傳算法［J］.系統(tǒng)工程理論方法應(yīng)用.2000，9（3）：236.LI Jun，XIE Binglei，GUO Yaohuang.Genetic algorithm for vehicle scheduling problem with non-full load［J］.Systems Engineering—Theory Methodology Application，2000，9（3）：236.