A Two Stage Recourse Stochastic Mathematical Model for the Tramp Ship Routing with Time Windows Problem

Document Type : Research Paper

Author

School of Industrial Engineering, College of Engineering, University of Tehran, Iran

Abstract

Nowadays, the majority of international trade in goods is carried by sea, and especially by ships deployed in the industrial and tramp segments. This paper addresses routing the tramp ships and determining the schedules including the arrival times to the ports, berthing times at the ports, and the departure times in an operational planning level. In the operational planning level, the weather can be almost exactly forecasted, however in some routes some uncertainties may remain. In this paper, the voyaging times between some of the ports are considered to be uncertain. To that end, a two stage stochastic mathematical model is proposed. In order to find near to optimum solutions in a limited amount of time, a new hybrid heuristic algorithm is proposed to solve large-size examples. Moreover, a case study is defined and tested with the presented model. The computational results show that this mathematical model is promising and can represent acceptable solutions. Specifically, the value of the stochastic solution, VSS, is computed, and the results show that using two stage stochastic with recourse improve 1.1% of the objective value.

Keywords

References

               [1]        Toth P. and D.  Vigo, “The Vehicle Routing Problem”, Philadelphia: Society for Industrial and Applied Mathematics, 2002.
               [2]        Berbeglia, G.  Cordeau, G.-F., Gribkovskaia I., and Laporte G., “Static Pickup and Delivery Problems: A Classification Scheme and Survey, TOP, 2007; 15: 1-31.
               [3]        Grandinetti, L., Guerriero, F., Pezzella, F., Pisacane, O., The Multi-Objective Multi-Vehicle Pickup and Delivery Problem with Time Windows, Social and Behavioral Sciences, 2014; 111: 203 – 212.
               [4]        Wassan N. A., and Nagy, G., Vehicle Routing Problem with Deliveries and Pickups: Modelling Issues and Meta-heuristics Solution Approaches, International Journal of Transportation, 2014; 2 (1) 95-110.
               [5]        Ronen, D., Cargo ship routing and scheduling: Survey of models and problems, European Journal of Operational Research, 1983; 12: 119-126.
               [6]        Christiansen, M., Fagerholt, K., Nygreen, B., Ronen, D., Ship routing and scheduling in the new millennium, European Journal of Operational Research, 2013; 228 (3): 467-483.
               [7]        Kjeldsen K. H., Routing and Scheduling in Liner Shipping, PhD Thesis, Dep. of Economics and Business, AARHUS University, Denmark, 2012.
               [8]        Cho, S. C., and Perakis, A. N., An Improved Formulation for Bulk Cargo Ship Scheduling with a Single Loading Port.  Maritime Policy and Management, 2001; 28 (4): 339-345.
               [9]        Fagerholt, K., Christiansen, M., A combined ship scheduling and allocation problem. Journal of the Operational Research Society, 2000; 51: 834-842.
             [10]      Fagerholt, K., Ship Scheduling with Soft Time Windows: An Optimization Based Approach. European Journal of Operational Research, 2001; 131: 559-571.
             [11]      Liu H.-Y., Chen, C.-Y., An Optimization Model for the Tramp Ship Routing Problem, Storage Management Solutions, 2013; 3: 189-204.
             [12]      Romero, G.,  Dur´an, G., Marenco, J., Weintraub, A., An approach for efficient ship routing, International Transactions In Operational Research, 00: 1–28; 2013.
             [13]      De, A., Krishna Reddy Mamanduru, V., , Gunaskaran, A., Subramanian, N., Kumar Tiwari, M., Composite particle algorithm for sustainable integrated dynamic ship routing and scheduling optimization, Computers & Industrial Engineering, 2016; 96: 201-215
             [14]      Dithmer P., Reinhardt L., Kontovas C. A., The Liner Shipping Routing and Scheduling Problem Under Environmental Considerations: The Case of Emissions Control Areas, International Conference on Computational Logistics, ICCL 2017; 336-350
             [15]      Fan, H., Yu, J., and Liu, X., "Tramp Ship Routing and Scheduling with Speed Optimization Considering Carbon Emissions " sustainability, 2019; 11: 1-19.
             [16]      Kim H-J, Son D-H, Yang W., Kim J-G, Liner Ship Routing with Speed and Fleet Size Optimization: KSCE Journal of Civil Engineering, 2019; 23 (3),1341–1350
             [17]      Homsi, G., Martinelli, R., Vidal, T., and Fagerholt, K., "Industrial and tramp ship routing problems: Closing the gap for real-scale instances," European Journal of Operational Research, 2020; 283(3), 972-990.
             [18]      Dumas, Y., Desrosiers, J., E. Gelinas, Solomon, M.-M., An Optimal Algorithm for the Traveling Salesman Problem with Time Windows, Operations Research, 1995; 43(2):367-371.
             [19]      Eglese, R.W., simulated annealing: A Tool for Operational Research, European Journal of Operational Research, 1990; 46, 271-281.
             [20]      Kennedy, J., Eberhart, R.C., Particle swarm optimization. In: Proc. of the IEEE International Conference on Neural Networks, IEEE service Center, Piscataway, N.J., 1995; 4, 1942-1948.
             [21]      Alhamed A., Alkharashi S., Dong J., Metaheuristic algorithm for ship routing and scheduling problems with time window: Cogent Business & Management ; 2019, 6(1), 1-16
Advances in Industrial Engineering
Volume 54, Issue 1
January 2020
Pages 41-52

Files

Share

How to cite

Statistics