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

PAGE  PAGE 9 需求可拆分的车辆路径问题及其研究进展 　　摘要：车辆调度是运输环节优化的关键所在，可拆分车辆路径问题作为车辆路径问题的一个重要分支，具有更切合车辆配送的实际情况，更能满足企业经营管理的实际需求。本文首先对需求可拆分的车辆路径问题进行了简要介绍，然后对其国内外研究进展进行了详细分析。 　　Abstract： Vehicle scheduling is the key of the transportation optimization， vehicle routing problem with split demand is an important branch， is more in line with 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 words： split demand；vehicle routing problem；research progress 　　中图分类号：TP301.6 文献标识码：A 文章编号：1006-4311（2016）34-0097-03 　　0 引言 　　运输是整个物流活动体系中非常重要的一个环节，贯穿着生产和销售的整个过程。通常，运输成本在企业的运营成本中占有较大的比重，尤其是在加工制造，能源等行业。同时，运输的高效性也对企业的仓储、生产和管理等环节有着很大影响。另外，作为联系企业和最终用户的纽带和桥梁，运输的效率直接影响着企业对客户需求的响应速度，影响客户对企业服务的满意程度。因此，运输环节的优化程度对于企业运营成本的降低，运行效率的提高以及竞争力的提高有着至关重要的影响。 　　车辆调度是运输环节优化的关键所在，其要解决的问题是如何在满足各种限制条件下，如车辆载重量，时间和客户需求量等，合理安排车辆的行驶路线和对客户进行服务的顺序，以达到降低运输成本的目的。可拆分车辆路径问题作为车辆路径问题的一个重要分支，具有更切合车辆配送的实际情况，更能满足企业经营管理的实际需求的特点，因此在理论研究方面也得到越来越多的关注。 　　1 可拆分的车辆路径问题 　　合理的车辆调度方案能够有效地降低物资运输成本，提高运输效率，然而，在实际的企业运营过程中，车辆调度方案的确定通常是由相关工作人员根据经验制定的，这样的车辆调度方案往往存在许多的不合理性，尤其是在信息量非常庞大的情况下。因此，如何帮助企业制定科学合理的车辆调度方案成为学者们日益关注的问题。 　　在这种背景下，Dantzig和Ramser在1959年提出了车辆路径问题（Vehicle Routing Problem， 简称VRP），迄今为止已有不同领域的众多专家学者对该问题进行了大量的研究。但是传统的VRP问题中存在一个限定条件：每个客户点只能由一辆车服务且只能服务一次，即客户点的需求不能进行拆分配送。但是在现实的车辆调度过程中往往会存在以下两种情况：①某个客户对物品的需求量超过车辆的最大载重量；②大多数客户的需求量都超过车辆最大载重量的一半。传统的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辆车才能完成，这样就必然会出现空车驶回的情况，造成车辆资源的浪费和物流成本的提高。考虑到上述两种情况的存在，Dror和Trudeau]在1989年提出了需求可拆分的车辆路径问题（Split Delivery Vehicle Routing Problem，简称SDVRP），即取消了传统的VRP问题中每个顾客点能且仅能被一辆车服务一次的约束条件，允许一个客户点被服务多次。显然，SDVRP更符合实际中车辆配