Liner shipping network design with deadlines.

*(English)*Zbl 1348.90139Summary: It is crucial for a liner shipping company to design its container shipping network. Given a set of port-to-port container shipment demands with delivery deadlines, the liner shipping company aims to design itineraries of portcalls, deploy ships on these itineraries and determine how to transport containers with the deployed ships in order to maximize its total profit. In this paper we first demonstrate NP-hardness of this problem and subsequently formulate it as a mixed-integer non-linear non-convex programming model. A column generation based heuristic method is proposed for solving this problem. Numerical experiments for container shipping on the Asia-Europe trade lane show that the proposed solution algorithm is efficient to find good quality solutions.

##### MSC:

90B06 | Transportation, logistics and supply chain management |

90B10 | Deterministic network models in operations research |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Software:

LINERLIB
PDF
BibTeX
XML
Cite

\textit{S. Wang} and \textit{Q. Meng}, Comput. Oper. Res. 41, 140--149 (2014; Zbl 1348.90139)

Full Text:
DOI

##### References:

[1] | Agarwal, R.; Ergun, O., Ship scheduling and network design for cargo routing in liner shipping, Transportation Science, 42, 2, 175-196, (2008) |

[2] | Alvarez, J. F., Joint routing and deployment of a fleet of container vessels, Maritime Economics & Logistics, 11, 2, 186-208, (2009) |

[3] | Amossen, R. R.; Pisinger, D., Multi-dimensional bin packing problems with guillotine constraints, Computers & Operations Research, 37, 11, 1999-2006, (2010) · Zbl 1188.90206 |

[4] | Brønmo, G.; Christiansen, M.; Fagerholt, K.; Nygreen, B., A multi-start local search heuristic for ship scheduling - a computational study, Computers & Operations Research, 34, 3, 900-917, (2007) · Zbl 1120.90031 |

[5] | Brouer, B., Alvarez, J.F., Plum, C., Pisinger, D., Sigurd, M., 2013. A base integer programming model and benchmark suite for linear shipping network design. Transportation Science, 10.1287/trsc.2013.0471, in press. |

[6] | Christiansen, M.; Fagerholt, K.; Ronen, D., Ship routing and scheduling: status and perspectives, Transportation Science, 38, 1, 1-18, (2004) |

[7] | Christiansen, M.; Fagerholt, K.; Nygreen, B.; Ronen, D., Maritime transportation, (Barnhart, C.; Laporte, G., Handbook in OR & MS, vol. 14, (2007), Elsevier), 189-284 |

[8] | Christiansen, M.; Fagerholt, K.; Flatberg, T.; Haugen, Ø.; Kloster, O.; Lund, E. H., Maritime inventory routing with multiple products: a case study from the cement industry, European Journal of Operational Research, 208, 1, 86-94, (2011) |

[9] | Christiansen, M.; Fagerholt, K.; Nygreen, B.; Ronen, D., Ship routing and scheduling in the new millennium, European Journal of Operational Research, 228, 3, 467-478, (2013) · Zbl 1317.90112 |

[10] | Desaulniers, G., Branch-and-price-and-cut for the split delivery vehicle routing problem with time windows, Operations Research, 58, 1, 179-192, (2010) · Zbl 1233.90065 |

[11] | Hvattum, L. M.; Fagerholt, K.; Armentano, V. A., Tank allocation problems in maritime bulk shipping, Computers & Operations Research, 36, 11, 3051-3060, (2009) · Zbl 1162.90501 |

[12] | Gelareh, S.; Nickel, S.; Pisinger, D., Liner shipping hub network design in a competitive environment, Transportation Research Part E, 46, 6, 991-1004, (2010) |

[13] | Korsvik, J. E.; Fagerholt, K.; Laporte, G., A large neighbourhood search heuristic for ship routing and scheduling with split loads, Computers & Operations Research, 38, 2, 474-483, (2011) · Zbl 1231.90093 |

[14] | Lübbecke, M. E.; Desrosiers, J., Selected topics in column generation, Operations Research, 53, 6, 1007-1023, (2005) · Zbl 1165.90578 |

[15] | Meng, Q., Wang, S., Andersson, H., Thun, K., 2013. Containership routing and scheduling in liner shipping: overview and future research directions. Transportation Science, 10.1287/trsc.2013.0461, in press |

[16] | Notteboom, T. E., The time factor in liner shipping services, Maritime Economics & Logistics, 8, 1, 19-39, (2006) |

[17] | Rana, K.; Vickson, R. G., A model and solution algorithm for optimal routing of a time-chartered containership, Transportation Science, 22, 2, 83-95, (1988) · Zbl 0642.90053 |

[18] | Rana, K.; Vickson, R. G., Routing container ships using Lagrangean relaxation and decomposition, Transportation Science, 25, 3, 201-214, (1991) · Zbl 0729.90984 |

[19] | Blander Reinhardt, L.; Pisinger, D., A branch and cut algorithm for the container shipping network design problem, Flexible Services and Manufacturing Journal, 24, 3, 349-374, (2012) |

[20] | Ronen, D., Cargo ships routing and scheduling: survey of models and problems, European Journal of Operational Research, 12, 2, 119-126, (1983) |

[21] | Ronen, D., Ship scheduling: the last decade, European Journal of Operational Research, 71, 3, 325-333, (1993) · Zbl 0800.90568 |

[22] | Shintani, K.; Imai, A.; Nishimura, E.; Papadimitriou, S., The container shipping network design problem with empty container repositioning, Transportation Research Part E, 43, 1, 39-59, (2007) |

[23] | Song, D.-P.; Dong, J.-X., Long-haul liner service route design with ship deployment and empty container repositioning, Transportation Research Part B, 55, 188-211, (2013) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.