基于真实路网的车辆路径问题研究

Solution to the Real Road Network Based Vehicle Routing Problem

车辆路径问题(VRP)是广泛应用于物流配送的组合优化问题。在实际应用中,传统的处理方法是先利用路网信息求出任意两点间最短路,生成完全连通图,然后进行VRP的优化求解,这样会浪费时间和空间,降低求解效率。因此,提出了一种基于真实路网的VRP建模方法,把任意两点间最短路的求解与VRP联合起来,通过仿真实验与传统的处理方法进行了比较,两种方法得到了相同的最优解,但基于真实路网的VRP建模方法在计算时间方面占优。

The paper proposes a modeling method for vehicle routing problem based on real road network which processes the shortest path problem and vehicle routing problem simultaneously. In a subsequent simulation experiment, the model proposed above is compared to the traditional one where the two yield the same optimal solution, yet the one of the paper is superior in computation time.