Article Contents
Article Contents

# Maritime inventory routing problem with multiple time windows

• * Corresponding author: Nurhadi Siswanto
The first author is supported by Ministry of Research, Technology and Higher Education, Republic of Indonesia through International Research Collaboration and Scientific Publication Research Grant No. 536/PKS/ITS/2017.
• This paper considers a maritime inventory routing problem with multiple time windows. The typical time windows considered that certain ports permit ships entering and leaving during the daytime only due to various operational limitations. We have developed an exact algorithm to represent this problem. However, due to the excessive computational time required for solving the model, we have proposed a multi-heuristics based genetic algorithm. The multi-heuristics are composed of a set of strategies that correspond to four decision points: ship selection, ship routing, the product type and the quantity of loading and unloading products. The experimental results show that the multi-heuristics can obtain acceptable solutions within a reasonable computational time. Moreover, the flexibility to add or remove the strategies means that the proposed method would not be difficult to implement for other variants of the maritime inventory routing problem.

Mathematics Subject Classification: Primary: 90B06, 90B10, 90B90; Secondary: 90C11, 68R99.

 Citation:

Figure 2.  Daily multiple time windows at a port

Figure 3.  Detailed activities of a ship during its time in a port

Figure 4.  Several alternatives of a ship arriving and leaving a port when considering time windows

Figure 5.  An Example of Chromosome

Figure 6.  Chromosome in one and two steps

Figure 7.  Changing states during every assignment in a chromosome

Figure 8.  The values of the fitness functions for test problem 1 with the 15 day planning horizon from each of 40 runs

Table 1.  An example of strategies for each decision point

 No Decision point Strategies 1 Ship selection Based on the least ships current time 2 Routing Visit two demand ports with the sequence based on the least CDik 3 Loading Compartment [1] for product[1], compartment[2] for product[2] with loading quantities up to the maximum of compartments capacities 4 Unloading Divide the same quantities for both ports

Table 2.  Data of port and their storages

 No Description H1 H2 H3 S11 S12 S21 S22 S31 S32 1 Maximum capacity (unit) 160 180 55 41 68 51 2 Minimum level (unit) 0 0 0 0 0 0 3 Initial level (unit) 44 28 19 27 46 25 4 Daily supply/demand rate (unit/day) 8 9 6 4 2 5 5 Fixed setup loading time (day) 0.039 0.059 0.074 0.060 0.067 0.049 6 Variable loading time (day/unit) 0.025 0.010 0.003 0.026 0.028 0.014 7 Fixed setup loading cost (＄) 10 8 6 9 8 10 8 Variable loading cost (＄/unit) 0 0 0 0 0 0 9 Quantity penalty cost (＄/day) 10 10 10 10 10 10 10 Fixed setup port time (day) 0 0 0 11 Fixed setup port cost (＄) 0 0 0 12 Daily starting time windows 7.12am 7.12am 7.12am 13 Daily ending time windows 4.48pm 4.48am 4.48pm

Table 3.  Data of ship and their compartments

 No Description V1 V2 C11 C12 C21 C22 1 Maximum compartment capacity 68 31 44 50 2 Initial level 0 0 40 4 3 Current product in the compartment - - P2 P1

Table 4.  Data of travelling cost and time between ports

Table 5.  The result of exact algorithm solved using Lingo

 Test Problem (TP) Planning Horizon (PH) Scenario 1 (Mp=3;Mc=2) Scenario 2 (Mp=3;Mc=2) Gap (%) Optimal Solution Run Time (in Second) Optimal Solution Run Time (in Second) 1 10 55.8 1,329 - ﹥﹥8.64E + 4(*) - 15 91.4 21,423 - ﹥﹥8.64E + 4(*) - 2 10 66.8 1,012 66.8 582 0 15 103, 0 25,451 103.0 74,166 0 3 10 99.0 46 - ﹥﹥8.64E + 4(*) - 15 216.0 34,827 - ﹥﹥8.64E + 4(*) - 4 10 137.0 640 137.0 211 0 15 265.0 47,210 265.0 ﹥﹥8.64E + 4(n) 0 (n)the solution did not terminate before the time limit of 8.64E+4 seconds (24 hours)(*)a feasible solution was not obtained before the time limit of 8.64E+4 seconds (24 hours)

Table 6.  The sequence of visiting demand ports

 Gene4 Gene3 The first visiting port The second visiting port 0 0 CDP[0] 1 CDP[0] CDP[1] 1 0 CDP[1] 1 CDP[1] CDP[0]

Table 7.  An example of one ship's assignment output

