J Shanghai Jiaotong Univ Sci

Journal of Shanghai Jiaotong University(Science) >

2025 , Vol. 30 >Issue 6: 1276 - 1288

DOI: https://doi.org/10.1007/s12204-023-2657-0

Transportation Systems

Tugboat Scheduling Problem Considering Time Windows and Flexible Returning Way to Base

Expand
  • 1. School of Transportation Engineering, Dalian Maritime University, Dalian 116026, Liaoning, China; 2. School of Information Science and Electrical Engineering, Shandong Jiaotong University, Jinan 250357, China

Received date: 2022-10-21

  Accepted date: 2023-01-16

  Online published: 2023-10-24

Fold

Abstract

In ports, inbound and outbound ships usually need tugboats to provide berthing and unberthing services. The decision-making problem on tugboat scheduling is important because it involves not only ships’ turnaround time at port but also tugboat operation costs. Encouraged by the problem faced by the tugboat operator, we formulate a mixed-integer programming model for tugboat scheduling problem with several practical constraints considered, such as dynamic arrival and departure of ships, qualification of tugboats, synchronization, and a flexible returning way to base to minimize the tugboat operation costs generated within the planning period. The model is inspired by genetic algorithm framework with three-dimensional coding. Effectiveness of our model and proposed solution method are testified and validated through experiments and computational results. This research helps to provide a scientific scheduling method and some insights for managers.

Cite this article

ZHONG Ming, WU Ying, WU Chunli, WANG Fang . Tugboat Scheduling Problem Considering Time Windows and Flexible Returning Way to Base[J]. Journal of Shanghai Jiaotong University(Science), 2025 , 30(6) : 1276 -1288 . DOI: 10.1007/s12204-023-2657-0

References

[1] LIU Z X, WANG S. The computer simulation study of port tugboat operation [J]. Journal of System Simulation, 2004, 16(1): 45-47 (in Chinese).

[2] LIU Z X. Hybrid evolutionary strategy optimization for port tugboat operation scheduling [C]//2009 Third International Symposium on Intelligent Information Technology Application. Nanchang: IEEE, 2009: 511-515.

[3] DONG L C, XU Z Q, MI W J. The dynamic tugboat schedule based on particle swarm algorithm combined with genetic operators [J]. Mathematics in Practice and Theory, 2012, 42(6): 122-133 (in Chinese).

[4] WANG W, ZHAO H, LI Q. Multi-objectives optimization for port tugboat scheduling considering multi-anchorage bases [J]. Computer Engineering and Applications, 2013,49(13):8-12 (in Chinese).

[5] WANG S, ZHU M, 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, 2014: 1-10.

[6] XU Q. Research on port tugboat scheduling optimization and  simulation [D]. Dalian: Dalian Maritime University, 2012 (in Chinese).

[7] XU Q, SHAO Q Q, JIN Z H. Optimization on tugport operation scheduling based upon the hybrid flow shop arrangement [J]. Systems Engineering: Theory & Practice, 2014, 34(2):485-493 (in Chinese).

[8] XU Q, BIAN Z, CHEN Y, et al. Scheduling optimization of port tugboat operation considering multi-anchorage [J]. Journal of Shanghai Jiao Tong University, 2014, 48(1): 132-139 (in Chinese).

[9] LI B T, WANG Z L, ZHOU H Y, et al. Fuzzy programming model and algorithm of port tugboat scheduling [J]. Computer Integrated Manufacturing Systems, 2021, 27(5): 1518-1530 (in Chinese).

[10] JIA S A, WU L X, MENG Q A. Joint scheduling of vessel traffic and pilots in seaport waters [J]. Transportation Science, 2020, 54(6): 1495-1515.

[11] WEI X Y, JIA S A, MENG Q A, et al. Tugboat scheduling for container ports [J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 142: 102071.

[12] CHANG D F, HU X N, BIAN Z C. A research on port tug dynamic scheduling model and algorithm [J]. Advanced Materials Research, 2012, 524/525/526/527: 832-835.

[13] ZHEN L, WANG K, WANG S A, et al. Tug scheduling for hinterland barge transport: A branch-and-price approach [J]. European Journal of Operational Research, 2018, 265(1): 119-132.

[14] CHEN S K, WANG F, WEI X Y, 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.

[15] DREXL M. Synchronization in vehicle routing: A survey of VRPs with multiple synchronization constraints [J]. Transportation Science, 2012, 46(3): 297-316.

[16] DOHN A, RASMUSSEN M S, LARSEN J. The vehicle routing problem with time windows and temporal dependencies [J]. Networks, 2011, 58(4): 273-289.

[17] EVEBORN P, FLISBERG P, RÖNNQVIST M. Laps Care: An operational system for staff planning of home care [J]. European Journal of Operational Research, 2006, 171(3): 962-976.

[18] BREDSTRÖM D, RÖNNQVIST M. Combined vehicle routing and scheduling with temporal precedence and synchronization constraints [J]. European Journal of Operational Research, 2008, 191(1): 19-31.

[19] LIU R, TAO Y Y, XIE X L. An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits [J]. Computers & Operations Research, 2019, 101: 250-262.

[20] DECERLE J, GRUNDER O, HAJJAM EL HASSANI A, et al. A memetic algorithm for multi-objective optimization of the home health care problem [J]. Swarm and Evolutionary Computation, 2019, 44: 712-727.

[21] TOHIDIFARD M, TAVAKKOLI-MOGHADDAM R, NAVAZI F, et al. A multi-depot home care routing problem with time windows and fuzzy demands solving by particle swarm optimization and genetic algorithm [J]. IFAC-PapersOnLine, 2018, 51(11): 358-363.

Options
Outlines

/

〈 〉