Routing and scheduling in liner shipping with multi-start local search heuristics

The continuous growth in international container trafic volumes makes it ever more important for carriers to optimize their service network. In this thesis, we present a multi-start local search algorithm for solving the routing and scheduling problem in liner shipping. The objective is to find a service network of routes, given the demand between ports, that maximizes profit. The algorithm consists of a randomized initialization phase that generates initial networks, and a local search phase that tries to improve the solution using local search operators. For each phase we present different implementations, such that several algorithm configurations are obtained, representing different multi-start local search heuristics. For the first phase, we propose the quantity sort insertion heuristic, and the profit-driven sort insertion heuristic. For the second phase, we propose three local search operators. The route-length operator removes ports from round trips that incur more costs than revenue, and tries to allocate unassigned cargoes by adding ports to round trips. The port-exchange operator relocates ports within a route or between routes in an attempt to improve solutions. The transhipment operator introduces the use of hubs and transhipment to save costs and allocate the remaining cargoes. The different configurations are subjected to an extensive benchmark study in order to analyze their performance. To that end, we also propose a data set that is based on the actual Asia-Europe network of Maersk Line. Results indicate that running the route-length operator, followed by the port-exchange operator, on average yields the best networks. The sorting method turns out to have negligible in uence on the final result. We achieve a gap to the upper bound of less than 5.5%. When we use a heterogeneous fleet, the gap is less than 2.6%.