考慮多基地拖輪使用平衡性的重調度優(yōu)化

鐘銘，張夢迪

自動化與智能化技術

考慮多基地拖輪使用平衡性的重調度優(yōu)化

鐘銘，張夢迪

（大連海事大學 交通運輸工程學院，遼寧 大連 116026）

解決多停泊基地背景下拖輪與船舶之間供需不匹配、需求響應時效要求越來越高以及各基地拖輪使用不平衡等問題。本文考慮多拖輪基地的影響，在對拖輪線路調度的基礎上進行區(qū)域調度，采用對拖輪進行跨基地重調度的方法，以總調度成本最小為目標建立拖輪重調度模型。將天津港數據搜集分析作為本文案例對模型進行驗證分析，結果顯示，采用區(qū)域調度后成本低于單純的線路調度，且拖輪工作時間基尼系數值為0.2～0.3，處于比較公平的狀態(tài)。此模型有效地降低了拖輪調度成本和在港船舶等待時間，平衡了拖輪使用時間。

多拖輪基地；數據分析；線路調度；區(qū)域調度；重調度

如今拖輪基地通常采用離散式布局，將不同馬力的拖輪配置在指定的基地。但是在某基地服務的船舶進港時間較密集時，船舶等待時間會增加，若其他基地拖輪空閑，則會存在拖輪使用不均衡的問題，僅靠基地內的線路調度并不能很好地解決拖輪與船舶的供需關系。調度除線路調度外還有區(qū)域調度的方式，他們的區(qū)別在于線路調度是將各基地視作單獨個體，在其內部進行調度。區(qū)域調度則將多個基地視作一個整體，可進行基地間的聯(lián)合調度，這種調度方式可以平衡拖輪利用率，提高服務效率。因此，本研究通過基地間區(qū)域調度的方式，對快速響應船舶的需求，提高拖輪工作的靈活性，降低拖輪工作成本具有重要意義。

當前，針對拖輪的研究主要是拖輪資源整體的配置和調度問題。Wang等[1]、Abou等[2]研究了拖輪與船舶的匹配關系及船舶服務順序。Chen等[3]對拖輪活動特性進行了分析，其研究對拖輪配置、調度等有一定的指導意義。鄭紅星等[4]、Yu等[5]設計了拖輪配置方案仿真模型。劉春建[6]除了拖輪配置方案還設計了基地選址模型。但如今更多的則是針對拖輪調度的研究。Wu等[7]以作業(yè)總成本最小化為目標，利用了分支定界法來解決拖輪調度問題。Kang等[8]在拖輪調度的研究中對船舶等待時間進行了限制。Jia等[9]考慮了泊位計劃和可用拖輪的數量限制、船舶停泊和離港延誤時間，以及部分船舶無法被服務的情況。Zhang等[10]不僅考慮了船舶等待時間，還考慮了航道占用時間。但大部分的拖輪調度研究是針對一個拖輪基地的，而越來越多的港口已經采用了多基地的經營模式，Wei等[11]對多基地布局方式的經濟性進行了分析與肯定。徐奇等[12]最早提出了多基地拖輪調度的意義，以距離最小化為目標研究了2個停泊基地的拖輪調度問題。王巍等[13]設計的模型目標中考慮了最大完成時間和燃油成本。李伯棠等[14]在多基地拖輪調度中考慮了拖輪完成一項任務后可停靠任意停泊基地的情況。大部分的拖輪調度是針對單基地的研究，多基地的拖輪調度研究較少且仍存在一些研究缺陷，其他領域多站點調度的研究可以給予一些借鑒。如王妍妍等[15]在應急物資分配中提出了區(qū)域自救與跨區(qū)域協(xié)同救援的方式，兼顧了效率與公平。Lei等[16]對需求進行了預測，在需求產生之前對車輛進行區(qū)域調度。Boujemaa等[17]用兩階段隨機規(guī)劃解決了救護車區(qū)域調度問題。

本文根據現有文獻的不足，對多基地拖輪調度問題進行了研究。主要貢獻如下：針對多拖輪基地的特點考慮拖輪使用不平衡的因素，模型中引入基尼系數的限制；在燃油成本中考慮不同類型拖輪工作成本的不同，并以燃油成本最小化為規(guī)劃目標；考慮拖輪完成上一任務后可從上一任務完成地點直接到下一任務地點的情況；在線路調度的基礎上設計區(qū)域調度的方式，并收集天津港真實數據對模型進行驗證。

1 問題描述

本文對船舶位置、進/離港需求、船長、船舶類型等進行分析，限制船舶最長等待時間。將任務分配給對應基地的拖輪，若對應基地拖輪在時間限制內不能滿足船舶的需求，則進行重調度，將調度任務分配給其他基地拖輪。綜上，本文研究的調度問題屬于在拖輪線路調度的基礎上進行空間重調度，其目標為總調度成本最小。

