Tugboat scheduling for container ports

作     者：Wei, Xiaoyang Jia, Shuai Meng, Qiang Tan, Kok Choon 

作者机构：Natl Univ Singapore Dept Civil & Environm Engn Singapore 117576 Singapore Natl Univ Singapore Dept Ind Syst Engn & Management Singapore 117576 Singapore Shenzhen Univ Coll Management Inst Big Data Intelligent Management & Decis Shenzhen 518061 Peoples R China Natl Univ Singapore Inst Operat Res & Analyt Singapore 117602 Singapore Natl Univ Singapore Sch Business Dept Analyt & Operat Singapore 11924 Singapore 

出 版 物：《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》 (运输研究E部分：后勤学与运输评论)

年 卷 期：2020年第142卷

页      面：102071-102071页

核心收录：

学科分类：0201[经济学-理论经济学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0814[工学-土木工程] 0823[工学-交通运输工程] 

基　　金：Ministry of Education of Singapore [R-726-000-003-646] 

主　　题：Container port Tugboat scheduling Mixed-integer linear programming Valid inequalities Branch-and-cut algorithm 

摘      要：Container ports play an important role in global logistics and supply chains by providing container handling services for container ships. In a port, container ships usually need the assistance of tugboats in order to undergo berthing, shifting, and unberthing movements. Effective scheduling of the tugboats for serving the ships is thus of great importance for ensuring safe and efficient container ship movements in a port. However, research on tugboat scheduling is scarce in the literature. We contribute to the literature by studying a real-life tugboat scheduling problem (Tug-SP). We formulate the Tug-SP using a mixed-integer linear programming (MILP) model taking into consideration various practical constraints. In view of the specific problem structure, we further develop six families of valid inequalities to strengthen the MILP model. To efficiently solve the Tug-SP, we develop a tailored branch-and-cut algorithm by incorporating these valid inequalities into a standard branch-and-bound solution framework. We evaluate the computational performance of the proposed branch-and-cut algorithm using a set of test instances generated from real-life ship traffic data collected from the Port of Singapore. The computational results validate the effectiveness of the proposed valid inequalities, and show that the branch-and-cut algorithm can optimally solve instances of realistic sizes with a reasonable amount of computation time.