Journal of Industrial Engineering and Management

Research on bulk-cargo-port berth assignment based on priority of resource allocation

Chunfang Guo, Zhongliang Guan, Yan Song

School of economics and management, Beijing Jiaotong University (China)

 

Received August 2012

Accepted December 2012

 

Guo, C., Guan, Z., & Song, Y. (2013). Research on bulk-cargo-port berth assignment based on priority of resource allocation. Journal of Industrial Engineering and Management, 6(1), 276-288. http://dx.doi.org/10.3926/jiem.673

---------------------

Abstract:

Purpose: This paper is to propose a Priority of Resource Allocation model about how to utilize the resources of the port efficiently, through the improvement of traditional ant colony algorithm, the ship-berth matching relation constraint matrix formed by ontology reasoning.

Design/methodology/approach: Through questionnaires, exploratory factor analysis (EFA) and priority factor analysis, the authors extract the importance of the goods, the importance of customers, and types of trades as the main factors of the ship operating priority. Then the authors combine berth assignment problem with the improved ant colony algorithm, and use the model to improve ship scheduling quality. Finally, the authors verify the model with physical data of a bulk-cargo-port in China.

Findings: Tested by the real data of a bulk cargo port, it shows that ships’ resource using priority and the length of waiting time are consistent; it indicates that the priority of resource allocation play a prominent role in improving ship scheduling quality and efficiency. 

Research limitations: The questionnaires is limited in only one port group, more  related influence factors should be considered to extend the conclusion.

Practical implications: The Priority of Resource Allocation model in this paper can be used to improve the efficiency of the dynamic berth assignment.

Originality: This paper makes the time of ship in port minimized as the optimization of key indicators and establishes a dynamic berth assignment model based on improved ant colony algorithm and the ontology reasoning model.

Keywords: ship-scheduling system, priority of resource allocation, ontology reasoning, dynamic berth assignment

---------------------

1. Introduction

With the accelerating process of global economics, modern port has become an important basis to maintain a leading position in international competition. In recent years, as important national economic materials, bulk materials occupy a very important position in international shipping market. According to statistics, 90% world trade goods is transported by shipping, of which bulk cargo transportation accounts for 1/3, while the main three bulks coal, ore and grain accounted for about 60% of the total bulk cargo transportation (Meng & Ji, 2007). The traditional ship scheduling and production deployment of resources has been unable to meet the frequency that ships go in and go out of port to load and unload cargo. Currently, how to improve the operating efficiency of cargo transportation, thereby to increase the overall level of production scheduling, is the key factor to realize the intelligence of ship scheduling in bulk groceries port.

2. The definition of dynamic berth assignment problem

The core content of ship scheduling in bulk groceries port is berth assignment problem. Berth assignment problem is a decision-making problem to arrange arriving ship dock to the specified berth quay at a time. How to assign its berth time and position dynamically, is of great importance to improve the level of port services and reduce port cost of production. The main factors affecting the berthing are: ship cargo information, ship cargo capacity, the length of the ship, shipping company, weather conditions, the ship's draft, draft berths, berth length. We also need to consider the completed handling capacity, the average handling speed and other factors to ensure the real-time of ship scheduling.

Table 1. Parameter list of dynamic berth assignment problem

To take total time of ship in the harbor minimum as optimization goals, the total time equal to the sum of waiting time and operating time.

The possibility of ship i handling at berth j, 0 means no and 1 means yes, y_ij means the matching degree between ship and the berth, we need to consider the match between not only the berth physical condition and ship form but the type of ship-loaded goods and the operating type of the berth. On the other hand, according to the difference of ship trades type and customer types, we also need to consider the total operating time of the ship and the operating order, the operating order is determined by the ship trade type, customer class, the emergency of the goods, warehouse conditions, weather conditions, and customer's local acts etc (Zheng, 2003).

3. Sort of priority based on the ship resources

With the increasing of the port operations, the existing port berths, storage yard, as well as machinery and other resources are relatively scarce, it is inevitable for the inbound operating vessels to wait in line, when port serve the ships, they do not pursuit efficiency of one ship, its performance evaluation should be evaluated by the minimum berth time of the ship in port in a period of time.

3.1. Marine resource usage based on priority factor analysis

In this paper, we use the questionnaires and study cargo transportation scheduling post, analyze the ship scheduling situation from the view of the practical application, extract important factors which affect the sort of ship operations and make weight distribution.

