Large ports, such as Rotterdam, have several terminals which are spread out over a wide area. Each visiting vessel has cargo to pick up and deliver at several different terminals, and must be routed to visit each of them. The objective is to minimise the departure times, of the vessels, from the port, not seldom under precedence constraints and strict time windows. When one adds capacity constraints to the terminals, such that a terminal can only serve one vessel simultaneously, the problem becomes a generalisation of the m-machine routing open shop scheduling problem with time windows and precedence constraints for both vessels and terminals. The problem is strongly NP-hard, as it has the travelling salesman problem, as well as the m-machine open shop problem, as special cases. Approximation algorithms for the routing open shop problem without additional constraints, have previously been developed, but the problem with time windows and/or precedence constraints is, to our knowledge, not yet studied. We present the problem, discuss its structure and properties and present an ALNS algorithm for solving it. We then compare computational results for the methods on a set of instances, developed in cooperation with industry, with up to 30 vessels and 7 terminals. Lastly, we explore additional constraints, such as opening hours for the terminals.
|Publication status||Published - 2018|
|Event||EURO 2018 conference on Operational Research - Valencia, Spain|
Duration: 9 Jul 2018 → 11 Jul 2018
|Conference||EURO 2018 conference on Operational Research|
|Period||09/07/2018 → 11/07/2018|