论文部分内容阅读
摘要：SDVRP允许单一节点的订单需求由多个车辆进行配送，与传统VRP相比可提高车辆利用率并降低车辆使用数目和运输成本。文中在国内外研究的基础上，重点介绍了SDVRP的主要分支，并与国内研究现状对比，发现我国在该领域的研究仍处于起步阶段。
关键词：需求可拆分车辆路径问题；分支；国内现状
一.引言
传统的VRP一直是网络最优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，多年以来，受到国内外广泛关注。传统的VRP假定每个客户端的需求只能由一辆车来完成，即需求不可以被拆分，但实际应用中，有可能会存在相当一部分任务点的需求量比较大，此时，如果仍然要求每个客户点只能由一辆车来完成服务，势必会造成车辆的空载率提高，浪费运输资源。1989年Dror & Trudeau首次提出了SDVRP的概念[1]，并指出 SDVRP 是一种约束松弛的 VRP，即每个客户点的需求由传统VRP中的只能由一辆车满足，扩展为可以由多辆车满足，这可使得车辆数量和路线总长得到节约。
二.SDVRP的分类
根据研究重点的不同，SDVRP 有多种分类方式。虽然诸如带时间窗、带集货和配送的VRP在传统VRP问题中已经被大量研究，但是，在SDVRP情况下，仍然会得出一些有意义的结论。根据对国内外文献进行归纳，常见的SDVRP的分支主要有以下几类：
（一）带时间窗限制（SDVRPTW）。
带时间窗限制，意味着订单必须在顾客规定的时间段内到达，带时间窗限制的车辆路径问题（VRPTW）属于传统VRP分支。Archetti et al.提出了第一个求解SDVRPTW的精确算法 [2]。他们运用禁忌搜索算法和新的有效不等式对子问题分别求解，一种新的启发式算法则被用于寻找最优拆分点。实验结果表明，该求解方法对顾客规模为100的SDVRPTW同样具有良好的求解效果。目前，基于禁忌搜索求解SDVRPTW的启发式算法，是由Ho & Haugland提出的[3]，该算法将SDVRPTW的求解规模扩大至100以上。
（二）带集货和配送限制（SDVRPPD）。
在SDVRPPD中，无时间窗和最大车辆路线限制，但每一节点只能被一辆车访问一次，且每一节点可能同时具有收货和配送两种需求，任一节点的需求都可能超过车辆容量。其目标函数是通过最小化车辆使用数目来最小化总运输成本。这一应用在实际生活中非常常见，如快递员在送货的过程中，经常也会收到客户寄送货物的需求.Nowak et al.通过研究证明[3]，在同一地理分布的顾客群下，当订单平均大小为车载容量一半时，拆分能够获得最大的收益。
（三）利润最大化
一般情况下，SDVRP的目标函数是最小化车辆行驶路线或运输成本，有时也对使用成本进行优化。但是，由于需求可拆分，可能带来额外收益。Brnmo et al.通过数学规划模型并整合分区的方法对此类问题进行求解[3]，结果证明允许拆分可以提高物流企业利润率。
（四）库存和生产
自从供应链管理的观念提出以来，库存路径问题已为很多学者关注。由于库存的概念是基于时间、库存成本以及库存容量之上，时间成为SDVRP中考虑的一个重要因素。在这些问题中，一个顾客通常在特定的时间范围可以被访问多次，但是一个配送日内只能访问一次。同时，库存路径模型还会考虑生产制造策略。
（五）其他
除了以上四种主要的SDVRP分支以外，考虑最小损耗率、混合车辆编队、随机性、需求的离散性以及弧路径的SDVRP分支也逐渐出现在国内外研究中，限于文章篇幅不在此一一赘述。
三.国内研究现状
当前，国内对SDVRP的研究尚不多见。隋露斯，唐加福等用蚁群算法求解SDVRP[4]，给出了基于整数规划的描述方法；通过仿真实验发现，该算法对车辆数目和运输距离的改进显著。鲁强等用遗传算法求解K-SDVRP[5]，数值试验表明，某些条件下，SDVRP较VRP车辆使用数和车辆运输距离更少。孟凡超等通过改进传统的数学模型[6]，建立SDVRP数学模型，利用禁忌搜索算法对SDVRP进行求解。算例结果表明，该模型可以节省车辆数目、缩短路线长度、提高车辆装载率。杨亚璪等等对SDVRPPD进行研究[7]，算例结果表明，所设计的算法可以得到合理的车辆路径，特别当集货需求的总量小于送货需求的总量时，优化效果更好。
无论是使用蚁群算法、禁忌搜索算法还是遗传算法，隋露斯、鲁强、孟凡超以及杨亚璨等人关于可拆分车辆路径问题的研究，都是在需求确定的情况下研究SDVRP，并未考虑客户的时间窗以及需求的随机性。
四.结论
在对SDVRP的主要分支以及常用求解方法进行总结的基础上，我们发现目前对SDVRP的求解方法主要是通过混合整数规划建模并整合精确或者启发式算法对问题进行求解，但随着问题规模的扩大，其求解面临着维数灾难的问题。计算机仿真作为一种新的建模方法，随着计算机技术的发展，使研究者可以通过搜索海量解空间找到问题的次优解或者最优解，为求解SDVRP提供了一种新的解决途径。（作者单位：深圳大学）
参考文献
[1]Dror， M.， Trudeau， P.， 1989. Savings by split delivery routing. Transportation Science 23， 141–145.
[2]Archetti， C.， Bouchard， M.， Desaulniers， G. Enhanced branch-and-price-and-cut for vehicle routing with split deliveries and time windows. Transportation Science.2011.
[3]Archetti C.， M. G. Speranza. Vehicle routing problems with split deliveries. International Transactions in Operational Research. 19（2012）：3-22
[4]隋露斯，唐加福. 用蚁群算法求解需求可拆分车辆路径问题[C]. 中国控制与决策会议. 2008：997-1001
[5]鲁强，唐加福等. 用遗传算法求解可拆分运输的车辆路径问题[C].第二届中国智能计算大会论文集，洛阳，2008年8月3-7日， pp1-5
[6]孟凡超，陆志强等，需求可拆分车辆路径问题的禁忌搜索算法[J]. 计算机辅助工程. 2010（1）：78-83
[7]杨亚璪，靳文舟等. 求解集送货可拆分车辆路径问题的启发式算法[J]. 华南理工大学学报（自然科学版）. 2010.38（3）： 58-63
关键词：需求可拆分车辆路径问题；分支；国内现状
一.引言
传统的VRP一直是网络最优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，多年以来，受到国内外广泛关注。传统的VRP假定每个客户端的需求只能由一辆车来完成，即需求不可以被拆分，但实际应用中，有可能会存在相当一部分任务点的需求量比较大，此时，如果仍然要求每个客户点只能由一辆车来完成服务，势必会造成车辆的空载率提高，浪费运输资源。1989年Dror & Trudeau首次提出了SDVRP的概念[1]，并指出 SDVRP 是一种约束松弛的 VRP，即每个客户点的需求由传统VRP中的只能由一辆车满足，扩展为可以由多辆车满足，这可使得车辆数量和路线总长得到节约。
二.SDVRP的分类
根据研究重点的不同，SDVRP 有多种分类方式。虽然诸如带时间窗、带集货和配送的VRP在传统VRP问题中已经被大量研究，但是，在SDVRP情况下，仍然会得出一些有意义的结论。根据对国内外文献进行归纳，常见的SDVRP的分支主要有以下几类：
（一）带时间窗限制（SDVRPTW）。
带时间窗限制，意味着订单必须在顾客规定的时间段内到达，带时间窗限制的车辆路径问题（VRPTW）属于传统VRP分支。Archetti et al.提出了第一个求解SDVRPTW的精确算法 [2]。他们运用禁忌搜索算法和新的有效不等式对子问题分别求解，一种新的启发式算法则被用于寻找最优拆分点。实验结果表明，该求解方法对顾客规模为100的SDVRPTW同样具有良好的求解效果。目前，基于禁忌搜索求解SDVRPTW的启发式算法，是由Ho & Haugland提出的[3]，该算法将SDVRPTW的求解规模扩大至100以上。
（二）带集货和配送限制（SDVRPPD）。
在SDVRPPD中，无时间窗和最大车辆路线限制，但每一节点只能被一辆车访问一次，且每一节点可能同时具有收货和配送两种需求，任一节点的需求都可能超过车辆容量。其目标函数是通过最小化车辆使用数目来最小化总运输成本。这一应用在实际生活中非常常见，如快递员在送货的过程中，经常也会收到客户寄送货物的需求.Nowak et al.通过研究证明[3]，在同一地理分布的顾客群下，当订单平均大小为车载容量一半时，拆分能够获得最大的收益。
（三）利润最大化
一般情况下，SDVRP的目标函数是最小化车辆行驶路线或运输成本，有时也对使用成本进行优化。但是，由于需求可拆分，可能带来额外收益。Brnmo et al.通过数学规划模型并整合分区的方法对此类问题进行求解[3]，结果证明允许拆分可以提高物流企业利润率。
（四）库存和生产
自从供应链管理的观念提出以来，库存路径问题已为很多学者关注。由于库存的概念是基于时间、库存成本以及库存容量之上，时间成为SDVRP中考虑的一个重要因素。在这些问题中，一个顾客通常在特定的时间范围可以被访问多次，但是一个配送日内只能访问一次。同时，库存路径模型还会考虑生产制造策略。
（五）其他
除了以上四种主要的SDVRP分支以外，考虑最小损耗率、混合车辆编队、随机性、需求的离散性以及弧路径的SDVRP分支也逐渐出现在国内外研究中，限于文章篇幅不在此一一赘述。
三.国内研究现状
当前，国内对SDVRP的研究尚不多见。隋露斯，唐加福等用蚁群算法求解SDVRP[4]，给出了基于整数规划的描述方法；通过仿真实验发现，该算法对车辆数目和运输距离的改进显著。鲁强等用遗传算法求解K-SDVRP[5]，数值试验表明，某些条件下，SDVRP较VRP车辆使用数和车辆运输距离更少。孟凡超等通过改进传统的数学模型[6]，建立SDVRP数学模型，利用禁忌搜索算法对SDVRP进行求解。算例结果表明，该模型可以节省车辆数目、缩短路线长度、提高车辆装载率。杨亚璪等等对SDVRPPD进行研究[7]，算例结果表明，所设计的算法可以得到合理的车辆路径，特别当集货需求的总量小于送货需求的总量时，优化效果更好。
无论是使用蚁群算法、禁忌搜索算法还是遗传算法，隋露斯、鲁强、孟凡超以及杨亚璨等人关于可拆分车辆路径问题的研究，都是在需求确定的情况下研究SDVRP，并未考虑客户的时间窗以及需求的随机性。
四.结论
在对SDVRP的主要分支以及常用求解方法进行总结的基础上，我们发现目前对SDVRP的求解方法主要是通过混合整数规划建模并整合精确或者启发式算法对问题进行求解，但随着问题规模的扩大，其求解面临着维数灾难的问题。计算机仿真作为一种新的建模方法，随着计算机技术的发展，使研究者可以通过搜索海量解空间找到问题的次优解或者最优解，为求解SDVRP提供了一种新的解决途径。（作者单位：深圳大学）
参考文献
[1]Dror， M.， Trudeau， P.， 1989. Savings by split delivery routing. Transportation Science 23， 141–145.
[2]Archetti， C.， Bouchard， M.， Desaulniers， G. Enhanced branch-and-price-and-cut for vehicle routing with split deliveries and time windows. Transportation Science.2011.
[3]Archetti C.， M. G. Speranza. Vehicle routing problems with split deliveries. International Transactions in Operational Research. 19（2012）：3-22
[4]隋露斯，唐加福. 用蚁群算法求解需求可拆分车辆路径问题[C]. 中国控制与决策会议. 2008：997-1001
[5]鲁强，唐加福等. 用遗传算法求解可拆分运输的车辆路径问题[C].第二届中国智能计算大会论文集，洛阳，2008年8月3-7日， pp1-5
[6]孟凡超，陆志强等，需求可拆分车辆路径问题的禁忌搜索算法[J]. 计算机辅助工程. 2010（1）：78-83
[7]杨亚璪，靳文舟等. 求解集送货可拆分车辆路径问题的启发式算法[J]. 华南理工大学学报（自然科学版）. 2010.38（3）： 58-63