Berth allocation planning in Seville inland port by simulation and optimisation

Berth allocation planning in Seville inland port by simulation and optimisation Carlos Arango 1 , Pablo Cortés 1 , Jesús Muñuzuri 1 , Luis Onieva 1 1 Ingeniería de Organización. Engineering School of Seville. University of Seville. Camino de los Descubrimientos s/n 41092. Seville, Spain. [email protected]s.es, [email protected].es, [email protected], [email protected]s.es Abstract We study the problems associated with allocating berths for containerships in the port of Seville. It is the only inland port in Spain and it is located on the Guadalquivir River. This paper addresses the berth allocation planning problems using simulation and optimisation with Arena software. We propose a mathematical model and develop a heuristic procedure based on genetic algorithm to solve non-linear problems. Allocation planning aims to minimise the total service time for each ship and considers a first-come-first-served allocation strategy. We conduct a large amount of computational experiments which show that the proposed model improves the current berth management strategy. Keywords: Berth allocation, Genetic algorithms, Port operations, Container transportation. 1. Introduction The Port of Seville is the only inland port in Spain. It is located on the Guadalquivir River, in the city of Seville and it can be accessed by rail, air, road and motorway. It has always been one of Spain’s main ports due to the high frequency in small ship traffic, including RO-ROs, ferries, feeders, etc. between Seville and the Canary Islands, and other Spanish and European ports. Seville’s inland port currently has a bottleneck because there is only one lock which is for small ships. Therefore, a new lock is being built that will increase the amount of ships which can enter in the coming years. Fig. 1 shows the port’s future appearance with the new lock. This lock is highly important for Seville inland port to continue being one of the main intermodal centres in the south of Spain. The new lock improves the port’s performance and will double current freight traffic. However, other processes and resources must be managed to maintain its competitiveness. The simulation presented in this paper considers the freight traffic data from the Port Authority of Seville (PAS). This data is mainly about cargo containers, because in the last 6 years this cargo type has increased greatly. It also represents additional ships arriving in the Seville port due to the new lock. We consider the freight traffic of ships carrying scraps, cement and cereal, and that new potential bottlenecks may occur in the container terminals, because the PAS has only two quay cranes for containerships. We therefore simulated the handling operations as the ships arrived, passing through the lock, unloading/loading containers, and propose an optimisation model for berth management. We have developed a genetic algorithm (GA) to solve the berth allocation problem (BAP). Fig 1. Future layout of the Seville port As an outline for the rest of the paper, we will give the literature review in Section 2. Section 3 looks at the simulation scenario and in Section 4 we describe the freight traffic situation. Section 5 presents the mathematical formulation for the berth allocation problem and the simulation model constructed from such. Section 6 shows the genetic algorithm approach to solve the BAP, and the results appear in section 7. Lastly, main conclusions and future work are addressed. 2. Literature review Several authors have approached the BAP concept. For example, Imai A. et al [1], and Nishimura E. et al [2] determine BAP as a dynamic berth allocation problem (DBAP) which is a generalisation of the static berth allocation problem (SBAP). They propose a genetic algorithm in public berth systems which can be adapted to real world application: Park and Kim [3], Liu et al [4] and Lim A. [5] consider BAP and quay crane scheduling problem (QCSP) as a single problem and that berth scheduling depends on the crane number that is assigned to the ship. Imai A. et al [6 and [7] approaches BAP in a multi-user container terminal (MUT). In the first work they use a continuous location space approach and in the second work they solved the BAP by GA at a port with indented berths, where mega-containerships and feeder ships are to be served for higher berth productivity. Imai A. et al [8] consider the relations between the ports and shipping lines, and when some vessel operators desire high priority services, the authors have indicated BAP as BAP with service priority. There are few port simulation and optimisation studies found in literature. Cortés P. et al [9] simulated the freight transport process in Seville’s inland port, considering all existing types of cargo and testing several scenarios. They analyse the performance of the several Seville port terminals and processes. Demetro L. et al [10] and Legato P. et al [11] developed optimisation and simulation models by scheduling yard crane use in the Gioia Tauro port. This proposal has some similarities to our work, however, authors follow ranking and selection (R&S) techniques to approach the scheduling yard crane (Rubber tired gantry cranes - RTG) at difference form us. 3. Simulation scenario PAS is a multi-purpose terminal: different types of cargo are moved through this port such as cereals, scrap metal and cement containers. The port has various specialised terminals for handling these types of cargo such as container terminals UTE Batan 1 and UTE Batan 2, TLP Esclusa cereals terminal, Holcim cement terminal, GPMA iron terminal, TLD Grupo Gallardo scrap and metal terminal and more. Our simulation scenario will only consider container terminals and the facilities needed for them to operate, the access channel and the lock. Fig 2 shows the simulation scenario model. Fig 2. Simulation scenario The container terminals Batan 1 and Batan 2 are for two different logistic operators although located in the same dock (Centenario). Therefore, all resources such as quay cranes, Reachsteakers and facilities are used in pairs for container handling. We therefore consider these two terminals to be one with two berths and two yards (yard Batan 1 and yard Batan 2). Table No. 1 shows the resources used in handling operations. All resources, such as the quay crane and reachsteaker must be scheduled by one terminal with two yards. 4. Freight traffic description The model simulation considers information about the ship–containers’ traffic through Seville port during February 2009. This simulation included data about arrival date, departure date; unload containers’ number and the load containers’ number by the study date. Table 2 shows an abstract about this information, in which we can observe that 32 ships came to the port in February. The arrival frequency and the ship’s country destination can also be seen. The 32 containerships transport 9954 TEUS ( Twentyfoot Equivalent Unit) of which 57% is loaded in the port. PAS has stated that containership traffic will double with the new lock therefore we have considered data about arrival dates, frequency, and departure dates for shipping lines that carry cement, grains and iron scrap to represent an increase in ship flow. Table 2 shows three shipping lines (24 ships in total) that have presented an increase. The data used in the simulation is based on the daily reports from the Port of Seville’s web during February 2009. The data shows that in an ordinary month 32 containerships arrived at the Port. The Seville port is a small port, because of this it moves small amounts of containers compared with hub ports. Towboat Reachstackers Ro-Ro Ramp Size Yard Capacity yard/TEUS Quay cranes 2 17 2 97,310m 2 150,000 2 Table 1 Containers terminal resource Country Frequency Cargo type Ships month Minimum Containers Maximum Average Spain 2/Week Containers 8 64 429 243 Morocco 1/Week Containers 4 100 157 114 Spain 1/Week Containers 4 54 86 75 Germany 1/Week Containers 4 30 43 41 Spain 1/Week Containers 4 64 86 75 UK 1/Week Containers 4 43 430 214 Netherlands 1/Week Containers 4 86 114 98 UK 3/Week Scrap 12 75 75 75 Spain 2/Week Cereals 8 75 75 75 Morocco 1/Week Cement 4 75 75 75 Table 2 Ship lines 5. Simulation model and mathematical formulation We proposed two simulation models: one by current berth allocation systems and another by BAP allocation systems using Arena software. We also propose an optimal mathematical model which is integrated with the simulation model. 5.1 Mathematical model Lai and Shih [12] consider ship arrival times to be a key factor for allocation strategy. They propose a heuristic algorithm for BAP with first-come-first-served strategy (FCFS). The optimisation model proposal aims to minimise the total service time for each containership, respecting the order in which it arrived. Note that this objective does not guarantee the sum of total service time for all ships to be minimum. Also, we consider the discrete case of the BAP proposal by Jean F. et al [14] used for berths with a limited set of berthing points. In this case there are two berths. We make the following assumptions: • Every containership must be serviced once and only once at any berth. • Each ship’s transport operation times depends on the berth which is servicing it, i.e. if all containerships are in Yard Batan 1, the transport time for each container is the same, but if some are in yard Batan 1 and others in yard Batan 2, each container’s transport time depends on the distance between the yard and the berth. • The logistic operation times on arriving and leaving the lock is not considered, but this is constant. The BAP may be formulated as follows Sets:  Numbers of ships where  =  , …  ∈  .  Numbers of berths where    =  , …  ∈  .   Logistic operations time of ship    Handling time of ship  at berth    Arrival time of ship  Decision variables:   Start time of handling operations of ship  .   ={ , , !"#$%& '  ′  ={ , , ! ′ %"$% !&()%)$*)(%&  +,--ℎ    ∈/∈ +-1  −3  +4  ∈ 517 Subject to -  ∈/ =1,∀ =1,,,,,,9 ∈ 9527 1  −3  ≥0∀ =1,,,,,,9 ∈9537 - -'  ′  >/ 5ℎ  +4  7 >?@{} ≤ -ℎ C +1  −3  +4  C>/ ,∀ =1,,,,,9 ∈9547 - -'  ′  >/>?@{} ≤ - C C>/ ,∀ =1,,,,,9 ∈ 9557 F  =∈{0,1},∀ =1,,,,,9 ∈ 9567 '  ′  =∈{0,1},∀ =1,,,,,9 ∈9577 1  ≥0, ∀ =1,,,,,9 ∈9587 The objective function (1) minimises the sum for each ship’s service time; these are the handling operations time, berth waiting time and logistic operations time. Constraint (2) ensures that each containership must be assigned only one berth. Constraint (3) guarantees that each ship must be serviced after arrival. Constraint (4) guarantees that if ship  J which arrived at port after ship i and is serviced first in berth j , This is because the service time of shipi in the berthj is greater than the service time in the berth k . This constraint is very important because ships that arrived after will be served first, only if the ships in port at this time do not increase its total service time. Constraint (5) completes the previous task and ensures that the ship which is still waiting has another berth assignment. Constraints (6), (7) and (8) are the constraints for decision variables. 5.2 Simulation model of the current system Ports are very important to the transport logistic networks, therefore all of its operations must be optimised, according to Ambrosino et al [13]. Some of the main operations are: container pre-marshalling problem, landside transport, stowage planning problem, yard allocation problem, etc in Voß S and Stahlbock R (2004) [14] and Steenken D and, Voß S. (2008) [15] which has been one of the most complete reviews and one of the most important papers. We are not optimising all operations in the Port of Seville, but the simulation model is formed by five module groups that represent some operations, such as 1.Truck arrivals. 2. Containership arrivals. 3. Berth assignment systems. 4. Towing vessels and 5. Berths. 5.2.1 Truck arrivals We include these modules in the simulation model because truck handling operations use the reachstacker at the same time as ship handling operations. Fig 3 shows the truck modules. The truck handling operation time depends on where the containers are located in the yard: it is modelled with a module named decide. Fig 3 Truck arrival modules 5.2.2 Containership arrivals More than 45% of the time intervals between the arrival of one containership and another are from 0 to 15 hours. The shipping lines used for obtaining that data are shown in Fig 4 and it is modelled by the module create. Fig 5 shows the containers arrival modules. The ship characteristics are assigned by a module assign when it arrives at the port, such as unload containers, load containers, containers located to load, etc. The ships wait in the channel access (module Queue) while they are waiting to be assigned a dock. Fig 4 Intervals time between arrivals of ships Fig 5. Containership arrival modules 5.2.3 Berth assignment systems A module seize and three modules choose were used in the study to simulate the current berth management system used in the port of Seville (Fig 6). The system used the First-come-first-served allocation strategy (FCFS). Hence when a ship arrives at the port it has to wait in the queue until a berth becomes free. If there are not any other ships waiting to be serviced and the two berths are free then it is assigned the berth that is near to yard where less containers will be handled. Fig 6 shows the berths assignment modules. Fig 6 Berths assignment modules 5.2.4 Towing vessels Two towboats are created when the simulation is started, one for each berth and it is sent to the first modules’ group (Fig 8). In this group the tows are waiting for the ships, and then a signal is sent to the towboats for them to collect the ships that have been assigned to berth to pick them up and carry them to the berth. Fig 7 shows the creation the towboat. Fig 7 Creating towboat Fig 8. Tow vessels modules 5.2.5 Berths The berth modules represent the handling operation time for each ship. This time depends on its characteristics and the amount of containers that need to undergo handling, containers’ location and the resources available at that time. There are two berth modules which are exactly equal, one for each berth (Fig. 9). The container loading operations can only begin if the unloading operations have finished. The towboat is called again to carry the ships to the lock. Fig 9. Berths modules 5.3 Berth assignment by optimisation model The optimisation model used for berth assignment is the same as the previous simulation model but there is a difference in the modules used. We used a VBA module which allows heuristic procedures to be created and can be applied to the programming language visual basic. When a ship arrives at the port and goes by the VBA modules, the heuristic procedure based on the genetic algorithm (GA) solves the non-linear problem (it integrates the simulation model and the optimisation model) (Fig 10).