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

    34 Downloads (Pure)

    Abstract

    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

    Conference

    ConferenceEURO 2018 conference on Operational Research
    CountrySpain
    CityValencia
    Period09/07/201811/07/2018

    Cite this

    Hellsten, E. O. (2018). An ALNS-search Algorithm for the Routing Open Shop Problem with Time Windows and Precedence Constraints. Abstract from EURO 2018 conference on Operational Research, Valencia, Spain.
    Hellsten, Erik Orm. / An ALNS-search Algorithm for the Routing Open Shop Problem with Time Windows and Precedence Constraints. Abstract from EURO 2018 conference on Operational Research, Valencia, Spain.
    @conference{f8ccda96c3fc4c39892f67bf852c3173,
    title = "An ALNS-search Algorithm for the Routing Open Shop Problem with Time Windows and Precedence Constraints",
    abstract = "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.",
    author = "Hellsten, {Erik Orm}",
    year = "2018",
    language = "English",
    note = "EURO 2018 conference on Operational Research, EURO 2018 ; Conference date: 09-07-2018 Through 11-07-2018",

    }

    Hellsten, EO 2018, 'An ALNS-search Algorithm for the Routing Open Shop Problem with Time Windows and Precedence Constraints' EURO 2018 conference on Operational Research, Valencia, Spain, 09/07/2018 - 11/07/2018, .

    An ALNS-search Algorithm for the Routing Open Shop Problem with Time Windows and Precedence Constraints. / Hellsten, Erik Orm.

    2018. Abstract from EURO 2018 conference on Operational Research, Valencia, Spain.

    Research output: Contribution to conferenceConference abstract for conferenceResearchpeer-review

    TY - ABST

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

    AU - Hellsten, Erik Orm

    PY - 2018

    Y1 - 2018

    N2 - 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.

    AB - 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.

    M3 - Conference abstract for conference

    ER -

    Hellsten EO. An ALNS-search Algorithm for the Routing Open Shop Problem with Time Windows and Precedence Constraints. 2018. Abstract from EURO 2018 conference on Operational Research, Valencia, Spain.