行駛時間區(qū)間不確定的裝配線物料配送路徑規(guī)劃

張家驊 李愛平 劉雪梅

1.同濟大學機械與能源工程學院，上海，2018042.無錫工藝職業(yè)技術學院機電與信息工程學院，宜興，214206

0 引言

準時化物料配送對企業(yè)降低生產成本、提高生產效率有重要意義。物料配送中的車輛路徑規(guī)劃問題是一個重要決策問題，近年來受到學者關注[1]。

文獻[2-4]對裝配線物料配送路徑規(guī)劃問題進行了研究，表明裝配線物料配送路徑規(guī)劃模型可以按帶時間窗的車輛路徑規(guī)劃問題進行建模與求解。吳倩云等[5]在此基礎上進一步考慮了物料在配送車輛上的三維裝載約束。

上述研究考慮了配送車輛行駛時間確定的情況，但在變速箱裝配線等生產中，零件由配送員駕駛拖車同時對幾條裝配線進行配送，該配送方式并不能精確控制拖車速度和行駛路線，車間中工作人員和貨物往來頻繁，更增加了配送車輛行駛時間的不確定性。不確定行駛時間增加了物料不能準時送達工位的風險。KORYTKOWSKI等[6]研究發(fā)現(xiàn)物料能否準時送達對裝配線生產性能有重要影響。TURNQUIST等[7]、VONOLFEN等[8]采用配送車輛行駛時間服從隨機概率的方法研究裝配線物料配送問題。李晉航等[9]對裝配線中配送車輛運輸時間等不確定信息進行模糊化處理，建立了混流裝配線配送路徑的模糊機會約束規(guī)劃模型，并采用遺傳算法進行了求解。然而實際生產中車輛不確定運行時間的概率分布或模糊隸屬函數(shù)可能難以獲得，使上述方法的應用受到了限制。

近年來，考慮不確定信息區(qū)間分布的魯棒優(yōu)化方法快速發(fā)展[10-11]，該方法不需要預知不確定信息的具體概率分布或模糊隸屬度函數(shù)，只需知道信息的區(qū)間范圍，這一方法在多個領域已經被廣泛研究和應用，包括應用于經典的車輛路徑規(guī)劃問題。SUNGUR等[12]首次采用魯棒優(yōu)化方法研究了服務點需求不確定的車輛路徑問題，建立了該問題的混合整數(shù)規(guī)劃模型。BRAATEN等[13]針對魯棒車輛路徑優(yōu)化問題的計算復雜性，提出了一種啟發(fā)式方法。HU等[14]針對車輛行駛時間和服務點需求不確定的魯棒車輛路徑問題，引入路徑相關不確定參數(shù)，建立了優(yōu)化模型，并設計了一個兩階段智能求解算法。MUNARI等[15]研究了車輛行駛時間和服務點需求均不確定的魯棒車輛路徑問題，設計了分支定價割平面求解算法。劉洋等[16]研究了養(yǎng)護時間不確定的養(yǎng)護車輛魯棒路徑規(guī)劃問題。目前未見有關魯棒優(yōu)化方法在裝配線準時化物料配送車輛路徑規(guī)劃中的應用。

本文針對行駛時間不確定的裝配線物料配送車輛路徑規(guī)劃問題，采用魯棒優(yōu)化方法，引入路徑相關不確定參數(shù)，建立行駛時間區(qū)間不確定的裝配線物料配送路徑規(guī)劃模型，并設計了求解該模型的混合遺傳算法。

1 問題描述及模型建立

1.1 確定行駛時間的路徑規(guī)劃數(shù)學模型

裝配線物料配送路徑規(guī)劃問題可以描述為：已知圖G=(V，A)，V={0，1，…，n}是工位節(jié)點集合，0表示物料配送中心，所有配送車輛從配送中心0出發(fā)，完成配送任務后返回配送中心，進行下一次配送；A表示工位節(jié)點之間的弧。已知配送車輛數(shù)目為K，負責對n個工位進行物料配送，每個工位只能由一輛車服務；每輛車的最大載重Q，車廂是三維矩形(長L、寬W、高H)；第i工位的物料需求質量為qi(i=1，2，…，n)，需ai個標準料箱來運送物料，第a個料箱尺寸為lai、wai、hai(a=1，2,…，ai)；車輛需滿足最大載重量約束，每個工位所需物品放入同一輛車，料箱尺寸滿足車廂尺寸約束；車輛在第i工位的服務時間是ui；第i個工位的服務時間窗為[ei，bi]，如果車輛早于ei到達，則車輛進行等待；晚于bi到達則被拒絕。

