基于高维多目标优化的多车场车辆路径问题

摘要

车辆路径问题是运筹学中著名的NP问题,在运输领域中具有重要的现实意义.多车场车辆路径问题是其中的一个重要分支,作为单目标优化问题和低维多目标优化问题被广泛研究.然而,多车场车辆路径问题本质上是一个高维多目标优化问题.因此,论文针对问题的本质,从物流企业和客户两个不同的角度考察四个优化目标,提出了基于高维多目标优化的多车场车辆路径问题,构造了相应的框架MO-MDVRP,并运用NSGA-Ⅲ和Ⅰ-DBEA得到了两个算法实例MD-VRP-NSGAⅢ和MDVRP-IDBEA.在六个Cordeau数据集上进行仿真实验,实验表明,运用MDVRP-NSGAⅢ和MDVRP-ID-BEA求解MO-MDVRP是可行的,MDVRP-NSGAⅢ的效果显著优于MDVRP-IDBEA.%Vehicle routing problem is a well-known NP problem in operations research,which has important practical significance in transportation field.As one of the important branches,multi-depot vehicle routing problem has been widely studied as a single-objective optimization problem and a multi-objective optimization problem.However,multi-depot vehicle routing problem is essentially a many-objective optimization problem.Therefore,in view of the nature of the problem,four optimization functions are inspected from the view of logistics enterprise and customer.Next,multi-depot vehicle routing problem based on many-objective optimization is proposed.Then,a framework called MO-MDVRP is constructed for this problem.After that,instances of this framework based on NSGA-Ⅲ and I-DBEA are proposed,namely MDVRP-NSGAⅢ and MDVRP-IDBEA.The algorithms are tests on six Cordeau datasets.The experiments show that MDVRP-NSGAⅢ and MDVRP-IDBEA are feasible in solving MO-MDVRP.And MDVRP-NSGAⅢ is more effective than MDVRP-IDBEA in these datasets.