馬千里　杜木子　李浩　李明駿

摘要：由于在集裝箱碼頭堆場冷藏集裝箱插拔電需要由機修工手動完成，為降低未能及時對冷藏集裝箱插電而造成箱內(nèi)貨物腐敗的風險，對機修工路徑進行優(yōu)化來減少總完工時間。建立考慮機修工的準備時間和懲罰時間的機修工插拔電路徑規(guī)劃模型，選用遺傳算法對模型進行求解。通過算例實驗證明了模型和算法的有效性。

關(guān)鍵詞：? 冷藏集裝箱; 帶有時間窗的旅行商問題; 路徑優(yōu)化; 遺傳算法

中圖分類號：? U691+.31文獻標志碼：? A

Mechanic path optimization of reefer container yard

under random demand

Abstract： As the power supply connection and disconnection operation of reefer containers in the container terminal yard needs to be manually completed by mechanics， in order to reduce the risk of cargo corruption caused by the failure to timely connect reefer containers to power supply， the mechanic path is optimized to reduce the total completion time. A mechanic path planning model for the power supply connection and disconnection operation is established considering the preparation time and the penalty time of mechanics. The model is solved by the genetic algorithm. The effectiveness of the model and the algorithm is proved by numerical examples.

Key words： reefer container; traveling salesman problem with time window; path optimization; genetic algorithm

引言

伴隨著食品冷鏈物流的市場規(guī)模越來越大，越來越多的冷藏集裝箱（簡稱“冷藏箱”）需要在相對較短的時間內(nèi)進行轉(zhuǎn)運。冷藏箱在轉(zhuǎn)運過程中需要插電以保持箱內(nèi)溫度，這一過程目前只能通過機修工完成。作為隨機事件，冷藏箱的到港和離港時間并不能事先確定，因此為進一步滿足冷藏箱的插拔電需求，碼頭的管理人員需要對現(xiàn)有機修工的工作流程進行優(yōu)化，加速冷藏箱的流轉(zhuǎn)，降低因不能及時插電而造成的貨物腐敗風險。

機修工的運動軌跡模型可以看成經(jīng)典的旅行商問題（traveling salesman problem， TSP），由于冷藏箱區(qū)場地過大，需要配置多名機修工，故將此問題視為多旅行商問題（multiple TSP， MTSP）。同時，由于提前拔電或者延后插電都可能造成冷藏箱制冷量不足，導致貨物腐敗，所以每個冷藏箱的插拔電時間都有一個嚴格的時間窗。目前，許多國內(nèi)外學者對TSP和MTSP進行了深入研究，取得了豐富的成果。HOUGARDY等[1]提出利用2opt啟發(fā)式算法對TSP進行求解;胡立栓等[2]對蟻群算法進行改進以增強算法的全局搜索能力;HU等[3]通過建立共享圖神經(jīng)網(wǎng)絡和分布式策略網(wǎng)絡來學習一個通用策略以求得近似最優(yōu)解;胡士娟等[4]提出一種模糊C均值聚類單親遺傳算法來加速求解過程;TOTH等[5]將MTSP看作車輛路徑問題（vehicle routing problem， VRP），取消運載能力限制后再進行求解;SOLOMAN等[6]首次在 VRP 的研究中引入時間窗概念;俞武揚等[7]以總成本最低為目標，分別考慮冷鏈車卸貨過程和運輸過程，建立了帶軟時間窗的優(yōu)化模型，利用蟻群算法仿真求解;邵舉平等[8]通過設計軟時間窗，將時間窗作為評判顧客滿意度的標準，建立了最大化顧客滿意度和最小化配送成本的多目標優(yōu)化模型;何小鋒等[9]在考慮時間窗的情況下，提出了量子蟻群算法，提高了算法的全局搜索能力，盡可能地避免算法陷入局部最優(yōu);夏文明等[10]基于最少旅行商數(shù)，在時間窗等約束條件下建立數(shù)學模型，利用改進的模擬退火算法進行求解，該算法增加了記憶因子，記住最小的局部最優(yōu)點，防止程序跳過全局最優(yōu)點后無法返回。在研究實際問題上，沈麗等[11]在細致量化貨損成本和碳排放成本的基礎(chǔ)上，考慮固定成本、燃油成本和時間懲罰成本，建立了總成本最低的生鮮產(chǎn)品配送路徑優(yōu)化模型;何繼紅等[12]通過分析冷藏箱堆場作業(yè)的特殊性，結(jié)合上海洋山深水港四期全自動化集裝箱碼頭的工程特點和裝卸工藝，提出該碼頭冷藏箱區(qū)布置方案。在研究冷藏箱堆場機修工插拔電路徑優(yōu)化問題上，國外有2個研究方向：HARTMANN[13]偏向于將碼頭作為整體，設計整體仿真系統(tǒng)進行研究;ZHANG等[14]偏向于對碼頭進行一定的簡單模擬，主要專注于求解MTSP的啟發(fā)式算法的創(chuàng)新。對應的國內(nèi)研究起步較晚，張曉龍等[15]以機修工行走路徑最短為目標，建立整數(shù)規(guī)劃模型來確定冷藏箱的插拔電作業(yè)順序。

