基于新型粒子群算法的散貨港口裝載機(jī)調(diào)度

李作志，王育靜

（天津工業(yè)大學(xué) 管理學(xué)院，天津 300387）

基于新型粒子群算法的散貨港口裝載機(jī)調(diào)度

李作志，王育靜

（天津工業(yè)大學(xué) 管理學(xué)院，天津 300387）

以散貨港口的裝載機(jī)為主要研究對象，在考慮車輛的速度、任務(wù)位置和運(yùn)送路徑的基礎(chǔ)上，建立以最短時間為目標(biāo)的車輛調(diào)度模型，對裝載車輛調(diào)度問題進(jìn)行優(yōu)化研究。在車輛調(diào)度優(yōu)化方面，采用三維向量的編碼方式在一種新型的粒子群算法下對模型進(jìn)行求解，證明算法的有效性，并且利用一種浮動的目標(biāo)函數(shù)得以使裝載機(jī)的任務(wù)量均勻，以求得在實際運(yùn)行中能幫助散貨港口提高工作效率、降低企業(yè)總體成本。

散貨港口；粒子群算法；裝載機(jī)調(diào)度

1 前言

港口的組成包括進(jìn)出港口的航道、錨泊設(shè)施、通信導(dǎo)航設(shè)施、裝卸疏運(yùn)設(shè)施、供應(yīng)服務(wù)設(shè)施，其中貨物裝卸是港口最基本的功能，實現(xiàn)運(yùn)輸方式的轉(zhuǎn)換，空間位置的有效轉(zhuǎn)移，從而開始或完成水路運(yùn)輸?shù)娜^程。港口貨物的裝卸要利用港口裝卸機(jī)械設(shè)備，主要包括：起重機(jī)（門座式、高架式、龍門式等）、裝船機(jī)、裝載機(jī)、汽車吊、輪胎吊、拖車、卡車、叉車等，其中裝載機(jī)對于散貨港口來說更是重中之重，港口管理者越來越認(rèn)識到裝載機(jī)調(diào)度的重要性，如何提高散貨港口裝載機(jī)的高效率和規(guī)范化作業(yè)，是一個亟待解決的問題。

目前國內(nèi)外對港口車輛調(diào)度的研究大部分是利用遺傳算法進(jìn)行優(yōu)化，在粒子群優(yōu)化算法上的研究并不深入。對于求解車輛調(diào)度問題，張維存等人利用主—從級遺傳算法建立以縮短顧客停留時間為目標(biāo)的數(shù)學(xué)模型，研究了港口散貨物流鏟車調(diào)度的問題[1]；郝志莉等對港口物流中非滿載車輛運(yùn)輸距離最短進(jìn)行調(diào)度問題的研究，并利用遺傳算法對模型進(jìn)行求解[2]。在優(yōu)化粒子群算法方面的研究，姜燕、劉長民等人利用主—從式的粒子群算法在水文模型上進(jìn)行了參數(shù)的優(yōu)化，并且提出了基于粒子群算法的主從群洗牌演化(MSSE—PSO)的新型算法，提高了計算精度和效率[3]；吳聰?shù)柔槍?biāo)準(zhǔn)粒子群優(yōu)化算法存在的不足，提出一種改進(jìn)粒子群算法(IPSO)的物流配送車輛調(diào)度優(yōu)化方法，并給出仿真實驗對其測試[4]；近期SabanGülcü,Halife Kodaz又提出了一種基于粒子群優(yōu)化算法的并行算法（PCLPSO），通過對其他粒子群算法的比較測試，發(fā)現(xiàn)多個群的主—從式協(xié)同合作方式可以提高解決問題的質(zhì)量和速度，對全局優(yōu)化問題更加適用[5]。

綜上所述，對粒子群算法的優(yōu)化是許多學(xué)者一直在努力的方向，在港口車輛調(diào)度中多注重所有車輛的研究，用遺傳算法求解也是按照傳統(tǒng)的方式進(jìn)行。通過本文的研究，以裝載機(jī)為例建立可以實際運(yùn)用到港口車輛調(diào)度的優(yōu)化模型，并利用新型粒子群算法求解模型，通過加強(qiáng)對裝載機(jī)的管理，以期提高港口散貨物流的管理水平、運(yùn)作效率和服務(wù)水平。

