范昌胜, 郭 强, 岳爱峰
(1.陕西广播电视大学工程管理部, 陕西 西安 710068;2.西北工业大学理学院, 陕西 西安 710129; 3.山东师范大学图书馆, 山东 济南 250014)
VRP(Vehicle Routing Problem)是一个典型的NP-hard问题,属于经典的复杂组合优化问题[1].图1所示为有两个车场两个配送中心的车辆路径问题.研究求解约束条件下VRP问题的有效算法具有现实意义.
一般地,很难找到VRP问题的最优解,或者花费很多的时间才可寻找到最优解[2].即使在规模比较小的情况下,求解也比较困难.研究车辆路径问题(VRP)的方法,有针对小规模问题的精确算法、启发式算法和人工智能优化算法[3-12].启发式算法在求解车辆路径问题中占有重要地位.近些年来,模拟退火[12]、遗传算法[6,10]、禁忌搜索算法[5]、蚁群算法[9]以及它们之间结合形成的混合算法等仿生学智能优化算法[13,15]的兴起,为解决VRP 提供了新的工具.禁忌搜索被普遍认为是解决VRP 问题的最快的算法,而遗传算法则在快速搜索能力和全局最优性上有着明显的优势.本文将问题的数学模型做了更贴近实际的改进,将模拟退火算法和小生境遗传算法结合求解,不仅克服了遗传算法容易早熟、不稳定等缺点,而且可以很好地控制其早熟.在染色体编码上,与目前出现的编码方式不同[6],充分利用车辆路径问题解的特点,采用分段编码,使杂交变异方便有效,加快获得近似最优解.
多车场、多个配送中心、整车配送、多用户的VRP问题描述:(1)物流配送网络是由相互连通的多个车场、多个配送中心和多用户组成, 车场的车足够用,配送中心的货物足够多;……