需求可拆分的车辆路径问题及其研究进展.doc

1、1需求可拆分的车辆路径问题及其研究进展摘要：车辆调度是运输环节优化的关键所在，可拆分车辆路径问题作为车辆路径问题的一个重要分支，具有更切合车辆配送的实际情况，更能满足企业经营管理的实际需求。本文首先对需求可拆分的车辆路径问题进行了简要介绍，然后对其国内外研究进展进行了详细分析。 Abstract： Vehicle scheduling is the key of the transportation optimization， vehicle routing problem with split demand is an important branch， is more in line wi

2、th the actual situation of vehicle delivery， and can better meet the actual needs of the enterprise management. This paper briefly introduces the vehicle routing problem with split demand， and then makes a detailed analysis of the domestic and foreign research progress. 关键词：需求可拆分；车辆路径问题；研究进展 Key wor

3、ds： split demand；vehicle routing problem；research progress 中图分类号：TP301.6 文献标识码：A 文章编号：1006-4311（2016）34-0097-03 0 引言 运输是整个物流活动体系中非常重要的一个环节，贯穿着生产和销2售的整个过程。通常，运输成本在企业的运营成本中占有较大的比重，尤其是在加工制造，能源等行业。同时，运输的高效性也对企业的仓储、生产和管理等环节有着很大影响。另外，作为联系企业和最终用户的纽带和桥梁，运输的效率直接影响着企业对客户需求的响应速度，影响客户对企业服务的满意程度。因此，运输环节的优化程度对于企业

4、运营成本的降低，运行效率的提高以及竞争力的提高有着至关重要的影响。 车辆调度是运输环节优化的关键所在，其要解决的问题是如何在满足各种限制条件下，如车辆载重量，时间和客户需求量等，合理安排车辆的行驶路线和对客户进行服务的顺序，以达到降低运输成本的目的。可拆分车辆路径问题作为车辆路径问题的一个重要分支，具有更切合车辆配送的实际情况，更能满足企业经营管理的实际需求的特点，因此在理论研究方面也得到越来越多的关注。 1 可拆分的车辆路径问题 合理的车辆调度方案能够有效地降低物资运输成本，提高运输效率，然而，在实际的企业运营过程中，车辆调度方案的确定通常是由相关工作人员根据经验制定的，这样的车辆调度方案往

5、往存在许多的不合理性，尤其是在信息量非常庞大的情况下。因此，如何帮助企业制定科学合理的车辆调度方案成为学者们日益关注的问题。 在这种背景下，Dantzig 和 Ramser 在 1959 年提出了车辆路径问题（Vehicle Routing Problem， 简称 VRP） ，迄今为止已有不同领域的众多专家学者对该问题进行了大量的研究。但是传统的 VRP 问题中存在一个限定条件：每个客户点只能由一辆车服务且只能服务一次，即客户点3的需求不能进行拆分配送。但是在现实的车辆调度过程中往往会存在以下两种情况：某个客户对物品的需求量超过车辆的最大载重量；大多数客户的需求量都超过车辆最大载重量的一半。传

6、统的 VRP 问题显然不适用于情况，对于情况而言，传统的 VRP 问题也不能达到很好的优化效果。如图 1 所示，V0 为车场，V1，V2，V3，V4，V5 为五个等待服务的客户点，且每个客户点的需求量均为 6 单位，假设每两个顾客之间的距离均为 1，车辆的最大载重量 Q=15，则图 1（a）为传统 VRP 下的最优解，图 1（b）为对需求进行拆分后的得到最优解。 从图 1 中可以看出图 1 （a） 、1 （b）中车辆的总行驶路程都是 8，但是在允许拆分配送的情况下仅需要 2 辆车就能完成对全部顾客点的服务，而图 1 （a）情况下则需要 3 辆车才能完成，这样就必然会出现空车驶回的情况，造成车辆

7、资源的浪费和物流成本的提高。考虑到上述两种情况的存在，Dror 和 Trudeau在 1989 年提出了需求可拆分的车辆路径问题（Split Delivery Vehicle Routing Problem，简称 SDVRP） ，即取消了传统的 VRP 问题中每个顾客点能且仅能被一辆车服务一次的约束条件，允许一个客户点被服务多次。显然，SDVRP 更符合实际中车辆配送的特点，也更能满足现实生活中优化车辆调度的目的。 2 SDVRP 的研究进展 2.1 国外研究进展 Dror 和 Trudeau 最早提出的并构建了 SDVRP 的数学模型，Dror 和Trudeau 还证明了配送中心在对客户点进