2 粒子群算法

2.1 標(biāo)準(zhǔn)粒子群算法

粒子群算法(Particle Swarm Optimization，簡稱PSO) 由Kennedy和Eberhart博士于1995年提出，基本概念源于對鳥群捕食行為的研究。群體在D維解空間上搜尋全局最優(yōu)解，并且每個粒子都有一個適應(yīng)函數(shù)值和速度來調(diào)整它自身的飛行方向以保證向食物的位置飛行，在飛行過程中，群體中所有的粒子都具有記憶的能力，能對自身位置、自身經(jīng)歷過的最佳位置（pbest）和種群中最好的粒子位置（gbest）學(xué)習(xí)，最終接近食物的位置。圖1給出粒子速度和位置在第t代和第t+1代的調(diào)整示意圖，全局最優(yōu)解在處。

圖1 粒子速度和位置調(diào)整示意圖

圖中：t—迭代的時刻；

t+1—下一迭代時刻；

v1—“社會經(jīng)驗”學(xué)習(xí)引起粒子向gbest方向飛行的速度；

v2—“自身經(jīng)驗”學(xué)習(xí)引起粒子向pbest方向飛行的速度；

v3—粒子自身具有的速度。

標(biāo)準(zhǔn)粒子群算法的數(shù)學(xué)描述，假設(shè)搜索空間為D維，種群規(guī)模為N，第i個微粒個體所處位置為Xi=(xi1,xi2,...,xid)，每個個體的飛行速度為Vi=(vi1,vi2,...,viD)，個體經(jīng)歷過的位置可定義為Si=(si1,si2,...,siD)，第i個粒子截至目前搜索到的最優(yōu)位置為Pi=(pi1,pi2,...,piD)，整個粒子群迄今為止經(jīng)過的最優(yōu)位置為Pg=(pg1,pg2,...,pgD)。所以可以定義為，每個粒子的位置變化可以用如下公式進(jìn)行表示：

式中：t—當(dāng)前粒子進(jìn)化代數(shù)；

w—慣性因子，非負(fù)數(shù)，是控制速度的權(quán)重；

c1、c2—加速系數(shù)；

r1、r2—介于［0,1］之間的隨機(jī)數(shù)。

2.2 新型的粒子群算法

標(biāo)準(zhǔn)的粒子群算法雖然應(yīng)用比較廣泛，但是也存在一些缺陷，比較明顯的有兩點：其一，是收斂速度慢；其二，是容易陷入局部最優(yōu)化。本文經(jīng)過對該算法資料的大量收集與研究，對其進(jìn)行了一定的改善，以達(dá)到滿足實際車輛調(diào)度的應(yīng)用。

基于種群互惠共生和共棲的思想，考慮到多群體協(xié)同進(jìn)化，設(shè)計出一種新型粒子群算法模型，在該模型中利用一個主（master）—從（slave）式的結(jié)構(gòu)來模擬共生群體之間的關(guān)系。整個種群被分為Z個子群（共生群體），其中Zm為主群（master swarm）數(shù)，Zs為從群（slave swarm）數(shù)，每個子群均包含相同的個體數(shù)，在搜索過程中各子群獨立進(jìn)化負(fù)責(zé)在解空間中全局廣度搜索，而主群根據(jù)其共生群體（從群或其他主群）的經(jīng)驗負(fù)責(zé)局部精確搜索，共生群體間的信息傳遞，在一定程度上避免了個體信息誤判造成的陷入局部最優(yōu)的危險[6]。

