Multi-agent-based Fuzzy Dispatching for Trucks at Container Terminal

Published Online December 2010 in MECS                                  and Computer Science

Modern container terminal consists of containers, ships, handling equipments, communication equipments, berths, container yards and human resource, etc. The loading/unloading equipments at a container terminal are mainly Quay Cranes (QCs), Yard Cranes (YCs) and Container Trucks (CTs). Containers arrive at a terminal by truck and are stored in the terminal yard. The flow of containers is composed of an import flow, i.e. containers arriving at the terminal from the sea, to be directed to the final destinations by trucks or trains, and an export flow, i.e. containers leaving the terminal on ships1, 2.

Since container ships arrive at terminal randomly and their loading capacities are also stochastic, the problem of terminal dispatch decision-making is discrete and dynamic. The target of terminal equipment dispatching is to make the existed resource of terminal most and to optimize dispatching decision-making in order to shorten

The open research has been supported by the project fund of Natural Science Foundation of China(60904067/F030207).

the time in port for ships (transshipment time) on the basis of technological process of loading and unloading.

The most popular strategy for dispatching CTs is a static dispatching mode or a semi-dynamic dispatching mode, which is that several CTs are fixed to a QC or to some QCs (loading and unloading one ship) to make delivery tasks for period of time. Although the traditional dispatching rules are simple to use, one drawback of these rules is that in the yard and wharf apron, half of the round trip is empty; if the operating line is longer, it is likely that all CTs serving for a QC would be waiting in yard and the QC would be idle simultaneity. Contrarily, if the operating line is shorter, some CTs servicing for a crane maybe be waiting in line at the quay. This operation mode, has not only leaded to waste of manpower, material, but also low utilization rate of equipments 3-6.

To overcome this problem, when a CT becomes idle and needs a delivery task to be assigned, all CTs must be considered simultaneously as well as all the delivery tasks. That is, multiple tasks are matched with multiple CTs in order to decrease rate of empty loading and waiting time in condition that containers are handled by QCs normally and continuously. The dispatching decision must be made in many-to-many basis instead of one-to-many basis. This is called dynamic dispatching, however, which is more difficult to realize compared with traditional static dispatching style. Furthermore, the optimal decision-making for all the CTs is computationally impractical especially when the number of CTs involved is large. Also, dispatching decisions must be made by a central processor that has complete information on states of all the CTs and workstations.

Since Agent has some intelligence to fulfill tasks in an automatic way, receive information, negotiate about affair and can confederate with other ones to solve complex problem, it can reduce manual workforce and information burden. So, Agent technique has been used extensively in many applications such as enterprise modeling, SRM, ERP, production and control dispatching, raw material process and inventory management2,7,8. Agent technique is helpful to such complex problems as dispatching CTs.

CTs dynamic dispatching problem is a multi-objective optimization problems, including maximizing CTs utilization, minimizing the total empty travel time, reducing waiting line of equipment and the optimal path selection, etc., which will inevitably be affected by many factors and constraints, such as container ships arrival at terminal randomly, their stochastic loading capacities, the terminal layout of the configuration and mechanical equipment, ship loading, CTs driving distance and other factors. The actual dispatching often contains the experience and knowledge with its inevitable ambiguity.

This paper focused on how to consider these factors synthetically and fuse experience and intelligence dispatching personnel rationally in dispatching the CTs at terminal. Therefore, it is necessary to introduce fuzzy reasoning into decision-making of dispatching. According to the container terminal link with dispatching involved in the internal resources, production, process and characteristics of relationship, the dispatch of CTs can be defined as the assignment of CT Agent (equipment operating Agent) to a delivery task allocated by CT dispatching Agent (equipment decision-making Agent) which is responsible for the external environment.

• II.  .MAS A PPLIED IN C ONTAINER T ERMINAL AND

S CHEDULING

Multi-Agent system (MAS) is a system that consists some Agents with some resources and abilities, these Agents are independent to each other but can also interact with each other, and the system mainly focuses on the intelligent activity to resolve problems, to cooperate with each other in an environment isolated logically or physically. These Agents cooperate and supply services to each other with the same goal. The activities of each Agent are independent and autonomous, the goal and activity of one agent is not constrained by another, and the conflicts between Agents can be resolved by contest or negotiation. 2,7,9

