# American Institute of Mathematical Sciences

• Previous Article
Linear bilevel multiobjective optimization problem: Penalty approach
• JIMO Home
• This Issue
• Next Article
The optimal pricing and ordering policy for temperature sensitive products considering the effects of temperature on demand
July  2019, 15(3): 1185-1211. doi: 10.3934/jimo.2018091

## Maritime inventory routing problem with multiple time windows

 1 Department of Industrial Engineering, Institut Teknologi Sepuluh Nopember, Surabaya 60111, Indonesia 2 School of Engineering and Information Technology, University of New South Wales, Canberra, ACT 2600, Australia

Received  May 2017 Revised  February 2018 Published  July 2018

Fund Project: 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.

Citation: Nurhadi Siswanto, Stefanus Eko Wiratno, Ahmad Rusdiansyah, Ruhul Sarker. Maritime inventory routing problem with multiple time windows. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1185-1211. doi: 10.3934/jimo.2018091
##### References:

show all references

##### References:
Daily multiple time windows at a port
Detailed activities of a ship during its time in a port
Several alternatives of a ship arriving and leaving a port when considering time windows
An Example of Chromosome
Chromosome in one and two steps
Changing states during every assignment in a chromosome
The values of the fitness functions for test problem 1 with the 15 day planning horizon from each of 40 runs
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
 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
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
 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
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
 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
Data of travelling cost and time between ports
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)
 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)
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]
 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]
An example of one ship's assignment output
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)
 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] Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240 [2] T. W. Leung, Chi Kin Chan, Marvin D. Troutt. A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics. Journal of Industrial & Management Optimization, 2008, 4 (1) : 53-66. doi: 10.3934/jimo.2008.4.53 [3] Erfan Babaee Tirkolaee, Alireza Goli, Mani Bakhsi, Iraj Mahdavi. A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026 [4] Jiao-Yan Li, Xiao Hu, Zhong Wan. An integrated bi-objective optimization model and improved genetic algorithm for vehicle routing problems with temporal and spatial constraints. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-18. doi: 10.3934/jimo.2018200 [5] Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435 [6] Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391 [7] Lan Luo, Zhe Zhang, Yong Yin. Simulated annealing and genetic algorithm based method for a bi-level seru loading problem with worker assignment in seru production systems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019134 [8] Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99 [9] Ji Zhang, Hongxia Lv, Boer Deng, Wenxian Wang. An adaptive genetic algorithm for solving the optimization model of car flow organizat. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020200 [10] Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11 [11] Ali Fuat Alkaya, Dindar Oz. An optimal algorithm for the obstacle neutralization problem. Journal of Industrial & Management Optimization, 2017, 13 (2) : 835-856. doi: 10.3934/jimo.2016049 [12] Sangkyu Baek, Jinsoo Park, Bong Dae Choi. Performance analysis of transmission rate control algorithm from readers to a middleware in intelligent transportation systems. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 357-375. doi: 10.3934/naco.2012.2.357 [13] Xiaoling Sun, Hongbo Sheng, Duan Li. An exact algorithm for 0-1 polynomial knapsack problems. Journal of Industrial & Management Optimization, 2007, 3 (2) : 223-232. doi: 10.3934/jimo.2007.3.223 [14] Lauri Oksanen. Solving an inverse problem for the wave equation by using a minimization algorithm and time-reversed measurements. Inverse Problems & Imaging, 2011, 5 (3) : 731-744. doi: 10.3934/ipi.2011.5.731 [15] Ping-Chen Lin. Portfolio optimization and risk measurement based on non-dominated sorting genetic algorithm. Journal of Industrial & Management Optimization, 2012, 8 (3) : 549-564. doi: 10.3934/jimo.2012.8.549 [16] Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191 [17] Qiang Long, Changzhi Wu. A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1279-1296. doi: 10.3934/jimo.2014.10.1279 [18] Marcin Studniarski. Finding all minimal elements of a finite partially ordered set by genetic algorithm with a prescribed probability. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 389-398. doi: 10.3934/naco.2011.1.389 [19] Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2019088 [20] Sheng Wang, Xue An, Chen Yang, Long Liu, Yongchang Yu. Design and experiment of seeding electromechanical control seeding system based on genetic algorithm fuzzy control strategy. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020210

2018 Impact Factor: 1.025

## Tools

Article outline

Figures and Tables