根據(jù)不同的主、從群數(shù)設(shè)置，可以表示不同共生模式，本文以Zm∈[1,Z)，ZS=Z-Zm為例，即部分個體參與信息交流的共棲模式，來說明主-從式粒子群算法的計算原理。對種群進(jìn)行分群后，每一個從群在迭代過程中利用標(biāo)準(zhǔn)的粒子群算法獨立更新速度和位置，在狀態(tài)更新之前把它們迄今為止發(fā)現(xiàn)的pbest發(fā)送給某一主群，此主群根據(jù)獲得的所有pbest及其他主群中最好個體信息進(jìn)行速度和位置的更新，更新方程如下：

式中：M—主群；

以上方程是一種協(xié)作型的主—從式粒子群算法，在這種更新機(jī)制中，主群中的每個粒子根據(jù)自己的經(jīng)驗，自身群體中其他粒子的經(jīng)驗，再加上從群中的最好經(jīng)驗進(jìn)行速度和位置更新，通過多方考慮在一定程度上避免了陷入局部最優(yōu)化。

3 裝載機(jī)調(diào)度的數(shù)學(xué)模型

3.1 問題描述

經(jīng)調(diào)查得知，港口車輛調(diào)度存在以下問題：調(diào)度基本處于人工方式，有很多不完善之處；車輛載貨行駛至相應(yīng)任務(wù)目標(biāo)位置后空載返回；在實際港口裝卸作業(yè)中，來港船只所裝卸貨物不可能正好是裝卸車輛滿載的整數(shù)倍，可能造成車輛非滿載行駛的資源浪費(fèi)。本文在以上問題的基礎(chǔ)上，利用新型粒子群算法對港口裝載車輛進(jìn)行合理的調(diào)度，為每個任務(wù)選擇最合適的裝載車輛，為裝載車輛選擇最合適的行駛路線，以及滿足車輛最佳的裝載順序，以達(dá)到充分的利用資源，提高效率節(jié)約成本的目的。

3.2 前提假設(shè)

（1）車輛調(diào)度剛開始時，所有的裝載機(jī)都可使用，所處位置為車庫；

（2）裝載機(jī)完成一次任務(wù)后就停在任務(wù)目標(biāo)位置，新任務(wù)的起始位置就是上一任務(wù)目標(biāo)位置，所有任務(wù)完成后車輛返回車庫；

（3）堆場和泊位的位置及相關(guān)信息已知；

（4）泊位卸船的貨物優(yōu)先級相同，無先后之分；

（5）每條路徑均順暢，不會產(chǎn)生交通堵塞和擁擠等情況。

3.3 數(shù)學(xué)模型

根據(jù)散貨港口的實際情況，本文著重以在船舶裝卸過程中每輛裝載機(jī)行駛總時間T最小為目標(biāo)對裝載機(jī)進(jìn)行調(diào)度，建立裝載機(jī)調(diào)度的優(yōu)化模型如下：

（1）決策變量：Pjkab，Qjkbc

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

（3）約束條件：

（4）變量描述：j港口裝載機(jī)編號(j=1,2,...,J)；k等待裝卸的任務(wù)編號(k=1,2,...,K)；a裝載機(jī)當(dāng)前位置(a=1,2,...,A)；b需要裝卸的任務(wù)位置(b=1,2,...,B)；c裝卸任務(wù)的目標(biāo)位置(c=1,2,...,C)；vj裝載機(jī)j的速度，vj∈(0,45)；Pjkab第k個任務(wù)由第j輛裝載機(jī)從當(dāng)前位置a到任務(wù)位置b的距離；Qjkbc任務(wù)位置b到任務(wù)目標(biāo)位置c的距離。

上述目標(biāo)函數(shù)（5）表示任務(wù)過程中裝卸車輛行駛的時間，包括兩部分：一是第k個任務(wù)由第j輛裝載機(jī)從當(dāng)前位置a到達(dá)任務(wù)位置b所用時間；二是任務(wù)位置b到任務(wù)目標(biāo)位置c所用時間。關(guān)于裝載機(jī)、任務(wù)位置及任務(wù)目標(biāo)位置的確定，是通過裝載機(jī)的車載設(shè)備讀取，當(dāng)位置確定后它們之間的距離也就確定了。調(diào)度的目的是求這兩部分行駛時間最短，每次迭代以用時最長的那輛裝載機(jī)任務(wù)為目標(biāo)函數(shù)，此時目標(biāo)函數(shù)是變動的，即哪個裝載機(jī)用時長就優(yōu)化哪個，從而使任務(wù)整體的運(yùn)輸時間最優(yōu)。

