Abstract
This paper presents a formalization of the bidding and awarding decision process that was left undefined in the original contract net task allocation protocol. This formalization is based on marginal cost calculations based on local agent criteria. In this way, agents having very different local criteria (based on their self-interest) can interact to distribute tasks so that the network as a whole functions more effectively. In this model, both competitive and cooperative agents can interact. In addition, the contract net protocol is extended to allow for clustering of tasks, to deal with the possibility of a large number of announcement and bid messages and to effectively handle situations in which new bidding and awarding is being done during the period when the results of previous bids are unknown. The protocol is verified by the TRACONET (TRAnsportation COoperation NET) system, where dispatch centers of different companies cooperate automatically in vehicle routing. The implementation is asynchronous and truly distributed, and it provides the agents extensive autonomy. The protocol is discussed in detail and test results with real data are presented.
Introduction
The Contract Net Protocol (CNP) is a foundational framework in Distributed Artificial Intelligence (DAI) for task allocation through negotiation. While the original protocol established the high-level communication patterns between managers and contractors, it left the internal logic—specifically how agents should formulate bids and how managers should select winners—largely unspecified. Furthermore, traditional CNP implementations often assumed perfectly cooperative agents and independent tasks. This paper addresses these limitations by introducing a formal model for marginal cost-based decision-making, task clustering, and asynchronous negotiation in a real-world transportation domain.
The TRACONET Framework and Marginal Cost Logic
The proposed system, TRACONET, models dispatch centers as autonomous agents. Each agent manages its own fleet and delivery tasks, aiming to minimize local transportation costs. To facilitate effective negotiation, the protocol formalizes the three-stage cycle of announcement, bidding, and awarding.
Central to this implementation is the use of marginal cost calculations. Instead of subjective suitability scores, agents calculate the precise change in their local objective function if a task set is added ($c_{add}$) or removed ($c_{rem}$). This "universal language" of cost allows agents with diverse internal optimization algorithms or business goals to interact seamlessly.
The paper defines upper and lower bounds for bids, distinguishing between "safe" pricing (guaranteeing immediate cost decreases) and "opportunistic" pricing. While opportunistic policies may lead to temporary "unbeneficial" awards, they allow the system to explore the solution space more rapidly, often reaching superior results in less time.
To handle task dependencies (e.g., packages with nearby destinations), the protocol supports task clustering, where multiple deliveries are grouped into a single atomic bargaining unit. This prevents the inefficiencies associated with negotiating interdependent tasks in isolation. Additionally, the system employs congestion control mechanisms, such as time-limit filters, to manage message traffic in truly distributed, asynchronous environments.
Experimental Evaluation
The protocol was validated using real-world vehicle and delivery data from a one-week period in Finland. The dataset involved 5 dispatch centers from two different companies, managing 77 vehicles and 771 deliveries. Constraints included vehicle capacity (weight and volume), maximum route duration, and distance-based costs.
In a 30-minute simulation, the decentralized negotiation achieved a 17% reduction in total transportation costs. Even within a shorter 15-minute window, an 11% saving was realized. Each agent processed between 100 and 200 local control cycles, demonstrating the system's suitability for real-time operative decision-making. The congestion control mechanisms ensured the system remained functional despite high volumes of announcement messages.
Discussion and Future Directions
The results demonstrate that marginal cost-based CNP can effectively reach "k-optimal" states—where no further beneficial exchanges of $k$ tasks can be made between any two agents—without requiring a global optimizer. This approach allows for a "plug-and-play" architecture where agents can use entirely different local optimization heuristics as long as they can output a cost delta.
However, several areas for improvement remain. Current agents lack foresight, making decisions based only on their current state without anticipating future contracts. Future work could explore multi-agent contracts (beyond bilateral deals), counterproposals to speed up convergence, and more sophisticated profit-sharing mechanisms for purely competitive environments. Additionally, handling scenarios where agents start without a feasible initial solution remains a challenge for future research.
Summary updated