带有潮汐时间窗的支线船舶路径规划问题研究  

Feeder ship routing problem with tidal time windows

作　　者：高远 孙卓 王奇[3] GAO Yuan;SUN Zhuo;WANG Qi(School of Maritime Economics and Management,Dalian Maritime University,Dalian 116026,China;College of Transportation Engineering,Dalian Maritime University,Dalian 116026,China;Collaboration Platform Program,Huawei Technologies Co.Ltd.,Suzhou 215000,China)

机构地区：[1]大连海事大学航运经济管理学院,大连116026 [2]大连海事大学交通运输工程学院,大连116026 [3]华为技术有限公司智能协作产品部,苏州215000

出　　处：《系统工程理论与实践》2022年第9期2496-2508,共13页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(61304179,71831002);教育部人文社会科学研究青年基金(19YJC630151);大连市科技创新基金(2020JJ26GX023);辽宁省自然科学基金(2020-HYLH-32);辽宁省社会科学规划基金(L19BGL011)。

摘　　要：在海运网络中,枢纽港与喂给港之间的货物运输需要由支线船舶承担.支线船舶的路径规划不但要考虑如何使运输总成本最小,而且需要了解各个港口航道水深的限制,以便在潮汐涨退以及船舶装载量的影响下顺利地进出港.有别于经典的车辆路径规划问题的时间窗限制(VRPTW,vehicle routing problem with time windows),本研究提出的“潮汐时间窗”与船舶路径的调整相互牵制,使得问题的求解具有挑战性.本研究在VRPTW模型的基础上建立了带有非线性潮汐时间窗约束的支线船舶路径规划模型(FSRPTTW,feeder ship routing problem with tidal time window),使用Dantzig-Wolfe方法将问题分解为主问题和子问题,并设计了列生成算法进行求解.通过数值实验与灵敏度分析验证了算法的有效性以及乘潮出入港的经济性.In shipping network,feeder ships are needed to fulfill the demand of cargo transportation between a hub-port and its feeder ports.The objective of feeder ship routing problem(FSRP) is to minimize the transportation cost,while the feasible time of entering and leaving a port is affected by tide and load,due to the limitation of the waterway depth.Different from classic VRPTW(vehicle routing problem with time windows),the tidal time windows of FSRP raised by this study changes by the route of the ship,bringing challenge to solve the problem.This paper studies an FSRP with nonlinear time window,and solved by column generation,after a model simplification by Dantzig-Wolfe Decomposition.Numerical experiment and sensitivity analysis proofed that the algorithm is effective as well as that consider tidal influence can effectively reduce the operation cost of fleet.

关 键 词：潮汐时间窗 支线船舶路径规划问题 列生成算法 

分 类 号：U692.31[交通运输工程—港口、海岸及近海工程]