在上述約束條件中，式（6）表示對裝載機(jī)的調(diào)度必須滿足完成所有裝卸任務(wù)；式（7）表示所有裝卸任務(wù)之間的距離不小于零；式（8）表示裝載機(jī)新任務(wù)的起始位置就是上一任務(wù)的目標(biāo)位置；式（9）表示第j輛裝載機(jī)所用時間與第j+1輛差的絕對值小于ξ，目的是讓每個裝載機(jī)的任務(wù)執(zhí)行時間均衡。

4 裝載機(jī)調(diào)度問題的算法實現(xiàn)

4.1 粒子的編碼和解碼

裝載機(jī)調(diào)度問題模型建立以后，面臨著兩大問題需要解決，一是將裝載機(jī)分配到裝卸任務(wù)位置，二是各裝載機(jī)與裝卸任務(wù)的順序安排。根據(jù)裝載機(jī)調(diào)度問題的基本思路，提出了新型粒子群算法即主-從式的粒子群算法來求解該調(diào)度問題。假設(shè)裝卸任務(wù)總數(shù)為K，裝載機(jī)總數(shù)為J，構(gòu)建一個粒子長度為K的三維粒子，其中第一維表示裝卸任務(wù)；第二維表示裝載機(jī)任務(wù)分配；第三維表示裝載機(jī)作業(yè)順序。三維粒子的表示方法見表1。

表1 三維粒子的編碼

在上述三維粒子表示中，粒子位置向量xjk被限制在[1，J+ 1）的范圍內(nèi)，考慮實際情況對于裝載任務(wù)k所對應(yīng)的粒子位置向量xjk進(jìn)行取整，即操作函數(shù)為INT（xjk），INT（xjk）∈[1,J]，可知，裝載任務(wù)k就由裝載機(jī)INT（xjk）來完成，這樣就得到J輛裝載機(jī)在各裝載任務(wù)K上的分配方案，對于車輛j的作業(yè)順序，解碼時通過yjk的大小對同一裝載機(jī)的任務(wù)按照編號進(jìn)行粒子向量從小到大排序，從而確定裝載機(jī)的作業(yè)順序，通過以上解碼可得到調(diào)度問題的一個解。由此可見，通過以上操作就可以在粒子位置與調(diào)度問題解之間建立映射關(guān)系，如圖2、圖3所示。

圖2 粒子位置與裝載機(jī)任務(wù)分配的映射更新關(guān)系

圖3 粒子位置和裝載機(jī)作業(yè)順序的映射更新關(guān)系

從上述表示方法中，可以看出粒子位置與調(diào)度解的映射關(guān)系解碼過程很簡單，在實際應(yīng)用中需要在算法的初始階段對生成的初始方案進(jìn)行判斷，如果有不滿足現(xiàn)實調(diào)度情況的粒子就重新初始化該粒子。

4.2 新型粒子群算法的偽代碼

針對前面的新型粒子群算法[6]，利用MATLAB7.14 (R2012a)運(yùn)行環(huán)境進(jìn)行算法流程的編制，其中新型粒子群算法的偽代碼如下：

5 實例仿真及分析

5.1 數(shù)據(jù)來源

為更好的驗證新型粒子群算法的有效性和MATLAB編制程序的可行性，下面對散貨港口中的裝載機(jī)調(diào)度進(jìn)行動態(tài)的仿真實驗。粒子群算法的粒子數(shù)為20，為了更好的優(yōu)化結(jié)果，在先前研究者的基礎(chǔ)上，對初始參數(shù)進(jìn)行設(shè)置：學(xué)習(xí)因子c1= c2=2.05，c3=2；慣性權(quán)重的設(shè)置是線性下降的，隨著迭代次數(shù)的增加從0.9下降到0.4；實驗中總子群數(shù)Z=4，即其中主群Zm=1，Zs=3，是共生群體的規(guī)模；最大迭代次數(shù)為200次。仿真對象為：4個裝卸任務(wù)，3輛裝載機(jī)，裝載機(jī)在廠區(qū)行駛速度小于50km/h，每個任務(wù)的位置、任務(wù)的目標(biāo)位置及裝載機(jī)的位置和速度通過車載設(shè)備傳輸?shù)礁蹍^(qū)的數(shù)據(jù)回傳系統(tǒng)當(dāng)中，采集數(shù)據(jù)獲得信息，位置信息用坐標(biāo)表示，港區(qū)在（100，100）范圍內(nèi)，圖上1cm代表實際50m。在進(jìn)行車輛的調(diào)度中，除了需要考慮裝載機(jī)和任務(wù)的位置之外，還要考慮裝載機(jī)在調(diào)度時是否在作業(yè)中，以及作業(yè)時間。以下表2、表3是仿真所需要提供的數(shù)據(jù)。