在港口實際生產作業(yè)過程中，按照船舶的船長將其劃分為不同的類型。不同類型的船舶所需的拖輪馬力數和艘數有著不同的要求，表1表示了拖輪實際作業(yè)時與船舶的配比關系。船舶按照船長分為5類，分別代表100 m以下、[100，200)m、[200，250)m、[250，300)m和300 m及以上[18]。拖輪按照功率分為8種類型，所表示的功率分別為1 911、2 352、2 499、2 940、3 675、3 822、4 410和4 777.5 kW。

表1 拖輪與船舶的配比關系

Tab.1 Ratio relationship between tug and ship

2 模型建立

2.1 建立步驟

模型建立步驟如下：

1）獲取到港船舶的基本信息并對數據進行處理，確定被服務船舶到港的時間分布和最大等待時間。

2）根據船型劃分被服務船舶噸位等級，并確定所需的拖輪數量及馬力需求。

3）建立整數規(guī)劃模型，確定進行重調度的拖輪及其移動方式。

2.2 模型假設

1）考慮靠泊和離泊2個作業(yè)過程。

2）拖輪調度涉及的位置包括船舶作業(yè)泊位、錨地及拖輪停泊基地。

3）拖輪移動的原則為就近原則，避免對同一拖輪多次或往返移動。

4）拖輪的速度是相同的，與拖輪服務的船舶噸位等級無關。

2.3 參數和變量設定

參數和變量設定如表2—4所示.

表2 集合定義

Tab.2 Definition of sets

表3 參數定義

Tab.3 Definition of parameters

表4 決策變量定義

Tab.4 Definition of decision variables

2.4 調度模型：

目標函數：

約束條件：

式（1）為目標函數，表示拖輪的總調度成本最小。式（2）～（7）表示在時間能夠有足夠數量、足夠馬力的拖輪能夠到達作業(yè)位置為船舶服務。式（8）引入基尼系數的概念保證拖輪工作的平衡性；式（9）為重調度數量約束，表示經歷拖輪的調度后基地的拖輪數量變化，+1時期的拖輪數等于時期；式（10）表示時期在拖輪基地配置的型拖輪艘數；式（11）表示所有基地分配的拖輪數不能超過該類型拖輪的總數；式（12）表示每個時間段分配給各基地的拖輪數量應小于該時間段可用的拖輪數量；式（13）為各基地的容量約束。

3 模型求解

本文研究的多拖輪基地區(qū)域調度問題，屬于NP-Hard問題，找到精確解會十分困難，而近似優(yōu)化算法對此問題的求解具有一定的優(yōu)勢。遺傳算法的搜索方式靈活，具有結果穩(wěn)定，求解效率高的優(yōu)點。綜合考慮遺傳算法的特點，本文采用遺傳算法對模型求解。首先采用雙染色體的編碼方式對拖輪基地及船舶進出港任務編碼，將船舶進出港任務編碼分配給拖輪，根據分配的進出港任務編碼次序對拖輪調度。解碼方法是根據進出港任務編碼與基地編碼相對應再進行拖輪分配。以拖輪調度總成本最小為適應度函數。通過限制種群中個體的生成方式來滿足模型約束，根據個體的適應度大小，用輪盤賭的方法挑選個體，用單點交叉和小概率變異進行遺傳操作對模型進行求解。

求解流程是依據先到先服務和大船優(yōu)先原則選定被服務的船舶，并根據其靠泊區(qū)域確定拖輪基地；分析基地能夠在時間限制內能為船舶服務的拖輪，根據船舶對拖輪的馬力要求確定拖輪的類型和數量，按照燃油消耗成本最小確定具體拖輪，完成一艘在港船舶的服務。

針對被服務船舶：若其所需拖輪數量或等待時間限制不能滿足，則需針對拖輪繼續(xù)決策下一拖輪基地；若要求已滿足，則繼續(xù)依據服務時限和大船優(yōu)先原則選定下一艘被服務的船舶+1和拖輪，直到將所有被服務船舶均被服務，流程如圖1所示。

圖1 模型求解流程

4 結果與分析

4.1 算例信息

為了便于模型求解，將天津港拖輪分布情況，隨機分配在4個拖輪停泊基地，作為拖輪的初始位置，并給各拖輪分配虛擬編號。具體如表5所示。

基地的虛擬編號、容量限制編號以及具體配置情況如表6所示。

表5 天津港拖輪信息

Tab.5 Tug information in Tianjin Port

表6 天津港拖輪基地信息

Tab.6 Tug base information in Tianjin Port