Table Appendix A.  The results of the multi-heuristics based GA in comparison to the results of the exact algorithm

 Test Problem (TP) Planning Horizon (PH) Exact Algorithm Solution Multi-Heuristics based GA (40 runs repetition) No. of Individuals in a population Best Solution (Min) Gap (%) Max. Solution Average Standart Deviation No. of infeasible solutions Average Running Time (in 2nd) 1 10 55.8 20 55.8 0 55.8 55.8 0 0 50.3 50 55.8 0 55.8 55.8 0 0 105.6 100 55.8 0 55.8 55.8 0 0 222.7 15 91.4 20 91.4 0 108.7 94.3 5.4 0 166.0 50 91.4 0 102.0 91.9 2.0 0 401.2 100 91.4 0 91.4 91.4 0 0 879.0 20 $(*)$ 20 107.7 - 148.0 126.9 9.3 0 248.5 50 107.7 - 135.0 122.2 7.1 0 626.0 100 107.7 - 122.4 116.0 3.7 0 1,312.0 25 $(*)$ 20 146.3 - 196.9 175.4 14.7 5 234.9 50 140.8 - 195.4 165.3 15.9 2 774.2 100 143.4 - 188.7 154.4 10.5 0 1,824.1 2 10 66.8 20 66.8 0 76.8 68.4 3.6 0 93.08 50 66.8 0 68.6 66.9 0.2 0 212.9 100 66.8 0 66.8 66.8 0 0 497.1 15 103.0 20 109.3 6.12 140.2 125.6 6.4 0 197.3 50 103.0 0 130.5 120.2 6.5 0 535.2 100 105.2 2.14 124.2 116.6 4.4 0 1,207.4 20 $(*)$20 149.7 - 191.8 170.3 9.8 3 208.3 50 142.3 - 184.0 166.2 7.5 5 694.3 100 149.7 - 191.0 163.7 10.4 3 1,520.2 25 $(*)$ 20 177.5 - 231.2 202.8 12.5 12 295.8 50 171.6 - 207.3 190.9 10.4 6 938.4 100 173.6 - 208.7 187.0 8.6 4 1,771.2 3 10 99.0 20 99.0 0 99.0 99.0 0 0 43.9 50 99.0 0 99.0 99.0 0 0 109.0 100 99.0 0 99.0 99.0 0 0 239.9 15 216.0 20 216.0 0 241.0 222.4 5.0 0 147.0 50 216.0 0 241.0 220.1 4.8 0 377.2 100 216.0 0 221.0 217.4 2.3 0 796.1 20 $(*)$ 20 306.0 - 423.0 343.6 25.1 0 184.0 50 304.0 - 344.0 316.5 11.35 0 585.2 100 304.0 - 401.0 312.0 16.0 0 1,222.6 25 $(*)$ 20 401.0 - 508.0 466.8 24.4 1 236.7 50 346.0 - 522.0 422.5 46.2 2 753.3 100 346.0 - 483.0 404.8 41.6 0 1,476.9 4 10 137.0 20 137.0 0 147.0 140.0 4.6 0 84.7 50 137.0 0 137.0 137.0 0 0 180.4 100 137.0 0 137.0 137.0 0 0 406.6 15 265.0 20 277.0 4.53 363.0 291.6 14.6 0 196.3 50 275.0 3.77 294.0 284.6 5.4 0 530.0 100 265.0 0 287.0 281.4 4.8 0 1,294.4 20 $(*)$ 20 354.0 - 479.0 423.7 24.7 1 217.5 50 407.0 - 454.0 423.2 15.2 5 676.3 100 350.0 - 454.0 396.3 29.5 0 1,498.9 25 $(*)$ 20 484.0 - 632.0 543.2 31.9 14 304.6 50 431.0 - 567.0 517.9 34.3 7 894.2 100 431.0 - 558.0 505.3 31.8 6 1,818.1 Note: (*) a feasible solution was not found before the time limit of 8.64E+4 seconds (24 hours)