上述文獻雖均對冷藏箱插拔電問題進行了較為深入的研究，但考慮的機修工移動因素較為簡單、單一，且建立的機修工移動模型較為簡化，與現(xiàn)實中機修工的工作方式難以吻合。本文在上述文獻的基礎(chǔ)上，進一步考慮機修工乘坐場地皮卡時的水平移動速度、攀登梯子時的移動速度、完成每個任務的時長等，充分模擬機修工在堆場內(nèi)部的移動軌跡。李敏等[16]驗證了遺傳算法在求解TSP上具有優(yōu)化過程短、運行速度快的優(yōu)點，因此本文利用遺傳算法對機修工插拔電路徑進行優(yōu)化，并對機修工的水平移動速度和機修工人數(shù)的變化對路徑優(yōu)化的影響進行分析。

1問題描述與數(shù)學建模

1.1問題描述

機修工插拔電路徑優(yōu)化問題可以看作一個MTSP，每當有插拔電需求產(chǎn)生時，便會對應產(chǎn)生一次任務。每次插電需求與到達堆場的冷藏船（車）有關(guān)，每次拔電需求與該冷藏船（車）需要離開堆場有關(guān)。在本文研究中，由于集裝箱碼頭現(xiàn)實問題往往十分復雜多變，為使模型更加準確且具有更強的普適性和參考價值，根據(jù)集裝箱碼頭的實際運營情況和冷藏箱區(qū)工作人員的工作內(nèi)容和方式，假設：（1）機修工乘坐的場地皮卡的移動始終是勻速的;（2）扶梯位于每排冷藏箱的正下方，以方便計算機修工到達各任務點的時間。

機修工完成一次任務的流程如下：（1）機修工通過通信設備接收有插拔電需求的集裝箱的位置信息的任務指令;（2）機修工乘坐場地皮卡到達相應位置，完成插拔電的工作;（3）機修工將完成任務的信息通過通信設備回傳給碼頭管理系統(tǒng)（ terminal operating system， TOS），等待下一任務指令的發(fā)布。

機修工在2種情況下將接收到任務：（1）當某位機修工完成了當前的任務，并將完成任務的信息通過通信設備回傳給TOS后，則由TOS繼續(xù)向該機修工發(fā)布新任務。（2）有新的任務產(chǎn)生，且至少有一名機修工處于空閑狀態(tài)，此時會有處于空閑狀態(tài)的機修工接收到新任務。

