Berth Allocation Problem

Berth Allocation Problem

اسلاید 1: Berth Allocation Problem(BAP)Zeinab TerikanFall 2008In The Name Of Allah

اسلاید 2: An introduction to berth allocation problem (BAP) Berth allocation importanceBAP; past, present and futureBerth Allocation ProblemSome classificationsModeling and solution techniquesLiterature review on the BAPSome SamplesKim and Moon(2003)Nishimura, Imai and Papadimitriou(2001)Lee and Chen(2008)ReferenceContent

اسلاید 3: A good berth allocation can :maximize the utilization of a wharfreduce costs lead to higher revenues of portincrease port throughputreduce turnaround time of shipsimprove customers satisfactionBerth allocation importance Kim and Moon(2003),Liang et al.(2008)

اسلاید 4: BAP; past, present and futureFCFS ruleNegotiationTrial-and-error Graphic-user-interface in a computer systemFuture perspective : “An optimization –based approach that can serve as the core of a future DSS that schedules the berth usages automatically”Lee and Chen(2008)

اسلاید 5: An example of a berth scheduleKim and Moon(2003)

اسلاید 6: BAP Classifications

اسلاید 7: BAP Classifications(cont’d)

اسلاید 8: BAP modelingInteger programmingMixed-integer-linear programming (Kim and Moon(2003))Binary integer programming (Lee and Chen(2008))non-linear integer programming(Nishimura et al.(2001))

اسلاید 9: BAP objective functions

اسلاید 10: BAP objective functions(cont’d)

اسلاید 11:

اسلاید 12: PaperPropertiesLai and Shih (1992)Heuristic algorithm – FCFS allocation strategy Brown et al. (1994,1997)Naval ports – Maximize the sum of benefits for ships while in portImai et al. (1997)Commercial and busy ports – Ignore FCFS allocation strategy – Static situation – Heuristic algorithmLim (1998)Minimizing the maximum amount of quay space used at any time - every ship berthed as soon as it arrived at the portLi et al. (1998)Solved BAPC both with and without ship’s movement restriction – Minimize the makespan of scheduleLiterature review on the BAP

اسلاید 13: PaperPropertiesImai et al. (2001,2005a)DBAP – Maximize berth performance – Heuristic algorithm using subgradient method with Lagrangian Relaxation – same water depth for all the berthNishimura et al. (2001)DBAP with multi-water depth configuration - genetic algorithms Guan et al. (2002)Developed a heuristic for the BAPC with the objective that minimizes the total weighted completion time of ship servicesPark and Kim (2002)BAPC - minimize the costs of delayed departures of ships –subgradient optimization methodKim and Moon (2003)BAPC – simulated annealing methodLiterature review on the BAP

اسلاید 14: PaperPropertiesImai et al. (2003)Extended the BAP in Imai et al. (2001, 2005a) - treat the ships with different prioritiesImai et al. (2005b)BAPC – heuristic algorithm - handling time depends on the berthing location of ship Cordeau et al. (2005)A tabu search heuristic for the DBAP - both discrete and continuous location indexesImai et al. (2007)BAP with simultaneous berthing of multiple ships at the indented berth - potentially useful for fast turnaround of mega-containershipsLiterature review on the BAP

اسلاید 15: A linear integer program was formulated.The objective is to minimize the penalty and the additional handling costs. Simultaneously determines the berthing time and location. The wharf is considered to be a continuous space.The simulated annealing algorithm was applied to the problem. Kim and Moon(2003)

اسلاید 16: Kim and Moon(2003)(cont’d)

اسلاید 17: Kim and Moon(2003)(cont’d)

اسلاید 18: Kim and Moon(2003)(cont’d)

اسلاید 19: Kim and Moon(2003)(cont’d)

اسلاید 20: Kim and Moon(2003)(cont’d)

اسلاید 21: Nishimura et al.(2001) Dynamic berth allocation to ships in the public berth system.The objective is to minimize the total service time of incoming ships.A non-linear integer program was formulated.A GA-based heuristic was employed to solve the problem.

اسلاید 22: Nishimura et al.(2001)GA flowchart

اسلاید 23: Lee and Chen(2008)The objective is to maximize the total utility.Included a number of practical considerations not seen in previous papers.The problem is dynamic.The space is continuous.The ships berthed within one of several preferred sections, which are independently defined by the agents of each ship. Ships are berthed on a FCFS basis, but shifting the position of a ship to make space for another is also allowed. The required clearance distance between ships berthed side by side, which depends on the ship lengths as well as the berthing order, is also considered.

اسلاید 24: Lee and Chen(2008)(cont’d)The proposed solution process solves the problem in three stages: In the first stage it generates a number of candidate berthing allocations for each ship. In the next stage it uses a neighborhood search heuristic to come up with a good combination of feasible candidates. Finally a greedy approach further improve the solution.

اسلاید 25: Lee and Chen(2008)(cont’d)Flow chart of the neighborhood search stage

اسلاید 26: The simultaneous berth and quay crane allocation

اسلاید 27: Nishimura, E., Imai, A., Papadimitriou, S., 2001. Berth allocation planning in the public berth system by genetic algorithms. European Journal of Operational Research 131, 282–292.Kim, K., Moon, K., 2003. Berth scheduling by simulated annealing. Transportation Research B 37, 541–560.Imai, A., Sun, X., Nishimura, E., Papadimitriou, S., 2005. Berth allocation in a container port: using a continuous location space approach. Transportation Research Part B 39, 199–221.Imai, A., Nishimura, E., Hattori, M., Papadimitriou, S., 2007. Berth allocation at indented berths for mega-containerships. European Journal of Operational Research 179, 579–593.Reference

اسلاید 28: Reference(cont’d)Wang, F., Lim, A., 2007.A stochastic beam search for the berth allocation problem. Decision Support Systems 42, 2186–2196.Imai, A., Chen, H., Nishimura, E., Papadimitriou, S., 2008. The simultaneous berth and quay crane allocation problem. Transportation Research Part E 44, 900–920.Lee, Y., Chen, C., 2008. An optimization heuristic for the berth scheduling problem. European Journal of Operational Research, Article in press.Liang, C., Huang, Y., Yang, Y., 2008. A Quay Crane Dynamic Scheduling Problem by Hybrid Evolutionary Algorithm for Berth Allocation Planning. Computers & Industrial Engineering, Article in press.