遺傳離散粒子群算法求解車輛貨物配裝問題

牛江川，劉 凱，申永軍，韓彥軍

（石家莊鐵道大學 機械工程學院，河北 石家莊 050043）

1 引言

隨著信息技術的發展，企業面臨的生存與發展環境日趨復雜。物料配送車輛在進行貨物配裝時，目前常依靠經驗，進行估算配裝，沒有預先進行統一的設計，低效的空間利用率和混亂的貨物擺放等問題嚴重影響貨物配裝效率，甚至裝卸需要多次嘗試才能完成配裝，從而導致人力和財力的浪費，企業必須不斷地采用創新的理念與技術，才能為生產部門和運輸部門帶來效益。

貨物配裝是一個有約束條件的離散組合優化問題，求解體積或重量的最優利用率，研究方法主要有精確算法、啟發式算法和智能算法。精確算法只能有效求解中小規模問題，在可以求出結果前提下，可以獲得比人工智能算法更優的解[1]。啟發式方法缺乏全局尋優能力，尤其是在求大規模問題時效率不高[2]。當求解大規模多約束條件的復雜問題時，智能算法應用更為普遍。文獻[3]采用改進模擬退火算法依靠降溫策略求解了單一品種和多品種貨物配裝問題。文獻[4]通過對遺傳算法設計改進求解鐵路集裝箱運輸中多類型普零貨物的配裝問題，優化了裝載結果，并對遺傳算法解決該類貨物配裝問題的可行性給予了證明。文獻[5]用蟻群算法求解雙目標散貨配裝模型求解單貨車的載重和容積利用率最大問題，在求解速度和準確度方面均有提高。文獻[6]采用標準粒子群算法，將超載懲罰函數加入到粒子適應度的計算中，同時提出合并優化策略，使粒子的局部優化能力有所提高。將遺傳算法和離散粒子群算法的思想結合起來，將交叉和變異步驟加入到離散粒子群算法粒子速度和位置的更新之中，采用遺傳離散粒子群算法求解貨物配裝問題。

2 數學模型

設有j（j=1，2，3，…，m）個體積和重量均不相同的貨物，gj為貨物j的重量，cj為貨物j的體積，容積為C、載重為G的貨車，研究貨物如何配裝才能合理利用車廂容積和載重。

假設前提條件如下：

（1）裝箱貨物無優先級；

（2）貨物體積不可壓縮，為外徑體積；

（3）貨物為直接送往同一個地點；

（4）假設每類貨物體積和重量均不相同，實際情況體積和重量相同的貨物可歸為一類。

則可以得到目標函數：

式中：λ∈（0，1），當 λ=1 時，表示求載重量最大；μ∈（0，1），當 μ=1時，表示求容積利用率最大；xj—一個01變量，當xj取值為0時，表示這一批次的貨物配裝不裝貨物j，反之，當xj取值為1時，表示這一批次的貨物配裝需裝貨物j。若最優解為（1，0，1，0，…）表示要裝載的貨物為 1，3，…。

3 遺傳離散粒子群算法

3.1 離散粒子群算法

設D維搜索空間中，n個粒子組成一個群體，每個粒子都具有位置和速度兩個特征，每個粒子都表示搜索空間中的一個潛在的可行解，其中，第 i個粒子的位置記為 Xi=（xi1，xi2，…，xiD），i=1，2，3，…，n，速度記為 Vi=（vi1，vi2，…，viD），該粒子經過搜索，得到的最優位置即最優的適應度值記為 pi=（pi1，pi2，…，piD），也稱 pbest。在粒子群體中，所有粒子經過的最優位置記為pg，也稱為gbest。當粒子找到個體極值（pbest）和全局極值（gbest）時，根據式（7）來更新當前粒子的速度。

式中：w—慣性權重；u1、u2—加速度系數；rand1、rand2—［0，1］間取值的隨機數；vkid—第k次迭代粒子i飛行速度矢量的第d維分量；pid—粒子i個體極值的第d維分量；pgd—全局極值的第d維分量。

由于粒子位置的每一維只有0和1兩種取值，將粒子設計為一個XnD的0-1矩陣，為了表示速度值是二進制位取1的概率，速度值采用Sigmoid函數被映射到區間［0，1］上，故根據式（8）、式（9）改變粒子的位置。

式中：xid—第k次迭代粒子i位置矢量的第d維分量，xid=1—裝貨物 i，xkid=0 則表示不裝貨物 i。rand3—［0，1］間的隨機數，位置更新依賴于粒子速度決定的狀態轉移概率，速度大于一定的數值，粒子取1的可能性大，反之，取0的可能性大，且這個數值為［0，1］間的隨機數。

從上述粒子速度、位置更新策略可知，粒子某一位取1的概率為 Sigmoid，取 0 的概率則為 1-Sigmoid，由此可得到粒子某一位發生變化的概率：

3.2 交叉變異策略

保持種群多樣性有利于種群進化，借鑒遺傳算法中的交叉變異操作，增加粒子的多樣性，是避免種群陷入局部最優死循環的有效手段。當種群全局極值連續10次迭代沒有發生變化時，則認為種群陷入了局部最優解[7]。