•  [1] A. Agra, M. Christiansen, et al., A maritime inventory routing problem with stochastic sailing and port times, Computers & Operations Research, 61 (2015), 18-30 doi: 10.1016/j.cor.2015.01.008. [2] F. Al-Khayyal and S. J. Hwang, Discrete Optimization-Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk, Part Ⅰ: Applications and model, European Journal of Operational Research, 176 (2007), 106-130.  doi: 10.1016/j.ejor.2005.06.047. [3] K. Chakhlevitch and P. Cowling, Hyperheuristics: Recent developments, in Adaptive and Multilevel Metaheuristics (eds. C. Cotta, M. Sevaux, K. Sorensen), Springer-Verlag Berlin Heidelberg, (2008), 3-29 [4] M. Christiansen and B. Nygreen, A method for solving ship routing problems with inventory constraints, Annals of Operations Research, 81 (1998), 357-378.  doi: 10.1023/A:1018921527269. [5] M. Christiansen and B. Nygreen, Modeling path flows for a combined ship routing and inventory management problem, Annals of Operations Research, 82 (1998), 391-412.  doi: 10.1023/A:1018979107222. [6] M. Christiansen, Decomposition of a combined inventory and time constrained ship routing problem, Transportation Science, 33 (1999), 3-16.  doi: 10.1287/trsc.33.1.3. [7] M. Christiansen and K. Fagerholt, Robust ship scheduling with multiple time windows, Naval Research Logistics, 49 (2002), 611-625.  doi: 10.1002/nav.10033. [8] M. Christiansen, K. Fagerholt, B. Nygreen and D. Ronen, Chapter 4 maritime transportation in handbooks in operations research and management science, (eds, C. Barnhart, G. Laporte), North-Holland, Amsterdam, 14 (2007), 189-284. [9] M. Christiansen and K. Fagerholt, Maritime inventory routing problems, in Encyclopedia of Optimization, Second edition (eds C. A. Floudas, P. M. Pardalos), Springer-Verlag, (2009), 1947-1955 [10] M. Christiansen, K. Fagerholt, T. Flatberg, Ø. Haugen, O. Kloster and E. H. Lund, Maritime inventory routing with multiple products: A case study from the cement industry, European Journal of Operational Research, 208 (2011), 86-94.  doi: 10.1016/j.ejor.2010.08.023. [11] K. F. Doerner, M. Gronalt, R. F. Hartl, G. Kiechle and M. Reimann, Exact and heuristic algorithms for the vehicle routing problem with multiple interdependent time windows, Computers and Operations Research, 35 (2008), 3034-3048.  doi: 10.1016/j.cor.2007.02.012. [12] D. Favaretto, E. Moretti and P. Pellegrini, Ant colony system for a VRP with multiple time windows and multiple visits, Journal of Interdisciplinary Mathematics, 10 (2007), 263-284.  doi: 10.1080/09720502.2007.10700491. [13] K. C. Furman, J. H. Song, G. R. Kocis, M. K. McDonald and P. H. Warrick, Feedstock routing in the exxonmobil downstream sector, Interfaces, 41 (2011), 149-163.  doi: 10.1287/inte.1100.0508. [14] A. Hemmati, L. M. Hvattum, et al., An iterative two-phase hybrid matheuristic for a multiproduct short sea inventory-routing problem, European Journal of Operational Research, 252 (2016), 775-788 doi: 10.1016/j.ejor.2016.01.060. [15] S. J. Hwang, Inventory Constrained Maritime Routing and Scheduling for Multi-Commodity Liquid Bulk, Dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, USA, 2005. [16] Y. Jiang and I. E. Grossmann, Alternative mixed-integer linear programming models of a maritime inventory routing problem, Computers & Chemical Engineering, 77 (2015), 147-161.  doi: 10.1016/j.compchemeng.2015.03.005. [17] J. Lee and B. I. Kim, Industrial ship routing problem with split delivery and two types of vessels, Expert Systems with Applications, 42 (2015), 9012-9023.  doi: 10.1016/j.eswa.2015.07.059. [18] D. J. Papageorgiou, G. L. Nemhauser, J. Sokol, M. S. Cheon and A. B. Keha, MIRPLib - A library of maritime inventory routing problem instances: Survey, core model, and benchmark results, European Journal of Operational Research, 235 (2014), 350-366.  doi: 10.1016/j.ejor.2013.12.013. [19] D. J. Papageorgiou and A. B. Keha, et al., Two-stage decomposition algorithms for single product maritime inventory routing, INFORMS Journal on Computing, 26 (2014), 825-847 doi: 10.1287/ijoc.2014.0601. [20] V. Rodrigues and R. Morabito, et al., Ship routing with pickup and delivery for a maritime oil transportation system: MIP model and heuristics, Systems, 4 (2016), p31. [21] B. Santosa and R. Damayanti, et al., Solving multi-product inventory ship routing with a heterogeneous fleet model using a hybrid cross entropy-genetic algorithm: a case study in Indonesia, Production & Manufacturing Research, 4 (2016), 90-113 doi: 10.1080/21693277.2016.1204961. [22] M. Savelsbergh and J. H. Song, Inventory routing with continuous moves, Computers and Operations Research, 34 (2007), 1744-1763.  doi: 10.1016/j.cor.2005.05.036. [23] N. Siswanto, D. Essam and R. Sarker, Solving the ship inventory routing and scheduling problem with undedicated compartments, Computers and Industrial Engineering, 61 (2011), 289-299.  doi: 10.1109/ICCIE.2009.5223771. [24] N. Siswanto, D. Essam and R. Sarker, Multi-heuristics based genetic algorithm for solving maritime inventory routing problem, IEEE International Conference on Industrial Engineering and Engineering Management, Singapore, (2011), 116-120 doi: 10.1109/IEEM.2011.6117890. [25] J. Sokol, C. Zhang, G. Nemhauser, D. Papageorgiou and M. S. Cheon, Robust inventory routing with flexible time window allocation, Working paper, 2015. [26] J. H. Song and K. C. Furman, A maritime inventory routing problem: Practical approach, Computers and Operations Research, 40 (2011), 657-665.  doi: 10.1016/j.cor.2010.10.031. [27] F. Tricoire, M. Romauch, K. F. Doerner and R. F. Hartl, Heuristics for the multi-period orienteering problem with multiple time windows, Computers and Operations Research, 37 (2010), 351-367.  doi: 10.1016/j.cor.2009.05.012.

Figures(8)

Tables(8)