Bidding Agents Acquire Cargo in Online Auctions

by Pieter Jan 't Hoen

A growing field of applications for Multi-Agent Systems is the world of logistics and planning. CWI's research in the DEAL project focuses on optimising the use of road transport capacity through acquisition of cargo by agents bidding in online auctions. This promises a substantial gain in profit.

CWI's Evolutionary Systems and Applied Algorithms group headed by Prof. J.A. La Poutré is a participant in the Distributed Engine for Advanced Logistics (DEAL) project. The goal of this project is to optimise the use of road transport capacity in a logistics setting, using agent-based technology. Among other things, this involves providing an open market where business participants can conduct online electronic acquisitions and place orders.

As real-world scenarios in logistics and planning grow in size and complexity, classical centralised approaches become unwieldy and brittle. In a logistics setting, a centralised planner can be overwhelmed by the stochastic nature of real-world events. For example, new business opportunities arise that cannot be efficiently exploited. Furthermore, schedules can go awry and their repair can require extensive rescheduling . A Multi-Agent System (MAS) offers a robust alternative to a centralised planning approach. An individual agent within the system is an autonomous and adaptive piece of software. It is therefore able to learn to respond effectively to changing scenarios, and can efficiently solve tasks requiring multiple agents by communicating with and coordinating other agents. For example, MASs have been successfully applied to difficult supply-chain management problems where centralised control has failed. In the transportation setting, agents, which act for individual trucks or coalitions of transporters, are able to continuously optimise and update planning as incidents occur and new opportunities for profit arise. An agent can quickly assess the value of new cargo or inform relevant agents if a planned delivery is delayed because of traffic or an unexpected overhead in the unloading of a truck.

Agents increase profits by continuous acquiring new cargo for transportation in online auctions.

For application to transportation settings, research at CWI focuses on possible market mechanisms and bidding and negotiation strategies of the agents. CWI is developing robust, distributed market mechanisms as part of MASs for usage in (simulations of) the transportation sector. Online decentralised auctions serve as the model, where agents - representing trucks - bid for cargo. Current centralised planning is only able to utilise 40 to 60% of the total truck haulage capacity. Preliminary experiments show that continuous acquisition of new orders by agents bidding in online auctions (spot markets) can raise this to 80%.

A bidding strategy under further development at CWI is the use of decommitment as a tool for handling unknown future orders available for auction. Using a decommitment strategy, an agent is able to postpone the transportation of an acquired load to a more opportune time. This allows the agent/truck to bid in auctions it would not otherwise consider due to prior commitments. Experiments show that substantial increases in performance through the use of a decommitment strategy can be expected due to additional flexibility in the planning capabilities of the MAS. This increase in performance for the (abstract) model of the transportation sector can be seen as a lower bound for expected additional performance in practice. This claim is substantiated through experiments (see the links below for publications), which have shown that the relative impact of a decommitment strategy increases with the complexity of the world.

A full-scale MAS also facilitates communication and therefore advanced negotiation between agents. Logistics planning is faced with complex constraints and the varying goals and capabilities of the transporters. CWI has demonstrated through evolutionary simulation that agents can learn to negotiate successfully over complex multi-issue goals (see the links below for publications). Agents can also learn to exchange tasks/orders so as to improve performance for both parties. Negotiations between agents allow for continuous optimisation, while adaptivity promotes efficient negotiation strategies with specific opponents. Furthermore, agents can negotiate to form coalitions for the execution of complex tasks. For example, an order too large to be transported by one truck can be split up over a temporarily cooperating group of agents.

The DEAL project intends to deliver a working prototype of a platform supporting online acquisition of cargo using MASs in three years' time. Research will continue at CWI into the precise conditions and parameters required in the underlying model of decentralised auctions for successful application of an MAS in such a logistics setting. The research focuses on the market mechanisms required, ie which rules guide the bidding behaviour of the agents and how can agents best negotiate over a transport? This is comparable to the study of rules as found in a market economy. The application of the right type of intelligent software will play a major role.

Links:
http://www.almende.com/deal
http://www.cwi.nl/sen4
http://www.cwi.nl/~hoen

Please contact:
Pieter Jan 't Hoen, CWI
Tel: +31 20 592 4276
E-mail: hoencwi.nl