在結束了上一次迭代后，根據粒子目前的最優適應度值，從粒子中選出適應度最好的全局最優粒子，后隨機選擇另1個與全局最優粒子配對的粒子，然后在個體編碼串中選擇2個交叉點，第1個位置在［1，D/2）內隨機選擇，第2個位置在（D/2，D］內隨機選擇，最后將兩個粒子中2個交叉點之間的編碼互換，得到新的粒子，如圖1所示。對這一代得到的新粒子，采用優秀個體保留的策略，當新得到的粒子適應度優于交叉前的粒子才更新粒子，否則上一代的全局最優粒子將直接保存到下一代。

圖1 交叉操作Fig.1 Crossover Operation

在交叉過程中，為了增加粒子群粒子的多樣性，避免一些優良因子由于交叉被替換出粒子群，引入變異操作，以取值低于0.01的概率對粒子中的因子進行取反操作，新產生的粒子有益于保持粒子群的多樣性。低于0.01變異概率意味著交叉后的粒子因子取反的可能性很低，產生不良因子的概率很低，如果交叉后產生不良因子，通過適應度值的對比也可以將其替換出粒子群。

3.3 參數分析

遺傳粒子群算法的參數包括搜索空間維數D、種群規模N、慣性權重 w、加速度系數 u1、u2。

（1）搜索空間維數D：搜索空間維數D是由所求解問題解的長度確定的，一般為目標函數中未知數的個數。

（2）種群規模N：種群規模N一般取搜索空間維數D的5倍。

（3）慣性權重w：慣性權重系數w越大，算法的全局搜索能力就越強，但求解精度低，而較小的慣性權重系數w能加強算法的局部搜索能力求解精度高但求解速度慢。慣性權重系數w一般在（0.1～0.9）間取值[8]，實驗表明，當 w=0.6 和 w=0.729 時，算法性能較佳。

（4）加速度系數 u1、u2：加速度系數 u1、u2代表了粒子向個體極值pbest和全局極值gbest推進的最大步長[9]。加速度系數太小，會使粒子在遠離目標區域內振蕩，而加速度系數太大，又容易越過目標區域，所以，理想的加速度系數不但有利于目標函數的收斂，而且可避免算法陷入局部最優無法跳出。當u1=（2.75～1.25），u2=（0.5～2.25），大多數目標函數都可以得到較好的適應度值。

3.4 算法實現流程

遺傳粒子群算法具體實現步驟如下：

（1）參數給定，給定群體個體數目N、搜索空間維數D、算法重復次數HX、最大迭代次數MaxDT、慣性權重w、加速度系數u1、u2。粒子種群位置X、速度V的初始化，生成初始解。

（2）計算種群的適應度值fitness。

（3）根據粒子適應度值的計算結果，更新粒子的個體極值pbest和全局極值 gbest。

（4）根據得到的個體極值 pbest、全局極值 gbest以及式（7）、式（8）、式（9）更新粒子的速度和位置。

（5）選擇、交叉、變異操作。

（6）計算新產生種群的適應度值fitness。

（7）對比新產生種群的fitness與上一代種群的fitness，若新產生的粒子的fitness優于當前種群的fitness，那么新粒子替換當前粒子，否則粒子的路徑信息不更新。

（8）根據適應度值更新個體極值pbest和全局極值gbest，并判斷循環條件是否達到，若達到，輸出最優解，算法結束，否則，返回（2）。

遺傳粒子群算法具體實現流程圖，如圖2所示。

圖2 遺傳離散粒子群算法流程圖Fig.2 Flow Chart of Genetic Discrete Particle Swarm Optimization Algorithm

4 算例求解

算例數據取自文獻[10]，某載重量為30t的箱式貨車，車廂內容積為70m3，要對14種貨物選擇配裝，各種貨物的重量、體積，如表1所示。求出合理的貨物裝箱結果。采用遺傳離散粒子群算法和基本粒子群算法對上述貨物配裝算例在Matlab中求解，主要參數設置如下：群體個體數目N=70、搜索空間維數D=14、算法重復次數HX=10、最大迭代次數MaxDT=300、慣性權重w=0.729、加速度系數u1=1.49445、u2=1.49445。兩種算法平均運行10次，具體優化配裝結果，如表2、表3所示。

表1 訂單配裝貨物信息表Tab.1 Orders for Freight Loading Information Table

表2 優化配裝結果Tab.2 The Optimization Results

表3 結果對比Tab.3 Comparison Results

采用的遺傳離散粒子群算法（GDPSO）求解配裝問題最優方案：體積利用率為99.93%，比啟發式算法（HA）[10]的體積利用率提高了6.33%，比基本粒子群算法（PSO）的體積利用率提高了8.5%。啟發式算法與基本粒子群算法的載重利用率均為95.83%，而遺傳離散粒子群算法載重利用率為99.33%，比其他兩種方法的載重利用率提高3.5%。遺傳離散粒子群算法并沒有像傳統的算法那樣，使載重利用率和體積利用率的求解結果顧此失彼，充分均衡地利用了車輛裝載空間。

5 結論

首先根據貨物配裝問題的特點，建立了同時考慮配裝車輛載重和體積的數學模型，采用遺傳離散粒子群算法求解貨物配裝問題，通過算例對比，驗證了該方法的有效性，該算法克服了傳統算法在載重利用率和體積利用率上顧此失彼，無法同時達到最優的缺點，充分合理地利用了車輛的載重和體積，使車輛的總體利用率達到最大，對企業經營成本的降低，作業效率的改善具有較好指導意義。