需求隨機(jī)條件下冷藏集裝箱堆場(chǎng)機(jī)修工路徑優(yōu)化

馬千里　杜木子　李浩　李明駿

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

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

中圖分類(lèi)號(hào)：? U691+.31文獻(xiàn)標(biāo)志碼：? 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

引言

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

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

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

1問(wèn)題描述與數(shù)學(xué)建模

1.1問(wèn)題描述

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

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

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

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

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

1.2符號(hào)說(shuō)明

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

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

目標(biāo)函數(shù)為

（1）

（2）

（3）

（4）

（5）

（6）

（7）

（8）

（9）

（10）

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

2遺傳算法

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

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

步驟2設(shè)置適應(yīng)度評(píng)估值。

步驟3初始化種群。

步驟4對(duì)當(dāng)前種群進(jìn)行路徑規(guī)劃，規(guī)劃出當(dāng)前種群最優(yōu)路線(xiàn)，進(jìn)行繪圖。

步驟5進(jìn)行適應(yīng)度評(píng)估。如果滿(mǎn)足適應(yīng)度評(píng)估條件，輸出結(jié)果。否則，進(jìn)行步驟6。

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

3算例分析

3.1算例構(gòu)建

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

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

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

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

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

3.2算法參數(shù)設(shè)置

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

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

3.3算例求解分析

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

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

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

分2種情況進(jìn)行討論：

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

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

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

3.3.2機(jī)修工水平移動(dòng)速度對(duì)路徑優(yōu)化的影響

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

分2種情況進(jìn)行討論：

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

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

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

4結(jié)論

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

參考文獻(xiàn)：

[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]胡立栓， 王育平， 亓呈明. 基于改進(jìn)蟻群算法的物流配送車(chē)輛路徑優(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的模糊聚類(lèi)單親遺傳算法[J]. 計(jì)算機(jī)科學(xué)， 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áng)， 楊沈記. 帶軟時(shí)間窗的冷鏈物流配送路徑優(yōu)化研究[J]. 生產(chǎn)力研究， 2017（6）： 6770， 116. DOI： 10.19374/j.cnki.141145/f.2017.06.015.

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

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

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

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

[12]何繼紅， 姜橋， 張曉龍. 自動(dòng)化集裝箱碼頭冷藏箱箱區(qū)布置[J]. 水運(yùn)工程， 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]張曉龍， 浦新平， 林洋. 自動(dòng)化集裝箱碼頭冷藏箱區(qū)插拔電路徑優(yōu)化[J]. 港口裝卸， 2019（1）： 1013， 49.

[16]李敏， 吳浪， 張開(kāi)碧. 求解旅行商問(wèn)題的幾種算法的比較研究[J]. 重慶郵電大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2008， 20（5）： 624626， 630.

（編輯趙勉）

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

基金項(xiàng)目： 遼寧省社會(huì)科學(xué)規(guī)劃基金（L21CGL006）

作者簡(jiǎn)介： 馬千里（1989—），河南襄城人，博士，研究方向?yàn)榻煌ㄟ\(yùn)輸系統(tǒng)優(yōu)化、冷鏈物流、港口規(guī)劃，（Email）qianlima@dlmu.edu.cn

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