由于提前拔電或者延后插電都可能造成冷藏箱制冷量不足，導致貨物質(zhì)量下降，所以每個冷藏箱的插拔電時間都有一個嚴格的時間窗，即最早開始時刻和最晚開始時刻，不同作業(yè)任務的時間窗定義如下：（1）插電作業(yè)時間窗。最早開始時刻等于冷藏箱進入堆場的時刻;最晚開始時刻取決于冷藏箱在無外接電源情況下能保持箱內(nèi)溫度的時間。（2）拔電作業(yè)時間窗。最早開始時刻取決于拔電需求產(chǎn)生的時刻和冷藏箱在無外接電源情況下能保持箱內(nèi)溫度的時間;最晚開始時刻等于冷藏箱離開堆場的時刻減去機修工進行拔電工作的處理時間。

在實際工作環(huán)境中，冷藏箱是按順序進行提取的，斷電時間過長會對貨物冷藏效果造成影響從而產(chǎn)生貨物損失，因此針對機修工的工作時間設立時間窗，根據(jù)順序?qū)洳叵溥M行操作。以拔電作業(yè)為例，在時間窗外開始工作，提前開始會導致冷藏箱斷電時間延長增加貨損風險、延后開始會導致總工作時間延長，將這2種情況都視作延誤。本文針對不同任務下存在的隨機延誤情況設立懲罰系數(shù)，以此來對延誤時間進行約束。懲罰系數(shù)選取延誤時間與準備時間的權(quán)重比，考慮其影響程度較大，結(jié)合實際經(jīng)驗，取值為10。懲罰系數(shù)與延誤時間相乘后得到懲罰時間，并與準備時間合并設立目標函數(shù)，優(yōu)化目標為目標函數(shù)值最小，這樣設計不再單純考慮準備時間，與提升數(shù)量級后的懲罰時間相加，使得結(jié)果能夠以更好的效果呈現(xiàn)。

1.2符號說明

N為任務集合，N={1，2，…，n}，i∈N;M為機修工集合，M={1，2，…，m}，k∈M;[si，ei]為任務i的插拔電時間窗，其中Ti，s為任務i最早開始時刻，Ti，e為任務i最晚開始時刻;dij，h為機修工乘坐場地皮卡從任務i到任務j的水平移動距離;vh為機修工乘坐場地皮卡時的水平移動速度;hi，v為任務i所在的高度;vv為機修工上下攀爬梯子的速度;tij，s為從任務i處到任務j處的準備時間，tij，s=dij，h/vh+（hi，v+hj，v）/vv;ti，p為任務i的處理時間;Tki為機修工k完成任務i的時刻;tki為機修工k未在規(guī)定的時間窗內(nèi)完成任務i所延誤的時間，tki=max{0，Tki-Ti，e}+max{0，Ti，s-Tki};λ為懲罰系數(shù)，表示與準備時間比較，延誤時間所占的權(quán)重;M為無窮大的整數(shù);xkij為01變量，若任務i為任務j的緊前任務，且都由機修工k完成，則xkij=1，否則為0。

1.3數(shù)學模型

目標函數(shù)為

（1）

（2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

以上公式中，i，j∈N;k∈M。式（1）為目標函數(shù)，即優(yōu)化目標為最小化延誤時間與準備時間之和;式（2）限制每個任務只能被某位機修工完成一次;式（3）保證每位機修工從起點出發(fā)一次;式（4）用于保證每位機修工按照正確的工作順序完成工作;式（5）明確兩個任務的優(yōu)先級順序，如果機修工k的任務i的優(yōu)先級高于任務j的優(yōu)先級，則任務j的完成時間要大于等于任務i的完成時間、任務i到任務j的準備時間、任務j的完成時間之和，以保證任務的連續(xù)性;式（6）表示每位機修工的延誤時間;式（7）和（8）定義變量的取值范圍;式（9）確保被安排任務的機修工人數(shù)不超過機修工總?cè)藬?shù);式（10）確保無子回路。

2遺傳算法