表2 港區(qū)裝載機(jī)的行駛速度

表3 數(shù)據(jù)采集獲得的相關(guān)數(shù)據(jù)

表中坐標(biāo)位置已知，裝載機(jī)車庫的位置編號0坐標(biāo)為（40，54），假設(shè)兩個坐標(biāo)分別為（a，b）和（c，d），可得兩個位置的距離為：D= (a-c)2+(b-d)2。所有裝卸任務(wù)和任務(wù)目標(biāo)位置的平面分布如圖4所示。

圖4 裝卸任務(wù)和目標(biāo)位置的平面分布圖（單位：cm）

5.2 結(jié)果分析

仿真實驗中首先驗證了新型粒子群算法比標(biāo)準(zhǔn)的粒子群算法的優(yōu)越性，在同一臺計算機(jī)上用同一MATLAB版本進(jìn)行多次計算,發(fā)現(xiàn)新型的粒子群算法有著較快的收斂速度和求解精度，這一點從圖5迭代200次的結(jié)果可以看出。而從計算結(jié)果還可知，最優(yōu)車輛調(diào)度方案為：

裝載機(jī)1：0→1→1’→0

裝載機(jī)2：0→2→2’→3→3’→0

裝載機(jī)3：0→4→4’→0

經(jīng)過多次計算求得裝載機(jī)調(diào)度問題的最優(yōu)方案所用時間是0.76h，最優(yōu)函數(shù)值隨函數(shù)迭代次數(shù)變化的曲線如圖5所示。從圖5中可以明顯看出，采用本文所提出的新型粒子群算法能夠快速準(zhǔn)確的求出三維粒子群編碼的車輛調(diào)度問的最優(yōu)方案，并且搜索到最優(yōu)值的效率和準(zhǔn)確度都優(yōu)于標(biāo)準(zhǔn)粒子群算法，因此為求解港區(qū)裝載機(jī)問題提供了一種新的方法。

Study on Loader Deployment in Bulk Harbors Based on Innovative PSO

Li Zuozhi,Wang Yujing
(School of Management,Tianjin Polytechnic University,Tianjin 300387,China)

In this paper,with the loading machines at the bulk harbors as the object,and on the basis of the consideration of the vehicle speed,task location and transport route,we built the vehicle dispatching model aiming at the shortest operation time,solved it using a newly developed PSO,which proved the validity of the algorithm,and at the end,used a floating objective function to spread out the task volume of the loading machines to improve the operational efficiency of the ports and reduce their overall costs.

bulk harbor;PSO;loading machine deployment

U653.923

A

1005-152X(2015)11-0130-04

10.3969/j.issn.1005-152X.2015.11.036

2015-09-28

李作志（1975-），男，天津人，天津工業(yè)大學(xué)管理學(xué)院副教授，主要研究方向：管理科學(xué)與工程、資源經(jīng)濟(jì)及管理；王育靜（1991-），女，山東濟(jì)南人，天津工業(yè)大學(xué)管理學(xué)院碩士研究生，主要研究方向：物流工程。