# A method for solving ship routing problemswith inventory constraints

*Marielle Christiansen* and
*Bjorn Nygreen*

*Annals of Operations Research*, 1998, vol. 81, issue 0, 357-378

**Abstract:**
We present an optimisation-based solution approach for a real ship planning problem,which is a combination of a variant of the multi-vehicle pickup and delivery problemwith time windows (m-PDPTW), and a multi-inventory model. This problem involves thedesign of a set of minimum cost routes for a fleet of heterogeneous ships servicing a set ofproduction and consumption harbours with a single product (ammonia). The production andinventory information at each harbour, together with the ship capacities and the location ofthe harbours, determine the number of possible arrivals at each harbour during the planningperiod, the time windows for start of service and the load quantity intervals at each arrival.We call this problem the inventory pickup and delivery problem with time windows -IPDPTW. In the mathematical programming model, we duplicate some of the variables anduse a Dantzig - Wolfe decomposition approach. Then the IPDPTW decomposes into a sub-problemfor each harbour and each ship. By synchronising the solutions from both types ofsubproblems, we get extra constraints in the master problem as compared to the masterproblem for the m-PDPTW discussed in the literature. The LP-relaxation of the masterproblem is solved by column generation, where the columns represent ship routes or harbourvisit sequences. Finally, this iterative solution process is embedded in a branch-and-boundsearch to make the solution integer optimal. Our computational results indicate that theproposed method works for the real planning problem. Copyright Kluwer Academic Publishers 1998

**Date:** 1998

**References:** Add references at CitEc

**Citations:** View citations in EconPapers (24) Track citations by RSS feed

**Downloads:** (external link)

http://hdl.handle.net/10.1023/A:1018921527269 (text/html)

Access to full text is restricted to subscribers.

**Related works:**

This item may be available elsewhere in EconPapers: Search for items with the same title.

**Export reference:** BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text

**Persistent link:** https://EconPapers.repec.org/RePEc:spr:annopr:v:81:y:1998:i:0:p:357-378:10.1023/a:1018921527269

**Ordering information:** This journal article can be ordered from

http://www.springer.com/journal/10479

**DOI:** 10.1023/A:1018921527269

Access Statistics for this article

Annals of Operations Research is currently edited by *Endre Boros*

More articles in Annals of Operations Research from Springer

Bibliographic data for series maintained by Sonal Shukla ().