在尋優(yōu)算法中，遺傳算法具有如下優(yōu)勢：可以直接對結(jié)構(gòu)對象進行操作，不存在求導和函數(shù)連續(xù)性的限定;具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力;采用概率化的尋優(yōu)方法，不需要確定的規(guī)則就能自動獲取和優(yōu)化搜索空間，自適應地調(diào)整搜索方向。因此，本文根據(jù)整體優(yōu)化法的思路和上述模型，設計遺傳算法。具體步驟如下：

步驟1初始值設置。設置各冷藏箱位置信息、冷藏箱之間的距離、機修工人數(shù)、機修工移動速度、算法迭代次數(shù)。

步驟2設置適應度評估值。

步驟3初始化種群。

步驟4對當前種群進行路徑規(guī)劃，規(guī)劃出當前種群最優(yōu)路線，進行繪圖。

步驟5進行適應度評估。如果滿足適應度評估條件，輸出結(jié)果。否則，進行步驟6。

步驟6利用遺傳算法因子對種群進行選擇、交叉、變異操作，得到子代種群，然后返回步驟5。

3算例分析

3.1算例構(gòu)建

為驗證本文所描述的冷藏箱堆場機修工插拔電路徑優(yōu)化模型的有效性，使用上海洋山深水港四期全自動化集裝箱碼頭相應數(shù)據(jù)進行實驗。算例設計如下：

該碼頭共有6個冷藏箱區(qū)，分別位于第14、15、30、31、46、47號箱區(qū)，每個箱區(qū)靠近陸側(cè)垂直于碼頭岸線布置。在相鄰的2個箱區(qū)之間設有場地皮卡通道，機修工只能在通道上駕車通行;如果需要跨箱區(qū)作業(yè)，只能通過跨箱區(qū)通道進入另一箱區(qū)。

每個箱區(qū)包含有8個大貝和2個小貝，每個貝位可以堆放7排，除第1排只能碼放2層冷藏箱外，其余每排可以碼放4層冷藏箱。第14和15號冷藏箱區(qū)結(jié)構(gòu)示意圖見圖1。

電源支架有4層，40英尺（1英尺=0.304 8 m）冷藏箱長度為12 m，20英尺冷藏箱長度為6 m，寬度均為3 m，層高均為 2.5 m，且上下電源支架的樓梯位于支架中部，跨箱區(qū)通道長為50 m。機修工攀爬樓梯時的移動速度為1 m/s。

各冷藏箱位置可以按照其所在箱區(qū)、貝位、排位、層數(shù)編碼：若需要插拔電的冷藏箱位于第30號箱區(qū)的第9貝第1排第4層，則該冷藏箱位置為（30，9，1，4）。用ai、bi、ci、di分別表示冷藏箱i所在箱區(qū)、貝位、排位及層數(shù)，則從任務點i（ai，bi，ci，di）到任務點j（aj，bj，cj，dj）的準備時間為

3.2算法參數(shù)設置

本文使用的測試數(shù)據(jù)參考上海洋山深水港四期全自動化集裝箱碼頭冷藏箱區(qū)的真實數(shù)據(jù)，根據(jù)某一時間點的實時堆存情況構(gòu)建三維立體坐標系，在冷藏箱區(qū)隨機產(chǎn)生40個插拔電需求點，再通過參考實際集裝箱調(diào)度數(shù)據(jù)對模型進行時間窗和工作時間的相應模擬。

共有40個插拔電任務，設第1個任務為所有機修工的出發(fā)點，非任務點。若某一任務的時間窗為（0， 3 600），則表示該任務的最早開始時刻是第 0 s，最晚開始時刻是第3 600 s。由于未能按時插拔電會使得貨物有腐爛的風險，造成的影響較大，故設懲罰系數(shù)為10。

3.3算例求解分析

設有4名機修工，其水平移動速度為5 m/s。求解出的路徑見表1，對應的路徑示意圖見圖2。求解結(jié)果顯示，4名機修工在水平移動速度為5 m/s時的總完工時間為51 463 s，其中總懲罰時間為45 698 s，總準備時間為5 765 s?？倯土P時間占比較高，其主要原因為懲罰系數(shù)為10。由此引發(fā)了新的問題：能否通過增加機修工人數(shù)來減少總懲罰時間和總完工時間？

