Study Of Multi-Agent Based Two-Stage Real-Time Vehicle Scheduling System

Transportation and vehicle scheduling plays an important role in the supply chain management. As the market competition intensifies continually and the customers need change quickly, the enterprises can't make the static distribution plan based on all known information through traditional methods. Even though they make a plan, it's difficult to implement because of many external factors. So many researchers begin to pay more attention to the study of real-time Vehicle Routing Problem (VRP). However the current study is not enough in many ways, there are still a number of problems to be researched, such as how to deal with real-time events, how to design simple and effective algorithm, etc.The key to solve the real-time VRP is how to get information timely and adequately, and make in-time response. The former problem has been solved as the development of IT technology. The latter one needs to design a simple and effective method to change the static plan rapidly without decreasing the solution quality according to some optimization strategy. To implement this goal, Multi-Agent system is used to solve the real-time VRP, which can satisfy the variety in the distribution system, such as the geographical distribution of vehicles, the dynamic change of information, and the changes of customers any time. Multi-Agent system has been widely used in many industrial systems.In this paper, real-time VRP with time window is studied. We design a system solving model based on Multi-Agent negotiation mechanism, and the architecture and function of the model are described. Also we consider dealing with static plans and real-time orders respectively, and propose a two-stage algorithm based on the Multi-Agent System:The first stage is to generate the static plan. Two different methods are studied in this paper: the Multi-Agent negotiation mechanism and the improved genetic algorithm. The experimental results of Solomon benchmarks show the improved genetic algorithm has advantages of wide applications, less computing time, and high precision;The second stage is to simulate the generated static distribution plan and handle the real-time events (new orders arrival). Vehicle agents begin to service the assigned customers one by one. And the simulation system deals with the real-time events based on the negotiation mechanism of Contract-NET Protocol. We focus on the improved negotiation algorithm based on traditional Contract-NET Protocol in Multi-Agent system, and point out the disadvantage of the traditional Contract-NET Protocol. And a number of improvements of the Contract-NET negotiation algorithms are proposed. The experiments results show the improvement algorithms can significantly reduce the negotiation numbers and the negotiation time without decreasing the solution quality distinctly.In order to validate the reliability and validity of the new framework, this paper proposes a new kind of testing benchmark for real-time VRP, which is different from the traditional benchmarks and can verify the capability of making static plan and the rapid reactivity of real-time orders.