|
Article Excerpt
We consider the problem of scheduling the storage and retrieval of containers in the storage area of a container terminal. Some arcs in the underlying directed network must be visited; other arcs may be--but need not be--visited. We can, therefore, consider this problem to be a special case of the directed rural postman problem. We show that this problem can be reformulated as an asymmetric Steiner traveling salesman problem. This reformulation can be efficiently solved to optimality by a combination of optimal assignments in bipartite networks for parts of the problem and dynamic programming for the connections between those parts.
Subject classifications: transportation; freight/materials handling; facilities/equipment planning; scheduling. Area of review: Transportation.
History: Received February 2005; revisions received September 2006, February 2008; accepted March 2008. Published online in Articles in Advance March 11, 2009.
1. Introduction
The main purpose of a container terminal is to transfer containers from one mode of transportation to another. Especially seagoing vessels put a large strain on the terminals because they may have to load or unload up to 10,000 containers per visit. To deal with these large ships adequately, there is an ever-increasing pressure to improve the speed and efficiency of terminal operations. One of the activities at a container terminal is the temporary storage of containers at the stack, where containers wait for further transport.
A typical stack consists of a number of parallel rows where containers can be stored. Often container terminals have two sets of vehicles. One set of vehicles operates exclusively in the stack; the other set of vehicles is used for transporting containers between the stack and other areas. Containers can be delivered to and picked up from both sides of each row in the stack. For example, a container that arrives by sea and leaves at a later date by road is typically delivered to the stack on one side ("seaside") by a transport vehicle and picked up from the other side ("landside") by a truck. In this paper, we will focus on the sequencing of storage and retrieval requests within the stack for a single straddle carrier (a general-purpose vehicle for transporting and storing containers). The objective is to route the straddle carrier efficiently through a number of parallel rows to handle all requests.
Our problem is part of a more general class of problems, which consists of planning and scheduling for the transport of unit loads. Unit-load transport means that each load requires its own vehicle for transportation. The vehicle routing problem with unit loads (VRPUL) consists of two components: (1) assignment of transport requests to vehicles and (2) scheduling of the requests for each vehicle. Scheduling per vehicle should be, because of the unit-load principle, such that all assigned requests for the vehicle are executed sequentially. This means that the next load can be picked up for transport only after the previous load has been delivered to its destination. A vehicle's route therefore consists of an alternating sequence of loaded rides to execute transport requests and empty rides to make connections to the starting point of the next request. The VRPUL can be seen as a variant of the classical vehicle routing problem.
In the VRPUL, a directed network is required and there is a set of required arcs to traverse (each required arc is the path from a pickup location to the corresponding dropoff location). Typical examples include internal transport of pallets in a warehouse (De Koster et al. 2004), full truck load movements between cities (Arunapuram et al. 2003), collection of full skips and delivery of empty skips for waste collection, which is similar to the rollon rolloff problem (De Meulemeester et al. 1997, Bodin et al. 2000), and scheduling of automated storage and retrieval systems in warehouses (Van den Berg and Gademann 1999).
Compared to the existing literature on VRPUL, our problem and solution method are interesting for a number of reasons. First, in our setting of container terminals, an algorithm that solves the scheduling problem for a single vehicle also solves the complete VRPUL for most practical purposes. This is because of the fact that it is common in practice to dedicate straddle carriers to specific quay cranes working on a ship to unload and load specified parts of a ship. As a result, it is known exactly which storage and retrieval requests need to be handled by that specific straddle carrier (see Kim and Kim 1999a). Furthermore, the stack is often divided into a number of subareas, each of which is served by a single straddle carrier, which avoids time-consuming interference among straddle carriers (see Kim et al. 2003). The assignment of straddle carriers to quay cranes and the number of rows assigned to each straddle carrier are typically based on requirements concerning the speed of unloading and loading ships (10,000 containers in 24 hours for a large seagoing vessel).
The second point where our research differs from previous work is that our scheduling problem is relatively complex compared to some of the other instances. Consider, for example, the collection of full skips and delivery of empty skips for waste collection. Typically, all full skips must be delivered to a central facility and all empty skips must be retrieved from this location. Thus, all arcs have either their origin or their destination at the central facility. Furthermore, most customers typically receive an empty skip at the same time that a full skip is collected, which means that these requests do not have to be taken into account for the scheduling. In our problem, origins and destinations may be different for all arcs; i.e., the vehicle does not need to return to the same central facility after every retrieval and before every storage.
Third, our algorithm is capable of finding an optimal solution for the scheduling problem in a container stack in polynomial time. The general VRPUL is NP-hard. Therefore, solution methods mainly focus on enumerative procedures, such as branch and bound (Arunapuram et al. 2003, De Meulemeester et al. 1997) and/or heuristics (Bodin et al. 2000, De Koster et al. 2004, De Meulemeester et al. 1997). Also, the sub problem of scheduling a given list of requests for a vehicle is generally a hard problem. A few efficiently solvable cases for the scheduling problem are known. Kim and Kim (1999b) studied the problem of crane routing in container terminals, which has the same practical background as our problem. An optimal solution to their problem can be found efficiently. However, their assumptions of considering only retrievals and only one side of the stack limit the practical applicability. We present an algorithm that can deal with storage and retrieval requests at both sides of the stack as is common in practice. A solution method that allows for retrieval requests and storage requests on opposite sides is presented by Van den Berg and Gademann (1999) for an automated storage and retrieval system (AS/RS) in warehouses. However, this method works only for a single aisle and one input point for retrieval requests and one output point for storage requests. Contrary to Van den Berg and Gademann (1999), our approach can be used for multiple rows with both an input and an output point on each side of each row.
In the next section, we will show that our problem can be formulated as a special case of the rural postman problem (see, e.g., Lawler et al. 1985). The aim in the rural postman problem (RPP) is to find a shortest tour that traverses a specified subset of the edges in the network. A well known special case of the rural postman problem is the Chinese postman problem, for which the subnetwork of required edges is strongly connected. The Chinese postman problem (directed or undirected) is solvable in polynomial time (see, e.g., Ahuja et al. 1993), whereas the more general rural postman problem is known to be NP-hard (Lenstra and Rinnooy Kan 1976).
The rural postman formulation of our problem can subsequently be transformed into a Steiner traveling salesman problem, which provides a convenient structure to solve the problem efficiently to optimality. The Steiner traveling salesman problem (STSP) looks for a shortest tour such that a given subset of the vertices is visited at least once. The Steiner traveling salesman problem is solvable only in polynomial time for some situations (see, e.g., Cornuejols et al. 1985). An interesting example of a solvable case of the Steiner traveling salesman problem is the problem of routing order pickers in a warehouse (Ratliff and Rosenthal 1983). In this problem, a shortest tour has to be found to retrieve a number of products from specified locations in a warehouse with a number of parallel aisles (partly comparable with the rows in a container stack). However, this method is applicable only to undirected networks and does not incorporate storage requests.
We develop an algorithm that solves the scheduling problem of container storage and retrieval requests in multiple rows with an input and output point at each end of each row to optimality. The main body of the paper presents the base case algorithm, which solves the problem under a number of restrictions. Relaxations are given in the online supplement to this paper. In [section]2, we give a directed network representation of this sequencing problem, which conforms to the definition of the rural postman problem. Next, we show how to transform the rural postman formulation into a Steiner traveling salesman problem. We...
|
