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

Research output: Contribution to conferenceConference abstract for conference – Annual report year: 2018Researchpeer-review

Documents

View graph of relations

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

Download statistics

No data available

ID: 158911540