8、行产品配送时，如果客户点的需求允许被拆分配送，那么，无论是从车辆的行驶距离还是所使用车辆的4数量上看，都优于客户需求只能被一辆车服务一次的情况，同时，作者还使用算例证明了当客户点数趋于无穷大时，拆分配送求解得到的最优值可能仅是传统 VRP 最优值的一半。 Dror 和 Trudeau 在提出 SDVRP 时就指出了该问题是一个 NP 难题，求解具有很大的难度。但是，由于可拆分的车辆路径问题更符合现实中车辆配送的情况，而且也更有利于降低配送企业的成本，因此，可拆分的车辆路径问题一经提出后就有大量学者根据不同的背景和假设条件对其进行了研究，目前对该问题的研究主要集中在带时间窗、带集送货需求和利润最

9、大化等领域。 2.1.1 时间窗 对于带时间窗的可拆分车辆路径问题可用精确算法进行求解，首先采用 Dantzig-Wolfe 分解法将问题进行分解，再用分支定界发对子问题进行求解，同时采用列生成算法求解主问题。随后，有学者又提出了一种不同的 Dantzig-Wolfe 分解法，引入一种极端配送方式，即对于所有的客户，其需求如果无法被全部满足那么就不对其进行配送。Archetti等对求解该问题的算法进行了改进，用禁忌搜索算法求解子问题。 2.1.2 集送货需求 Mitra 就带集送货需求的可拆分车辆路径问题构造了混合整数线性规划模型，与传统集送货问题的假设不同之处在于一个客户点可以同时拥有取货和

10、集货需求，而且需求数量没有限制，可以超过车辆的最大载重量。对这个问题的求解作者构造了一种启发式方法，首先决定车辆的最小需求量，然后根据节约插入的标准设计路径。将拆分配送在集送货问5题中的优势进行了量化，可以证明对于一个给定的配送网络，当需求量正好是车辆容量的一半时，拆分配送的节约值最大。Thangiah 等研究了带集送货需求和时间窗因素的可拆分车辆路径问题。 2.1.3 利润最大化 一般的可拆分车辆路径问题在目标函数的设定时只是考虑最小化车辆所行驶的距离，Feillet 等将车辆的使用成本也加入到目标函数，作为衡量求解结果满意程度的标准之一。在这种情况下，配送中心需要从潜在的客户点中选择一部分

11、能使利润最大化的客户点，只对这些客户点进行服务。 除此之外，也有部分学者对其他条件下的可拆分车辆路径问题进行了研究，例如 Bertazzi 等将库存问题与可拆分车辆路径问题相结合进行了研究；Tavakkoli-Moghaddam 等考虑了多车队的情况，构造了最小化车队成本和距离成本的目标函数，其中车队成本包括使用的车辆数量以及车辆的非满载惩罚，并设计了相应的模拟退火算法对模型进行求解；Bouzaiene-Ayari 等考虑顾客需求量为随机的情况；Nagao 和 Nagamochi对多产品可拆分车辆路径问题进行了研究，该研究中配送中心可以提供多种产品，每个客户对不同的产品都有不同的需求，客户可以

12、被服务多次，但是每种产品只能由一辆车服务，作者使用动态规划算法对实际数据进行了求解实验。 2.2 国内相关研究现状 可拆分车辆调度问题近几年才得到国内学者的重视，研究相对较少。下面本文从模型和算法两部分对国内在可拆分车辆路径问题领域的研究6成果进行简单的回顾和总结。 2.2.1 问题模型 侯立文等构造了同时考虑客户需求可拆分和配送中心有时间窗限制的车辆路径模型，该模型中的时间窗为硬时间窗，车辆可以提前到达客户点，但是不允许晚于客户点的最晚开始服务时间。谭家美，徐瑞华假设只有当客户需求大于车辆剩余载重量时才进行拆分运输，构造了基于这一假设的新的需求可拆分车辆调度模型，并利用实验证明当客户点的需求

