在海运网络中，枢纽港与喂给港之间的货物运输需要由支线船舶承担.支线船舶的路径规划不但要考虑如何使运输总成本最小，而且需要了解各个港口航道水深的限制，以便在潮汐涨退以及船舶装载量的影响下顺利地进出港.有别于经典的车辆路径规划问题的时间窗限制（VRPTW，vehicle routing problem with time windows），本研究提出的"潮汐时间窗"与船舶路径的调整相互牵制，使得问题的求解具有挑战性.本研究在VRPTW模型的基础上建立了带有非线性潮汐时间窗约束的支线船舶路径规划模型（FSRPTTW，feeder ship routing problem with tidal time window），使用Dantzig-Wolfe方法将问题分解为主问题和子问题，并设计了列生成算法进行求解.通过数值实验与灵敏度分析验证了算法的有效性以及乘潮出入港的经济性.
Abstract
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.
关键词
潮汐时间窗 /
支线船舶路径规划问题 /
列生成算法
{{custom_keyword}} /
Key words
tidal time-windows /
feeder ship routing problem (FSRP) /
column generation
{{custom_keyword}} /
中图分类号：
U692.3+1
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Zheng J, Meng Q, Sun Z. Liner hub-and-spoke shipping network design[J]. Transportation Research Part E, 2015, 75:32-48.
[2] Hemmati A, Hvattum L M, Fagerholt K, et al. Benchmark suite for industrial and tramp ship routing and scheduling problems[J]. INFOR:Information Systems and Operational Research, 2014, 52(1):28-38.
[3] Fukasawa R, He Q, Santos F, et al. A joint routing and speed optimization problem[J]. INFORMS Journal on Computing, 2016, 30(4):694-709.
[4] Yu S, Wang S, Zhen L. Quay crane scheduling problem with considering tidal impact and fuel consumption[J]. Flexible Services & Manufacturing Journal, 2017, 29:345-368.
[5] Rakke J G, Christiansen M, Fagerholt K, et al. The traveling salesman problem with draft limits[J]. Computers & Operations Research, 2012, 39(9):2161-2167.
[6] Arnesen M J, Gjestvang M, Wang X, et al. A traveling salesman problem with pickups and deliveries, time windows and draft limits:Case study from chemical shipping[J]. Computers & Operations Research, 2017, 77:20-31.
[7] Meena B L, Agrawal J D. Tidal level forecasting using ANN[J]. Procedia Engineering, 2015, 116:607-614.
[8] Pan B, Zhang Z, Lim A. Multi-trip time-dependent vehicle routing problem with time windows[J]. European Journal of Operational Research, 2020, 291:218-231.
[9] Tas D, Jabali O, Woensel T V. A vehicle routing problem with flexible time windows[J]. Computers & Operations Research, 2014, 52:39-54.
[10] Belhaiza S, Hansen P, Laporte G. A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows[J]. Computers & Operations Research, 2014, 52:269-281.
[11] Li J, Qin H, Baldacci R, et al. Branch-and-price-and-cut for the synchronized vehicle routing problem with split delivery, proportional service time and multiple time windows[J]. Transportation Research Part E:Logistics and Transportation Review, 2020, 140:101955.
[12] Wang Z, Sheu J B. Vehicle routing problem with drones[J]. Transportation Research Part B:Methodological, 2019, 122:350-364.
[13] 揭婉晨, 杨#
[27], 杨超. 多车型电动汽车车辆路径问题的分支定价算法研究[J]. 系统工程理论与实践, 2016, 36(7):1795-1805.Jie W C, Yang J, Yang C. Branch-and-price algorithm for heterogeneous electric vehicle routing problem[J]. Systems Engineering—Theory & Practice, 2016, 36(7):1795-1805.
[14] Pureza V, Morabito R, Reimann M. Vehicle routing with multiple deliverymen:Modeling and heuristic approaches for the VRPTW[J]. European Journal of Operational Research, 2012, 218(3):636-647.
[15] Martins S, Ostermeier M, Amorim P, et al. Product-oriented time window assignment for a multi-compartment vehicle routing problem[J]. European Journal of Operational Research, 2019:893-909.
[16] Azi N, Gendreau M, Potvin J Y. An adaptive large neighborhood search for a vehicle routing problem with multiple routes[J]. Computers & Operations Research, 2014, 41:167-173.
[17] Berghida M, Boukra A. EBBO:An enhanced biogeography-based optimization algorithm for a vehicle routing problem with heterogeneous fleet, mixed backhauls, and time windows[J]. The International Journal of Advanced Manufacturing Technology, 2015, 77(9-12):1711-1725.
[18] Sun Z, Zheng J. Finding potential hub locations for liner shipping[J]. Transportation Research Part B:Methodological, 2016, 93:750-761.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金（61304179，71831002）；教育部人文社会科学研究青年基金（19YJC630151）；大连市科技创新基金（2020JJ26GX023）；辽宁省自然科学基金（2020-HYLH-32）；辽宁省社会科学规划基金（L19BGL011）
{{custom_fund}}
PDF(873 KB)
