Application of multi-agent technologies to transportation problem with time windows and multiple depots

In this paper a multi-agent approach to MDVRP (Multiple Depot Vehicle Routing Problem with Time Windows) problem is presented. The multi-agent system consists of interacting trucks, depots and orders interacting in an artificial environment. Truck agents are seeking to maximize the number of orders delivered with minimal route cost. Order agents are looking for a truck with minimal tariff. Depot agents are in charge for the whole coordination. Every agent can interact only with agents in its local neighborhood. The performance of the system depends on the number of messages processed by every agent. Delaney triangulation based scene structure is proposed to limit the intensity of agent negotiations. The system was evaluated on a number of testbed problems known from literature. It's shown that solutions obtained by the method proposed is worse by 10-30