The object of this survey includes the ports corporation scheduling manager, dispatchers of a port, we conduct a survey of the factors that affect the order of ship operationg priority in their professional and work areas, and we analyze the questionnaires by statistical methods. Given that cargo transportation is strong regional and the geographical situations are different (Gan & Qi, 2006). We select the whole Port Group (which involve four sub-Ports Corporation) as a whole object, and get the factors shown in Table 2.

Table 2. Factors of priority about ship using resources

Table 3. Check list of Importance and point

We distributed 60 questionnaires and recovered 51, of which 45 are valid. According to the actual work of the cargo transportation ship scheduling, we identified the priority of the ship operating factors, stripping the cross or related higher impact factors through in-depth analysis of the questionnaire to determine the main influencing factors. Exploratory factor analysis (EFA) was used in this study, which uses a small amount of factor to take place of the original variables. In factor analysis, we use principal component analysis with the variance maximum orthogonal rotation, the factor extraction criteria is the Eigen value greater than 1.

At first, we need to use KMO (Kaiser-Meyer-Olkin measure of sampling adequacy) to test whether the data are suitable for factor analysis or not. According to Kaise (1974), the larger KMO, the more suitable for factor analysis; if KMO is too low, it is not suitable for factor analysis, as shown in Table 5:

Table 4. Check list of KMO and factor analysis sufficiency

Then we use SPSS13.0 to measure KMO value and Bartlett’s spherical test, the result shows that KMO value is 0.737>0.7. Bartlett ball test significance level of sig. = 0.00 <0.05, very significant. According to table 4-5, it is suitable for factor analysis if KMO value is greater than 0.7.

Table 5. KMO and Bartlett's Test

We can conclude from the previous analysis and moderate test, the questionnaire data samples are suitable for factor analysis, then we use SPSS13.0 to make factor extraction to determine the number of factors. The number of Eigen value that greater than 1 is also the number of factors should be extracted. The result of the analysis is shown with gravel map, in Figure 1.

Figure 1. Scree Plot of investigation

It can be seen from Figure 1, the Eigen values of the first three factors are greater than 1. The Eigen values of the other four factors are flat, according to the rules of the gravel map. We can extract the first three factors as the main factors of ship operating priority. They are the importance factor of the goods, the importance of customers, and type of trade.

4. Berth assignment based on improved ant colony algorithm

In the field of ship scheduling in bulk and general cargo port group, the essence of dynamic berth assigned problem is to solve the problem that the minimization of the total time of ship stay in port under the ship operating constraints.

4.1. Assignment problem combined with the improved ant colony algorithm

There are alternative relationships between many production resources in discrete production systems. Because berth is the scarcest productive resources of pier, the substitute relationship between the various berths is of a decisive impaction for ship scheduling. It occupies an important position in ship scheduling.

Ship - berth constraints

Figure 2. Relationship of ship and berth

As is Shown in Figure 2, when the port make ship-berth selection, according to the specialized adapt requirements of the port cargo types to the berths, there is docked constraint set between specialized berths and different types of cargo, constraints of the collection contains two aspects:

(1) ships - berth physical condition (boat length, type width and maximum draft and other property and the length of the berth, draft, etc.) must be met;

(2) ships - berth job match degree: as is shown in Figure 2, relationship of bulk and general cargo port and berth type and ship type is corresponding to the network. According to the literature (Stutzle & Hoos, 1997), the berths in accordance with the type of operation are divided into: coal berths, food categories berth, the general-purpose berths and oil berths. The corresponding relations of the various types of berths and the ship can be shown as following model:

v_i is ship waiting for berthing operations, berth(v_i) is the berth ship v_i docked, cargo(v_i) is the information of the goods ship v_i carried, B_type is the services type that the berths provide, formula (8) show that only when the goods information on ship accord to the requirements of loading and unloading cargo information of the berths provided, can the ship choose the berth (Liu, 2008).

Based on the ship - berth constraints concept and the two types of constraints above, we merge the ant colony algorithm and the constraint conditions turns into (9), Ship - berth constraint matrix.

Prioritization of the vessel operation

Since the scarcity of port productive resources, it is inevitable for inbound operating ships to wait on line. We put forward the ships resource using priority model based on the Analytic Hierarchy Process to measure the different resources using priority of the ship.

Calculate marine resources using priority sequence v_odr, Sort the ship in v_odr in accordance with the resources using priority.

When all the ships complete one operation, it is said that the berth assignment problem obtained a solution.

antN-Ant number;

m-Ship number;

n-Berth number;

iteratorTimes-Iteration number;

Q-Total amount of pheromone ant released after the completion of every iteration,

a,b,r-Mean the importance degree of the pheromone, the relative importance of the operations time, pheromone residual coefficient respectively.