提取2021年8月1日0:00至8月2日0:00天津港船舶進出港數據，將處理后的數據作為算例進行研究。由2021年8月天津港船舶在港時間及在泊時間得出船舶平均等待時間為8.64 h，因此取=8.64。圖2為本文研究中涉及到的錨地和拖輪停泊基地位置示意。

圖2 拖輪基地、錨地位置示意圖

利用海圖數據信息確定錨地、泊位及拖輪停泊基地的位置數據，取錨地邊界、各泊位及拖輪基地中心。為了便于問題的求解，將實際問題合理簡化，按照在港船舶實際靠泊的地理位置劃分區(qū)域，為船舶分配虛擬靠泊位置B1～B9，圖3為泊位區(qū)位置示意。

圖3 泊位區(qū)位置

本文采用計算直角距離的方式來近似替代，取一分緯線距離等于1.86 km，一分經線距離等于1.442 km進行計算。

4.2 實驗結果

將設計的模型用Matlab R20212b求解，得到方案：港輪17號在8:00時由基地2調度到基地3，港消拖20號在10:36時由基地1調度到基地2，港輪34號在15:12時由基地3調度到基地1，港輪6號在16:48時由基地4調度到基地2，重調度開始情況如圖4所示。各拖輪工作時長如表7所示。

圖4 重調度開始情況示意圖

表7 拖輪工作時長

Tab.7 Tug working hours

驗證計算其基尼系數等于0.281 962 33，其區(qū)間為0.2～0.3，從其結果上來看各拖輪工作時長比較公平。由實驗結果也可得知，采用動態(tài)配置優(yōu)化后的成本低于不采用動態(tài)配置優(yōu)化的成本，成本結果如圖5、圖6所示。模型中限制船舶等待時間閾值也使得在港船舶等待平均時間變短。

分析得到該結果的主要原因為港口拖輪資源有限，當在港船舶達到一定數量后，拖輪使用頻率增加。若本基地中的拖輪無空閑，在港船舶須等待其完成上一作業(yè)任務后再進行作業(yè)，此時使用其他停泊在基地中有空閑的拖輪來完成作業(yè)，則可減少船舶在港等待時間，且從空閑停泊基地到達作業(yè)位置的距離成本會低于本基地拖輪在上一工作地點到達作業(yè)位置的距離成本。因此在拖輪調度過程中采用動態(tài)配置的方法可以有效減少拖輪作業(yè)成本，減少船舶在港等待時間，提高服務效率。

圖5 重調度前最優(yōu)解目標值變化

圖6 重調度后最優(yōu)解目標值變化

5 結語

本文構建了拖輪重調度模型，用遺傳算法進行求解，選取了天津港水域信息對模型進行實例驗證，結果顯示此模型有效降低了拖輪調度成本及在港船舶等待時間。主要貢獻體現在考慮了各基地拖輪使用不平衡的問題，在拖輪線路調度的基礎上進行了區(qū)域調度，通過這種方式減少了船舶的等待時間，對拖輪使用不平衡的問題起到了一定的改善作用；從人性化角度考慮也能夠平衡引航員之間的工作時長，縮小收入差距。

[1] WANG Su, ZHU Min, KAKU I, et al. An Improved Discrete PSO for Tugboat Assignment Problem under a Hybrid Scheduling Rule in Container Terminal[J]. Mathematical Problems in Engineering, 2014, 22: 1-10.

[2] ABOU K O, DIABAT A, OZBAY K. Vessel Scheduling under Different Tugboat Allocation Policies[J]. Computers & Industrial Engineering, 2023: 108902.

[3] CHEN Shu-kai, WANG Feng, WEI Xiao-yang, et al. Analysis of Tugboat Activities Using AIS Data for the Tianjin Port[J]. Transportation Research Record Journal of the Transportation Research Board, 2020, 2674(5): 498-509.

[4] 鄭紅星, 徐海棟, 曹紅雷. 復式航道港口拖輪配置仿真優(yōu)化[J]. 重慶交通大學學報(自然科學版), 2017, 36(8): 102-109.

ZHENG Hong-xing, XU Hai-dong, CAO Hong-lei. Simulation Optimization of Compound Channel Port Tugboat Configuration[J]. Journal of Chongqing Jiaotong University (Natural Sciences), 2017, 36(8): 102-109.

[5] YU Wen-hui. Heuristic Algorithm for Simulation and Optimization System of Port Tugboats Allocation[C]// International Conference on Internet Computing & Information Services, IEEE, 2011.

[6] 劉春建. 大連港拖輪停泊基地選址及配置優(yōu)化研究[D]. 大連: 大連海事大學, 2018.

LIU Chun-jian. Study on the Location and Allocation Optimization of Dalian Port Tugboat Berth Base[D]. Dalian: Dalian Maritime University, 2018.