問題目標是在滿足約束的條件下尋找合理的車輛路徑，以達到車輛總行駛距離的最小化：

(1)

(2)

(3)

(4)

(5)

(6)

?k∈{1,2，…,K}p∈{1,2，…,n}

(7)

?i∈V{0}a∈{1,2，…,ai}

(8)

sik+ui+tij-M(1-xijk)≤sjk

(9)

ei≤sik≤bi

(10)

xijk∈{0,1}yik∈{0,1}

目標函數(shù)式(1)表示最小化行駛距離，dij表示工位i到工位j的距離，xijk是決策變量，xijk=1表示車輛k從工位i駛往j。約束式(2)～式(5)分別表示有K輛車離開配送中心、每個工位正好被訪問一次，以及進入和離開每個工位組只有一輛車，式中yik是輔助決策變量，yik=1表示工位i采用車輛k配送。約束式(6)保證車輛行駛線路的連通性。式(7)是料箱在車廂內的尺寸約束，xai，yai，zai表示的是工位i所需料箱a在車廂中的左后下角的坐標，坐標系原點位于車廂內側左后下角頂點，即首個料箱左后下角擺放的位置頂點。式(8)是每輛車的裝載容量限制。約束式(9)要求由同輛車配送的兩個工位，只有配送完前一個工位，車輛行駛到后一個工位后，才能執(zhí)行配送，sik為車輛k在工位i服務開始時間，ui為車輛在工位i的服務時間，tij為車輛從工位i到工位j的行駛時間，此處該時間是確定的，M是一個大的正數(shù)。式(10)是時間窗約束。

1.2 不確定行駛時間的路徑規(guī)劃模型

θ=0，Λk=0，表明車輛k路徑中任一弧上的行駛時間均不發(fā)生波動；θ=1，Λk=|Ak|，表明車輛k所在路徑中的所有弧的行駛時間都發(fā)生波動。根據(jù)魯棒優(yōu)化原理[17]，當每條路徑中最多|Ak|段弧發(fā)生波動時，解仍然是可行的，說明該解是魯棒的。

定義si,k,γk是第k條路徑有γk條弧上的行駛時間發(fā)生波動的情況下車輛k在工位i的最差服務開始時間，該值可以通過下式計算得到：

(11)

其中，當i是物料中心即i=0時，車輛服務開始時間不受不確定性的影響；當i是物料需求工位時，分兩種情況：①如果γk=0則表示弧上沒有行駛時間發(fā)生波動，車輛最差服務開始時間等于行駛時間確定情況下的值；②如果γk≠0則車輛在工位i的最差服務開始時間與該工位的時間窗的下限、上一個工位已經達到最差服務開始時間或本工位達到最差服務開始時間相關。

按照上述分析，不確定行駛時間的路徑規(guī)劃模型只需要在上一節(jié)確定行駛時間的模型基礎上，根據(jù)式(11)對式(9)和式(10)修改為

si,k,γk+ui+tij-M(1-xijk)≤sj,k,γk

(12)

?i,j∈Vk=1,2，…,Kγk=0,1，…,Λk

(13)

?i,j∈Vk=1,2，…,Kγk=1,2，…,Λk

ei≤si,k,γk≤bi

(14)

其余公式均保留不變。

2 混合遺傳算法

傳統(tǒng)的車輛路徑問題被證明是NP-hard問題，本問題在傳統(tǒng)車輛路徑問題上，還需考慮時間窗，三維裝載和不確定行駛時間約束，求解更加困難。智能算法是求解該類問題的主要方法，其中遺傳算法被認為是最有效的求解方法之一，但單純的遺傳算法存在早熟收斂、易陷入局部最優(yōu)的缺點[18]。已有研究表明，模仿鳥類飛行行為的萊維飛行可以擴大算法的搜索范圍，幫助算法及時跳出局部最優(yōu)[19-20]。傳統(tǒng)的萊維飛行不能直接應用于離散優(yōu)化問題，文獻[21]針對旅行商問題提出一種離散萊維飛行，通過控制萊維飛行的步長來實現(xiàn)不同弧之間的局部搜索。本文針對所研究的問題，在上述文獻的基礎上，設計了另一種離散萊維飛行來增強算法的搜索能力。

圖1是算法流程圖，首先利用遺傳算法快速找到可行解，然后通過離散萊維飛行對可行解進行局部搜索，改善解的質量。

圖1 算法流程圖

2.1 初始種群與適應度值評估