Construct the ship - berth time matrix WorkT(t), as formula (10) shown that, the expected turnaround of ship I at time t, in berth j .

berthFinishTime[j]-Ship j Job completion time

Transition probability at time t

ShipAllowed[i]=1-Sjip i can schedule operations

Y_ij=1 _- ship and berth j meet ship—berth matrix A vorder_i^k belongs to V_{odr –} ants access path constrains

antTrialTotalTime[it][k]-the first it iterations, the ants k complete a path exploration, the total stop time obtained

antTrialTotalCombine[it][k]- the first it iterations, the ants k complete a path exploration, ship - berth combination obtained

bestTrialTotalTime[it]-the first it iterations, the optimal value of the total stop time obtained

bestTrialTotalTime[it]=min(antTrialTotalTime[it][k])

bestTrialTotalCombine[it]-the first it iterations, bestTrialTotalTime[it] the optimal combination of ship - berth that corresponds.

5. Calculation Example

In this section, we use actual data of a bulk cargo port to calculate the solution methods and models in 4.1. As is shown in Table 6, which contains important data as: ship wide, trade type, time of arrival and cargo information, customer rating etc.

Table 6. Ship data list

 

Table 7 is the information about berths as is shown in the table.

Table 7. Berth data list

Table 8 and 9 are the importance of cargo and importance of trade, use 10-point scale, the higher importance degree of goods and trade type, the higher the score.

Table 8. Importance of cargo

Table 9. Importance of trade

Table 10 is the priority of ship using resources. Higher priority index and higher priority means shorter waiting time before the operations.

Table 10. Priority of Ship using resources

Having made iteration 100 times with improved ant colony algorithm, we get the ship scheduling jobs, as is shown in Table 4-11 and ship scheduling Gantt chart figure 3. The entire ship - berth assigned program time-consuming: 316.73 hours.

Table 11. Result of Ship-Scheduling

Two questions can be found in the following through the analysis of ship scheduling results list and the Gantt chart:

-3 berth and 8 berth in the working process has not been assigned

3 berth’s length is just165 m, 8 berth’s draft depth is11 meters, in all waiting operations ships, only the length is 97 m, draft 6.25 m Hongyangwan is able to meet the berthing conditions. But Hongyangwan has higher priority, in the beginning of the iteration, it has the priority to choose a good berth (higher operating efficiency) berths. Therefore, the 3 berth and 8 berth in the operations process has not been assigned.

-4 berth and 6 berth utilization is relatively low

4 berth and 6 berth only have one ship assignment, except 6 berth is 184 meters berth length restrictions, ships all reflect tend to choose higher operating efficiency berths; View on berth type, all ships - berth match the conditions of the ship - berth match constraints, indicating that the ship - berth reasoning constraints played a role.

In addition, the ship’s resource using prioritization and waiting time sort are consistent; it also indicated the important role of marine resource use priority that played a prominent role in improving ship scheduling quality.

Figure 3. Gantt Chart of Ship-Scheduling

6. Conclusion

Result of berth assignment problems is to obtain the loading and unloading order of the ship, expected ship berthing time and docking berth .In this paper, we firstly build a ship scheduling problem model of bulk and general cargo port group. Secondly, based on the maximum and minimum ant colony algorithm, we propose a way to adjustment pheromone allocation to further improve the search capabilities through standard deviation coefficient, which form the improved ant colony algorithm based on the mixing behavior.

Through the questionnaire analysis of ship resource usage priority affecting factor, this paper put forward the ship resources priority model. And then combining with knowledge-based reasoning, it puts forward the ship -berth match collection, and uses the improved ant colony algorithm model to improve the efficiency of the dynamic berth assignment.

Acknowledgments

This research was supported by “the Fundamental Research Funds for the Central Universities” under Grant 2011JBM042.

References

Gan, Y., & Qi, H. (2006). Priority Algorithm of Ship Scheduler in Navigation Co-scheduling System for the Three Gorges-Gezhouba Dam. Computer and Communications, 133, 128-135.

Liu, J. (2008). Improved Virtual Enterprise Partner Selection and integration of genetic algorithm and ant colony algorithm. Beijing University of Aeronautics and Astronautics, 25-79.

Meng, Y., & Ji, Y. (2007). Based on Multi-Agent Container Terminal Production Scheduling. Wuhan University of Technology, 1-5.

Stutzle, T., & Hoos, H. (1997). The Max-Min ant system and local search for the traveling salesman problem. Proceedings of IEEE-ICEC-EPS’97, 309-314.

Zheng, H. (2003). Port Management. Beijing: Communications Press, 117-205.