The Maritime Pickup and Delivery Problem with Time Windows and Split Loads

The purpose of this paper is to present an exact solution method for an important planning problem faced by many shipping companies dealing with transportation of bulk cargoes. A bulk shipping company usually has a set of contract cargoes that it is committed to carry and will try to derive additional revenue from optional spot cargoes. Each cargo, either it is a contract or spot cargo, consists of a given quantity to be picked up in a given loading port and delivered in a given unloading port within specified time windows. The shipping company controls a fixed fleet for the purpose of transporting the cargoes. In most of the literature on ship routing and scheduling problems, a cargo cannot be transported by more than one ship. By introducing split loads, this restriction is removed and each cargo can be transported by several ships. The resulting planning problem can be denoted as a maritime pickup and delivery problem with time windows and split loads (PDPTWSL). We present an arc flow formulation of the PDPTWSL. We also suggest a solution method based on a priori generation of single ship schedules and two alternative path flow models that deal with the selection of ship schedules and assignment of cargo quantities to the schedules. Computational results show that the solution method can provide optimal solutions to small realistic planning instances. We also believe this paper provides an important starting point for research on other exact solution methods for the maritime PDPTWSL.