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

鐘銘，張夢(mèng)迪

自動(dòng)化與智能化技術(shù)

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

鐘銘，張夢(mèng)迪

（大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，遼寧 大連 116026）

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

多拖輪基地；數(shù)據(jù)分析；線路調(diào)度；區(qū)域調(diào)度；重調(diào)度

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

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

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

1 問(wèn)題描述

本文對(duì)船舶位置、進(jìn)/離港需求、船長(zhǎng)、船舶類型等進(jìn)行分析，限制船舶最長(zhǎng)等待時(shí)間。將任務(wù)分配給對(duì)應(yīng)基地的拖輪，若對(duì)應(yīng)基地拖輪在時(shí)間限制內(nèi)不能滿足船舶的需求，則進(jìn)行重調(diào)度，將調(diào)度任務(wù)分配給其他基地拖輪。綜上，本文研究的調(diào)度問(wèn)題屬于在拖輪線路調(diào)度的基礎(chǔ)上進(jìn)行空間重調(diào)度，其目標(biāo)為總調(diào)度成本最小。

在港口實(shí)際生產(chǎn)作業(yè)過(guò)程中，按照船舶的船長(zhǎng)將其劃分為不同的類型。不同類型的船舶所需的拖輪馬力數(shù)和艘數(shù)有著不同的要求，表1表示了拖輪實(shí)際作業(yè)時(shí)與船舶的配比關(guān)系。船舶按照船長(zhǎng)分為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 拖輪與船舶的配比關(guān)系

Tab.1 Ratio relationship between tug and ship

2 模型建立

2.1 建立步驟

模型建立步驟如下：

1）獲取到港船舶的基本信息并對(duì)數(shù)據(jù)進(jìn)行處理，確定被服務(wù)船舶到港的時(shí)間分布和最大等待時(shí)間。

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

3）建立整數(shù)規(guī)劃模型，確定進(jìn)行重調(diào)度的拖輪及其移動(dòng)方式。

2.2 模型假設(shè)

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

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

3）拖輪移動(dòng)的原則為就近原則，避免對(duì)同一拖輪多次或往返移動(dòng)。

4）拖輪的速度是相同的，與拖輪服務(wù)的船舶噸位等級(jí)無(wú)關(guān)。

2.3 參數(shù)和變量設(shè)定

參數(shù)和變量設(shè)定如表2—4所示.

表2 集合定義

Tab.2 Definition of sets

表3 參數(shù)定義

Tab.3 Definition of parameters

表4 決策變量定義

Tab.4 Definition of decision variables

2.4 調(diào)度模型：

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

約束條件：

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

3 模型求解

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

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

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

圖1 模型求解流程

4 結(jié)果與分析

4.1 算例信息

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

基地的虛擬編號(hào)、容量限制編號(hào)以及具體配置情況如表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天津港船舶進(jìn)出港數(shù)據(jù)，將處理后的數(shù)據(jù)作為算例進(jìn)行研究。由2021年8月天津港船舶在港時(shí)間及在泊時(shí)間得出船舶平均等待時(shí)間為8.64 h，因此取=8.64。圖2為本文研究中涉及到的錨地和拖輪停泊基地位置示意。

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

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

圖3 泊位區(qū)位置

本文采用計(jì)算直角距離的方式來(lái)近似替代，取一分緯線距離等于1.86 km，一分經(jīng)線距離等于1.442 km進(jìn)行計(jì)算。

4.2 實(shí)驗(yàn)結(jié)果

將設(shè)計(jì)的模型用Matlab R20212b求解，得到方案：港輪17號(hào)在8:00時(shí)由基地2調(diào)度到基地3，港消拖20號(hào)在10:36時(shí)由基地1調(diào)度到基地2，港輪34號(hào)在15:12時(shí)由基地3調(diào)度到基地1，港輪6號(hào)在16:48時(shí)由基地4調(diào)度到基地2，重調(diào)度開(kāi)始情況如圖4所示。各拖輪工作時(shí)長(zhǎng)如表7所示。

圖4 重調(diào)度開(kāi)始情況示意圖

表7 拖輪工作時(shí)長(zhǎng)

Tab.7 Tug working hours

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

分析得到該結(jié)果的主要原因?yàn)楦劭谕陷嗁Y源有限，當(dāng)在港船舶達(dá)到一定數(shù)量后，拖輪使用頻率增加。若本基地中的拖輪無(wú)空閑，在港船舶須等待其完成上一作業(yè)任務(wù)后再進(jìn)行作業(yè)，此時(shí)使用其他停泊在基地中有空閑的拖輪來(lái)完成作業(yè)，則可減少船舶在港等待時(shí)間，且從空閑停泊基地到達(dá)作業(yè)位置的距離成本會(huì)低于本基地拖輪在上一工作地點(diǎn)到達(dá)作業(yè)位置的距離成本。因此在拖輪調(diào)度過(guò)程中采用動(dòng)態(tài)配置的方法可以有效減少拖輪作業(yè)成本，減少船舶在港等待時(shí)間，提高服務(wù)效率。

圖5 重調(diào)度前最優(yōu)解目標(biāo)值變化

圖6 重調(diào)度后最優(yōu)解目標(biāo)值變化

5 結(jié)語(yǔ)

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

[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] 鄭紅星, 徐海棟, 曹紅雷. 復(fù)式航道港口拖輪配置仿真優(yōu)化[J]. 重慶交通大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]. 大連: 大連海事大學(xué), 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] 徐奇. 港口拖輪調(diào)度優(yōu)化及其仿真研究[D]. 大連: 大連海事大學(xué), 2012.

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

[13] 王巍, 趙宏, 李強(qiáng). 面向多停泊基地的港口拖輪調(diào)度優(yōu)化研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 李伯棠, 王智利, 周海英, 等. 港口拖輪調(diào)度模糊規(guī)劃優(yōu)化模型及算法[J]. 計(jì)算機(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] 王妍妍. 地震災(zāi)害應(yīng)急物資多周期分配優(yōu)化模型研究[D]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 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è)組織的港口拖輪調(diào)度優(yōu)化[J]. 系統(tǒng)工程理論與實(shí)踐, 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

國(guó)家社會(huì)科學(xué)基金項(xiàng)目（22BGJ034）

責(zé)任編輯：曾鈺嬋