3.3.1機修工人數(shù)對路徑優(yōu)化的影響

在機修工水平移動速度為5 m/s時，將機修工人數(shù)從2人逐漸增加至8人，模型求解結(jié)果見表2。表2反映了機修工人數(shù)與總完工時間、總懲罰時間和總準備時間的關(guān)系。

分2種情況進行討論：

（1）將機修工人數(shù)從4人逐漸增加至8人，分析其結(jié)果可以看出：當機修工人數(shù)超過5人后，并不能對總完工時間、總懲罰時間起到明顯的優(yōu)化效果，反而會出現(xiàn)小幅度增長現(xiàn)象。8名機修工在水平移動速度為5 m/s時的路徑見表3，對應的路徑示意圖見圖3。

（2）將機修工人數(shù)從4人減至2人，分析其結(jié)果可以看出：減少機修工人數(shù)并不能實現(xiàn)更好的優(yōu)化，反而會增加總懲罰時間和總完工時間。2名機修工在水平移動速度為5 m/s時的路徑見表4，對應的路徑示意圖見圖4。

由圖5和6可以看出：隨著機修工人數(shù)的增加，總完工時間和總懲罰時間均呈現(xiàn)先降后升的趨勢。

3.3.2機修工水平移動速度對路徑優(yōu)化的影響

在機修工人數(shù)為4人時，將機修工水平移動速度從2 m/s逐漸增加至8 m/s，模型求解結(jié)果見表5。

分2種情況進行討論：

（1）當機修工水平移動速度從5 m/s逐漸增加至8 m/s時，分析其結(jié)果可以看出，每次的速度增加都會對總完工時間和總懲罰時間產(chǎn)生優(yōu)化。然而，速度的增加是有上限的，可以考慮在一定合理范圍內(nèi)提高速度。4名機修工在水平移動速度為8 m/s時的路徑見表6，對應的路徑示意圖見圖7。

（2）當機修工水平移動速度從5 m/s逐漸降低至2 m/s時，分析其結(jié)果可以看出，隨著機修工水平移動速度的降低，總懲罰時間大幅度增加，總準備時間小幅度增加，從而造成總完工時間大幅度增加。4名機修工在水平移動速度為2 m/s時的路徑見表7，對應的路徑示意圖見圖8。

從圖9和10可以得出：逐漸增加機修工水平移動速度，總完工時間和總懲罰時間均呈現(xiàn)逐步下降的趨勢，且下降速度逐漸減緩。

4結(jié)論

本文建立考慮需求隨機的冷藏集裝箱（簡稱“冷藏箱”）堆場機修工插拔電路徑優(yōu)化模型，計算包含機修工的準備時間和懲罰時間的總完工時間。采用上海洋山深水港四期全自動化集裝箱碼頭的真實數(shù)據(jù)進行算例分析，并對機修工人數(shù)和其水平移動速度進行敏感性分析，較為完整地研究了機修工人數(shù)及其水平移動速度的變化對機修工路徑優(yōu)化的影響。在實際工作中，導致冷藏箱貨損的因素不僅僅涉及冷藏箱插拔電環(huán)節(jié)，還涉及運輸途中的各類狀況，因此在堆場環(huán)節(jié)能做到的就是穩(wěn)定工作時間，使插拔電時間與后續(xù)集裝箱處理環(huán)節(jié)相匹配，將間隔時間做到最小化。本文考慮的數(shù)學模型規(guī)模較小，且在研究過程中只研究了在某個時刻的路徑規(guī)劃，而在實際的機修工工作過程中，任務是隨時間不斷變化的，甚至在某些時刻將會把某些任務設置為更高的優(yōu)先級去進行處理，這些將作為下一步研究的方向。

參考文獻：

