Study on Joint Dispatching of Bulk Carriers Berth and Ship Unloader ()
1. Introduction and Motivation
Coal resources are the most important part of China’s energy supply. Coal terminals play an important role in the port cargo transportation in some areas in China. Iron ore resources are the raw materials for industrial steel. The low self-sufficiency rate of iron ore in our country requires a large amount of imports from Australia and other countries. Shipping is the main mode of transportation for iron ore. Under the excess shipping capacity and fierce competition in the shipping industry, enhancing the efficiency of bulk terminals, shortening the time for shipping in port and enhancing the competitiveness of bulk terminals will directly affect customer experience and satisfaction. Berths are the most important docking facilities for bulk terminals. The unloader is the most important loading and unloading equipment for bulk terminals. Under the conditions of the number of berths, the berth depth, the length of shoreline, the number of unloaders and the efficiency of ship unloaders, the rational allocation of berths and ship unloaders directly affect the operational efficiency of the entire terminal.
In this paper, berths and ship unloaders are considered as scarce resources for bulk terminals. The dynamic allocation problem of berths and unloaders is studied. Aiming at reducing the total port time in ships, a feasible way to rationally allocate terminal resources is explored. Explore the way to allocate the wharf resources rationally, establish the operational research optimization model, design the algorithm, and evaluate the validity of the algorithm through concrete examples. The main contribution of this paper is to establish a mixed integer optimization model, design heuristic algorithms, adjust algorithm parameters, and provide methods for solving similar problems. The limitation is that only the impact of the two resource scarcity factors of the ship unloader and the berth is considered, and other factors that may affect the scheduling are ignored, and the actual problems are slightly different. In addition, the algorithm innovation is not sufficient.
2. Literature Review
In view of the optimization problems related to port scheduling, scholars at home and abroad have conducted in-depth discussions and researches. Bierwirth and Meisel (2009) [1] summarized the academic researches on port operations in three parts according to berth allocation, ship unloader allocation and ship unloader scheduling. The existing research results have been systematically divided and described. Bierwirth and Meise (2015) [2] also point out that the integrated research of berth and ship unloader scheduling. The integrated optimization research that considers actual production factors is more realistic Situation, more practical guidance. Imai et al. (2001) [3] proposed a dynamic allocation model for discrete berths. The objective was to minimize the total service time and solve the problem by Lagrange relaxation heuristic. A large number of computational experiments were carried out to prove the feasibility of the algorithm. Based on the Imai (2001) dynamic programming model, Nishimura et al. (2001) [4] further extended the genetic algorithm to obtain the approximate optimal solution, and the calculation results were more effective, indicating that the genetic algorithm is suitable for practical problems. Park and Kim (2003) [5] first proposed the joint scheduling problem of continuous berth and ship unloader, designed a two-stage solution algorithm. In the first stage, the entry position and time of each ship were determined. Then the number of ship unloaders assigned to each ship was obtained. In the second phase, the specific ship unloader is assigned to the designated ship by means of dynamic planning. Later, Kim and Park (2004) [6] considered various constraints related to ship unloader and established a mixed integer programming model. The optimal solution was obtained by using branch and bound method. Imai et al. (2008) [7] applied genetic algorithm to solve the scheduling problems of discrete berths and ship unloaders. The chromosomes in the algorithm are berths, ships and orders. The fitness function values are calculated by joint scheduling of berths and ship unloaders. Han Xiaolu et al. (2009) [8] studied the dynamic berth allocation with priority of ships, and solved the problem by genetic algorithm, tabu search and simulated annealing hybrid algorithm respectively. Golias et al. (2010) [9] proposed a 2-opt neighborhood search algorithm to solve the small-scale problem based on the research status of the discrete berth allocation problem. In addition, a genetic algorithm for solving large-scale problems is also proposed. Lee et al. (2010) [10] established a hybrid integer programming model for the distribution of discrete berths and ship unloader, and designed a genetic algorithm to solve the problem. Experiments on the examples demonstrate the effectiveness of the algorithm. Raa and Dullaert (2011) [11] also studied the issue of the joint distribution of berths and ship unloaders. The author used the MILP model to solve the factors, such as ship characteristics, preferred berths and processing time. Junliang He (2015) [12] studied the distribution of berth and ship unloader, introduced the energy consumption of ship unloader equipment into the model, and built a mixed integer programming model with the objective of minimizing the energy consumption and the delay time of the ship. The model was evaluated by using Genetic algorithm to solve, verify the “save time and energy” model validity. Karam and Eltawil (2016) [13] constructed a distribution model for berth and ship unloader, in which the berth allocation sub-model aiming at the lowest operating cost and the unloader allocation problem aiming at minimizing the average working time per ship.
From the content point of view, the research on port dispatching gradually turns from the independent study of berth allocation and ship unloader scheduling to the integrative research on the joint dispatch of berth and ship unloader. Research on port dispatching is often linked with facilities and physical factors of wharf operations such as berth length, wharf depth, yard space and tide height, and is closer to the reality of production. The natural factors such as weather and water flow affect the homework are also researched by some scholars to make them more appropriate to actual production.
From the perspective of research methods, operations research is the main method to solve the scheduling problem of berths and ship unloaders. The mathematical models are developed from linear programming to integer programming, target programming and nonlinear programming. In the model solving, often combined with the idea of genetic evolution, developed a variety of heuristic algorithms, or combined with simulation techniques to simulate the problem. Looking at the research results of berth dispatching, ship unloader distribution, ship unloader scheduling and integration optimization of domestic and foreign scholars in recent years, the dispatch of forward-looking service facilities for containers and bulk terminals can be solved to a large extent.
3. Problem Description and Model Establishment
3.1. Problem Description
Bulk terminal is the key logistics node connecting sea and land transport, with bulk cargo handling and distribution functions. A typical bulk terminal is mainly composed of berthing shoreline and cargo yard, equipped with unloader to unload the cargo from the ship and equipped with conveyor belt network to deliver goods to the designated stack yard; stack yard with the stacker reclaimer in accordance with the instructions of the cargo pile pickup operation, and with the conveyor belt network, and loading machine to complete the goods transport function. The above core equipment and other auxiliary equipment are coordinated to operate the production operation system that constitutes the bulk terminal.
In this paper, we study the joint scheduling problem of discrete berths and ship unloader, consider the distribution of berths and the scheduling of ship unloader, set up the objective function with the goal of minimizing the total port time of the ship, establish mathematical optimization model, finally determine the time of entry, parking location, the number of ship unloaders assigned to each ship in operation.
3.1.1. Berth Allocation Problem
The main factors that determine the distribution of berths are berth-related information such as the number of berths, berth length, berth depth, etc., as well as relevant information of the ship, such as the schedule of the ship, the load of the ship, draft of the ship, etc. The distribution standard of berths is to minimize the waiting time of the ship, Maximize the utilization of berths. In this paper, the object of study is discrete berths. The rational allocation of berths is the key factor that affects the total time of a ship in port.
3.1.2. Ship Unloader Scheduling Problem
After determining the berth assigned by the ship, the unloader combination is determined according to the unloader allocation rules and the unloader usage, and a reasonable unloader unit is assigned to the berth. Dynamically allocating the number of ship unloaders served by each berth at each moment can overcome the limitations of static dispatching of ship unloaders and reduce the idleness of ship unloaders and make full use of ship unloader resources so as to effectively reduce the working hours of ships in port, Reasonable arrangements for the scheduling of ship unloaders are another key factor affecting the total time of a ship in port.
3.2. Model Establishment
3.2.1. Model Assumptions
1) Berth type is discrete berth, all berths are distributed on the same shoreline;
2) The ship’s planned arrival time is known, the length of the ship, draft and load are known;
3) Unloader on the same track, can be moved between different berths, ship unloader dispatching time between different bets neglected;
4) Do not consider the impact of other physical factors on the dockwork.
3.2.2. Parameter Setting
1) B is the berth number of sets,
, i is an integer.
2) V is the Collection of ships,
, j is an integer.
3) Q is the Collection of unloaders,
, q is an integer.
is the minimum number of ship unloaders that can simultaneously operating in ship j per hour, and
is the maximum number of ship unloaders that can simultaneously operating in ship j per hour.
4) One research period are L days, t is the moment in the research cycle,
.
5)
is the time ship j arrived at the port.
6)
is the load of the ship j.
7)
is the working efficiency of ship unloader q.
8) M is an infinite positive number.
3.2.3. Decision Variables
9)
: When the ship j enter the berth i,
, otherwise
.
10)
: When the ship j before j' entering the berth,
, otherwise
.
11)
: Unloader q assigned to the ship j,
, otherwise
.
3.2.4. Auxiliary Decision Variables
12)
is the time for the ship i to enter the berth j;
13)
is the time for ship unloader q to start working for the ship j;
14)
is the departure time of ship j;
3.2.5. Objective Functions and Constraints
The objective function: The ship has the least total time in port:
(3-1)
Restrictions:
(3-2)
The ship j must enter the berth and can only enter a berth;
(3-3)
The time of arrival of a ship must be later than the time of arrival;
(3-4)
Ships must be unloaded to leave the port;
(3-5)
When the berths i provide service to the ship j and j' in succession, the service for the ship j' must be after the service of j has been completed;
(3-6)
At least one ship unloader serves the ship j, but does not exceed the maximum number of ship unloaders that are capable of simultaneously working on the ship;
(3-7)
When ship unloader q continue to serve ship j and ship j', ship unloader q need to be able to participate in the unloading of ship j' after ship j leave port.
(3-8)
Bridge unloader with orbital constraints, can not cross each other;
4. Solution
4.1. Overview of Genetic Algorithms
The genetic algorithm was developed and established by Professor J. Holland [14] . The main theories originated from Darwin’s theory of evolution and Mendel’s theory of inheritance. They gradually evolve to the optimal solution through the iterative process. Finally, the approximate optimal solution of the problem was converged. Belong to Evolutionary Algorithms [15] . Genetic algorithm has the process of coding, selecting, crossing, mutation, decoding and so on. It constructs the optimization-oriented iterative process with parameters space of encoding space representation, setting parameters of intersection and mutation rate, and uses fitness function as evaluation basis.
4.1.1. Genetic Algorithm Elements
Genetic algorithm has five basic components: the solution of the coding scheme, the initial population settings, fitness function design, genetic operator design and genetic parameters set.
1) Coding and decoding
The solution of practical problems needs to be expressed as chromosomes. The actual problem of generating chromosomes is called coding, which transforms the feasible solution of a problem from its solution space (phenotype space) to the search space that genetic algorithm can handled.
2) The initial population settings
The initial population is a set of solutions. Each individual represents a solution to the problem. The initial population is set to ensure the solution of the problem. When the optimal solution is slowed down, the size of the population is moderately increased. However, if the population size is too large, the calculation will be affected speed, population size calculation can be based on data from repeated tests.
3) Fitness function design
The fitness function is used to evaluate the individual’s strengths and weaknesses. The fitness value is the only evaluation indicator of individual’s survival. Whether the fitness function is reasonable or not determines the evolutionary behavior of the population. Therefore, the selection of the fitness function is very important.
4) Select, cross, mutation operator
Genetic operators include three basic forms: selection, crossover and mutation, which constitute the core of search capability of genetic algorithms. They are the main carriers of the phenomenon of reproduction, hybridization and mutation in natural selection and evolution. The choice is to select good individuals in the initial population based on individual fitness values, and by choosing to give outstanding individuals more opportunities to breed the next generation, essentially Darwin’s natural selection theory. The crossover is a certain probability exchange of the gene sequences corresponding to the two chromosomes. The purpose of the crossover is to pass on the original good gene patterns to the next generation and hope that the next generation will become a better new individual after being reorganized. Variation is the random change of the value of one or more genes on a chromosome with a certain probability in order to form a new individual, usually with a lower probability of mutation. Mutation is to change the random direction of individuals, which is good for population updating genes, increasing population diversity and avoiding the algorithm’s precocious jump out of local optimum, which determines the local search ability of the algorithm and helps to find the global optimal solution.
5) Genetic parameters set
Control parameters in genetic algorithm include population size, crossover probability, mutation probability, evolution termination condition and so on. These parameters have a very important effect on the performance of the genetic algorithm. The size of the population affects the speed and quality of the solution. When the size of the population is small, the diversity of the population is small, the computation is small and the computing speed is faster, which may lead to premature phenomenon. When the population size is too large, the population diversity is more sufficient, the calculation is large and the operation efficiency will be reduced. The crossover probability controls the execution frequency of crossover operator. As the main genetic operator, the crossover probability generally takes a larger value in order to obtain a new gene pattern quickly. The range of the crossover probability is about 0.4 - 0.99. The mutation probability must be weighed against the protection of good individual genes and to prevent the problem of premature convergence. If the mutation probability is too large, the high individual gene damage rate in the population makes the search tend to be random, convergent slowly or not converge; if the mutation probability too small to produce new individuals with poor ability, prone to premature phenomenon. The general recommended value range between 0.0001 - 0.1. The number of iterations sets an iteration number, which is generally recommended to be 100 - 1000 as the termination condition.
4.1.2. Genetic Algorithm Standard Process
Standard Genetic Algorithms usually refers to random, iterative and widely adaptive search algorithms based on natural selection and population genetics proposed by Holland. The two main ideas are the survival of the fittest selection mechanism and self-learning information exchange principle.
Step 1: The solution of the problem model is coded into chromosome genes according to certain rules, and randomly generated initial population with the specified population size as the basis of evolution;
Step 2: Calculate the fitness value of each individual in the population as the basis for evaluation of the genetic operation;
Step 3: Judge whether the optimization of the termination conditions, if the output is the best solution, and the end of the calculation; Otherwise, go to Step 4, to continue iteration;
Step 4: Carry out the survival of the fittest according to the fitness value, retain or copy the individuals with high fitness value according to certain rules, and eliminate the individuals with low fitness value;
Step 5: Generate a new individual by performing gene crossover with the set probability and certain rules;
Step 6: Execute the gene mutation operation with the set probability and certain rules to generate a new individual;
Step 7: the population change, return to Step 2;
The advantage of standard genetic algorithm is that it has strong robustness, parallelism and directionality. However, compared with the adaptability of evolutionary process, the fixed parameter setting actually limits the performance of genetic algorithm, and the adaptive parameter setting is closer the rules of natural evolution, thereby enhancing the efficiency and effectiveness of genetic algorithms. Based on this consideration, the improved genetic algorithm will be adopted for solving the model in this paper.
4.2. Genetic Algorithm to Solve
4.2.1. Genetic Algorithm Coding
In the berth allocation model, the key decision is to determine berthing berths and berthing time. In this paper, the algorithm of ship unloader distribution is not written as a chromosome encoding, but the ship unloader assignment in the solution by the fitness function to be limited. The ship unloader distribution in the algorithm needs to assign constraints according to the unloader, and the unloader combination that does not satisfy the allocation constraints sets its fitness function to zero. Considering the content and model of this paper, the integer coding rule [7] is adopted to solve this problem. The length of chromosome is the number of arriving ships plus the number of berths minus 1 [16] . Taking one of the six arriving ships and three berths during the study period, the chromosome coding methods are shown in Tables 1-3.
The values of the berths in the above table are randomly generated by the computer to be an integer between 1 and 3. Here we take i = [1 2 3 1 2 3] as an example. Where the value is the key to berth allocation in the genetic algorithm,
Table 1. Chromosome initial coding.
and # = i means that the numbering ship is assigned to the berth number. According to the above genetic algorithm berth allocation corresponds to the chromosome encoding form as follows in Table 2.
The first line, whose value is expressed as [1 4 0 2 5 0 3 6], is the form of the chromosome in the genetic algorithm. The first line indicates that there are 6 ships in a schedule and the second line indicates that there are 3 berths at the wharf, of which 0 is used in the genetic algorithm to distinguish the berths of each berth. This chromosome means that No. 1 and No. 4 ships are assigned to berth No. 1, No. 2 and No. 5 berths to berth No. 3, and numbers 3 and 6 to berth No. 3. After finishing, the distribution of berths can be decoded. The ships on each berth are shown in Table 3.
This integer coding design takes into account not only the berths of arriving vessels but also the order in which the berths are serviced at that berth as well as the practical constraints that the same berth can serve only one ship at the same time, the coding of the chromosomes did not duplicate the description of the study.
4.2.2. Algorithm Parameter Settings
Population size: According to the coding rules, for m berths and n ships, chromosome codes are generated by arranging natural numbers from 0 to m, and a berth allocation plan is obtained. In order to improve the adaptability of initial population and the diversity of population, we first generate N times population size individuals, and then select the non-repetitive individuals with higher fitness as the initial population according to the set population size.
The maximum number of iterations: In this paper, the number of iterations to achieve the maximum termination conditions for the algorithm, based on the actual case analysis needs, combined with the test results to be adjusted.
Crossover, mutation probability: Based on experience and repeated test results, Chromosome crossover, mutation with the following probability. The first chromosome insertion mutation, this mutation method is set to 45% probability. The second way is transposition variation, the probability of this mutation is set to 45%.
4.2.3. Fitness Function Settings
The design of fitness function is the key to the algorithm. In this paper, the algorithm solves the constraint problem after the initial solution is generated, and rejects the solutions that do not meet the constraint. In addition to the berth length and water depth constraint, this paper is mostly a logic constraint, with berth length and water depth as hard constraints. When the length and water depth are not satisfied, the fitness value is zero. In other constraints, berth allocation and ship unloader distribution are the main targets, taking the ship’s total port time as the main consideration. When the berth is available, the ship can enter the port, when the unloader is available, the unloader can be added to the ship unloader unit for operation. After processing the constraints, the objective function of total time in port is calculated, and its function value is used as the only criterion for evaluating the individual’s merits.
Fitness function:
4.2.4. Algorithm to Solve the Process
The joint distribution problem studied in this paper consists of two levels: distribution of berths for ships and distribution of unloading units for anchored ships. Among them, the distribution of berths mainly considers the order of berths assigned to each ship and the order of each berthing ship. The distribution of ship unloader mainly considers the real-time status of ship unloaders near berths and the distribution rules of ship unloaders. The algorithm design mainly considers the berth scheduling problem, and adds the unloader constraint when calculating the fitness function to form the optimal unloader combination.
1) Berth scheduling strategy
Step 1: At the moment t the ship j arrives,to see if there are any berths available. If there is currently a berth available, the ship is allowed to enter the berth i smoothly and the registered berths i are recorded. The vessel entering the berth is included in the work ship collection WS (work ship) and the berths i occupied are marked as occupied and iteratively entered into Step 3. Otherwise, the vessel is included in the NWS (not work ship), iteration Go to Step 2.
Step 2: After arriving in port, vessels that have not successfully entered the berth are checked to see if any qualified berths can be parked after the ship has completed the work to leave the berth, if the conditions for entering the port are satisfied, the ship enters the operation, iterating to Step 3; if all The berth will not be able to serve, and the ship will continue to wait and continue looping with Step 2.
Step 3: According to the berthing dock arrival time
, loading capacity
and ship unloader operating efficiency
, in accordance with the ship unloader can not cross the distribution rules to determine required unloader combination of the ship j, the unloader occupied by the vessel j is marked as occupied.
2) Unloader allocation strategy
Step 1: Ships moored at time t, The ship unloader is assigned according to the information of ship’s weight and the unloader use situation, and obey the rules that unloader can not be crossed. Then the ship unloader in working status is marked as occupied. According to the number of ship unloader and its efficiency to calculate and update the ship’s departure time, go to Step 2.
Step 2: When the ship completes the unloading operation, it releases its occupied berth and ship unloader, respectively marks the released berth and ship unloader as idle, and adds the ship which has completed the unloader to the shipwreck WFS ( work finished ship).
3) Joint distribution process
Step 1: Through the judgment of the physical conditions such as the time of arrival of the ship, the length of the ship, the draft of the ship, the carrying capacity of the ship, the length of the berth and the depth of the berth, the berth scheduling strategy is adopted to arrange the ship to berth.
Step 2: If the berth has an idle tag, the arriving ship enter the berth according to the berth scheduling strategy, and implement Step 1 of berth scheduling strategy. If berths are all marked as occupied, execute Step 2 of berth scheduling policy.
Step 3: In WS, select the earliest departure vessel j and release the berth and unloader occupied by the vessel j at the end time
of the vessel’s operation, and go to Step 4.
Step 4: For ships that have arrived in port but have not been able to enter in time, select the ship j' from the NWS collection and adopt the berth scheduling strategy to enter the port and go to Step 5.
Step 5: Determine whether all the ships arriving at the port have finished their work. If all the unloading operations are completed, stop calculating the output. Otherwise, go back to Step 3.
Step 6: After the completion of berth allocation and ship unloader, according to the ship load and ship unloader efficiency, to calculate ship work time, plus the ship’s waiting time is the ship’s port time;
5. Numerical Analysis
5.1. B Terminal Profile
B dock’s area are 260,000 square meters, it’s unloading berth pier are 527 meters long, with two 70,000-ton unloading berths, depth of both berth is −12.5 m, berth length are 240 m and 245 m. B dock’s loading dock berth are 400 m, dedicated railway line length are 1.3 km, design and handling capacity are 14 million tons, pick-off capacity of yard are 750,000 tons, equipped with six unloaders, two loading machines, nine bucket wheel stacker reclaimer, 1 Taiwan-installed train card machines and electronic measurement, the central control system and other advanced equipment, with water supply, drainage, control, power supply, watering and dust removal, sewage treatment, communications and other facilities, the implementation of computer management, formed a coal loading and unloading ships, automobiles and electronic weighing, stacking conveyor system of the professional production line a total of 1344 processes. B pier ship unloader efficiency and energy consumption information is as follows Table 4.
In this paper, we collect the relevant data of ship dispatching in terminal B, and through the analysis and arrangement of the data, we determine the density of ships arriving at port each month, the carrying capacity of ships and the draft range of ships. Within 10 days of the formation, 12 ships the data collected in port are as follows Table 5.
5.2. Calculation Results
The number of berths is 2, the number of ships is 12, the number of ship unloaders is 6, the maximum number of ship unloaders can be operated at the same time for each ship is 3, and the operating efficiency of ship unloader is 50%. Set the population size to 50 and the number of iterations to 100 using the matlab R2014a software running on Intel (R) Core (TM) i7-4600U mainframe with Windows 7 operating system. The calculation results and scheduling scheme are as follows Table 6 and Figure 1.
The algorithm iterates to the 18th generation when the fitness function is the
Table 4. B Special Terminal Unloader Information.
Table 5. Terminal B Arrival Ship Data.
Figure 1. B Pier Genetic Algorithm Fitness iteration diagram.
Table 6. Genetically calculated results of Coal Terminal B Dispatch.
smallest. At this moment, the last vessel of the ship departs for 281.12 hours and the total time in port are 616.84 hours.
6. Conclusions
Through a large number of reading relevant literature, study and research methods, models, design algorithms, and the discretion of actual operation of bulk cargo terminals, a joint scheduling model of berths and ship unloaders with the least total port time in the port of navigation is constructed. Close to the actual production of bulk terminals: the actual case analysis of terminal B, the model close to the actual production and operation, put forward feasible solutions, based on the existing resources to improve efficiency, a certain degree of practical significance.
The problem of bulk cargo terminal dispatching is a complicated issue with many factors affecting: the factors of ship, unloader, yard and water depth, as well as uncontrollable factors such as tide, water flow and weather. The author’s research ability is limited and it is impossible to conduct a comprehensive study, can only focus on some of the factors, other factors are not considered, reducing the difficulty of solving the model.
In view of the limitations of this paper, the following perspectives are made: 1) To study the optimal scheduling problem from different perspectives of different terminals, for example, cost considerations, ship unloader constraints and time window constraints are still the focus of further research. 2) The influence of real-time dynamic factors such as available space and tide on the quay operations needs to be further explored. 3) The development and innovation of algorithms, various research practices show that no algorithm is superior to another algorithm absolutely, and that different algorithms may solve different problems with better results. Therefore, it is an important direction for algorithm research and innovation in solving such problems.