期刊
COMPUTERS & OPERATIONS RESEARCH
卷 39, 期 12, 页码 3361-3375出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2012.04.021
关键词
Maritime transportation; Branch-price-and-cut; Pickup and delivery; Split loads
We present a branch-price-and-cut method to solve a maritime pickup and delivery problem with time windows and split loads. The fleet of ships is heterogeneous and fixed for the planning horizon, and no common depot exists. The cargoes picked up and delivered consist of both mandatory and optional cargoes, and each cargo may be split among several ships. The objective is to design a route for each ship that will maximize the total profit from transporting all the mandatory and a subset of the optional cargoes. To solve this problem we introduce a new path-flow formulation, which we solve by branch-price-and-cut. The subproblem is a new variant of the elementary shortest path problem with resource constraints, where a multi-dimensional knapsack problem is solved to compute optimal cargo quantities. Further, we present new valid inequalities for this problem, and adaptations of existing inequalities successfully used to solve related problems in the literature. Finally, the computational results show that for certain types of instances, our solution method outperforms existing methods proposed in the literature. (c) 2012 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据