Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.20 No.4 pp.662-671
DOI : https://doi.org/10.7232/iems.2021.20.4.662

Scheduling for a Container Supply Chain to Minimize Costs Using the Meta-Innovation Approach

Ismail Husein*, Arif Suhada, Paitoon Chetthamrongchai, Andrej P. Peressypkin, Anis Siti Nurrohkayati, Vo Hoang Ca, Huynh Tan Hoi, John William Grimaldo Guerrero, M. Kavitha
Department of Mathematics, Universitas Islam Negeri Sumatera Utara, Medan, Indonesia
Andalas Prima Teknology. Medan. Indonesia
Faculty of Business Administration, Kasetsart University, Thailand
Belgorod State University, Russia
Department of Mechanical Engineering, Universitas Muhammadiyah Kalimantan Timur, Samarinda, Indonesia
Ho Chi Minh City Open University, Vietnam
Language department, FPT University, Vietnam
Departamento de Energía, Universidad de la Costa, Barranquilla, Colombia
Saveetha School of Engineering, Saveetha Institute of Medical and Technical Sciences, Saveetha University, Chennai, India
*Corresponding Author, E-mail: husein_ismail@uinsu.ac.id, syahril1@usu.ac.id
August 10, 2021 September 10, 2021 September 18, 2021

ABSTRACT


In this study, a problem of scheduling shipping lines for a container supply chain is addressed in order to minimize the costs of charging ships and the cost of maintaining the inventory of empty containers in the port by considering the time window of the port and the amount of fuel. This is a hard-NP problem and cannot be solved on a large scale with precise methods in a logical time. Therefore, to solve and optimize the model, a meta-innovative algorithm, genetic algorithm, has been used. Also, to increase the effectiveness of the genetic algorithm, the parameters of the algorithm are adjusted using the Taguchi method. Finally, a number of problems have been solved to show the performance of this algorithm and its computational results have been compared with the results obtained from GAMS software.



