1、SDVRP 的算法研究综述摘 要：作为企业的“第三利润源泉” ，物流日益受到企业的关注。但物流运输成本过高，日渐成为制约我国物流业发展的主要瓶颈。文中对国内外前沿成果进行分析和归纳的基础上，介绍了主要的 SDVRP 求解算法，并针对不足提出了新的求解途径。 关键词：需求可拆分车辆路径问题；精确算法；启发式算法 一、引言 伴随着全球经济一体化，社会分工日趋细化，配送功能从企业中外包出来。在我国，第三方物流作为一个新兴产业，于 20 世纪 80 年代后期开始快速发展。但由于起步较晚，物流运作水平与发达国家相比仍存在较大差距，其中最突出的问题就是物流成本高。国家发改委、国家统计局和中国物流与采购联合
2、会联合发布的 2012 年统计数据显示1，全国社会物流总费用为 9.4 万亿元，占 GDP 的比重为 18%，而同期新加坡、美国等发达国家物流总费用占 GDP 比重仅为 8%-10%。运输成本是物流成本的重要组成部分，2011 年与 2012 年的全国物流运行统计数据显示，全国社会物流总费用中运输成本分别为 4.4 万亿元与 4.9 万亿元，占社会物流总费用的比重分别为 52.8%与 52.5%，以上数据显示，我国运输成本占物流总费用比例高，且增长较快，因此降低运输成本，无疑是提高运输质量与效率，促进物流产业发展的重要途径。 配送中心是物流配送网络的枢纽，是企业实施供应链管理的重要设施之一。配
3、送中心接受并处理末端用户的订货信息，根据客户的需求进行配送。其主要任务是处理不确定环境下的订单整合（Order Consolidation，OC）和车辆路径问题（Vehicle Routing Problem，VRP） 。VRP 是物流配送优化的核心环节，配送路线的规划合理与否都将对配送成本、时间和效率产生较大的影响，特别是在有着多客户需求且其路径规划比较复杂的情况下，如何确定合理的配送路线，是配送规划过程中一项非常重要的工作。 二、SDVRP 的常用求解算法 SDVRP 是传统 VRP 的一个较新分支。自从 SDVRP 被提出后，对其求解算法的研究一直是研究的重点和难点。Archetti e
4、t al. （2005）指出2，当 Q=2 时，具备整数需求的 SDVRP 可以在多项式时间里得到相对满意的解；当 Q2 时，SDVRP 则成为一个 NP-hard 问题。而在 Archetti et al. （2010）的研究里2，通过对特定图中 VRP 和 SDVRP 的计算复杂度进行研究，其结果表明，在某些特定的图中，SDVRP 的计算复杂度不会难于 VRP。目前，关于 SDVRP 的主要求解算法主要分为精确算法和启发式算法两大类： （一） 精确算法 精确算法可以求得问题的最优解，但是，其计算时间会随问题规模的扩大呈指数增长，因此，精确算法只适用于求解小规模问题。第一种精确算法由 Dro
5、r et al. （1994）于 1994 年提出2，在其研究中，他们提出了一个集合新的有效不等式类的弧流列方程式，其实验结果证明不等式在求解下界上得到显著改善，在大多数的算例中，对上下界差值的改善超过 30%。Desaulniers （2010）设计了一种分支定价法优化带时间窗的 SDVRPTW 的运输成本2。当需求确定且顾客数目小于 100 时，该优化方法表现优异。Gulczynski et al. （2010）研究了带最小运输量约束的 SDVRP2，并建立了一个混合整数规划模型优化该问题的运输成本。Hertz et al. （2012）对有一个拥有不同车型的车队和很多仓库4，并且顾客需求
6、量大于车载容量的水泥运输问题进行了研究。在他们的论文中，他们提出了一个两阶段整数线性规划模型解决这种 SDVRP。 （二） 启发式算法 当问题规模较大，利用精确算法无法在有效时间内求得最优解时，通常釆用启发式算法求取“近优解”或“满意解” 。Dror & Trudeau （1989，1990）提出了第一个基于局部搜索的启发式算法2。Archetti et al. （2006）提出了一种禁忌搜索算法2，实验证明虽然计算速度相对较慢，但此算法在计算效率上明显优于 Dror & Trudeau 提出的基于局部搜索的启发式算法。Boudia et al.（2007）在遗传算法的基础上提出了一种文化基因
7、算法2，该算法对局部搜索过程进行强化，并整合距离策略以控制群体的多样性。通过与 Archetti et al. （2006）的算例集进行对比测试3，发现禁忌搜索算法在某些算例上其计算结果优于Archetti et al. （2006）提出禁忌搜索算法。除此以外，为了规避单一算法计算速度慢或者计算效率过低的问题，Chen et al. （2007） 、Archetti et al. （2008）和 Jin et al. （2008）提出了三种不同的混合启发式算法2，其中前两种算法的实验结果与 Archetti et al. （2006）相比在很多的算例上，都得到了不同程度的改进。而 Jin et
8、 al. （2008）相对割平面法在 Belenguer et al. （2000）所测试的 12 个算例中的 6 个中，都能够求得更好的上下界。2 三、结论 通过对 SDVRP 的常用算法进行总结和归纳，我们发现 SDVRP 的复杂性决定了利用精确算法和传统的启发式算法很难得到满意的解，精确算法可以得到相对精确地最优解，但是运算效率较低；启发式算法运行时间较短，很容易陷入局部最优，或者出现无法收敛的现象。但随着计算机硬件和软件的进步，现代启发式算法的运行效率得到很大的改善。从文献检索的结果看，目前，已经有学者开始采用以现代启发式优化算法为核心，结合系统仿真的方法对 SDVRP 问题进行建模与
9、优化。随着全球供应链管理观念的流行，物流管理的水平日益成为衡量一个国家综合能力的重要指标，对 SDVRP 问题进行研究不仅可以很大程度上减少国内物流运输成本过高的现状，而且具有很高的经济意义。 参考文献 1国家发展改革委，国家统计局，中国物流与采购联合会.2012 年全国物流运行情况通报R.http：/ 2Archetti， C.， M. G. Speranza. Vehicle routing problems with split deliveries. International Transactions in Operational Research. 19（2012）：3-22 3A
10、rchetti， C.， Hertz， A.， Speranza， M.G. A tabu search algorithm for the split delivery vehicle routing problem. Transportation Science ， 2006（40）： 6473. 4Hertz， A.， M. Uldry， and M. Widmer. Integer linear programming models for a cement delivery problem. European Journal of Operational Research 2012（222）： 623631.
