An adaptive large neighborhood search heuristic for the multi-port continuous berth allocation problem

• URL: http://arxiv.org/abs/2302.02356v1
• Date: Sun, 5 Feb 2023 10:29:09 GMT
• Title: An adaptive large neighborhood search heuristic for the multi-port continuous berth allocation problem
• Authors: Bernardo Martin-Iradi, Dario Pacino, Stefan Ropke
• Abstract summary: We study a problem that integrates the vessel scheduling problem with the berth allocation into a collaborative problem denoted as the multi-port continuous berth allocation problem (MCBAP) This problem optimize the berth allocation of a set of ships simultaneously in multiple ports while also considering the sailing speed of ships between ports. We present a mixed-integer problem formulation for the MCBAP and introduce an large neighborhood search (ALNS) algorithm enhanced with a local search procedure to solve it.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study a problem that integrates the vessel scheduling problem with the berth allocation into a collaborative problem denoted as the multi-port continuous berth allocation problem (MCBAP). This problem optimizes the berth allocation of a set of ships simultaneously in multiple ports while also considering the sailing speed of ships between ports. Due to the highly combinatorial character of the problem, exact methods struggle to scale to large-size instances, which points to exploring heuristic methods. We present a mixed-integer problem formulation for the MCBAP and introduce an adaptive large neighborhood search (ALNS) algorithm enhanced with a local search procedure to solve it. The computational results highlight the method's suitability for larger instances by providing high-quality solutions in short computational times. Practical insights indicate that the carriers' and terminal operators' operational costs are impacted in different ways by fuel prices, external ships at port, and the modeling of a continuous quay.

Related papers

• Learning to Solve the Min-Max Mixed-Shelves Picker-Routing Problem via Hierarchical and Parallel Decoding [0.3867363075280544]
  The Mixed-Shelves Picker Routing Problem (MSPRP) is a fundamental challenge in logistics, where pickers must navigate a mixed-shelves environment to retrieve SKUs efficiently. We propose a novel hierarchical and parallel decoding approach for solving the min-max variant of the MSPRP via multi-agent reinforcement learning. Experiments show state-of-the-art performance in both solution quality and inference speed, particularly for large-scale and out-of-distribution instances.
  arXiv  Detail & Related papers  (2025-02-14T15:42:30Z)
• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems. We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• Container pre-marshalling problem minimizing CV@R under uncertainty of ship arrival times [2.9061423802698565]
  The container pre-marshalling problem involves relocating containers in the storage area so that they can be efficiently loaded onto ships without reshuffles. We derive a mixed-integer linear optimization model to find an optimal container layout. We devise an exact algorithm based on the cutting-plane method to handle large-scale problems.
  arXiv  Detail & Related papers  (2024-05-27T18:19:09Z)
• A reinforcement learning guided hybrid evolutionary algorithm for the latency location routing problem [14.9829752183927]
  The latency location routing problem integrates the facility location problem and the cumulative capacitated vehicle routing problem. This problem involves making simultaneous decisions about depot locations and vehicle routes to serve customers. We propose a reinforcement learning guided hybrid evolutionary algorithm following the framework of the memetic algorithm.
  arXiv  Detail & Related papers  (2024-03-21T13:54:03Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts. We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances. We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
  arXiv  Detail & Related papers  (2023-04-28T07:09:23Z)
• Scalable Batch Acquisition for Deep Bayesian Active Learning [70.68403899432198]
  In deep active learning, it is important to choose multiple examples to markup at each step. Existing solutions to this problem, such as BatchBALD, have significant limitations in selecting a large number of examples. We present the Large BatchBALD algorithm, which aims to achieve comparable quality while being more computationally efficient.
  arXiv  Detail & Related papers  (2023-01-13T11:45:17Z)
• Reinforcement learning for multi-item retrieval in the puzzle-based storage system [0.694936386455667]
  This work develops a deep reinforcement learning algorithm to solve the multi-item retrieval problem in the puzzle-based storage system. Extensive numerical experiments demonstrate that the reinforcement learning approach can yield high-quality solutions. A conversion algorithm and a decomposition framework are proposed to handle simultaneous movement and large-scale instances.
  arXiv  Detail & Related papers  (2022-02-05T12:39:21Z)
• Multi-Agent Path Planning Using Deep Reinforcement Learning [0.0]
  In this paper a deep reinforcement based multi-agent path planning approach is introduced. The experiments are realized in a simulation environment and in this environment different multi-agent path planning problems are produced. The produced problems are actually similar to a vehicle routing problem and they are solved using multi-agent deep reinforcement learning.
  arXiv  Detail & Related papers  (2021-10-04T13:56:23Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications. There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints. We show that PDD-SSCA can achieve superior performance over existing solutions.
  arXiv  Detail & Related papers  (2021-05-05T03:36:00Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.