染色體采用自然數(shù)編碼方式，自然數(shù)1,2，…,n代表工位數(shù)，0表示配送中心，車輛數(shù)K已知，可表示長度為n+K+1的向量(0，i11，i12，…，i1s，0,i21，i22，…，i2t，…，0，iK1，iK2，…,iKw，0)，其中ikj表示第k輛車服務的第j個工位的工位號。圖2所示染色體表示2輛車對7個工位進行物料配送。為增加種群的多樣性，按種群規(guī)模，采取隨機法生成初始種群。

圖2 染色體示例

根據(jù)染色體的基因值，可直接解碼得到車輛的行駛路徑。由圖2所示染色體可得第一輛車的行駛路徑是0-1-3-7-0，第二輛車的路徑是0-2-4-5-6-0。根據(jù)車輛路徑，可計算出第k輛車的行駛距離fdk，第k輛車的載重fqk。按照式(11)可得在不同θ下每輛車經過工位i的最差可能服務開始時間si,k,Λk。

染色體中每輛車訪問過的工位可以進一步解碼為(rai，xai，yai，zai，lai，wai，hai)，rai是工位i中料箱a的疊放順序。按照料箱放置從下到上、從前到后、從左到右的規(guī)劃，可以得到每輛車料箱的最終xk、yk、zk。

由以上得到的結果，可以計算出適應度值：

其中，M用來對違反約束進行懲罰。

2.2 遺傳算子

輪盤賭選擇就是按照適應度值計算染色體在子代中出現(xiàn)的概率，該方法適用于求解最大化問題，如果求解最小化問題，則需要對適應度值函數(shù)進行轉化，而采用錦標賽選擇可以避免此類問題并獲得更好性能[22]。由于本文研究最小化問題，故采用錦標賽選擇，每次從種群中隨機抽取兩個染色體，選擇其中最好的一個進入子代種群。交叉算子采取類PMX交叉過程，若得到的子個體不合法，則通過調整0代碼的位置來使染色體可行[9]。變異算子采用交換兩點基因值策略[23]。

2.3 離散萊維飛行

式中，β∈[1, 2]，β一般取值為1.5；Γ(·)表示伽馬函數(shù)。

文獻[20]針對旅行商問題提出了一種離散萊維飛行，通過λ控制鄰域搜索，實現(xiàn)解的更新。本文據(jù)此設置萊維飛行策略如下：如果λ≤1，則隨機選擇一條路徑，對路徑內的任一段基因序列進行逆轉，實現(xiàn)短距離的萊維飛行；如果λ>1，則隨機選擇兩條路徑，對其進行2-opt*交換[24]，實現(xiàn)在路徑間的鄰域搜索。圖3和圖4是離散萊維飛行的兩種不同方式的示例。

圖3 路徑內飛行

圖4 路徑間飛行

最后，將離散萊維飛行后的種群與原種群進行比較，將目標值較小的染色體保留形成新的種群，進行下一次進化，直到滿足迭代要求。

3 案例分析

3.1 算法對比

文獻[3]針對16個工位、6輛配送車輛的總裝線物料配送路徑規(guī)劃問題提出了一種遺傳算法進行求解，具體數(shù)據(jù)見文獻[25]。針對文獻[3]的問題，采用其模型和算法參數(shù)，在MATLAB平臺上使用本文所提算法對該案例進行了計算，結果如表1所示。從表1中可得，本文的算法能夠得到比原算法更優(yōu)的結果，這主要是由于采用離散萊維飛行后擴大了算法的搜索空間，說明本文提出的算法改進策略有效。

表1 不同算法結果的對比

3.2 實例描述

某變速器裝配車間由變速器總成裝配線、制動器分裝線、輸入軸和離合器分裝線、后蓋分裝線和主箱體分裝線組成，車間共有9個物料需求工位。物料配送由2輛相同的拖車執(zhí)行，拖車參數(shù)見表2。表3所示是物料使用的4種不同規(guī)格的料箱尺寸。表4所示是工位的物料需求量和需求時間窗。表5所示是工位間的距離與行駛時間，其中行駛時間用區(qū)間數(shù)表示。各物料需求工位的服務時間是1 min。

表2 拖車規(guī)格參數(shù)

表3 標準料箱規(guī)格參數(shù)

表4 各工位貨物需求量和時間窗

表5 各工位間行駛距離和行駛時間

算法參數(shù)設置如下：種群規(guī)模100，交叉概率0.8，變異概率0.2，終止迭代次數(shù)100。

3.3 實例結果分析

