CLAIO_2008_submission_197
•
1 like•101 views
This document presents a mathematical formulation for the dynamic container allocation problem that considers the movement of both empty and loaded containers. The formulation models the problem as a scheduling problem to determine the departure times of loads while optimizing the allocation of containers. An example application using 47 loads solved the problem of minimizing total tardiness in approximately 4 hours. The formulation makes assumptions about container types, routes, and facilities to develop a linear optimization model that can be solved to provide optimal container allocations and schedules.
![XIV Latin Ibero-American Congress on Operations Research (CLAIO 2008) – Book of Extended Abstracts
A MATHEMATICAL FORMULATION FOR THE DYNAMIC
CONTAINER ALLOCATION PROBLEM WITH EMPTY AND LOADED
CONTAINERS MOVEMENT
Éfrem de A. Maranhão Filho*, João L. Becker* and Leo Lopesâ€
*Universidade Federal do Rio Grande do Sul
Rio Grande do Sul, Brasil
e-mail: eamaranhao@ea.ufgrs.br, jlbecker@ea.ufrgs.br
â€
University of Arizona
Arizona, United States
e-mail: leo@sie.arizona.edu
1 INTRODUCTION
Adequate container management characterizes a very important problem because of the high costs of
acquiring, maintaining, handling and transporting containers [6]. Empty container allocation is a core
problem for shipping companies, due to the usual imbalance in supply and demand pattern [13].
As research directions, it has been proposed that the empty containers flow problem should be
addressed dynamically, combining loading and empty flows problems at operational level [6].
Nevertheless, the Dynamic Container Allocation (DCA) problem [5] is still being modeled concerning
only with empty flows [2]. Another characteristic of DCA problem is that it is mostly modeled as
network flows [3]. We speculate that this is one of the reasons for formulations mostly concerned just
with empty containers flows.
Four questions are presented in [10] as important questions about return logistic system: how many
containers should be available in the system; how should the distribution, collection, and relocation of
the containers be organized; how many container depots should there be and where should they be
located; and what are appropriate service, distribution and collection fees.
Recent formulations for reverse logistics and particularly DCA and their heuristics ([1]; [2]; [4]; [9];
[11]; [12]; [14]), can be found in the literature but no exact deterministic formulation for combined
load and empty flows were found. Inspired in the n/m Job-shop problem [8], we modeled a scheduling
formulation to the problem.
2 METHODOLOGY
Using the classification methodology of [11], this model is an operational model. We are concerned
with long-haul transportation, especially maritime trade [7], although the model could be extended for
inland trade, as we will show after. Since this is an operational model, from the four questions
presented in [10] above mentioned, we are concerned with the first two.
Based on this, an analytical, dynamic, deterministic and MIP, formulation was developed. An example
of optimization for this problem were stated and tested and will be presented in section 4.
3 ANALYTICAL FORMULATION
The assumptions of the analytical formulation are presented first. First of all, and this one is the
strongest assumption, is that a logistic design already exists and for this, some indirect assumptions are
necessary: there is only one route links two facilities of the system; there is no specific transport modal;
there is no distinction among facilities (warehouses, harbors and so on) and all of them can send and
receive containers.](https://image.slidesharecdn.com/af7d4b86-d24e-43d6-8c9a-c9684574fbc2-160307003429/85/CLAIO_2008_submission_197-1-320.jpg)
![Éfrem de A. Maranhão Filho, João L. Becker and Leo Lopes.
5 SUMMARY
We presented a mathematical general formulation for the Dynamic Container Allocation problem, with
a very intuitive example of an objective functions. As future works, a real life example is desire as a
test, with others objective, including some others real life restrictions and the development of faster
optimal method for this polyhedron.
REFERENCES
[1] Alshamrani, A., Mathur, K., Ballou, R. H. Reverse logistics: simultaneous design of delivery routes
and returns strategies. Computers & OR 34, 595-619, 2007.
[2] Bandeira, D. L. Alocação e movimentação de contêineres vazios e cheios – um modelo integrado e
sua aplicação. Phd Dissertation, Universidade Federal do Rio Grande do Sul, 2005.
[3] Cheung, R. K., Chen, C. A two-stage stochastic network model and solution methods for the
dynamic empty container allocation problem. Transportation Science 32(2), 142-162, 1998.
[4] Choong, S. T., Cole, M. H., Kutanoglu, E. Empty container management for intermodal
transportation networks. Transportation Research Part E 38(6), 423-438, 2002.
[5] Crainic, T. G., Gendreau, M., Dejax, P. Dynamic and stochastic models for the allocation of empty
containers. Operations Research 41(1), 102-126, 1993.
[6] Dejax P. J., Crainic T. G. A review of empty flows and fleet management models in freight
transportation. Transportation science. 21(4), 227-247, 1987.
[7] Ghiani, G., Laporte, G., Musmanno R. Introduction to logistics systems planning and control. West
Sussex: Wiley-Interscience series in systems and optimization, 2004.
[8] Johnson, L. A.. Operations research in production planning, scheduling, and inventory control.
New York: Wiley, c1974. xiv, 525 p.
[9] Ko H. J., Evans G. W. A genetic algorithm-based heuristic for the dynamic integrated
forward/reverse logistics network for 3PLs. Computers and Operations Research 34(2), 346-366, 2007.
[10] Kroon, L. e Vrijens, G. Returnable containers: an example of reverse logistics. International
Journal of Physical Distribution & Logistics Management 25(2), 56-68, 1995.
[11] Lam, S. W., Lee, L. H., Tang, L. C. An approximate dynamic programming approach for the
empty container allocation problem. Transportation Research Part C 15(4), 265-277, 2007.
[12] Li, J. A., et al. Allocation of empty containers between multi-ports. European Journal of
Operational Research 182(1), 400-412, 2007.
[13] Shen, W. S., Khoong, C. M. A DSS for empty container distribution planning. Decision Support
Systems 15(1), 75-82, 1995.
[14] Shintani, K., Imai A., Nishimura E., Papadimitriou S. The container shipping network design
problem with empty container repositioning. Transportation Research Part E 43(1), 39-59, 2007.
APPENDIX A
1
2
3
4 5 6 7 8 9 10
0
1000
2000
3000
4000
5000
6000
0 2 4 6 8 10 12
Figure 1 – The increment of one container evolution](https://image.slidesharecdn.com/af7d4b86-d24e-43d6-8c9a-c9684574fbc2-160307003429/85/CLAIO_2008_submission_197-3-320.jpg)
CLAIO_2008_submission_197
- 1. XIV Latin Ibero-American Congress on Operations Research (CLAIO 2008) – Book of Extended Abstracts A MATHEMATICAL FORMULATION FOR THE DYNAMIC CONTAINER ALLOCATION PROBLEM WITH EMPTY AND LOADED CONTAINERS MOVEMENT Éfrem de A. Maranhão Filho*, João L. Becker* and Leo Lopes†*Universidade Federal do Rio Grande do Sul Rio Grande do Sul, Brasil e-mail: eamaranhao@ea.ufgrs.br, jlbecker@ea.ufrgs.br †University of Arizona Arizona, United States e-mail: leo@sie.arizona.edu 1 INTRODUCTION Adequate container management characterizes a very important problem because of the high costs of acquiring, maintaining, handling and transporting containers [6]. Empty container allocation is a core problem for shipping companies, due to the usual imbalance in supply and demand pattern [13]. As research directions, it has been proposed that the empty containers flow problem should be addressed dynamically, combining loading and empty flows problems at operational level [6]. Nevertheless, the Dynamic Container Allocation (DCA) problem [5] is still being modeled concerning only with empty flows [2]. Another characteristic of DCA problem is that it is mostly modeled as network flows [3]. We speculate that this is one of the reasons for formulations mostly concerned just with empty containers flows. Four questions are presented in [10] as important questions about return logistic system: how many containers should be available in the system; how should the distribution, collection, and relocation of the containers be organized; how many container depots should there be and where should they be located; and what are appropriate service, distribution and collection fees. Recent formulations for reverse logistics and particularly DCA and their heuristics ([1]; [2]; [4]; [9]; [11]; [12]; [14]), can be found in the literature but no exact deterministic formulation for combined load and empty flows were found. Inspired in the n/m Job-shop problem [8], we modeled a scheduling formulation to the problem. 2 METHODOLOGY Using the classification methodology of [11], this model is an operational model. We are concerned with long-haul transportation, especially maritime trade [7], although the model could be extended for inland trade, as we will show after. Since this is an operational model, from the four questions presented in [10] above mentioned, we are concerned with the first two. Based on this, an analytical, dynamic, deterministic and MIP, formulation was developed. An example of optimization for this problem were stated and tested and will be presented in section 4. 3 ANALYTICAL FORMULATION The assumptions of the analytical formulation are presented first. First of all, and this one is the strongest assumption, is that a logistic design already exists and for this, some indirect assumptions are necessary: there is only one route links two facilities of the system; there is no specific transport modal; there is no distinction among facilities (warehouses, harbors and so on) and all of them can send and receive containers.
- 2. Éfrem de A. Maranhão Filho, João L. Becker and Leo Lopes. The demand for containers, that is, the quantity of containers, with its origin and destination are given, for a given discrete set of facilities. We look after a schedule for q time slots, where MAX{oi} = q, loads are sort by oi and for simplicity the demand for containers doesn’t change in this period. The only delay permitted is the late shipping of a load (all the others times are constant). Maintenance time is not modeled separately, being included in the transportation time. Another assumption is that all the loads are transported in containers and the loads are shown in container unit (values of a12,…,zxx-1). For simplicity, just one type of container exists in the model and there is no distinction about the property of the container. Now with assumptions defined, we can show the notation used. Index Sets I Loads set K Containers set Parameters pi Transportation time of load i from its origin to its destination oi Demand instant of shipping load i ttij Transportation time of an empty container between load i destination and load j origin m Constant sufficiently large Decision variables Rik Ti Departure instant of load i; + ℜ∈≥ * ii oT Yij As so, for complete the polyhedron (P) we can define the follow linear relations: ∑k ikR = 1 Ii ∈∀ , Kk ∈∀ (01) m (3 – Yij – Rik – Rjk) + Tj – Ti – pi – ttij ≥ 0 Iji, ∈∀ , i < j, Kk ∈∀ (02) m (2 + Yij – Rik – Rjk) + Ti – Tj – pj – ttij ≥ 0 Iji, ∈∀ , i < j, Kk ∈∀ (03) Where: (01) guarantee that a load only can be sent inside one container, (02) and (03) guarantee the precedence of the loads using the same container (two loads can not use the same container at the same time) and using i < j instead of i ≠j, we lose a generalization, but simplified the model for when the distance between two facilities doesn’t depends of the direction. 4 RESULTS AND DISCUSSION After define the basic Ρ we can solve an optimization problem. The first intuitive objective is to minimize the total tardiness. This could be accomplished using, as the objective function: Min z = ∑i iT (04) Using OPL(5.1)/CPLEX(10.1) we created a illustration example using 47 loads, q = 5 and a the containers range between 1-10. Although the solve time depends of the polyhedron structure, normally our results were found in approximately 4 hours. The results of z can be found in APPENDIX A. 1 if load i precedes load j 0 otherwise 1 if load i is transported in container k 0 otherwise
- 3. Éfrem de A. Maranhão Filho, João L. Becker and Leo Lopes. 5 SUMMARY We presented a mathematical general formulation for the Dynamic Container Allocation problem, with a very intuitive example of an objective functions. As future works, a real life example is desire as a test, with others objective, including some others real life restrictions and the development of faster optimal method for this polyhedron. REFERENCES [1] Alshamrani, A., Mathur, K., Ballou, R. H. Reverse logistics: simultaneous design of delivery routes and returns strategies. Computers & OR 34, 595-619, 2007. [2] Bandeira, D. L. Alocação e movimentação de contêineres vazios e cheios – um modelo integrado e sua aplicação. Phd Dissertation, Universidade Federal do Rio Grande do Sul, 2005. [3] Cheung, R. K., Chen, C. A two-stage stochastic network model and solution methods for the dynamic empty container allocation problem. Transportation Science 32(2), 142-162, 1998. [4] Choong, S. T., Cole, M. H., Kutanoglu, E. Empty container management for intermodal transportation networks. Transportation Research Part E 38(6), 423-438, 2002. [5] Crainic, T. G., Gendreau, M., Dejax, P. Dynamic and stochastic models for the allocation of empty containers. Operations Research 41(1), 102-126, 1993. [6] Dejax P. J., Crainic T. G. A review of empty flows and fleet management models in freight transportation. Transportation science. 21(4), 227-247, 1987. [7] Ghiani, G., Laporte, G., Musmanno R. Introduction to logistics systems planning and control. West Sussex: Wiley-Interscience series in systems and optimization, 2004. [8] Johnson, L. A.. Operations research in production planning, scheduling, and inventory control. New York: Wiley, c1974. xiv, 525 p. [9] Ko H. J., Evans G. W. A genetic algorithm-based heuristic for the dynamic integrated forward/reverse logistics network for 3PLs. Computers and Operations Research 34(2), 346-366, 2007. [10] Kroon, L. e Vrijens, G. Returnable containers: an example of reverse logistics. International Journal of Physical Distribution & Logistics Management 25(2), 56-68, 1995. [11] Lam, S. W., Lee, L. H., Tang, L. C. An approximate dynamic programming approach for the empty container allocation problem. Transportation Research Part C 15(4), 265-277, 2007. [12] Li, J. A., et al. Allocation of empty containers between multi-ports. European Journal of Operational Research 182(1), 400-412, 2007. [13] Shen, W. S., Khoong, C. M. A DSS for empty container distribution planning. Decision Support Systems 15(1), 75-82, 1995. [14] Shintani, K., Imai A., Nishimura E., Papadimitriou S. The container shipping network design problem with empty container repositioning. Transportation Research Part E 43(1), 39-59, 2007. APPENDIX A 1 2 3 4 5 6 7 8 9 10 0 1000 2000 3000 4000 5000 6000 0 2 4 6 8 10 12 Figure 1 – The increment of one container evolution