Currently, by the knowledge type used to resolve problems, agents have 5 categories:

• •    Agents have linear programming, dynamic

programming, integer programming knowledge;

• •    Agents have heuristic, field issue resolving

• knowledge based on;

• •    Agents have AI network issue resolving

• k nowledge based on AI network optimization;

• •    Agents have genetic algorithms, simulated

• a nnealing algorithm issue resolving knowledge based on bionics optimization;

• •    Agents have special optimization methods.

In recent years, Multi-Agent technology has been applied in operation of container terminal and scheduling in other fields. Degano and Pellegrino10 apply agents in operating cycles called export, import, and transshipment in an intermodal container terminal. The dispatching of containers and the stacking or storage of containers is touched upon in the research. Petri nets are used to assist in fault diagnosis and recovery. Their monitoring system uses agents that detect disturbances to a Daily Process Plan. Rebollo, et al.11 have suggested the multi-agent system paradigm in a few papers in order to solve the port container terminal management problem and specifically the automatic container allocation in order to minimize the time a ship is berthed. The use of wrapper agents is suggested for legacy systems in order to provide access to the database, along with communication with external software. Thurston and Hu12focused on the berth allocation and the crane policies. The researchers simulated the PECT terminal in Busan, Korea by testing various policies with physical and logical agents. The agent based simulator results indicated that the stronger the partnership relationships between shipper agents and CT operator agents, the faster the handling of containers.

LIAO Qiang9 put forwards an approach based on field bus and multi-agent for job-shop dynamic scheduling problem. The approach is a hybrid multi-agent scheduling one. In this approach, there is a primary agent that sends scheduling tasks to other secondary agents. After all secondary agents complete their scheduling tasks, they transfer the scheduling results to the primary agent. Then the primary agent modifies these results until getting a good scheduling solution. Wen CHEN 13proposed A novel multi-agent based workshop dynamic scheduling(WDS) model which is presented and the principle of this model is given. Then the realization of ant colony algorithm for WDS and a new dynamic scheduling approach are introduced.

In this paper a model of scheduling system based on Multi-Agent of container terminal is set up. The system focuses on how to solve resource conflicts during scheduling at container terminal by means of Multi-Agent technology. The intelligent Agents in it possess Scheduling rule, reasoning arithmetic and optimization arithmetic. Relationship between delivery tasks and transport of CTs is considered as a contract net using the fuzzy set theory and method. The CNP-based dispatching method assumes a market system in which CTs attempt to earn money as much as possible by performing delivery tasks with the highest possible price at the lowest possible costs, and delivery tasks attempt to pay charges as less as possible by hiring CT with the lowest possible opportunity cost through tendering, bidding and contracting of tasks for collaborative work. The advantage of the CNP-based dispatching method is simple, convenient, strategies for the tasks assigned with good performance and openness and can be easily realized the load balance between various resources.

• II.    C ONTAINER TERMINAL SCHEDULING SYSTEM

• A.    Problems of container terminal scheduling system

The container terminal schedule system focus on the process of container transport by Quay Cranes and Yard Cranes between the containership and the container yard, shown as Figure 1. The primary objective is the reduction of the time in port for the ships by maximizing the productivity of the gantry cranes, or in other words, minimizing the delay times of container transports that causes the quay cranes to stop.

As a whole, all resources of loading/unloading are certain and the resource allocated to every task is limited. Therefore it is necessary to arrange the tasks of loading/unloading properly, to manage, allocate and usage exited resources efficiently and to avoid process failure, block or queue. Investments may for instance concern the berths, Quay Crane, and Yard cranes.

• B.    Rules of Scheduling Equipments at CT

After ship berthing, the equipments at terminal must be arranged according to length, capacity est. of container ship.

Containers are moved from berth to the storage area to be stacked or placed in an area for dispatch or containers from the stack are delivered to the quay crane at the berth to be loaded on a ship. The import container information such as its number, weight, seal number, and other information are recorded along with the location identification to a central database, such as a yard in the terminal. Usually, every Quay Crane will be served with a fixed number of transport machinery, i.e. Container Trucks. Yard crane can transfer the containers in the terminal and can stack them to a certain height depending on the type of transport machinery employed and/or policies dictated by a yard manager. The Container Truck is a link between Quay Crane and Yard Crane. For fluent loading/uploading service by Quay Crane and Yard crane, it is considered how to scheduling the container trucks and how to optimize the path of each vehicle once the start and end point have been confirmed.

