王駿 浦新平 陳維斗

由于冷藏箱對溫度控制有特殊要求，集裝箱碼頭裝卸冷藏箱時需要安排工作人員進(jìn)入箱區(qū)實施插拔電輔助操作。就自動化集裝箱碼頭而言，為了確保冷藏箱區(qū)正常作業(yè)，工作人員必須在規(guī)定時間內(nèi)完成插拔電操作。本文以上海港洋山深水港區(qū)四期自動化集裝箱碼頭（以下簡稱“洋山四期碼頭”）為例，在考慮冷藏箱作業(yè)時間窗約束的條件下，結(jié)合旅行銷售員問題（travelling salesman problem，TSP）的特點(diǎn)，以工作人員行走路徑最短為目標(biāo)，建立自動化集裝箱碼頭冷藏箱區(qū)插拔電路徑規(guī)劃模型，并通過算例分析驗證模型的有效性。

1 研究背景

目前國內(nèi)學(xué)者對時間窗和路徑規(guī)劃問題已有較多研究，例如：楊燕霞等[1]針對帶時間窗的非滿載車輛調(diào)度問題建立數(shù)學(xué)模型，并設(shè)計啟發(fā)式算法，得到最優(yōu)結(jié)果；潘振貞[2]針對T公司物流配送存在的問題，以行駛路徑最短、運(yùn)輸成本最低、配送車輛最少和客戶滿意度最高為目標(biāo)，以車輛裝載能力、時間窗、車輛行駛距離等為約束條件，在考慮T公司物流配送特殊性的基礎(chǔ)上，建立帶時間窗的車輛路徑問題多目標(biāo)規(guī)劃模型，并運(yùn)用簡單的遺傳算法求解和分析實例；羅耀波[3]運(yùn)用非線性混合整數(shù)規(guī)劃理論，在考慮倉庫容量限制和路徑容量約束的條件下，針對客戶同時存在送貨和取貨需求以及客戶可配送時間范圍模糊的情況，建立基于模糊時間窗的同時送取貨的多倉庫、多車型選址路徑模型；何繼紅等[4]分析冷藏箱堆場作業(yè)的特殊性，并結(jié)合洋山四期碼頭的工程特點(diǎn)和裝卸工藝，提出該碼頭冷藏箱區(qū)布置方案。本文在上述研究成果的基礎(chǔ)上，研究自動化集裝箱碼頭冷藏箱區(qū)插拔電路徑規(guī)劃問題，以期進(jìn)一步提高自動化集裝箱碼頭作業(yè)效率。

2 問題描述

洋山四期碼頭共有6個冷藏箱區(qū)。為了方便研究，對冷藏箱區(qū)作如下假設(shè)：（1）每個冷藏箱區(qū)縱向可堆放8個大箱和2個小箱，橫向可堆放7個集裝箱；（2）集裝箱的寬度和高度均為2.5 m，長度為12 m，集裝箱間距忽略不計；（3）插拔電支架有4層，寬度為3 m，層高為2.5 m，與集裝箱間距為3 m，且上下支架的樓梯位于支架中部。

本文主要考慮相鄰冷藏箱區(qū)的插拔電任務(wù)，并要求工作人員在規(guī)定時間內(nèi)完成插拔電操作。假設(shè)共有n項插拔電任務(wù)，任務(wù)點(diǎn)i與任務(wù)點(diǎn)j之間的距離為dij且路徑唯一，工作人員必須從起點(diǎn)出發(fā)，每個任務(wù)點(diǎn)只去1次，直至完成所有任務(wù)。要求合理安排任務(wù)順序，使工作人員在規(guī)定時間內(nèi)完成任務(wù)，并使其行走路徑最短。

3 模型構(gòu)建

3.1 符號說明

3.2 自動化集裝箱碼頭冷藏箱區(qū)插拔電路徑規(guī)劃模型

