Multi-agent Tender-Bidding Hybrid Genetic Algorithm for Dynamic Vehicle Routing Problem with Time Windows
The paper presented an algorithm, which is called ITBA for short, to meet the needs of the dynamic routing plan and static routing plan. The algorithm combines DVRP with static VRP together. The DVRP is disjoined into a series of snapshots; the routing plan of snapshot at the moment is dealt with a static VRP. The next nodes of the vehicles current location are regarded as their start nodes and their depots as the end nodes for dispatching enough computational time. So the DVRP is turned into a series of static VRP. All routes are readjusted by using the ITBA as soon as a new demand arrives.The real time routing parameters, such as travel time and traffic conditions etc, are employed to treat with the time-dependent travel time problems in the process.The ITBA algorithm deploys an agent as the tenderer and each vehicle has an agent that is regarded as its bidder. The tenderer agent takes charge to send out the tender notice, which includes the all information of the node that is being readjusted,to all bidder agents in the global scope. And each bidder agents takes charge to seek the best inserting point in its tour and to compute the distance increment after the node has been inserted.Finally, the node is added into the vehicles tour that its distance increment is the least. The above process is repeated to form the iterative tender-bidder algorithm (ITBA). The initial population is produced and the fitness of the offspring is improved in the genetic algorithm by the ITBA, which is combined with the genetic algorithm to form the hybrid genetic algorithm. In the hybrid genetic algorithm, the evolutional process of the monkey colony is adopted to accelerate the computational convergence,and the mutation rate is increased consumedly to avoid the precocity of the population. The algorithm is proved to have good robustness and availability.
DVRP Hybrid genetic algorithm Dispatch policy Tender-Bidding algorithm
HONG Lianxi DONG Shaohua HOU Wenying
Machine Engineering College University of Science and Technology Beijing Beijing, 100083, China;Comp Machine Engineering College University of Science and Technology Beijing Beijing, 100083, China
国际会议
厦门
英文
60-65
2006-07-27（万方平台首次上网日期，不代表论文的发表时间）