[1]HOUGARDY S， ZAISER F， ZHONG X H. The approximation ratio of the 2opt heuristic for the metric traveling salesman problem[J]. Operations Research Letters， 2020， 48（4）： 401404. DOI： 10.1016/j.orl.2020.05.007.

[2]胡立栓， 王育平， 亓呈明. 基于改進蟻群算法的物流配送車輛路徑優(yōu)化[J]. 智能建筑， 2017（6）： 6062， 80..

[3]HU Y J， YAO Y， LEE W S. A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs[J]. KnowledgeBased Systems， 2020， 204： 106244. DOI： 10.1016/j.knosys.2020.106244.

[4]胡士娟， 魯海燕， 向蕾， 等. 求解MMTSP的模糊聚類單親遺傳算法[J]. 計算機科學， 2020， 47（6）： 219224. DOI： 10.11896/jsjkx.190500137.

[5]TOTH P， VIGO D. The vehicle routing problem[M]. Philadelphia： Society for Industrial and Applied Mathematics， 2002： 225242.

[6]SOLOMAN M M， DESROSIERS J. Time window constraint routing and scheduling problems[J]. Transportation Science， 1988， 22（1）： 113.

[7]俞武揚， 楊沈記. 帶軟時間窗的冷鏈物流配送路徑優(yōu)化研究[J]. 生產(chǎn)力研究， 2017（6）： 6770， 116. DOI： 10.19374/j.cnki.141145/f.2017.06.015.

[8]邵舉平， 曹倩， 沈敏燕， 等. 生鮮農(nóng)產(chǎn)品配送中帶時窗的VRP模型與算法[J]. 工業(yè)工程與管理， 2015， 20（1）： 122127， 134. DOI： 10.19495/j.cnki.10075429.2015.01.019.

[9]何小鋒， 馬良. 帶時間窗車輛路徑問題的量子蟻群算法[J]. 系統(tǒng)工程理論與實踐， 2013， 33（5）： 12551261.

[10]夏文明， 李國富. 有路徑均衡和時間窗約束的MTSP問題研究[J]. 內(nèi)蒙古科技與經(jīng)濟， 2011（8）： 7980.

[11]沈麗， 李成玉， 甘彥， 等. 考慮貨損和碳排放的生鮮產(chǎn)品配送路徑優(yōu)化[J]. 上海海事大學學報， 2021， 42（1）： 4449. DOI： 10.13340/j.jsmu.2021.01.008.

[12]何繼紅， 姜橋， 張曉龍. 自動化集裝箱碼頭冷藏箱箱區(qū)布置[J]. 水運工程， 2016（9）： 5255. DOI： 10.16233/j.cnki.issn10024972.2016.09.011.

[13]HARTMANN S. Scheduling reefer mechanics at container terminals[J]. Transportation Research Part E， 2013， 51： 1727. DOI： 10.1016/j.tre.2012.12.007.

[14]ZHANG J T， SONG Y J. Mathematical model and algorithm for the reefer mechanic scheduling problem at seaports[J]. Discrete Dynamics in Nature and Society， 2017（3）： 113. DOI： 10.1155/2017/4730253.

[15]張曉龍， 浦新平， 林洋. 自動化集裝箱碼頭冷藏箱區(qū)插拔電路徑優(yōu)化[J]. 港口裝卸， 2019（1）： 1013， 49.

[16]李敏， 吳浪， 張開碧. 求解旅行商問題的幾種算法的比較研究[J]. 重慶郵電大學學報（自然科學版）， 2008， 20（5）： 624626， 630.

（編輯趙勉）

收稿日期： 20210713修回日期： 20211227

基金項目： 遼寧省社會科學規(guī)劃基金（L21CGL006）

作者簡介： 馬千里（1989—），河南襄城人，博士，研究方向為交通運輸系統(tǒng)優(yōu)化、冷鏈物流、港口規(guī)劃，（Email）qianlima@dlmu.edu.cn

*通信聯(lián)系人。（Email）dumuzi@pdiwt.com.cn