An adaptive large neighborhood search heuristic for the planar storage location assignment problem: application to stowa
- PDF / 1,325,417 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 240 Views
An adaptive large neighborhood search heuristic for the planar storage location assignment problem: application to stowage planning for Roll-on Roll-off ships Jone R. Hansen1
· Kjetil Fagerholt1 · Magnus Stålhane1 · Jørgen G. Rakke2
Received: 26 September 2019 / Revised: 15 July 2020 / Accepted: 17 July 2020 © The Author(s) 2020
Abstract This paper considers a generalized version of the planar storage location problem arising in the stowage planning for Roll-on/Roll-off ships. A ship is set to sail along a predefined voyage where given cargoes are to be transported between different port pairs along the voyage. We aim at determining the optimal stowage plan for the vehicles stored on a deck of the ship so that the time spent moving vehicles to enable loading or unloading of other vehicles (shifting), is minimized. We propose a novel mixed integer programming model for the problem, considering both the stowage and shifting aspect of the problem. An adaptive large neighborhood search (ALNS) heuristic with several new destroy and repair operators is developed. We further show how the shifting cost can be effectively evaluated using Dijkstra’s algorithm by transforming the stowage plan into a network graph. The computational results show that the ALNS heuristic provides high quality solutions to realistic test instances. Keywords Maritime transportation · Packing · Stowage · Roll-on/Roll-off · RoRo
1 Introduction This paper considers a generalized version of the planar storage location assignment problem (PSLAP), which is a sub-class of the general storage location assignment problem (SLAP). The SLAP is to assign incoming products to storage locations in storage departments/zones in order to reduce material handling cost and improve space utilization (Gu et al. 2007). This problem arises in many industrial applications, e.g. warehouse management (Xiao and Zheng 2010), and container terminal operations
B
Jone R. Hansen [email protected]
1
Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, Trondheim, Norway
2
Wallenius Wilhelmsen Logistics, Lysaker, Norway
123
J. R. Hansen et al.
(Chen et al. 2003). In warehouse operations, a warehouse typically has one entry point where the incoming products arrive before they are transported to a storage zone and put in a shelf. When there is a demand for a product, it is retrieved from its storage location and delivered to an exit point. For a recent survey on SLAP we refer to Reyes et al. (2019). The PSLAP, first introduced by Park and Seo (2009), considers the storage of incoming objects on a planar, two-dimensional surface. When retrieving a given object from its location, it may be necessary to temporarily move other objects in order to retrieve it, as other objects may block every possible retrieval route. The objective is to minimize the number of such undesirable relocations. Park and Seo (2009) consider a version of the PSLAP arising in the assembly block stockyard operations at a shipyard, where the st
Data Loading...