為了分析θ對結果的影響，計算θ為0、0.1、0.5、1時的結果。θ=0表示結果不考慮不確定的影響，θ為0.1、0.5、1分別代表結果考慮低、中、高3種不確定程度。圖5是不同θ下的目標值收斂曲線，表6所示是具體路徑方案和目標值。從圖5中可得，θ值越大，目標值收斂速度越快，這是由于隨著考慮不確定程度增加，可滿足約束條件的解越少，使問題可行解對應染色體空間可能性變小，種群內的解差異性增大，利于算法更早達到全局最優(yōu)解。

圖5 不同θ下的行駛距離的對比

表6 不同θ下的具體結果

從圖5和表6中可得，θ對車輛行駛距離也有影響。θ從0增加到0.5，目標值不斷增大；θ為0.5和1時，目標值保持不變。這是因為為了抵抗不確定的行駛時間，需要調整行駛路線，增加行駛距離；但當考慮了足夠的不確定程度時，行駛路線不再發(fā)生變化。

以θ為0和0.1的結果分析解如何抵抗不確定行駛時間的影響。圖6所示是θ=0時配送車輛的路徑方案，工位號上方的是各個工位的時間窗，下方是車輛到達工位的服務開始時間。得到的路徑方案保證了服務開始時間在物料配送的時間窗內，但這個方案不考慮不確定行駛時間。如果行駛時間發(fā)生波動，例如第一條路徑中工位3-工位4，見表5，則存在可能的波動時間0.5 min，如果發(fā)生波動，那么實際最差的服務開始時間是18.6+0.5=19.1 min，該時間超過了工位4允許的時間窗上限，導致方案不可行。

圖6 θ=0時車輛服務開始時間(min)

圖7所示是θ=0.1時的路徑方案，工位的服務開始時間下方的數(shù)字是考慮如果路徑中發(fā)生θ=0.1不確定情況時每個工位最差服務開始時間。與θ=0路徑的不同之處在于，該方案將訪問順序4和5進行了互換。由圖7可以看到，即使路徑中發(fā)生θ=0.1的行駛時間波動，車輛的服務開始時間依然滿足時間窗要求，有效抵抗了不確定行駛時間的影響。

圖7 θ=0.1時車輛服務開始時間(min)

為了進一步獲得各個路徑方案抵抗不確定行駛時間的能力，采用蒙特卡羅模擬法[26]對結果進行分析。在給定θ下，蒙特卡羅模擬法評價解抵抗不確定行駛時間的過程如下：①輸入路徑方案；②產生N個θ條件下的不確定行駛時間場景(N=10 000)，每個場景中的不確定行駛路徑的路段數(shù)按照θ隨機選擇，路段內不確定行駛時間在各自區(qū)間內按均勻分布產生；③對解在每個場景中的可行性進行分析；④對解可行性的結果進行統(tǒng)計，輸出解在當前θ下的可行概率。

通過調整θ可以觀察不同方案抵抗不同不確定程度的能力，結果如表7所示，方案4結果同方案3。從表7中可看到，方案1抵抗不確定性的能力隨著路徑中的不確定程度增加而降低，這是因為該方案完全沒有考慮行駛時間不確定的影響；方案2與要求一致，能夠完全抵抗θ=0.1的不確定性，隨著不確定性程度的增加，該方案的抵抗能力依然很強；方案3的結果則能夠完全抵抗住所有不確定的情況。

表7 各方案抵抗不同不確定程度的可行概率

由上文分析可知，為了抵抗不確定性，需要調整車輛運行路徑，這會導致車輛行駛距離增加，因此決策者要根據(jù)實際情況，綜合運行成本來選擇最佳車輛路徑方案。從本案例分析可以得到，方案2能夠以較短的行駛距離，使行駛路徑基本不受不確定行駛時間的影響，保證裝配線的穩(wěn)定運行。

4 結論

(1)為了考慮裝配線物料配送中車輛行駛時間區(qū)間不確定對路徑規(guī)劃的影響，本文采用魯棒優(yōu)化方法，引入路徑相關不確定參數(shù)，建立了魯棒路徑規(guī)劃模型。

(2)提出了一種求解該模型的混合遺傳算法，在算法中，使用錦標賽選擇算子，避免適應度值的轉換；使用離散萊維飛行來提高算法的搜索性能。計算案例表明該混合算法比傳統(tǒng)遺傳算法能得到更好的解。

(3)求解結果與路徑相關不確定參數(shù)有關，決策者需要根據(jù)實際情況，綜合運行成本來選擇最佳路徑方案。