基于面向对象的离散事件仿真的VRP问题研究

Vehicle Routing Problem Based on Object-Oriented Discrete Event Simulation

针对车辆路径问题(VRP)研究的复杂性,提出了一种新的解决方案.首先对客户货物的配送过程建立离散事件仿真模型,在模型中,配送过程事件、资源等利用面向对象的方法进行描述,VRP问题涉及的各种约束条件在仿真流程中予以处理,所以该模型可以真实模拟复杂的车辆配送过程.然后利用遗传算法对离散事件的仿真结果进行优化,得到了车辆路径问题的最优解.这种将离散事件仿真和遗传算法相结合的方法可以有效克服精确算法和智能启发式算法较难解决多约束车辆路径问题的弊端.实验结果验证了新方法的有效性和可行性,由于仿真结果详细记载了配送的全过程,因此该方法对车辆路径问题的实际应用具有一定的指导意义.

A new solution for vehicle routing problem （VRP） is proposed in view of its complexity. First, discrete event simulation model of customer＇s distribution process is established. In this model, the events of distribution process and resources have been described by the object - oriented approach. A variety of constraints which VRP problem in- volves is processed in the simulation. The model simulates complicated vehicle delivery process. Then discrete event simulation results are optimized by the genetic algorithm. The optimal solution of VRP is finally obtained. The method which combines genetic algorithm with discrete event simulation technique can effectively overcome the disadvantages that the exact algorithms and intelligent heuristics algorithms are difficult to solve vehicle muting problem with multiple con- straints. The experimental results prove the feasibility and effectiveness of the proposed method. As the simulation results can document the whole distribution process in detail, this method has some significance to the practical application of vehicle muting problem.