Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 39, Issue 12, Pages 3361-3375Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2012.04.021
Keywords
Maritime transportation; Branch-price-and-cut; Pickup and delivery; Split loads
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available