基于Multi-Agent仿真的动态车辆路径算法研究

Dynamic vehicle routing algorithm based on Multi-Agent simulation

针对DVRP(Dynamic Vehicle Routing Problem,动态车辆路径问题)的复杂性和灵活性,考虑到DVRP问题中的客户需求、交通流和车队管理,提出将MATSim(Multi-Agent Transport Simulation,多Agent交通仿真)和DVRP算法相结合的策略,利用MATSim仿真框架构造一个动态的现实世界环境,结合DVRP算法来求解DVRP问题。DVRP算法采用的是结合进化算法和局部搜索策略的模因算法,同时给出了3种不同客户拓扑结构下的测试用例,并比较了DVRP算法与蚁群算法和禁忌搜索算法的结果,表明该算法具有更高的效率。

This paper proposes a strategy that combines MATSim, a multi-agent transport simulation system, with the DVRP Optimizer, an application for solving the dynamic vehicle routing problem. The MATSim framework can construct a dynamic real-world environment, considering the problem of customer demand, traffic flow and fleet management. The DVRP Optimer uses a memtic algorithm, consisting of an evolutionary algorithm and a local search procedure, for solving the DVRP. This paper gives out three types of service areas with a comparison of the solution quality among the DVRP optimization, ant colony algorithm and tabu search algorithm, shows that the algorithm is more efficient.