摘要
多车场带时间窗车辆路径问题是车辆路径问题集合中的一个极为复杂、且仍未得到较好解决的问题。针对这一问题,建立了它的整数规划数学模型,提出了一种改进型变邻域搜索算法。该算法在初始解的构造阶段采用聚类方法完成客户的分配,运用混合算子进行局部搜索,通过后优化过程增强寻优效果,引入模拟退火模型对新解的接受进行控制。最后,在Cordeau提出的标准用例上对改进型变邻域算法进行了实验,实验结果更新了大部分目前该问题的最优解,并在算法的稳定性和求解时间上体现出一定优势。实验表明,该算法是一种求解多车场带时间窗车辆路径问题的有效方法。
The Multi Depot Vehicle Routing Problem with Time Windows（MDVRPTW） is an important variant of the Vehicle Routing Problem（VRP）,which is extremely complex and still not resolvedr well.To solve the problem,mathematical model of the MDVRPTW is constructed and a modified variable neighborhood search algorithm is proposed.In the algorithm,a clustering algorithm is utilized to allocate customers in the initial solution construction phase,a hybrid operator is applied in the local search phase to come up with a local optimal solution,a post optimization procedure is incorporated to further improve the best found solutions,the idea of simulated annealing is introduced to take control of the acceptance of new solutions.The performance of the proposed algorithm is tested on the benchmark instances proposed by Cordeau and compared with other algorithms in the literature.The results indicate that the proposed algorithm is effective in solving the MDVRPTW and showes some advantage both in stability and runtime.And finally most of the old optimal solutions are updated.
出处
《中国管理科学》
CSSCI
北大核心
2011年第2期99-109,共11页
Chinese Journal of Management Science
基金
国家自然科学基金资助项目(70801008)
国家自然科学基金重大研究计划(90924006)
国家杰出青年基金(70725004)
辽宁省博士启动基金(20071091
20081093)
关键词
多车场带时间窗车辆路径问题
变邻域搜索
后优化
模拟退火
multi depot vehicle routing problem with time windows
variable neighborhood search
post optimization
simulated annealing
