1. INTRODUCTION
With global economic integration and the improvement of container ship transportation technology, an increasing number of shipping companies have begun to pursue large economies of scale for container transportation. The demand has pushed container ships towards the large-scale direction, but large container ships can only berth in major deep-water ports. Under this condition, feeder line transportation is required to transfer freight to and from the main routes. This has developed rapidly and a hub and spoke mode for maritime transport has developed. The feeder transportation of container ships is inevitably the outcome of the development of international container transportation. Shipping schedules are a key factor that affects enterprise competitiveness and operational efficiency in optimising routes. Thus, designing a feeder line for container ships that reasonably saves operation time is crucial to shipping companies. In current shipping route optimisation studies, the sailing time between two ports is mostly calculated by using the linear distance to be divided by the speed based on paper maps. The disadvantage is that the error is too large, which can directly impact on the accuracy of route optimisation algorithms. An electronic chart system can provide reliable information, including the deep-water points, contours and danger zones. Such information can be used to precisely design routes between two ports, automatically detect risks, judge the rationality of routes and provide an accurate arrival time between two ports to optimise a route. Electronic charts contain more information than paper charts and there are several advantages in using an Electronic Chart Display and Information System (ECDIS) with Electronic Navigational Charts (ENC) over paper charts. The most obvious advantage is the integration of nautical chart, position fixing and navigational information. Other advantages include: real-time presentation of ship position in the nautical chart, automatic monitoring of the planned route, situation-dependent presentation of data, reduction of human errors in route planning based on the nautical chart, and the ability to set alarms in relation to ship position and movement. ECDIS is a system that aids the navigator in taking qualified decisions, is able to scan the area ahead of the ship, and warn the navigator of dangers.
The current literature on shipping schedules and course design, both local and overseas, mainly concerns trunk transportation of tankers, bulk carriers, container ships and other types of ships. Bremer and Perakis (Reference Bremer and Perakis2002) discussed liner transportation based on studies on bulk and tanker operations. The authors established a line-fitting optimisation model that can solve the optimal scheduling scheme of each vessel according to the cargo situation of a fleet over a certain period. Rana and Vickson (Reference Rana and Vickson2004; Reference Rana and Vickson2006) discussed the route optimisation problem regarding certain ships sailing on fixed routes in a region. They set the maximisation of a shipping company's profits as the goal, designed the routes and analysed the optimal selection of ship berthing order in the harbour. Based on the principle that ships never berth in unprofitable ports, the researchers also constructed a nonlinear mixed integer programming model to solve the problems in port selection and route optimisation by using the Lagrange multiplier method. Powell and Perakis (Reference Powell and Perakis2007) improved the earlier research of Bremer and Perakis (Reference Bremer and Perakis2002) on the ship scheduling method and established an integer programming model with the objective of minimising the total cost of operation and idle time when the capacity, service properties and route situations of a ship were known. They identified a reasonable scheduling method by comparing two examples. Cho and Perakis (Reference Cho and Perakis2006) studied the fleet size of a container liner company and liner route optimisation by selecting several routes and then analysing them by using a linear programming model. Song and Zhang (Reference Song and Zhang2005) proposed a heuristic algorithm to solve the problem of shipping cost minimum and the direction of container flow in the transportation network after studying the international container shipping network.
Christiansen and Nygreen (Reference Christiansen and Nygreen2011), Christiansen et al., (Reference Christiansen, Fagerholt and Ronen2004) and Fagerholt (Reference Fagerholt2001) extended the Vehicle Routing Problem (VRP) to the main routes for bulk carriers, and proposed soft-time window constraints for integrating collection and delivery, as well as a ship scheduling model for multi-type ships. Hsu and Hsish (Reference Hsu and Hsish2007) studied the hub and spoke network problems of marine container transport to minimise operating and inventory costs. A dual objective function model was established to determine optimal ship routes, ship types and frequency on each route, as well as to solve the axial–radial route network design problem of direct transport or transit port transportation. Pang et al. (Reference Pang, Zhou and Li2011) considered berth utilisation and studied the arrangement of the route and frequency of sailing to relieve berth congestion. They developed an optimisation model and a heuristic algorithm to solve the aforementioned problem. Karlaftis et al. (Reference Karlaftis, Kepaptsoglou and Sambracos2009) studied the route-planning problem for containerships based on the branch axial–radial network and developed an integer programming model. However, they ignored the time period spent waiting to berth. Jin et al. (Reference Jin, Xie and Li2008) studied time window constraints and space utilisation in terms of a spool–radial maritime transport model and established a scheduling model. They aimed to minimise the operating cost, solving the problem by using a particle swarm optimisation algorithm. The model only considered the branch operation cost of shipping and ignored the problem of route planning. Scholars, both local and abroad, have also discussed route design.
Christiansen et al. (Reference Christiansen, Fagerholt and Ronen2004) discussed the course design method based on the optimisation decision support system. Gunnarsson et al. (Reference Gunnarsson, Ronnqvist and Carlsson2006) integrated macroeconomic mathematical models into route design. Xu (Reference Xu2000) proposed a route design and surveillance method, and then implemented this method based on an ECDIS. Yin et al. (Reference Yin, Zhang and Sun2007) and Zhang et al. (Reference Zhang, Yin and YiCheng2011) designed a simplified marine simulator model and used it to calculate target ship positions when the ship starts and ends a turn. In the marine simulator, a trainee controls the position of his/her own ship. The precision of the hydrodynamic mathematical model of the ship was relatively high. In general, no hydrodynamic model corresponded to the target ships planned by an instructor. The navigation of the target ships along a planned sea route was set by the instructor, along with the speed and course of the ships. This study introduced a simplified mathematical model for target ships and explained the calculation of the starting position, instantaneous position, course and ending position of ships.
2. PROBLEM DESCRIPTION
Regional container ships primarily provide transportation services to major liners by acting as an extension to the main services. Aside from the general characteristics of the main transportation, container feeder transportation has numerous other features, such as short distances between ports, less freight and less port resource. Compared with container ships on the main routes, regional container ships usually require less space and have lower speed, more flexible operation, shallower draft, easier navigation and fewer constraints from ports and waterways. The competition in regional container transport does not only depend on cost, but also on the quality and efficiency of service. Sometimes, the latter is valued more by customers. Therefore the objective is to design routes that can minimise total sailing time and reduce costs under the condition of satisfying service quality and efficiency. Regional container lines include coastal and inland river regional container transports. This article mainly discusses the inland feeder between hub and feeder ports, i.e., hub and spoke feeder transportation.
Actual sailing data between hub and feeder ports are not available. Hence, we need to formulate the Turn Around Time (TAT), the amount of time required between the two types of ports. The sailing speed of ships used in previous literature is simply averaged when the TAT among main inland river ports is calculated. This method does not consider wind, current and the influence of ship manoeuvring performance at high speed. Therefore, the actual circumstances of underway vessels are not reflected accurately. In this research, actual environmental conditions, including the influence of wind and current on ship speed, are considered. An accurate calculation method for TAT is then designed by calculating the turning radius and sailing time according to ship manoeuvring performance.
The containers that require regional transport are unloaded in the hub port and delivered to different feeder ports through middle- and small-scale container ships in the hub port. Meanwhile, the containers that require main transport are brought back to the hub port. This situation is recognised as a combinatorial optimisation problem that consists of a Vehicle Routing Problem (VRP). The containers that need to be carried to feeder ports via a planned route must be loaded on the ship in the hub port and then unloaded in each feeder port before being loaded back to the hub port. The payload capacity and time constraints of the containers being carried to the hub port and sailing via feeder vessels must be addressed. Each feeder port can only be serviced by one ship. Overall, such constraints are nondeterministic polynomial time-hard problems limited by time windows, capacities and routes.
3. MODEL CALCULATIONS
3.1. TAT Calculation
The routes between the starting and destination ports are planned according to accurate channel data from ECDIS by using a route design method. In reality, underway vessels do not turn at the turning point. Instead, they turn in advance at a certain radius according to their manoeuvring performance. Therefore, the actual sailing time cannot be determined based on the total accumulated time of the straight line segment but on the combined accumulated time of the straight line and arc segments. The sailing time in the turning points is calculated to obtain an accurate TAT of the total voyage. The algorithm divides the planned route into n sections and captures one section of the planned course APB shown in Figure 1. Each sailing period is determined by the time consumed by a ship in linear AP 1, segmental arc P 1P 2, and linear P 2B. The calculation methods for sailing time in the straight line and arc segments are described below.
Figure 1. TAT calculation.
3.1.1. The calculation method for sailing time in the straight line segment
The influences of wind and current on sailing must be considered when calculating sailing time.
a) In this study, two coordinate systems are used in this chapter: inertial coordinate system OX 0Y0 and moving coordinate system Gxy, as shown in Figure 2.
Figure 2. Coordinate systems.
The origin O of OX 0Y0 is any point in the earth, OX 0 points to the north and OY 0 points to the east. The origin G of Gxy is the centre of gravity in the ship, Gx points to the ship heading, GY is perpendicular to the stern line and points to the ship's starboard side. The influence of uniform current on the manoeuvring motion of a ship is considered. The disturbance can be described in the following equations by using the speed of synthesis method:
$$\left\{ {\matrix{ {u = u_c \cos(\varphi _{\rm c} {\rm -} \varphi ) + u_r} \cr {v = v_c \sin (\varphi _{\rm c} {\rm -} \varphi ) + v_r} }} \right.$$
where u r and v r represent the velocity components of ship speed through the water in the longitudinal and transverse directions, respectively; u and v represent the velocity components of ship speed over the ground in the longitudinal and transverse directions, respectively; v c denotes the current velocity component in ordinate; u c denotes the current velocity component in abscissa; ϕ c denotes the current direction and ϕ denotes the bow direction. Thus, ship velocity with current influence over the ground can be expressed as 
$\vec u_g = \vec u + \vec v$.
b The influence of uniform wind on the manoeuvring motion of a ship is also considered. The disturbance can be described in the following equation by using the speed of synthesis method:
(2)
$$v_f = \sqrt {\displaystyle{{\rho _a} \over \rho} \cdot \displaystyle{{A_L} \over {L \cdot d}} \cdot \displaystyle{{C_{aY}} \over {C_{HY}}}} \cdot V_a $$
where v f is the drift velocity of the ship in the transverse direction (m/s), ρ a is the air density, ρ is the water density, A L is the wind age area, L is the ship length (Length Over All - LOA), d is the ship draft, C aY is the transverse wind pressure coefficient, C HY is the hydrodynamic coefficient of ship hulk, and V a is the relative speed of wind (m/s). If V a is significantly larger than v f, then it is approximately equal to the true wind speed. The meanings of the other symbols are the same as those indicated earlier.
Hull hydrodynamic coefficients are closely associated with water depth. A shallow water depth indicates a large C HY and a small drift velocity. By contrast, deep water indicates a small C HY and a large drift velocity.
In Equation (2), ρ a / ρ ≈ 0·0012. For a very large crude carrier, C aY / C HY ≈ 1.2. Thus, the drift velocity can be estimated by the following equations:
$${\rm When \, sailing \, in \, ballast},\,\displaystyle{{A_L} \over {L \cdot d}} \approx 1\!\cdot\!8,v_f \approx \displaystyle{1 \over {20}} \cdot V_a $$
$${\rm When \, sailing \, at \, full \, load},\,\displaystyle{{A_L} \over {L \cdot d}} \approx 0\!\cdot\!8,v_f \approx \displaystyle{1 \over {30}} \cdot V_a $$Ship speed that considers the influences of current and wind can be expressed by:
$$\mathop {u_h} \limits^\Gamma = \mathop {u_g} \limits^\Gamma + v_f $$Hence, sailing time can be described as:
$$t = AP_1 /\mathop {u_h} \limits^\Gamma $$3.1.2. The calculation method for sailing time in the arc segment
We assume that a ship is sailing on a planned route with a uniform speed in a straight line (shown as AP 1 and P 2B in Figure 2), and that it will not turn its direction suddenly at turning point P on the planned route. However, the ship is actually making arc movements according to a certain turning radius. In this study, the movements of a ship around turning points can be simplified for the steady turning motion of the ship.
The experiments show the relations between the turning diameter D T of large-scale oil tankers and cargo ships and the length L of a ship through Equation (8), as follows:
$$D_T = \left\{ {\matrix{ {3\!\cdot\!0L} \, &{\rm large \, tankers} \cr {4\!\cdot\!0L} & \!\!\!\!\!\!{\rm cargo \, ship} }} \right. $$Therefore, the relation between the steady turning diameter D and the length of a ship can be expressed as
$$D \approx 0\!\cdot\!9D_T = \left\{ {\matrix{ {2\!\cdot\!7L} \,& {\rm large \, tankers} \cr {3\!\cdot\!6L}\,& \!\!\!\!\!\!{\rm cargo \, ship} }} \right. $$
When 
$D_T /L \in \left[ {3\!\cdot\!0,4\!\cdot\!0} \right]$, the relation between pitch distance A d and tactical diameter D T is given as
$$A_d /D_T = 0\!\cdot\!85:1\!\cdot\!0$$Speed declines when a ship performs circular movements. When D T / L = 3·0, the downhill reaches 40% to 50%. The cycling speed can be estimated as follows:
$$V_h = \left\{ {\matrix{ {0\!\cdot\!6V_0} \,& {\rm large \, tankers} \cr {0\!\cdot\!7V_0} \,& \!\!\!\!\!\!\!{\rm cargo \, ship} }} \right. $$Assuming that the type and length of a ship are known; V 0 is the speed before cycling. Then, the steady turning diameter D and cycle speed V h of the ship can be estimated through Equations (8) and (10). The planned route with the target ship is designed by an instructor (shown by the bold lines in Figure 1). The turning point P(x, y) and intended course of the ship in AP and PB segments, respectively represented by ϕ 1 and ϕ 3, are known. The gyration radius R = D/2 is expressed in Equation (8). The main problem is identifying the positions of P 1, P 2 and the cyclotron centre of the circle to determine the arc length S h from the beginning to the end of gyration.
The distance expressed by d between the starting point P 1 and the turning point P can be determined according to known conditions as follows:
$$\left\{ {\matrix{ \!\!\!\!\!\!\!{d = R/\tan(\alpha /2)} & {(0 < \alpha < 180)} \cr {\alpha = 180 - (\varphi _3 - \varphi _1 )}}} \right.$$Given P 1(x1, y1) as the starting point of the constant cycle, P 2(x2, y2) as the terminal point and O(x o, yo) as the centre of constant cycle, then we can conclude that |P 1P|=|PP 2|=d
$$\left\{ {\matrix{ {x_1 = x - d\sin \varphi _1} \cr {y_1 = y - d\cos \varphi _1} \cr}} \right.,\left\{ {\matrix{ {x_2 = x + d\sin (\alpha - \varphi _1 )} \cr {y_2 = y - d\cos (\alpha - \varphi _1 )} \cr}} \right.$$The coordinate of the cycle centre can be calculated as
$$\left\vert {OP} \right\vert = R/\sin (\alpha /2),\beta = \alpha /2 - \varphi _1 $$
$$\left\{ {\matrix{ {x_0 = x + \left\vert {OP} \right\vert\sin \beta} \cr {y_0 = y - \left\vert {OP} \right\vert\cos \beta} \cr}} \right.$$Based on the positions of P 1, P2 and the cycle centre, we can measure the arc length S h in the arc segment, and the sailing time is
$$T_h = S_h /V_h $$Thus, the TAT of the APB segment can be expressed as
$$T_f = T_{AP1} + T_{P2B} + T_h $$And that of the total distance can be described as
$$T = \sum\limits_{\,f = 1}^n {T_f} $$Where n represents the number of segments.
According to the navigation channel chart for the Pearl River provided by the Guangzhou Waterway Bureau, the route from Huangpu Port to Nansha Port is planned as shown in Figure 3. The arc segment is shown in Figure 4, and the calculated TAT (hour) between the two ports is shown in Appendix 1. The meaning of the number represents the sailing time (hour) between any two ports.
Figure 3. Route designing from Huangpu to Nansha.
Figure 4. Route designing in arc segments.
3.2. Model Assumptions
According to the hub and spoke operation, a container ship is assumed to always start from and end at the hub port. Each feeder port can only work for one ship in one route, and the transportation between feeder ports is ignored. The time consumed in carrying the containers that require trunk line transportation from each feeder port to the hub port is limited to ensure that they can adhere to the liner schedule on the main route. The time limit and the quantity of containers being carried from the hub port to each feeder port or being transported between hub ports are assumed to be known. Calculating the objective function begins when a ship sails from the hub port and ends when the ship returns to the hub port.
3.3. Model Establishment
In the model, C represents the number of ports where ships require service; i and j indicate specific ports; V is the number of ships planned for the fleet; k is the ship number of one of the ships; t ijk is the travelling time of ship k from port i to port j; st ik is the service time of ship k in feeder port i; t ik is the arrival time of ship k in feeder port i; p i is the unloading container number from the hub port to feeder port i; q i is the loading container number from feeder port i to the hub port; L k is the maximum carrying capacity of ship k and nt i is the deadline for carrying containers from feeder port i to the hub port. The decision variables are as follows:
$$x_{ij}^k = \left\{ {\matrix{ {1}\, \hfill & {{\rm ship} \, k \, {\rm sail \, from \, port}\, i \, {\rm to \, port} \, j} \hfill \cr {0} \, \hfill & {{\rm others}} \hfill}} \right.$$
$$y_i^k = \left\{ \matrix{ {1}\, \hfill & {\rm ship}\, k \, {\rm call \, on \, feeder \, port}\, i \hfill \cr {0}\, \hfill &{{\rm others}} \hfill }\right.$$The objective function Equation (20) aims to minimise the total cost of all containerships, which consists of the total travelling cost and the total service cost.
$$\min T = \sum\limits_{k = 1}^V {\sum\limits_{i = 1}^C {\sum\limits_{\,j = 1}^C {t_{ij}^k x_{ij}^k}}} + \sum\limits_{k = 1}^V {\sum\limits_{i = 1}^C {st_i^k y_i^k}} $$such that:
$$\sum\limits_{i = 2}^C {X_{1i}^k \le 1 \quad k = 1,\Lambda, V} $$Equation (21) indicates that if ship k is executing a transportation task, then it must start from the hub port. Equation (22) indicates that if ship k is executing a transportation task, then it must end in the hub port.
$$\sum\limits_{\,j = 2}^C {X_{\,j1}^k \le 1 \quad k = 1,\Lambda, V} $$Equation (23) guarantees that a ship generally travels between two ports.
$$\sum\limits_{i = 1}^C {X_{ij}^k \le 1} \quad j = 2,...,C;k = 1,...,V$$Equation (24) ensures that each route is occupied by only one ship.
$$\sum\limits_{i = 1}^C {\sum\limits_{k = 1}^V {X_{ij}^k = 1}} \quad j = 2,...,C$$Equation (25) denotes that if a ship visits a feeder port, then it must leave from that feeder port.
$$\sum\limits_{i = 1}^C {X_{id}^k} - \sum\limits_{\,j = 1}^C {X_{dj}^k} = 0 \quad d \ne {\rm 1;}d \ne j;d = 2,\Lambda, C;k = 1,\Lambda, V$$Equation (26) guarantees that each feeder port is visited by one ship.
$$\sum\limits_{k = 1}^V {\sum\limits_{i = 1}^C {y_i^k = 1}} \quad j = 2,3,\Lambda, C$$Equation (27) guarantees that if a ship starts from the hub port, then the number of loading container will not exceed ship capacity.
$$\sum\limits_{\,j = 2}^C {X_{1j}^k} p_j \le L_k \quad k = 1,...,V$$Equation (28) indicates that if a ship visits a feeder port, then its dynamic loading will not exceed its maximum capacity.
$$\eqalign{& \sum\limits_{\,j = 2}^C X_{1j}^k p_j + \left( { - \sum\limits_{d = 2}^{i = 1} {\,p_d y_d^k + \sum\limits_{d = 2}^{i = 1} {q_d y_d^k - p_i y_i + q_i y_i}}} \right) \le L_k \cr & \quad d = 2,...,i - 1;i = 2,...,j;j = 2,...,C }$$Equation (29) ensures successive shipping between ports after the berthing time is considered when arriving in a feeder port.
$$x_{ij}^k (t_i^k + st_i^k + t_{ij}^k - t_j^k ) \le 0 \quad i,j = 1,2,\Lambda, C;k = 1,\Lambda, V$$Equation (30) ensures compliance to the deadline, i.e., that the total travelling time for each route must not exceed the time limit of the containers being carried from each feeder port to the hub port.
$$\sum\limits_{i = 1}^C {\sum\limits_{\,j = 1}^C {t_{ij}^k x_{ij}^k + \sum\limits_{i = 1}^C {st_i^k y_i^k}}} + \le \min \left\{ {nt_i} \right\}\quad k = 1,\Lambda, V$$Equation (31) indicates that the quantity of ships working in feeder port i is consistent.
$$\sum\limits_{k = 1}^V {y_j^k = \sum\limits_{k = 1}^V {\sum\limits_{i = 1}^C {\sum\limits_{\,j = 1}^C {x_{ij}^k}}}} \quad j = 2,3,\Lambda, C$$4. ALGORITHM DESIGN
We use a new genetic algorithm, which improves the construction of the solution, to solve the aforementioned model. The new algorithm is better than traditional genetic algorithms (Barrie and Ayechew, Reference Barrie and Ayechew2003; Jeon et al., Reference Jeon, Herman and Shim2007). By using it, we can determine the number of routes, the order of feeder ports on each route and the minimum total sailing time.
4.1. The Improved Genetic Algorithm Design
Genetic algorithms are described as random search techniques based on natural genetic mechanisms and natural selection. These algorithms adopt the model of natural evolution to study initial populations. According to the fitness function, individuals belonging to a group are optimised through selection, crossover and mutation. Finally, the individuals are restructured, and the optimal population is selected to continue the operation until the best individual is identified. To solve the model, an improved genetic algorithm is designed in this study. The algorithm includes four basic elements: schema structure, crossover, mutation and selection.
4.1.1. Schema Structure
In the model used in this study, we assume that six ports (1,2,3,4,5,6) exist. Among these, 1 is a hub port; and 2, 3, 4, 5 and 6 are feeder ports. The order 1,2,3,4,5,6 represents an actual port sequence that can be regarded as a solution for a genetic operation. Based on the order, a ship starts from hub port 1 and serves feeder port 2. Then, we should determine whether the ship can berth in feeder port 3. If the ship does not conform to the constraints, then the procedure must be terminated, and route 1-2-1 is generated. If the constraints are satisfied, the next port will be determined until all ports are visited. Finally, different courses are obtained and the initial solution to the genetic operations is determined.
The father generation individuals (1,2,3,4,5,6) and (1,4,5,3,6,2) are considered. If we choose position 3 as the crossover point, then we will obtain the corresponding offspring individuals (1,2,3,3,6,2) and (1,4,5,4,5,6). Given the presence of repeater ports in the sequence, we obtain a meaningless port order. To improve the efficiency of the crossover operator, we use the touring route coding method, which is easy to perform and ensures the actual meaning of each offspring.
The original port order is assumed to be A = (1,2,3,4,5,6), which is represented as B 0 = (1,2,3,4,5,6). If the actual berthing order of a ship is (1,3,5,6,2,4), i.e., the first calling port is hub port 1, then the position of the hub port in B 0 will be 1, which is recognised as C = (1).When 1 is removed from B 0, we obtain the new sequence B 1 = (2,3,4,5,6). The second calling port is feeder port 3 and its position in B 1 is 2, which is recognised as C = (1,2). By removing 3 from B 1, we obtain a new sequence B 2 = (2,4,5,6). The third calling port is feeder port 5 and its position in B 2 is 3, which is recognised as C = (1,2,3). By removing 5 from B 2, we obtain a new sequence B 3 = (2,4,6). Accordingly, we acquire the corresponding sequence of each port, i.e., C = (1,2,3,3,1,1), which is the touring route code.
4.1.2. Crossover, Mutation and Selection
In this study, the crossover in the solution after coding is performed based on a single point. We follow the rules of parental cross and Gemini hybridisations in the parent population, generate the cross point randomly and exchange all the genes after the cross point.
The coding, hybridisation and decoding procedures are shown in Figure 5.
Figure 5. The coding, hybridisation and decoding procedures.
The mutation operator changes the position of several genes in the individual coding string based on a small mutation probability to generate a new individual. In this study, the scale of individual chromosomes is small; if the mutation probability is significantly small, then the best solution will not be identified easily. Thus, we develop the mutation probability P m, which is equal to 0·2, and adopt the t displacement variation method to improve the port sequence for the solution after the coding operator, which is only suitable for the crossover operator, is used. The genes selections are shown in Figure 6.
Figure 6. The genes selections procedures.
The selection operator is used to restructure across individuals, and the selected individuals will continue to generate multiple individuals. The method for obtaining the next generation is called roulette wheel selection in this study.
4.2. Model Solution
Step 1: The initial population is generated randomly, and the number of the population is set to 23.
Step 2: The fitness function value is calculated according to the constraints in the model, i.e., the objective function of the model. The optimal value and the optimal solution are then identified.
Step 3: The iteration number can reach 500 generations. We should judge whether the final solution satisfies the termination rules of the genetic algorithm. If the rules are satisfied, then the optimal solution is obtained. If the rules are not satisfied, then genetic algorithm operators, including encoding, crossover, decoding, mutation and roulette wheel selection, are used to improve the population, and step 2 is repeated.
5. CASE APPLICATION
To validate the proposed model and algorithm, we consider an actual case from a shipping company in the Pearl River Delta Region in China regarding the branch routes of container transportation among 23 ports. We select Nansha as the hub port (labelled 1) and assign the other 22 ports as feeder ports (labelled 2 to 23). The ship scale in the branch line and the number of ships visiting the feeder ports are small, thus a ship can be serviced as soon as it reaches the port. Therefore, we ignore the waiting time spent in a port when calculating the total sailing time. The data for different ports are shown in Table 1.
Table 1. The unload and load capacity data of different ports.
The studies are divided into two situations in this research based on the actual situation of the shipping companies. Firstly, only one type of ship with a capacity of 150 TEU exists. Secondly, two types of ships with capacities of 100 TEU and 150 TEU exist.
In the first situation, we use the improved genetic algorithm to solve the problem and to obtain the optimal routes, as shown in Table 2.
Table 2. Routing optimisation for single-type containerships.
Table 2 shows that we can generate six routes for single-type container ships based on the constraints of the rated load of the ship and the deadline for the containers to reach the hub port. The total sailing time converges gradually with the increase in the number of genetic iterations. When the number of iterations reaches 90, the total sailing time closes to a minimum of 401·0 h, the iteration result of the single-type container ships is shown in Figure 7. Table 2 shows that six ships with a capacity of 150 TEU can finish the transportation task for the branch route in the case of single-type container ships.
Figure 7. The iteration result of the single-type container ships.
In the second situation, we use the improved genetic algorithm to solve the problem and to obtain the optimal routes, as shown in Table 3. The planned routes are shown in Figures 8 to 13.
Figure 8. Nansha—Rongqi—Jiangmen—Beijiao—Huangpu—Zengcheng—Nansha.
Figure 9. Nansha—Beihai—Yangpu—Nansha.
Figure 10. Nansha—Haifang—Fangcheng—Nansha.
Figure 11. Nansha—Zhongshan—Doumen—Yangjiang—Xinhui—Zhuhai—Nansha.
Figure 12. Nansha—Zhanjiang—Haikou—Nansha.
Figure 13. Nansha—Nanwei—Sanshan—Xinfeng—Sanshui—Sanrong—Taiping—Nansha.
Table 3. The shipping routes of multi-type container ships.
Table 3 shows that we can generate six routes for multi-type container ships based on the constraints of the rated load of a ship and the deadline for the containers to reach the hub port. The total sailing time converges gradually with the increase in the number of genetic iterations. When the number of iterations reaches 104, the total sailing time is close to a minimum of 394·6 h. The iteration result of the multi-type container-ships is shown in Figure 14. Table 3 shows that three ships with a capacity of 150 TEU and three ships with a capacity of 100 TEU can finish the transportation task for the branch route in the case of multi-type container ships.
Figure 14. The iteration result of multi-type container ships.
By comparing the two cases, the type of container ship is shown to have minimal effect on the total sailing time; however, total sailing time can use ship capacity to avoid waste caused by idle load. When the ship capacity is large and the price of a ship is high, the cost per unit when sailing will also be high. By considering these features and the results of this study, the second solution of multi-type container ships is determined to be more efficient for finishing tasks. Accordingly, we will generate the minimum total sailing time and the low transportation cost to increase the benefits from both sides.
6. CONCLUSIONS
In this study, we investigate the routing optimisation problem of container ships based on an electronic chart system. We consider the influences of wind, current and ship manoeuvring performance, and then determine the TAT of each route by calculating the sailing time in the straight line and arc segments. A mixed integer programming model is established according to the constraints of ship capacity and the liner schedule of the hub port. We propose an improved genetic algorithm to combine the characteristics of regional transport. The model is applied to the shipping tasks of 23 container ports in the Pearl River Delta. The results and the numerical analysis verify that the model and the algorithm conform to feeder routing optimisation design problems in actual situations, and thus both can have supplementary roles in the decision-making process of feeder shipping companies.
ACKNOWLEDGMENT
This work was financially supported by the National Natural Science Foundation of China (Grant No. 51309043), the Applied Basic Research of Ministry of Transport (Grant No. 2014329225020), China Postdoctoral Science Foundation (Grant No. 2014M551095), National Science Fund of LiaoNing Province (Grant No. 2014025005), Outstanding Young Scholars Growth Plan of LiaoNing Province (Grant No. LJQ201405), and the Fundamental Research Funds for the Central Universities (Grant No. 3132014202).
Appendix. TAT(turnaround time, amount of time required) between two ports(hour) (turnaround time, amount of time required) between two ports(hour).
