Green Shipping Oriented Berth Allocation

The global concern about climate change, the rapid growth of bunker fuel prices, and the more stringent legislation, of governments and international organizations, on vessel emissions have been conveying the signals of the coming of a new green shipping era. Shipping lines and ports are therefore making great efforts to reduce fuel consumption and emissions from both vessels and container trucks. The berth is the place in the port where vessels moor for the service of loading and unloading their cargoes. The berth allocation problem (BAP) is thus the business operation interface of the shipping line and the port, which also provides the best chance to coordinate both parties’decisions on energy saving and emission reduction. In fact, a new research stream, named green berth allocation problem (GBAP), is forming in the field of BAP. This dissertation aims to contribute some theoretical studies to this new research stream, and to theoretically support the implementation of green shipping and the construction of green ports.This dissertation studies the GBAP in three decision contexts:(a) The terminal constructs the berth plan without considering the speed optimization of the vessels;(b) The speed optimization problem (SOP) is integrated into the BAP, and the terminal is regarded as the sole centralized decision maker; and (c) The terminal and the vessel are treated as separate autonomic agents. They make their own decisions in a decentralized context and coordinate with each other via a dedicatedly-designed negotiation mechanism. The latter two contexts are both driven by port-shipping coordination. More specifically, the studies in this dissertation can be summarized as follows.First, in the first decision context mentioned above, the berth allocation and quay crane assignment problem with green considerations is addressed. In the mathematical model, a convex objective function of the departure delay time is employed to describe the dissatisfaction of the shipping line resulted from excessive fuel consumption and vessel emissions due to the speed-up in the sailing leg to next port. Also the emissions from the container trucks are implicitly considered by imposing a constraint on the available working hours of the quay cranes in the planning horizon. To overcome the computational intractability and the optimality absence, the mixed integer nonlinear programming (MINLP) model is equivalently transformed to a mixed integer second order cone programming (MISOCP) model, which is solved by the branch and cut (B&C) solver CPLEX. Since the B&C algorithm is time-consuming and runs out of memory for some test instances, an outer approximation (OA) algorithm is put forward based on a novel decomposition towards the original MINLP model. Through numerical experiments, the efficiency and effectiveness of the OA algorithm are verified, and the sensitivity analysis on the key parameters is conducted.Second, the BAP and the SOP are integrated into a comprehensive optimization model, in which the terminal is the centralized decision maker assuming that the vessels will accept the arrival times suggested by the terminal. By adopting a new berthing strategy called VAT (Variable Arrival Time) and regarding the arrival times of the vessels as decision variables, a bi-objective optimization model is formulated, which aims to minimize the departure delay time of the vessels, and to minimize the fuel consumption and the vessel emissions in the sailing period. To run over the barrier of the nonlinear complexity introduced by fuel calculation, the model is cast as a MISOCP one. Meanwhile, the ε-constraint approach is employed to generate the Pareto efficient solutions of the model. Furthermore, the vessel emission calculation (in sailing periods) is conducted with the widely-used emission factors. Besides, vessel emissions in mooring periods are also analyzed through a post-optimization phase on waiting time. Experimental results demonstrate that the VAT strategy is competent to significantly reduce fuel consumption and vessel emissions, while simultaneously retaining the service level of the terminal.Third, the VAT strategy is extended to the tidal seaport, and the GBAP in the tidal seaport is studied. As far as we know, this is the first study on the BAP of the container terminal in the tidal seaport. The mathematical model reflects the influence of the tide on the sailing of vessels in the navigation channel, and is equivalently transformed to weaken the potential nonconvexity and the nonlinearity involved. Extensive numerical experiments are conducted to answer several interesting questions arising from the management of the tidal seaport. Apart from the economic benefit of the reduction of fuel expenses and the environmental benefit of emission mitigation, experimental results also show that the VAT strategy can substantially ease the influence of the tide on the seaside operations in the container terminal, and is an applicable substitute for deepening the navigation channel in the tide port. Moreover, a model on the BAP with discrete berth space is also formulated, which contributes to the literature on the BAP in the tidal bulk port in two aspects.Last, the GBAP in the decentralized decision context is considered, in which the terminal and the shipping line are regarded as rational but selfish agents.In our solution based on the multi-agent technology, the terminal agent solves its BAP, the vessel agent (the shipping line) optimizes its sailing speed, and the performance of the whole system is improved incrementally through an iterative negotiation procedure based on a dedicatedly-designed mechanism. This study designs the negotiation mechanism for the tide-independent vessels based on the shadow prices derived from the linear programming relaxation of the BAP model, and some heuristics for the tide-dependent vessels. Afterwards, the optimization models and the corresponding algorithms, which reflect the individual rationality of the terminal agent and the vessel agent, are discussed. For the speed optimization model of the vessel agent and the algorithms, some analytical results are introduced in the form of propositions and theorems, and the Newton’s method is employed to find the global optima. Besides the experimental results, the issue on how to deploy the multi-agent system with respect to hardware and software is addressed such that the decentralized VAT strategy can be put into practice.