Maritime inventory routing problem with multiple time windows

Previous Article
The optimal pricing and ordering policy for temperature sensitive products considering the effects of temperature on demand
JIMO Home
This Issue
Next Article
Linear bilevel multiobjective optimization problem: Penalty approach

July 2019, 15(3): 1185-1211. doi: 10.3934/jimo.2018091

Maritime inventory routing problem with multiple time windows

Nurhadi Siswanto ^1,, , Stefanus Eko Wiratno ^1, , Ahmad Rusdiansyah ^1, and Ruhul Sarker ^2,

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

* Corresponding author: Nurhadi Siswanto

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.

Keywords: Maritime transportation, inventory routing problem, multiple time windows, exact algorithm, multi-heuristics, genetic algorithm.

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

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:

[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. Google Scholar
[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. Google Scholar
[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-29Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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-1955Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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.Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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.Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[25]	J. Sokol, C. Zhang, G. Nemhauser, D. Papageorgiou and M. S. Cheon, Robust inventory routing with flexible time window allocation, Working paper, 2015.Google Scholar
[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. Google Scholar
[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. Google Scholar

show all references

References:

[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. Google Scholar
[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. Google Scholar
[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-29Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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-1955Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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.Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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.Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[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. Google Scholar
[25]	J. Sokol, C. Zhang, G. Nemhauser, D. Papageorgiou and M. S. Cheon, Robust inventory routing with flexible time window allocation, Working paper, 2015.Google Scholar
[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. Google Scholar
[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. Google Scholar

Figure 1. Loading and unloading activities at a port

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2. Daily multiple time windows at a port

Figure Options

Download full-size image

Download as PowerPoint slide

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

Figure Options

Download full-size image

Download as PowerPoint slide

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

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5. An Example of Chromosome

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6. Chromosome in one and two steps

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7. Changing states during every assignment in a chromosome

Figure Options

Download full-size image

Download as PowerPoint slide

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

Figure Options

Download full-size image

Download as PowerPoint slide

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 CD_ik
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 Options

Download as excel

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 CD_ik
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	H₁		H₂		H₃
No	Description	S₁₁	S₁₂	S₂₁	S₂₂	S₃₁	S₃₂
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 Options

Download as excel

No	Description	H₁		H₂		H₃
No	Description	S₁₁	S₁₂	S₂₁	S₂₂	S₃₁	S₃₂
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	V₁		V₂
No	Description	C₁₁	C₁₂	C₂₁	C₂₂
1	Maximum compartment capacity	68	31	44	50
2	Initial level	0	0	40	4
3	Current product in the compartment	-	-	P₂	P₁

Table Options

Download as excel

No	Description	V₁		V₂
No	Description	C₁₁	C₁₂	C₂₁	C₂₂
1	Maximum compartment capacity	68	31	44	50
2	Initial level	0	0	40	4
3	Current product in the compartment	-	-	P₂	P₁

Table 4. Data of travelling cost and time between ports

Table Options

Download as excel

Table 5. The result of exact algorithm solved using Lingo

Test Problem (TP)	Planning Horizon (PH)	Scenario 1 (M_p=3;M_c=2)		Scenario 2 (M_p=3;M_c=2)		Gap (%)
Test Problem (TP)	Planning Horizon (PH)	Optimal Solution	Run Time (in Second)	Optimal Solution	Run Time (in Second)	Gap (%)
1	10	55.8	1,329	-	﹥﹥8.64E + 4^(*)	-
1	15	91.4	21,423	-	﹥﹥8.64E + 4^(*)	-
2	10	66.8	1,012	66.8	582	0
2	15	103, 0	25,451	103.0	74,166	0
3	10	99.0	46	-	﹥﹥8.64E + 4^(*)	-
3	15	216.0	34,827	-	﹥﹥8.64E + 4^(*)	-
4	10	137.0	640	137.0	211	0
4	15	265.0	47,210	265.0	﹥﹥8.64E + 4⁽ⁿ⁾	0
⁽ⁿ⁾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 Options

Download as excel

Test Problem (TP)	Planning Horizon (PH)	Scenario 1 (M_p=3;M_c=2)		Scenario 2 (M_p=3;M_c=2)		Gap (%)
Test Problem (TP)	Planning Horizon (PH)	Optimal Solution	Run Time (in Second)	Optimal Solution	Run Time (in Second)	Gap (%)
1	10	55.8	1,329	-	﹥﹥8.64E + 4^(*)	-
1	15	91.4	21,423	-	﹥﹥8.64E + 4^(*)	-
2	10	66.8	1,012	66.8	582	0
2	15	103, 0	25,451	103.0	74,166	0
3	10	99.0	46	-	﹥﹥8.64E + 4^(*)	-
3	15	216.0	34,827	-	﹥﹥8.64E + 4^(*)	-
4	10	137.0	640	137.0	211	0
4	15	265.0	47,210	265.0	﹥﹥8.64E + 4⁽ⁿ⁾	0
⁽ⁿ⁾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

Gene₄	Gene₃	The first visiting port	The second visiting port
0	0	CDP[0]
0	1	CDP[0]	CDP[1]
1	0	CDP[1]
1	1	CDP[1]	CDP[0]

Table Options

Download as excel

Gene₄	Gene₃	The first visiting port	The second visiting port
0	0	CDP[0]
0	1	CDP[0]	CDP[1]
1	0	CDP[1]
1	1	CDP[1]	CDP[0]

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

(A) Determining loading and unloading quantities
Product #	Quantity in supply port at the time a ship arrive^(*)		Remaining demands^(*)	Compartment Capacity^(*)		Loading Quantity^(*)		Unload for the first visited port^(*)	Unload for the second visited port^(*)
P₁	40.8		28.6	44.0		28.6		0.0	28.6
P₁	50.4		43.8	50.0		43.8		16.0	27.8
^(*) in product units
(B) Routing and schedule of the selected ship
Source Port	Departure		Destination Port	Port's last visit		Arrival		Waiting time to enter⁽ⁿ⁾	Lay time
Source Port	Date	Time	Destination Port	Date	Time	Date	Time	Waiting time to enter⁽ⁿ⁾	Date	Time
H₃	May 11	2.24pm	H₁	May 7	7.12am	May 12	9.36am	0:00	May 12	9.36am
H₁	May 13	3.37pm	H₃	May 11	2.24am	May 14	10.49am	0:00	May 14	10.49am
H₃	May 15	7.12am	H₂	May 11	7.12am	May 16	7.12am	0:00	May 16	7.12am
⁽ⁿ⁾ in (hour:minutes)
(C) Routing and schedule of the selected ship (continue)
Destination Port	Loading Time(n)		Waiting time for supply/space(n)	Ready to Leave		Waiting time to leave(n)			Leaving time
Destination Port	Loading Time(n)		Waiting time for supply/space(n)	Date	Time	Waiting time to leave(n)			Date	Time
H₁	30:01		0:00	May 13	3.37pm	0:00			May 13	3.37pm
H₃	6:33		0:00	May 14	7.12pm	12:00			May 15	7.12am
H₂	22:38		0:00	May 17	5.50am	1:22			May 17	7.12am
⁽ⁿ⁾ in (hour:minutes)
(D) Information of each visiting port's storage
Destination Port	Product#		CD_ik	Remaining Demand(*)		Level of Storages(*) at ship's lay time		Available space in storage(*)	Loading/Unloading quantity(*)
H₁	P₁		27.30	0.0		40.8		-	28.6
H₁	P₂		26.80	0.0		50.4		-	43.8
H₃	P₁		25.00	0.0		21.1		46.9	0.0
H₃	P₂		21.80	16.0		36.7		14.3	16.0
H₂	P₁		20.23	28.6		23.6		31.4	28.6
H₂	P₂		18.05	27.8		7.0		34.0	27.8
^(*) in product units

Table Options

Download as excel

(A) Determining loading and unloading quantities
Product #	Quantity in supply port at the time a ship arrive^(*)		Remaining demands^(*)	Compartment Capacity^(*)		Loading Quantity^(*)		Unload for the first visited port^(*)	Unload for the second visited port^(*)
P₁	40.8		28.6	44.0		28.6		0.0	28.6
P₁	50.4		43.8	50.0		43.8		16.0	27.8
^(*) in product units
(B) Routing and schedule of the selected ship
Source Port	Departure		Destination Port	Port's last visit		Arrival		Waiting time to enter⁽ⁿ⁾	Lay time
Source Port	Date	Time	Destination Port	Date	Time	Date	Time	Waiting time to enter⁽ⁿ⁾	Date	Time
H₃	May 11	2.24pm	H₁	May 7	7.12am	May 12	9.36am	0:00	May 12	9.36am
H₁	May 13	3.37pm	H₃	May 11	2.24am	May 14	10.49am	0:00	May 14	10.49am
H₃	May 15	7.12am	H₂	May 11	7.12am	May 16	7.12am	0:00	May 16	7.12am
⁽ⁿ⁾ in (hour:minutes)
(C) Routing and schedule of the selected ship (continue)
Destination Port	Loading Time(n)		Waiting time for supply/space(n)	Ready to Leave		Waiting time to leave(n)			Leaving time
Destination Port	Loading Time(n)		Waiting time for supply/space(n)	Date	Time	Waiting time to leave(n)			Date	Time
H₁	30:01		0:00	May 13	3.37pm	0:00			May 13	3.37pm
H₃	6:33		0:00	May 14	7.12pm	12:00			May 15	7.12am
H₂	22:38		0:00	May 17	5.50am	1:22			May 17	7.12am
⁽ⁿ⁾ in (hour:minutes)
(D) Information of each visiting port's storage
Destination Port	Product#		CD_ik	Remaining Demand(*)		Level of Storages(*) at ship's lay time		Available space in storage(*)	Loading/Unloading quantity(*)
H₁	P₁		27.30	0.0		40.8		-	28.6
H₁	P₂		26.80	0.0		50.4		-	43.8
H₃	P₁		25.00	0.0		21.1		46.9	0.0
H₃	P₂		21.80	16.0		36.7		14.3	16.0
H₂	P₁		20.23	28.6		23.6		31.4	28.6
H₂	P₂		18.05	27.8		7.0		34.0	27.8
^(*) in product units

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)
Test Problem (TP)	Planning Horizon (PH)	Exact Algorithm Solution	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)

Table Options

Download as excel

Test Problem (TP)	Planning Horizon (PH)	Exact Algorithm Solution	Multi-Heuristics based GA (40 runs repetition)
Test Problem (TP)	Planning Horizon (PH)	Exact Algorithm Solution	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]	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
[8]	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
[9]	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
[10]	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
[11]	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
[12]	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
[13]	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
[14]	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
[15]	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
[16]	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
[17]	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
[18]	Chia-Huang Wu, Kuo-Hsiung Wang, Jau-Chuan Ke, Jyh-Bin Ke. A heuristic algorithm for the optimization of M/M/$s$ queue with multiple working vacations. Journal of Industrial & Management Optimization, 2012, 8 (1) : 1-17. doi: 10.3934/jimo.2012.8.1
[19]	Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667
[20]	Jiangchuan Fan, Xinyu Guo, Jianjun Du, Weiliang Wen, Xianju Lu, Brahmani Louiza. Analysis of the clustering fusion algorithm for multi-band color image. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1233-1249. doi: 10.3934/dcdss.2019085

2018 Impact Factor: 1.025

Tools

Metrics

Tools

Article outline

Figures and Tables

2018 Impact Factor: 1.025

Tools

Figures and Tables

2018 Impact Factor: 1.025

American Institute of Mathematical Sciences