An ALNS-search Algorithm for the Routing Open Shop Problem with Time Windows and Precedence Constraints

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    65 Downloads (Pure)


    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.
    Original languageEnglish
    Publication date2018
    Publication statusPublished - 2018
    EventEURO 2018 conference on Operational Research - Valencia, Spain
    Duration: 9 Jul 201811 Jul 2018


    ConferenceEURO 2018 conference on Operational Research

    Fingerprint Dive into the research topics of 'An ALNS-search Algorithm for the Routing Open Shop Problem with Time Windows and Precedence Constraints'. Together they form a unique fingerprint.

    Cite this