式（2）和式（3）表示每個箱位均被且只能被經(jīng)過1次；式（4）表示流守恒，即工作人員到達(dá)任務(wù)點(diǎn)后必須離開；式（5）表示工作人員到達(dá)指定任務(wù)點(diǎn)的時間范圍；式（6）表示工作人員完成操作后離開任務(wù)點(diǎn)的時刻；式（7）表示上一項任務(wù)至下一項任務(wù)的時間約束；式（8）表示決策變量，取0或1。

4 算例分析

4.1 數(shù)據(jù)輸入

假設(shè)共有10項任務(wù)，每個任務(wù)點(diǎn)的具體位置及每項任務(wù)的最早開始時刻和最晚開始時刻見表1。工作人員的行走路徑唯一，行走速度為1 m/s，插拔電操作時間為20 s，起點(diǎn)在1號箱區(qū)入口處。若工作人員早于任務(wù)最早開始時刻到達(dá)任務(wù)點(diǎn)，則須等待至任務(wù)最早開始時刻；若工作人員晚于任務(wù)最晚開始時刻到達(dá)任務(wù)點(diǎn)，則賦予其100萬m的懲罰距離。

4.2 模型求解

4.2.1 按距離起點(diǎn)由近到遠(yuǎn)排序

工作人員優(yōu)先完成距離起點(diǎn)最近的任務(wù)，則任務(wù)排序及每項任務(wù)的實際開始時刻見表2。經(jīng)計算，工作人員行走總距離為3 001 380 m，并且第8項任務(wù)的實際開始時刻晚于最晚開始時刻，導(dǎo)致任務(wù)無法按時完成。由此可見，按距離起點(diǎn)由近到遠(yuǎn)排序無法得到最優(yōu)結(jié)果。

4.2.2 按開始時刻由先到后排序

工作人員優(yōu)先完成開始時刻最早的任務(wù)，則任務(wù)排序及每項任務(wù)的實際開始時刻見表3。經(jīng)計算，工作人員行走總距離為5 002 649 m，并且第4項任務(wù)的實際開始時刻晚于最晚開始時刻，導(dǎo)致任務(wù)無法按時完成。由此可見，按開始時刻由先到后排序無法得到最優(yōu)結(jié)果。

4.2.3 模型優(yōu)化計算

通過模型優(yōu)化計算，得到任務(wù)最優(yōu)排序及每項任務(wù)的實際開始時刻（見表4）。經(jīng)計算，工作人員行走總距離為1 399 m，并且每項任務(wù)均滿足時間約束。

5 結(jié)束語

本文以自動化集裝箱碼頭冷藏箱區(qū)插拔電路徑規(guī)劃問題為研究對象，在考慮冷藏箱作業(yè)時間窗約束的條件下，以工作人員行走距離最短為目標(biāo)設(shè)計模型并求解，從而得到自動化集裝箱碼頭冷藏箱區(qū)插拔電路徑規(guī)劃最優(yōu)方案。需要注意的是，雖然模型計算結(jié)果較為理想，但存在任務(wù)量太少、未考慮任務(wù)隨機(jī)性等問題，有待后期繼續(xù)研究。

參考文獻(xiàn)：

[1] 楊燕霞，伍岳慶，姚宇，等. 帶時間窗車輛調(diào)度問題的啟發(fā)式算法研究與應(yīng)用[J]. 計算機(jī)應(yīng)用，2013，33（S1）：59-61.

[2] 潘振貞. 基于時間窗的T公司配送路徑優(yōu)化研究[D]. 上海：華東理工大學(xué)，2017.

[3] 羅耀波. 基于模糊時間窗的同時送取貨選址路徑規(guī)劃模型研究[D]. 廣州：華南理工大學(xué)，2014.

[4] 何繼紅，姜橋，張曉龍. 自動化集裝箱碼頭冷藏箱箱區(qū)布置[J]. 水運(yùn)工程，2016（9）：52-55.

（編輯：張敏 收稿日期：2018-05-15）