Constraint Programming and Local Search Heuristic: a Matheuristic Approach for Routing and Scheduling Feeder Vessels in
- PDF / 2,389,962 Bytes
- 33 Pages / 439.642 x 666.49 pts Page_size
- 96 Downloads / 211 Views
Constraint Programming and Local Search Heuristic: a Matheuristic Approach for Routing and Scheduling Feeder Vessels in Multi-terminal Ports David Sacramento1
· Christine Solnon2 · David Pisinger1
Received: 11 May 2020 / Accepted: 12 October 2020 / © Springer Nature Switzerland AG 2020
Abstract In the liner shipping business, shipping ports represent the main nodes in the maritime transportation network. These ports have a collection of terminals where container vessels can load and discharge containers. However, the logistics and planning of operations differ depending on the vessel size. Large container vessels visit a single terminal, whereas smaller container vessels, or feeder vessels, visit several terminals to transport all containers within the multiple terminals of the port. In this paper, we study the Port Scheduling Problem, the problem of scheduling the operations of feeder vessels in multi-terminal ports. The resulting problem can be identified as a version of the General Shop Scheduling Problem. We consider a Constraint Programming formulation of the problem, and we propose a matheuristic solution approach for solving large instances. The proposed matheuristic is a hybrid solution method that combines Constraint Programming with a local search heuristic. The solution approach benefits from the fast search capabilities of local search algorithms to explore the solution space using an Adaptive Large Neighbourhood Search heuristic. During the search, we further use the Constraint Programming model as an intensification technique, every time a new best-known solution is found. We conduct detailed computational experiments on the PortLib instances, showing that the incorporation of Constraint Programming within the heuristic search can result in significant benefits. The high instability in solution quality obtained by local search heuristics can be lowered by a simple combination of both methods. Keywords Feeder vessels · Maritime optimisation · Constraint programming · ALNS · Matheuristic David Sacramento
[email protected]
Extended author information available on the last page of the article.
32
Page 2 of 33
SN Operations Research Forum
(2020) 1:32
1 Introduction Maritime transportation is one of the cheapest and most efficient mode of transportation, carrying out more than 80% in volume of the international trade [45]. The main characteristic of seaborne transportation is its huge capacity, which allows to transport large volumes over long distances. This makes maritime transportation one of the best options for international trade. Within the maritime industry, we focus on the liner shipping industry. Here, container vessels transport all of their cargo in standard containers, which are commonly given in two standard sizes: twenty foot equivalent units (TEU) and forty foot equivalent units (FFE). This standardisation helps to add flexibility and versatility in the logistics operations, since containers can be used across different modes of transportation. Due to the steady increase in the contai
Data Loading...
