A MULTI-AGENT FRAMEWORK APPLIED TO THE QUAY CRANE SCHEDULING PROBLEM IN CONTAINER TERMINAL PORTS

Abstract

In container ports, the application of OR techniques to various complex and inter-related aspects of terminal operations is necessary to maintain high productivity in the fiercely competitive port management business. In this thesis, we deal with a small component of port operations, quay crane (QC) scheduling, which essentially is the determination of the order of discharging and loading operations that QCs perform so that both the completion time (or makespan) of vessel operation and QC gantrying amount is minimized. Here, we have consulted an industry practitioner to incorporate realistic QC clearance and inter-crossing constraints, container precedence and yard congestion constraints into our model, which can deal with any number of ships berthing in the planning horizon. The vessel™s load profile, number of bays and number of allocated QCs for each vessel are input parameters to the problem. CPLEX is used to solve the model to optimality for small test cases. We propose a multi-agent framework to deal with larger-sized problems. Lower bounds on the optimal vessel makespan can be obtained by ranking bay region according to the number of jobs in them. Vessel and QC agents are created and they are organized in a hierarchical fashion. Each agent is self-interested and their decisions are guided by a utility function. A key issue is how to configure autonomous agents such that their self-interested behavior leads to a near-optimal solution for the system as a whole. Although many papers have appeared on multi-agent systems, literature on the performance comparison between industrial solvers such as CPLEX, and multi-agent systems are scarce. We show that our MAS framework does a credible job in balancing the various objectives, and produces computationally-cheap yet high quality solutions.