• III.    MAS FRAMEWORK OF CONTAINER TERMINAL S CHEDULING

• A.    Application of agent in scheduling

Port Scheduling System based on agents has 4

scheduling agent groups: Berth Schedule Agent, Quayside Crane (QC) Schedule Agent, Yard Crane(YC) Schedule Agent and Container Truck (CT)Schedule Agent. Port Container Scheduling System is complex, dynamic and multi-goal discrete system. Through researching on main domestic container terminals and their business process, appropriate model framework based on Multi-Agent is proposed. The article will analyze the MAS architecture.

• B.    Framework of the schedule system based on Multi

Agent

The Terminal Scheduling System based on agents consists different knowledge agent groups; the knowledge representing methods of each type of agent are different; the agents are connected through the communication network based on which agent cooperate with each other through communication level.

Figure 1 shows the architecture is of the system and break the problem into several sub-problems, each subproblem is solved by a specific Agent, which is relatively independent, has collaborative relationship and can communicate with other Agents. The system includes 10 Scheduling Agent: Berths Assigning Agent, Yard Allocation Agent, Quay Crane Scheduling Agent, Yard Crane Scheduling Agent, Container Truck scheduling Agent, Berth Agent, Yard Agent, Yard Crane Agent, Quay Crane Agent, Container Truck Agent, Which are the horizontal and vertical relationships between them. Among these Agents, Berths Assigning Agent, Yard Allocation Agent belong to Facilities Controlling Agent, Quay Crane Scheduling Agent; Yard Crane Scheduling Agent, Container Truck scheduling Agent Equipment

Container terminal collaborative scheduling platform based on Multi-Agent

Database           |         Knowledge Base | Inference Engine | Cooperative Management

Communication Level

BA-Berth Assigning; QCS- Quay Cranes Scheduling; CTS- Container Trucks Scheduling;

YCS-Yard Cranes Scheduling; YA- Yard Allocating figure 1. framework of container terminal schedule system based multi-agent

controlling Agent; Berth Agent, Yard Agent are Facility Agents and Yard Crane Agent, Quay Crane Agent, Container Truck Agent are Equipment Executing Agent. Facility Agents and Equipment Executing are respectively responsible for specific management of Facilities Controlling Agent and equipment controlling Agent. The core of every Agent consists Knowledge Database, Reasoning Machine and Competitive manager. Knowledge Database consist the Agent’s own selfinformation, information about other concerned Agents , reasoning methods and optimization algorithm. Reasoning Machine is the key module to make schedule decision on basis of Knowledge Database and Task Controller (including Task Scheduled Queue, Task Operated Queue, State of Task). Cooperative Manager’s task is to negotiate with other agents or cooperate with others and solve conflicts. The communicator is interface of the intelligent Agent and is responsible for connecting to other agents. Through communicator, the Agent can communicate with others, apperceive environments, gain information, issue tasks message, monitor the status of other Agents, etc.. It contains methods for sending and receiving messages as well as functions for scheduling various data type, which are required to solve the particular tasks to which the Agent belongs.

• IV.    N ET P ROTOCOL BASED ON BIDIRECTIONAL

NEGOTIATION

In the contract negotiation protocol Agent network, different types of equipment in collaboration between the task request and response with announcing, bidding, and awarding in contract net. In the form of traditional network, there are some drawbacks such as frequent communication, waste of resources and unclear tender evaluation scheme. If this phenomenon exists, especially with large scale, resources of dispatching system would not be used reasonably and effectively, which would lead a serious threat to the whole system.

Considering the load of communication and consultation efficiency in system, the bidirectional negotiation mechanism was adopted. On the one hand, equipment operating Agents report their respective status, needs and personal benefits to CT dispatching Agent; on the other hand, CT dispatching Agent is responsible for sensing the external environment, and allocating tasks to CT Agents properly to minimize global benefit. Furthermore, CT dispatching Agent no longer releases bidding information to all executing Agent unconditionally, but firstly detects which execute Agents submitted applications dispatching plan before releasing bidding information, and then invites public bidding among these operating Agent.