초록


    1. INTRODUCTION

    The world fleet expanded to more than nine billion dollars during 2012, reaching more than 1.5 billion deadweight tons (DWT) in 2012, an increase of over 37 percent in just four years. Container transport is regarded as a crucial part of the world's truly global supply chain. Numerous factors should be taken into account for ship route design, one of the most important of which is port service accessibility. In addition, timeline design plays a role in air pollution due to its impact on ship fuel consumption (Lei, 2022). Containers are moved by container shipping companies over scheduled routes. Several products such as manufactured goods, food, clothing and apparel are shipped in containers. Generally, shipping services operate within a fixed schedule and has an appropriate port arrangement, in a way that arrival and departure time at ports are specified and planned. Port schedules are posted on the APL website, and customers can set the delivery time of their shipments based on the dates announced on the website and determine the time required for reaching the port (Salido et al., 2011;Alharbi et al., 2014;Chang et al., 2010;Qi and Song, 2012). Therefore, container shipping is significant part of the world’s global supply chain.

    The network of container shipping lines includes many shipping lines that must be assessed for the route of each ship. Scheduling shipping lines is a planned decision at technical level made every three to six months. Port service accessibility is the first factor considered for ship route design, without which the ship route schedule design is not possible. The rotating time decreases when the ship’s speed is higher in container shipping lines, which leads to a lower number of ships required for transport. The present study aims to develop a model for scheduling shipping lines in each network of container shipping lines in order to minimize the overall ship costs, including the costs of charging ships and the cost of maintaining the inventory of empty containers in the port by considering the time window of the port and the amount of fuel. The remainder of the article is structured, as follows: Section 2 presents the research background, and Section 3 addresses the proposed mathematical model. Section 4 explains the solution method, and Section 5 focuses on the generation of initial solution. Section 6 presents computational results and section seven concludes and makes suggestions for future studies.

    2. RESEARCH BACKGROUND

    There are limited studies on the design of ship route schedule design. The first group of studies is related to designing a schedule at the technical planning level. In a research, Wang and Meng (2012) focused on a tactical-level liner ship route schedule design in a container shipping company with a high number of ports and different routes and a fixed sailing speed on each voyage leg (Wang et al., 2014). In another research, X and Song presented an optimal vessel schedule to minimize the total expected fuel consumption. In addition, the rotation time was randomly considered, meaning that ships arrived at a port of call no later than the announced time (Trappey et al., 2011). Wang and Meng (2012) considered a schedule for the ships existing on the route when uncertainty in port operations and scheduling were considered while assuming that the ships could make up for the delay by sailing across the ocean (Yan et al., 2009). In their previous research, Wang and Meng (2012) improved uncertainty at sea and ports by incorporating speed optimization. These scholars adopted a dynamic planning approach to a practical tactical liner ship route schedule design problem with a port time window. They assumed that each port on a ship route is visited only once in a round-trip journey. In reality, however, there are many routes where a port can be visited twice (Yin et al., 2011). Wang et al. (2015) developed their previous research with the assumption that each port on the route of the ship can be visited twice. In addition, they focused on the route of one ship instead of a container network with several shipping routes (Sun et al., 2012).

    Yan et al. (2009) developed a container routing model aiming at maximizing operating profit in order to set a schedule at operational level. In another research, Brouer et al. (2013) presented the Vessel Schedule Recovery Problem (VSRP) to evaluate a given disruption scenario and to select a recovery action balancing the tradeoff between increased fuel consumption and the impact on cargo in the remaining network and the customer service level. Other studies, such as those developed by Chang et al. (2010, 2011), He et al. (2010), Du et al. (2011), have focused on port operations. Sun et al. (2012) created a general simulation platform, which aims to provide a flexible modeling system. Yan et al. (2009) introduced a distributed agent system for dynamic port planning and scheduling and examined their hypothesis with a case study. Salido et al. (2011) developed a planning technique for solving the container stacking problem and a set of optimized allocation algorithms for solving the berth allocation problem independently. Moreover, He et al. (2010) postulated a strategy for resolve the issue of sharing internal porters across multiple container terminals and selected a near-optimal solution using an optimization method.

    Alharbi et al. (2014) examined a practical liner shipping schedule design problem with port time windows for container supply chain networks. They proposed a mixedinteger nonlinear non-convex model that incorporates the availability of ports to minimize the sum of ship cost and fuel cost while considering the port time window. In the end, the model was reformulated as an integer linear optimization model and was solved applying an iterative optimization approach.

    3. PROPOSED MATHEMATICAL MODEL

    In order to better design the mathematical model, the symbols, variables and parameters are defined first, followed by presenting the objective function and related constraints. Moreover, the necessary explanations of the details of the mathematical model are provided below.

    3.1 Symbols and Variables

    The symbols and variables used in the mathematical model are presented below:

    R shows the series of shipping routes and P indicates the set of ports, in a way that the route of a ship rR is shown, as follows:

    P r 1 P r 2 P r N 1 P r 1
    (1)

    PriP shows the port corresponding to the i-th port of call, and Nr is the number of ports existing on the route of the ship. The set of ports of call on the r route are defined, as follows:

    I r = { 1 , 2 , 3 ,   ,  N r }
    (2)

    • trij : the time (day) required for a ship to move from the i-th port to the j-th port on the r route.

    • W: total days of the week, W = {0,1,2,3,4,5,6}, where zero is indicative of Saturday, one shows Sunday, and…

    • t r i a r r : time of arrival at the i-th port of call on the r route, t r i a r r W .

    • t r , N r + 1 a r r : the time (day) required by a ship to return to the first port of call on the r route.

    • mr : the number of ships existing on the r route.

    • x r i h : the number of empty containers reserved at the i-th port on the r route.

    • z r i w : { 1 0 : a binary variable; 1, if the ship arrives at the i-th port of call on the r route in the w day of the week. Otherwise, 0.

    • z r i b w : { 1 0 : a binary variable; 1, if the ship arrives at the b-th harbor of the i-th port of call on the r route in the w day of the week. Otherwise, 0.

    In addition, fuel consumption (tons/miles) is considered as a function shown below:

    g r i = l r i a r i ( β )
    (3)

    3.2 Parameters

    Several parameters are used in the proposed mathematical model, as shown below:

    • α : Ship fuel prices (unit/ton)

    • δ b w : 1, if the bBp port is free in the w day; otherwise, 0.

    • β and ari : coefficients in the fuel consumption function (ari > 0)

    • Bp : the set of docks of the P port

    • C r s : the costs of charging ships existing on the r route

    • C r k : the cost of maintaining the inventory of empty containers at the i-th port in the r route

    • Lri : the distance between the i-th port and the j-th port in the r route

    • t r i p o r t : the time passed by a ship at the i-th route in the r route

    • t r i m i n : the shortest time expected for shipping to the i-th port in the r route

    • m r m a x : the maximum number of ships existing in the r route

    • x r i h m a x : the maximum number of empty containers reserved at the i-th port in the r route

    • v r m a x : the maximum ship speed in the r route

    • z + : the set of positive integers

    According to the mentioned symbols, parameters and variables, the mathematical model proposed encompasses a five-expression objective function and 14 sets of constraints, as described below:

    M i n ( r R C r s m r + i p r R C r k x r i h + α r R i I r l r i a r i β )
    (4)

    Accordingly, the objective is to minimize the total costs of recharging ships, costs of inventory of empty containers in the port, and costs of fuel.

    0 t r i a r r 6 r R
    (5)

    t r i j { t r i m i n . [ I r i 24 v r m a x ] } r R , i I r
    (6)

    t r i + 1 a r r = t r i j + t r i p o r t + t r i a r r r R , i I r
    (7)

    t r + N r + 1 a r r = t r i a r r + 7 m r r R
    (8)

    m r { 1.2.3.   . m r m a x } r R
    (9)

    x r i h { 1.2.3.   . x r i h m a x } r R
    (10)

    t r i a r r z + r R , i I r
    (11)

    Constraints (5) guarantee solution symmetry. Constraints (6) indicates that ship cannot travel at speeds in excess of the speed limit. Constraints (7) defines the relationship between a time of a round trip. Constraints (8) shows the time of return to the first port of call on the return path. Constraints (9) demonstrates that the number of ships does not exceed the maximum number of ships and is also a positive integer. The time of arrival at each port of call is a non-negative integer shown in Constraints (11). The second set of constraints show the time of week for arrival at each port of call in the network:

    w W w z r i w = t r i a r r 7 k r i r R , i I r
    (12)

    w W z r i w = 1 r R , i I r
    (13)

    z r i w { 0.1 } r R , i I r
    (14)

    k r i { 0.1.2. . m r 1 }   r R , i I r
    (15)

    The day of arrival at the port of call on the route is shown by constraints (12), whereas constraints (13) demonstrate that each ship must arrive at a port of call in each week. Constraints (14) define the binary variable, and the kri auxiliary variable is defined as a non-negative integer. The third set of constraints points out the accessibility of ports:

    r R t r i p o r t = 1 z r i b w + r R t r i p o r t = 2 ( z r i b , w 1 + z r i b w ) δ b w   b B P w W
    (16)

    z r i b w z r i w r R , i I r . b B P . w W
    (17)

    z r i b w { 0.1 } r R , i I r . b B P . w W
    (18)

    According to Constraints (16), an available port cannot serve more than one ship in a day. Moreover, Constraints (17) and (18) indicate that each ship can use each port of call within a week.

    4. THE PROPOSED GA SOLUTION METHOD

    Since the problem in the present study is an NP-hard problem, it is impossible to use precise methods for solving the problem in reasonable time. Therefore, heuristic or metaheuristic methods should be used to solve the problem. In this research, the genetics algorithm (GA) is applied to solve the problem. In addition, GAMS and GA are used to exhibit the solvability of the model at different dimensions. The GA implementation stages and the solution process are explained below.

    Algorithm 1. Pseudocode of the genetic algorithm

    • 1: t →0;

    • 2: Forming an initial population [P(t)];

    • 3: [P(t)]; population member assessment and sorting

    • 4: to be performed when the termination conditions are not realized

    • 5: P'(t); formation of new solutions

    • 6: P'(t); evaluation of new solutions

    • 7: [ P ' ( t ) Q ] applying genetics operators → P(t + 1); the next generation population

    • 8: T ← t + 1

    • 9: end (until)

    5. INITIAL SOLUTION GENERATION

    An initial population of chromosomes must be generated after determining the coding system and specifying the method of turning each solution into chromosome. In most cases, the initial population is created randomly. However, heuristic methods are sometimes used to increase algorithm quality and speed to generate the initial population. The size of the initial population often depends on the other coded string. For instance, the initial population selected must be definitely larger when there are 32-bit chromosomes in the problem, compared to 16- bit chromosomes. The cutoff point is often between 80 to 95%, whereas the probability of mutation is considered between 0.5 and 1 percent and the population size regarded in the range of 20-30. Based on the fit function, the selected chromosomes are allocated a real amount, which shows their value, and the GA stages continue. If there is a very low number of chromosomes, the GA will be less able to perform less combination operations, and only a small part of the search space will be discovered. On the other hand, the process of the GA algorithm will be slow if there is a very high number of chromosomes. According to the results, the use of the population will not be extremely effective as a result of some constraints that mostly depend on coding and the problem itself.

    5.1 Coding

    This is probably the most difficult problem solution stage of the algorithm method. Binary coding is one of the simplest coding techniques and the best conversion for genetic operators. In binary conversion, the members of the population become strings of zeros and ones. Figure 1 shows the chromosome coding structure.

    5.2 Population

    In the GA, the concept of population is similar to what actually exists in normal life. As the first stage of the GA, it is required to generate a set of doable solutions as the initial population. The members of this set are often selected randomly. However, some conditions are used in the optimization algorithms so that there is not an exces-sively scattered population. In addition, the number of population members depend on the type of problem. In fact, the number of members is a parameter that can be changed by improving the accuracy of solutions and search convergence speed. While an eight-member population might be completely suitable for some problems, a population with more than 100 members might not be sufficient for other problems. Therefore, it is best to specify the population within the range of 10-160 members.

    5.3 Population Size

    Equation (19) is used to calculate the population size:

    N p o p = 1 / 65 × 2 ( 0 / 21 × L c )
    (19)

    For instance, if each chromosome has a length of 25, then we will have: N p o p = 1 65 × 2 ( 0 / 21 × 25 ) , or if the length of each chromosome is equal to 25, the population size will be equal to 270.

    5.4 Roulette Wheel Selection

    The roulette wheel is one of the most suitable random selection methods, in which the probability of selection corresponding to each chromosome is estimated based on its fitness. In this regard, if fk shows the fit value of the k-th chromosome, the probability of survival corresponding to that chromosome will be as shown in Equation (20):

    P k = f k i = 1 n f i
    (20)

    Afterwards, the chromosomes are sorted based on Pk, and qk, which is the cumulative values of Pk, are obtained using Equation (21):

    q k = i k P i
    (21)

    In fact, the roulette wheel creates a random number between zero and one for selection of each chromosome, and the chromosome corresponding to the mentioned number is selected whatever the range of the number is.

    5.5 Mutation

    In nature, some factors, such as ultraviolet radiation, cause unpredictable changes in chromosomes. Since GAs follow the law of evolution, these algorithms use the lowprobability mutation operator. The mutation causes a search in the intact spaces of the problem, and the most important responsibility of mutation is to avoid convergence to local optimization. Figure 2 shows mutation and its function.

    In general, mutation prevents the GA from locating itself in local extremes. Each member is a value determined by the user that depends on the mutation possibility (Pm).

    5.6 GA Parameter Tuning

    The efficiency of metaheuristic algorithms is directly related to tuning its parameters so that the correct choice of parameter values increases the efficiency of the algorithm. The improper tuning of parameters could lead to improper solutions for the problem under study. While various statistical methods have been proposed for designing test, increasing the number of factors studied, complex and time-consuming calculations are performed in using a comprehensive approach such as complete factor experiments. Taguchi introduced a set of fractional factor experiments, which specifically reduce the number of tests required for assessment while maintaining the required information (1). In this project, control factors of Taguchi method include parameters of GA, population size and number of iterations, probability of crossover performance and probability of mutation performance. Three levels are used for analyzing the optimal values of parameters in Taguchi method, as shown in Table 1:

    For the factors considered from the standard tables of orthogonal arrays, the most suitable array is L9, which is presented in Table 2. The integer values in each column shows its level in each test. The goal of the method is to find optimal levels of significant and controllable factors and minimize the effect of confounding factors. The qualitative features of the values measured from the tests are turned into signal to noise (S/N). This rate shows the level of deviations in the solution variable. In this study, the lower the value of objective function, the better. Therefore, the (S/N) ratio has the feature of the larger the better. In the Taguchi method, this index is defined as Equation (22):

    S N = 10 × l o g 10 ( O b j e c t i v e f u n c t i o n ) 2
    (22)

    Five sample problems are considered for the implementation of the tests. Each of the nine different tests designed in the orthogonal array are implemented five times for each problem. Figure 3 shows the value of (S/N) for different GA levels. As observed, decrease of algorithm deviations occurs when the parameters of the problem are tuned for the algorithm, as follows: first-level crossover rate, third-level mutation rate, combination of the number of initial population and third-level generation, minimum value of second-level external weight and combination of number of particles and third-level generation.

    6. COMPUTATIONAL RESULTS

    After tuning the optimal levels of GA parameters, the GA results can be compared with exact solutions of GAMS 24.1.2 in terms of the value of objective function and solution time using coding in MATLAB. Equation 23 is applied to measure the relative gap between GAMS and MATLAB solutions:

    G a p = O p t i m a l   s o l u t i o n G A   o p t i m a l   s o l u t i o n O p t i m a l   s o l u t i o n × 100
    (23)

    Table 3 shows the input values of the most important parameters of the problem model:

    According to the presented model and its solution methods, some problems are generated as example and the problem is solved for each example. The results obtained from comparing the solution of 24 example problems with the results obtained from GA are presented in Table 4. A comparison of GA results with the optimal solution of GAMS 24.1.2 shows that the software is able to achieve an optimal solution in solving large-scale problems based on GA. On the other hand, the solution time of problems in two sections of GA and GAMS 24.1.2 indicates less solution time and is associated with a very slight increase in large scales.

    As observed in Figure 4, GAMS is unable to solve all problems. meanwhile, the GA could solve all the problems in reasonable time. There is a significant difference between GAMS and GA in terms of solution time with an increase in the problem dimension, which shows that the inability of GAMS to operate when there is an increase in the scale of the problem.

    According to Figure 5, the error of the meta-heuristic method is very small among the problems that have provided the ability to compare the GA with GAMS software, in a way that the maximum error rate is less than 1%. This confirms the high efficiency of the GA regarding the optimization of the mathematical model proposed in the current research.

    7. CONCLUSION

    This study modeled a scheduling problem for a container supply chain in order to minimize costs of recharging ships and costs of inventory of empty containers at the port, which is actually a planned decision technical level. The results of the present study could be used for real-world problems with a slight change. The results showed the effectiveness of displacement inside ports and fuel price on the overall costs, the optimal number of ships used, and the optimal scheduling table. The model presented in the current study was solved by GA for GAMS 24.1.2 at large scales. According to Table 4, the error percentage of the GA objective function was less than two percent in all solved problems, compared to the software, which demonstrated the efficiency of GA. It is not possible to solve the model at a reasonable time with available processing facilities for scales larger than 28 ports of call, which justified the use of the metaheuristic approach. According to Table 4, the time required for problem solving with GAMS 24.1.2 was extremely higher, compared to the GA. Therefore, with regard to the solutions obtained and very short time required for problem solving, the GA was reported to have high efficiency in this regard. It is recommended that scheduling problems be assessed and compared to container routing and the type of cargo transported between ports.

    Figure

    IEMS-20-4-662_F1.gif

    Coding structure of chromosomes in N-Ga.

    IEMS-20-4-662_F2.gif

    Mutation.

    IEMS-20-4-662_F3.gif

    Rate of (S/N) for the genetics algorithm at various levels of factors.

    IEMS-20-4-662_F4.gif

    A comparison of the solution time of different methods.

    IEMS-20-4-662_F5.gif

    Error percentage of the metaheuristic method in various problems.

    Table

    Genetics algorithm factors

    Orthogonal array of L9(34)

    Input values of parameters

    Computational results of GAMS and genetics algorithm

    REFERENCES

    1. Alharbi, A. , Wang, S. , and Davy, P. (2014), Schedule design for sustainable container supply chain networks with port time windows, Advanced Engineering Informatics, 29(3),
    2. Brouer, B. D. , Dirksen, J. , Pisinger, D. , Plum, C. E. M. , and Vaaben, B. (2013), The vessel schedule recovery problem (VSRP) – A MIP model for handling disruptions in liner shipping, European Journal of Operational Research, 224(2), 362-374.
    3. Chang, D. , Jiang, Z. , Yan, W. , and He, J. (2010), Integrating berth allocation and quay crane assignments, Transportation Research Part E: Logistics and Transportation Review, 46(6), 975-990.
    4. Chang, D. , Jiang, Z. , Yan, W. , and He, J. (2011), Developing a dynamic rolling-horizon decision strategy for yard crane scheduling, Advanced Engineering Informatics, 25(3), 485-494.
    5. Du, Y. , Chen, Q. , Quan, X. , Long, L. , and Fung, R. Y. K. (2011), Berth allocation considering fuel consumption and vessel emissions, Transportation Research Part E: Logistics and Transportation Review, 47(6), 1021-1037.
    6. He, J. , Chang, D. , Mi, W. , and Yan, W. (2010), A hybrid parallel genetic algorithm for yard crane scheduling, Transportation Research Part E: Logistics and Transportation Review, 46(1), 136-155.
    7. Lei, N. (2022), Intelligent logistics scheduling model and algorithm based on internet of things technology, Alexandria Engineering Journal, 61(1), 893-903.
    8. Qi, X. and Song, D. P. (2012), Minimizing fuel emissions by optimizing vessel schedules in liner shipping with uncertain port times, Transportation Research Part E: Logistics and Transportation Review, 48(4), 863-880.
    9. Salido, M. A. , Rodriguez-Molins, M. , and Barber, F. (2011), Integrated intelligent techniques for remarshaling and berthing in maritime terminals, Advanced Engineering Informatics, 25(3), 435-451.
    10. Sun, Z. , Lee, L. H. , Chew, E. P. , and Tan, K. C. (2012), MicroPort: A general simulation platform for seaport container terminals, Advanced Engineering Informatics, 26(1), 80-89.
    11. Trappey, C. V. , Lin, G. Y. , Trappey, A. J. , Liu, C. S. , and Lee, W. T. (2011), Deriving industrial logistics hub reference models for manufacturing based economies, Expert Systems with Applications, 38(2), 1223-1232.
    12. Wang, S. and Meng, Q. (2012), Liner ship route schedule design with sea contingency time and port time uncertainty, Transportation Research Part B: Methodological, 46(5), 615-633.
    13. Wang, S. , Alharbi, A. , and Davy, P. (2014), Liner ship route schedule design with port time windows, Transportation Research Part C: Emerging Technologies, 41, 1-17.
    14. Wang, S. , Alharbi, A. , and Davy, P. (2015), Ship route schedule based interactions between container shipping lines and port operators. In: C.-Y. Lee, Q. Meng (Eds.), Handbook of Ocean Container Transport Logistics: Making Global Supply Chains Effective, International Series in Operations Research & Management Science, Elsevier, Vol. 220, 279-313,
    15. Yan, S. , Chen, C.-Y. , and Lin, S.-C. (2009), Ship scheduling and container shipment planning for liners in short-term operations, Journal of Marine Science and Technology, 14(4), 417-435.
    16. Yin, X. F. , Khoo, L. P. , and Chen, C.-H. (2011), A distributed agent system for port planning and scheduling, Advanced Engineering Informatics, 25(3), 403-412.
    Do not open for a day Close