یک روش برنامه ریزی پویا تقریبی برای مشکل تخصیص کانتینر خالی

The objective of this study is to demonstrate the successful application of an approximate dynamic programming approach in deriving effective operational strategies for the relocation of empty containers in the containerized sea-cargo industry. A dynamic stochastic model for a simple two-ports two-voyages (TPTV) system is proposed first to demonstrate the effectiveness of the approximate optimal solution obtained through a simulation based approach known as the temporal difference (TD) learning for average cost minimization. An exact optimal solution can be obtained for this simple TPTV model. Approximate optimal results from the TPTV model utilizing a linear approximation architecture under the TD framework can then be compared to this exact solution. The results were found comparable and showed promising improvements over an existing commonly used heuristics. The modeling and solution approach can be extended to a realistic multiple-ports multiple-voyages (MPMV) system. Some results for the MPMV case are shown.

The rapid growth of containerized trade in the sea-cargo industry has effectively removed significant costs and inefficiencies in the movement of materials for shippers. However, in the area of containerized shipping industry, the problem of empty equipment relocation persists, primarily due to the nature of the equipments used for containerized shipping. Such planning problems have been referred to as dynamic container allocation (DCA) problems (Dejax and Crainic, 1987). DCA problems are further aggravated by the highly imbalanced nature of global trade. The problems of low margins and utilization prevalent in this trade and the deregulation brought about by Ocean Shipping Reform Act (OSRA) of 1998 have further underscored the need for the development of more efficient forms of empty container management. Extensive literature could be found for the generic empty equipment reallocation problem for different equipments ranging from sea-freight containers to rail-cars. The empty equipment balancing problem related to the railroad industry was identified as early as the mid 1950s (Feeney, 1957). A comprehensive survey of these models was provided by Assad (1987). Crainic and Laporte (1997) provided a comprehensive review of general freight planning models. For the DCA problem per se, several deterministic and stochastic models attempting to capture the special characteristics of container shipping have been proposed. Fig. 1 summarizes some of the existing literature related to the DCA problem under a two pronged classification along the methodological (deterministic, stochastic and simulation models) and application (in terms of strategic, tactical and operational planning horizons) axes. The classification of existing literature attempts to place the different methodological developments in a comprehensive planning perspective within a DCA planning system. An outline of a typical DCA planning system which describes the different decision problems encountered in different planning horizons is shown in Fig. 2. A brief description of the various research along the application (or planning horizon) axis is given here. Full-size image (27 K) Fig. 1. Classification of DCA research. Figure options Full-size image (16 K) Fig. 2. Outline of DCA planning systems. Figure options Deterministic models of empty container balancing have been proposed as early as 1970s (Ermol’ev et al., 1976). The key advantage that deterministic models offer is analytical tractability in consideration of practical complexities. Crainic et al. (1993) proposed several deterministic formulations which not only took into account the possibility of leasing in and off, but also considered the multi-commodity nature of different container types. Gao (1994) proposed a two-stage deterministic model to consider cost minimization in making the dual decisions of container fleet sizing and reallocation. The model considers both the long to mid-term capital investment in the purchase of containers and the daily operational inventory control decisions of empty container leasing, allocation and storage. Shen and Khoong (1995) discussed a deterministic network model for the DCA problem which took leasing decisions and leasing costs per period into explicit consideration. His approach also took into account the regional hierarchical decision making structure of some container shipping companies. Gendron and Crainic, 1995 and Bourbeau et al., 2000 also proposed empty vehicle management models that do not specifically take into account certain extraneous characteristics of the DCA problem in the container shipping industry. Gendron and Crainic (1995) addressed the problem of multi-commodity location problem with balancing requirements and presented a deterministic minimum cost network flow model which is solved by a novel branch and bound algorithm. This solution method was further improved by Bourbeau et al. (2000) by employing a parallelization strategy that can help to speed up the computations. Although deterministic models have advantages of its own, they do not take into account the important stochastic characteristics of demand or supply. These stochastic characteristics usually contain valuable information that can lead to highly non-optimal solutions when ignored. Beaujon and Turnquist (1991) presented a model which involves the optimization of the dual decisions of fleet sizing and empty and loaded vehicle allocations. Crainic et al. (1993) also proposed several dynamic deterministic and stochastic models specifically to address the DCA problem. Cheung and Chen (1998) also proposed a two-stage dynamic stochastic network flow formulation for the DCA problem that attempts to address some of its operational planning issues. A dynamic stochastic network model together with several stochastic quasi-gradient (SQG) methods were proposed and their solution effectiveness were compared. Powell and Carvalho (1998) proposed a new dynamic model for the optimization of the flow of flatcars that considers the broad range of complex constraints that govern the assignment of trailers and containers to a fleet of flatcars. Simulation approaches (Lai et al., 1995) were also undertaken to circumvent the modeling complexities encountered for more detailed analysis of the complex DCA system. From the literature, the DCA operational planning problem has not been formulated as a dynamic programming model for obtaining an average cost optimal solution with stochastic considerations. The proposed models are suitable for such a scenario. An advantage for using an average cost formulation in an infinite horizon framework is that it will not suffer from the distortions caused by this finite horizon approximation to an infinite horizon reality (Hughes and Powell, 1988). Stochastic models allow the consideration of uncertainty. We formulate the DCA problem as a dynamic stochastic program with the decision policy optimal in the infinite horizon average cost sense. A simulation based approximate policy iteration (API) algorithm is proposed to resolve the dynamic stochastic program. This methodology is based on a linear architecture for approximating the cost to go function at each stage. For a simple two-ports, two-voyages (TPTV) system, an exact average cost optimal solution methodology can be obtained with an optimal solution methodology such as the contracting value iteration (CVI) algorithm (Bertsekas, 1998). Results for the simple TPTV system from the approximate solution methodology was compared with the exact optimal solution obtained through CVI and with the result obtained through a simple heuristic that is commonly used in the industry. For realistically sized multiple-ports multiple-voyages (MPMV) system, comparison of results was made with the results obtained from a commonly known heuristic.