Through the bidirectional negotiation mechanism, the load of communication in system is greatly decreased and negotiation efficiency is greatly improved. Meanwhile, due to operating Agents actively notify the decisionmaking Agent their state, which makes the system master the whole status relatively timely and have a quicker reaction ability to abnormal cases.

In evaluating tender, fuzzy set theory and method is adopted to couple multiple factors on the tasks to assess to their urgency, which is a new method, called fuzzy-control-based CNP in multi-Agent-based dispatching system.

The process of dispatching CT Agent is shown in figure 2.

Figure 2. Sequence of dispatching tasks based on CPN

• V.  F UZZY REASONING PROCESS OF DISPATCHING

DECISIONS BASED CNP

• A.    Fuzzy reasoning process of dispatching decisions

Based on the contract agreement of Multi-Agent, there exists three points of decision-making in process of announcing, bidding, and awarding among the Agents, into which fuzzy assessment for distributing tasks at handling operation spots is embedded. That is fuzzy CNP technology proposed in this paper.

The realization of fuzzy dispatching decisions also needs to describe the knowledge model of dispatching knowledge and practical reasoning information of operations to produce the required control information. This task is completed by inference machine of Agents, whose core is fuzzy reasoning based on synthesis principle of fuzzy relationship. The structure of fuzzy reasoning controller is shown in figure 3.

Figure 3 . Modal of fuzzy assessment for distributing tasks

The inference engine for the multi-input and singleoutput, here are the four inputs, namely, traveled distance, priority of handling operation, the length of CT queues at loading location and the number of dispatched CTs; the output is the degree of dispatching emergency. Dispatching decision knowledge set consists of n subset, R 1 , R 2 … R n , being described in the next section. Each subset contains some knowledge of dispatching decision, which is described in a matrix form according to certain rules. The input information is given according to bidding document and database of Agents. The meaning or interpretation of the function module is based on the input linguistic variables to determine its value corresponding fuzzy sets A 1 ,A 2 ,A 3 and A 4 ; the role of information synthesis module is to synthesize the corresponding fuzzy knowledge set of inputs into one fuzzy set, that is, all input information is contained in one fuzzy set in order to achieve the follow-up of reasoning operations. Effect of fuzzy reasoning is to use and expertise subset R 1 , R 2 , ... R n , and the information of synthesis module A to obtain comprehensive information on the fuzzy relation composition operations in order to generate output result C. The result is also indicated by fuzzy sets. Linguistic matching function with the fuzzy decision module is translate the result into output language, with variable U, or the result of this reasoning is converted to exact amount of that task dispatching emergency degree , to which Agents can refer to bid.

• B.    Fuzzy Reasoning in bid inviting

When there are multiple tasks at the same time to require CTs delivering, the decision is to make sure to determine the allocation sequence of the tasks. In the CT dispatching system, QC Agents and YC Agents send operating requests to CT dispatching Agent, CT dispatching Agent receives the requests and invite bidding according to conditions of the operation request. The principle of announcing tasks is FIFO (First In and First Out), that is, bidding document is usually produced by the sequence of tasks to release. But when there are two or more tasks arriving simultaneously, some factors of releasing tasks bidding are considered, such as priority of handling operation, the length of CT queues and the number of dispatched CTs and so on. Generally, the higher priority and the less number of CTs queuing the handling operation request is, the more preferentially it is released.

• C.    Fuzzy Reasoning in biding

Bidding is completed by CT Agent. Each CT Agent firstly assesses the issued tasks and then determine whether tender according to the assessed value. The factors to consider include priority of requested handling operation, traveled distance from current location to loading location, the length of CT queues at loading location and so on. Generally, the closer to the loading location the CT is, the higher priority the requested handling operation request is, and the shorter the length of CT queue is, the greater probability to be bided by CT Agent.

• D.    Fuzzy Reasoning in winning the bidding

After the CT Agent awarding CT Dispatching Agent bid, the CT Dispatching Agent should select a successful bidder from multiple tenders. The factor to select the successful bidder is usually the assessment score of dispatching emergency. The higher evaluation of dispatching emergency is, the greater probability to select the CT is.