[7] WU Ling-xiao, JIA Shuai, WANG Shuai-an. Pilotage Planning in Seaports[J]. European Journal of Operational Research, 2020, 287(1) : 90-105.

[8] KANG Liu-jiang, MENG Qiang, TAN K C. Tugboat Scheduling under Ship Arrival and Tugging Process Time Uncertainty[J]. Transportation Research Part E Logistics and Transportation Review, 2020, 144(3): 102125.

[9] JIA Shuai, LI Shu-qin, LIN Xu-dong, et al. Scheduling Tugboats in a Seaport[J]. Transportation science, 2021(6): 55.

[10] ZHANG Xin-yu, LI Rui-jie, CHEN Xiang, et al. Multi-Object-Based Vessel Traffic Scheduling Optimisation in a Compound Waterway of a Large Harbour[J]. Journal of Navigation, 2018, 72(3): 1-19.

[11] WEI Xiao-yang, MENG Qiang, LIM A, et al. Dynamic Tugboat Scheduling for Container Ports[J]. Maritime Policy & Management, 2021, 50(4): 1-23.

[12] 徐奇. 港口拖輪調度優(yōu)化及其仿真研究[D]. 大連: 大連海事大學, 2012.

XU Qi. Optimization of Port Tugboat Scheduling and Its Simulation Research[D]. Dalian: Dalian Maritime University, 2012.

[13] 王巍, 趙宏, 李強. 面向多停泊基地的港口拖輪調度優(yōu)化研究[J]. 計算機工程與應用, 2013, 49(13): 8-12.

WANG Wei, ZHAO Hong, LI Qiang. Multi-Objectives Optimization for Port Tugboat Scheduling Considering Multi-Anchorage Bases[J]. Computer Engineering and Applications, 2013, 49(13): 8-12.

[14] 李伯棠, 王智利, 周海英, 等. 港口拖輪調度模糊規(guī)劃優(yōu)化模型及算法[J]. 計算機集成制造系統(tǒng), 2021, 27(5): 1518-1530.

LI Bo-tang, WANG Zhi-li, ZHOU Hai-ying, et al. Fuzzy Programming Model and Algorithm of Port Tugboat Scheduling[J]. Computer Integrated Manufacturing Systems, 2021, 27(5): 1518-1530.

[15] 王妍妍. 地震災害應急物資多周期分配優(yōu)化模型研究[D]. 哈爾濱: 哈爾濱工業(yè)大學, 2019.

WANG Yan-yan. Study on Multi-Period Allocation Optimization Model of Emergency Materials for Earthquake Disaster[D]. Harbin: Harbin Institute of Technology, 2019.

[16] LEI Zeng-xiang, QIAN Xin-wu, UKKUSURI S. Efficient Proactive Vehicle Relocation for On-Demand Mobility Service with Recurrent Neural Networks[J]. Transportation Research Part C Emerging Technologies, 2020, 117(10): 1-17

[17] BOUJEMAA R, JEBALI A, SONDES H, et al. Multi-Period Stochastic Programming Models for Two- Tiered Emergency Medical Service System[J]. Computers & Operations Research, 2020, 123: 104974.

[18] 徐奇, 邵乾虔, 靳志宏. 基于混合流水作業(yè)組織的港口拖輪調度優(yōu)化[J]. 系統(tǒng)工程理論與實踐, 2014, 34(2): 485-493.

XU Qi, SHAO Qian-qian, JIN Zhi-hong. Optimization on Tugboat Operation Scheduling Based Upon the Hybrid Flow Shop Arrangement[J]. Systems Engineering-Theory & Practice, 2014, 34(2): 485-493.

Rescheduling Optimization Considering the Use Balance of Multi-base Tugs

ZHONG Ming, ZHANG Meng-di

(College of Transportation Engineering, Dalian Maritime University, Liaoning Dalian 116026, China)

The work aims to solve the problems of mismatch between supply and demand of tugs and ships, increasing demand response timeliness requirements, and unbalanced use of tugs in various bases. Considering the impact of multiple tug bases, regional scheduling was carried out on the basis of tug line scheduling, and a tug rescheduling model was established with the goal of minimizing the total scheduling cost by adopting the method of cross-base rescheduling. With the data collected and analyzed from Tianjin Port as the case, the model was verified and the results showed that the cost after regional scheduling was lower than that of simple line scheduling, and the Gini coefficient of tug working time was 0.2 ～ 0.3, which was in a relatively fair state. The model effectively reduces the cost of tug scheduling and the waiting time of ships in port, and balances the use time of tugs.

multi tug base; data analysis; line scheduling; regional scheduling; rescheduling

TP391

A

1001-3563(2023)19-0158-07

10.19554/j.cnki.1001-3563.2023.19.020

2023-01-14

國家社會科學基金項目（22BGJ034）

責任編輯：曾鈺嬋