13、与车辆载重的比例较大时，拆分运输的结果优于不可拆分情况下的结果。杨亚?b，靳文舟等在 Mitra 的基础之上对集送货可拆分车辆路径问题继续进行了研究，假设各任务点即具有送货需求又具有集货需求，车辆在进行服务的时候采用先卸后装的方式。李三彬等提出了需求可拆分的多种车辆的开放式车辆路径问题，即车辆在服务完所有客户点后不必返回车场，同时在目标函数中对非满载车辆的剩余载重量进行惩罚。在现实生活中，客户往往有多个可以接受送货的时间窗，根据这一情况，马华伟等构建了需求可拆分的多时间窗车辆调度问题的模型，并用蚁群算法进行了求解。 2.2.2 求解算法 在求解方面，谢毅根据需求可拆分车辆调度问题模型分别设计了

14、禁忌搜索算法和遗传算法，将最近邻插入法应用到初始解的构造中，提高了算法的有效性，并通过对比两种算法的求解结果和所需时间发现禁忌搜索算法的整体质量要优于遗传算法。侯立文，谭家美，赵元将蚁群算法中的转移概率和最大最小蚂蚁算法相结合重新设计了算法，成功求解7了带时间窗的可拆分车辆调度问题。刘旺盛等人将可拆分车辆调度问题分成两个阶段进行求解，分别设计了先分组后路径和先路径后分组两种启发式算法，随后又证明了当客户需求大于车辆最大载重量时则该客户点的需求不宜被拆分，在此基础上采用先分组后路径的原则设计了一个两阶段的聚类算法。谢秉磊等对需求可拆分车辆路径问题的模型进行了改进，缩小了最优解的搜索空间，并用 2

15、-opt 法对蚂蚁算法进行了优化。3 总结 车辆调度是运输环节优化的关键所在，可拆分车辆路径问题作为车辆路径问题的一个重要分支，具有更切合车辆配送的实际情况，更能满足企业经营管理的实际需求，本文首先对需求可拆分的车辆路径问题进行了简要介绍，然后对其国内外研究进展进行了详细分析。希望本文能对企业的经营决策以及相关研究人员提供有益的借鉴和参考。 参考文献： 1Dantzig，DB， Ramser，JH. The truck dispatching problem. Management Science，1959，6：80. 2Archetti，C.，Bouchard，M.，Desaulniers，

16、G. Enhanced branch -and-price-and-cut for vehicle routing with split deliveries and time windows. Transportation Science，2011，45：285-298. 3Mitra，S. An algorithm for the generalized vehicle 8routing problem with backhauling. Asia-Pacific Journal of Operational Research，2005，22：153-169. 4Thangiah，SR.，

17、Fergany，A.，Awan，S. Real-time split-delivery pickup and delivery time window problems with transfers. Central European Journal of Operations Research，2007，15：329-349. 5Tavakkoli-Moghaddam，R.，Safaei，N. A new capacitated vehicle routing problem with split service for minimizing fleet cost by simulated

18、annealing. Journal of the Franklin Institute，2007，344：406-425. 6李三彬，柴玉梅，王黎明.需求可拆分的开放式车辆路径问题研究J.计算机工程，2011，37（6）：168-171. 7刘旺盛，黄娟.需求可拆分的车辆路径问题的分段求解J.集美大学学报，2011，16（1）：38-44. 8刘旺盛，杨帆.需求可拆分车辆路径问题的聚类求解算法J.控制与决策，2012，27（4）：535-541. 9马华伟，叶浩然，夏维.允许分割配送的多时间窗车辆调度问题的改进蚁群算法求解J.中国管理科学，2012，20：43-4. 10谭家美，徐瑞华.客户

19、需求可分的车辆路径问题求解J.系统管理学报，2008，17（1）：43-46. 11吴悦，汪定伟.用遗传/禁忌搜索混合算法求解可变加工时间的调度问题J.控制与决策，1998，13：428-432. 912谢秉磊，胡小明，张一?.需求可分的车辆路径问题模型与算法J.运筹与管理，2012，21（3）：72-76. 13杨亚?b，靳文舟.求解集送货可拆分车辆路径问题的启发式算法J.华南理工大学学报，2010，38（3）：58-63. 14汪婷婷，倪郁东，何文玲.需求可拆分车辆路径问题的蜂群优化算法J.合肥工业大学学报（自然科学版） ，2014（8）：1015-1018. 15熊浩，鄢慧丽.需求可拆分车辆路径问题的三阶段禁忌算法J.系统工程理论与实践，2015（5）：1230-1235.