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

（同濟大學 機械工程學院，上海201804）

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

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

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

1 SLTD 問題定義及模型建立

1.1 SLTD問題定義

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

1.2 模型參數及決策變量

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

決策變量為

1.3 SLTD 數學模型

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

2 算法設計

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

2.1 遺傳算法應用在模型中的適應性分析

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

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

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

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

（3）通過最佳保留和自適應交叉變異等策略改善 “早熟”和 “進化停滯”現象.

2.2 染色體結構

圖1 染色體結構示意圖Fig.1 Diagram of chromosome structure

圖1染色體結構中，子路徑內部有序即調整子路徑中需求點位置，目標函數值會發(fā)生變化；子路徑之間無序，即交換子路徑位置，目標函數值不發(fā)生變化.

2.3 初始種群

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

2.4 適應度函數

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

2.5 遺傳算子

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

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

父代1 0120｜345｜06780

父代2 0137｜026｜50480

｜｜內為匹配段，經過最大保留交叉運算后，結果為：

子代1 013402650780

子代2 017034502680

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

2.6 交叉變異率及終止條件

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

其中，k1，k2為常數，且滿足0＜k1＜k2＜1.

（2）算法終止條件：設置進化代數作為算法終止的判斷條件.

2.7 算法實現步驟

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

步驟2 構造染色體；

步驟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，轉步驟8，否則，刪除該染色體，轉步驟2；

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

步驟10 若Im=Φ，轉步驟11，否則轉步驟4；

步驟11m=m-1；

步驟12 若m≥1轉步驟3，否則，確認該染色體生成；

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

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

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

步驟16i=1；

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

步驟18 計算第i條染色體的適應度值；

步驟19i=i+1；

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

步驟21 進行最大保留交叉、2點變異；

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

3 實例計算與分析

3.1 實例計算

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

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

3.2 結果分析

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

表2 網點間距離矩陣Tab.2 Distance matrix of node km

圖2 配送結果柱狀圖Fig.2 Column map for distribution results

4 結束語

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

［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］.系統工程與電子技術，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］.陜西工學院學報，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］ 周明，孫樹棟.遺傳算法原理及應用［M］.北京：國防工業(yè)出版社，2002.ZHOU Ming，SUN Shudong.Genetic algorithm theory and application ［M］. Beijing： National Defence Industry Press，2002.

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

［15］ 李軍，謝秉磊，郭耀煌.非滿載車輛調度問題的遺傳算法［J］.系統工程理論方法應用.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.