• VI.    CASE ANALYSIS

There are four operation requested, shown in table I, and three idle CT, shown in table II.

After CT dispatching Agent that announcing the four tasks, three free CT Agents corresponding idle CTs gain task dispatching emergency degree according to distance, task priority, the number of arranged CT by fuzzy reasoning controller, shown in table III,IV,V.

TABLE I.     T HE INFORMATION OF IDLE CT S

CT Number	Current position	Operating state
CT301	0,1,0	idle
CT311	1,4,6	idle
CT312	1,3,4	idle

TABLE II.    T ABLE I T HE INFORMATION OF COOPERATIVE R EQUEST FOR TRANSPORTING

Task serial number	Request Equipment Number	Loading position	Task priority	The number of Arranged CTs	Loading container Number	Unloading position
1	QC105	0,2,0	7	2	CHPU2306280	1,2,3
2	QC111	0,4,0	6	1	SNBU476253	1,4,3
3	YC203	1,1,8	5	1	U4688360	0,1,0
4	YC208	1,3,2	4	1	AM2U4166740	0,3,0

TALBLE Ш.   Task dispatching emergency degree Evaluated

BY A GENT OF CT301

TALBLE V. Task dispatching emergency degree Evaluated

BY A GENT OF CT312

CT Number	Request Equipment Number	Loading position	Task important degree	Distance	Task dispatching emergency degree
CT312	QC105	0,2,0	5	1120	5.1
CT312	YC208	1,3,4	3	80	5.00
CT312	YC203	1,1,8	4	600	4.36
CT312	QC111	0,4,0	4	1120	4.0

CT Number	Request Equipment Number	Loading position	Task important degree	Distance	Task dispatching emergency degree
CT301	QC105	0,2,0	5	300	6.93
CT301	QC111	0,4,0	4	900	5.10
CT301	YC203	1,1,8	4	920	4.96
CT301	Y208	1,3,4	3	1260	4.00

(Note: Task priority and The number of Arranged CT are merged into Task important degree ;Distance is obtained based on Current position of CT and Loading position of and Current position Request Equipment., similarly hereinafter)

TALBLE W . T ASK DISPATCHING EMERGENCY DEGREE E VALUATED

BY A GENT OF C T311

CT Number	Request Equipment Number	Loading position	Task important degree	Distance	Task dispatching emergency degree
CT311	QC105	0,2,0	5	1240	5.10
CT311	QC111	0,4,0	4	840	5.10
CT311	YC203	1,1,8	4	980	4.96
CT311	YC208	1,3,4	3	420	4.36

Three CT Agents bid to QC105 whose emergency degree is the highest. CT dispatching Agent evaluates these bidders, shown in table VI. As the table shown, evaluated dispatching emergency degree of CT301 is the highest (shown in table VI), CT dispatching Agent rewards Agent of CT301 and meanwhile refuses to application of CT311 and CT312.

Then CT311 and CT312 select tasks to bid, whose dispatching assessed value of emergency is the highest among the remaining, namely QC111 and YC208. CT dispatching Agent respectively issue orders to CT311 and CT312 after evaluating.

TALBLE VI. Task dispatching emergency degree sort of QC105

Request Equipment Number	CT Number	Loading position	Task important degree	Distance	Task dispatching emergency degree
QC105	CT301	0,2,0	5	300	6.93
QC105	CT311	0,2,0	5	1240	5.1
QC105	CT312	0,2,0	5	1120	5.1

• VII.    C ONCLUSION

A fuzzy-CNP-based method was suggested for dispatching CTs to maximizing CT utilization, minimize the total empty travel time and reduce waiting line of equipment. The dispatching method described in this study is different from other dynamic dispatching rules in that relationship between transport tasks and service of CTs has been taken as a contract net using the fuzzy theory and method of optimum allocation of multiple tasks to multiple CTs. Considering the load of communication and consultation efficiency in system, the bidirectional negotiation mechanism was adopted. The fuzzy-CNP-based dispatching model was provided and fuzzy reasoning process of dispatching decisions was suggested.

Because this paper introduces a new concept for CT dispatching, only a limited number of practical factors were considered. Thus, further research is necessary to study on the method considering more practical factors before it can be applied in practice.