Improved Multi-Agent System for the Vehicle Routing Problem with Time Windows

The vehicle routing problem with time windows (VRPTW) involves assigning a fleet of limited capacity vehicles to serve a set of customers without violating the capacity and time constraints. This paper presents a multi-agent model system for the VRPTW based on the internal behavior of agents and coordination among the agents. The system presents a formal view of coordination using the traditional contract-net protocol (CNP) that relies on the basic loop of agent behavior for order receiving, order announcement, bid calculation, and order scheduling followed by order execution. An improved CNP method based on a vehicle selection strategy is used to reduce the number of negotiations and the negotiation time. The model is validated using Solomon’s benchmarks, with the results showing that the improved CNP uses only 30% as many negotiations and only 70% of the negotiation time of the traditional CNP.