1．目的及意义

1.研究背景

成品油是与我国国民经济发展和人民日常生活息息相关的重要战略性产品。随着我国成品油市场不断快速发展，成品油配送在成品油销售环节的重要性逐步上升。近年来，随着国际原油价格持续下跌，当前世界石油化工工业呈现负增长态势，国内石油石化公司盈利普遍降低^[1]。这给国内的石油石化企业带来了一定压力。国家经济社会稳定发展必须依靠石油石化产业作为重要保障，它的安全与否关系着国家国计民生的方方面面。我国石油石化产业经过多年的发展，产业也逐渐趋于成熟，在市场竞争方面，已经形成了以基本以中石油、中石化、中海油为主导的市场格局。石油石化企业面对多变而又竞争激烈的复杂市场环境，企业为了提高利润率和其多年经营积累下的市场占有率，需要持续改善自身管理模式、优化管理制度，以此来降低企业物流运作成本，提升管理水平，加强信息化建设。

2.国内外研究现状

车辆路线问题（Vehicle Routing Problem）简称VRP，是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。由Dantzing和Ramser首先提出^[2]，在此之后，许多领域都关注到了VRP问题，比如计算机应用领域、运筹学和数学领域。车辆路线问题将运筹学问题与企业实际问题相联系，自从提出后就受到了学术界和企业的高度重视，引起了研究学者们的广泛热议，成为优化组合和运筹学领域的热点和前沿问题。世界各国学者针对车辆路线优化研究问题做了大量的理论和实证分析，并且取得了一定的研究成果。P.Wark等人提出了利用重复匹配的方法来求解路线模型^[3]，该方法可以在模型中既考虑能力约束又考虑时间约束，更能有效地解决实际车辆路线问题。现实的车辆路线问题考虑的因素多，研究的问题比较复杂，并且运算量很大，许多学者开始将现代启发式算法引入VRP问题研究当中。Brian Kallehauge总结了精确算法在VRPTW(Vehicle Routing Problem Time Window)中的应用^[4]，指出VRPTW问题应当隶属于NP-Hard问题，同时还提出当路线优化问题规模增大时，求解时间会呈指数级增长。由于精确算法的局限性比较大，限制较多，解决实际路线规划问题应用较弱，人们转而研究应用启发式算法来解决VRPTW问题，比较典型的启发式算法有：节约算法、扫描法两阶段法等等。

国内对于VRP问题的研究最早起于20世纪90年代。近年来，随着社会企业和政府部门对物流产业的重视，物流产业在国民经济地位逐步提高，物流产业快速的发展促使我国物流配送网络的不断完善，与此同时也推动了专家学者对配送车辆调度问题的相关研究，随后不断有学者加入到车辆路线优化问题的研究领域当中来。其中针对利用C-W节约算法求解路线优化模型问题研究应用开始于20世纪90年代初，国内学者开始利用其解决简单的小规模路线优化问题，随后有些学者和专家将算法不断改进以提高其实用性。姜大立、杨西龙等人很早就提出应用启发式算法的C-W节约算法来来解决VRP问题^[7]，将解决旅行商路线选择问题应用到企业物流车辆配送路线上来。霍佳震等人提出了一种基于里程节约值比较的成本最小化的启发式算法^[8]。此算法根据车辆的满载程度将车辆路线划分为三类，即两端往返运输、多端连续满载运输和多端间隔满载运输，里程节约值不仅考虑了车辆固定成本，而且还考虑了变动成本。近些年来，C-W节约算法经过不断发展和完善，而且C-W算法经过适当改进已经在各领域得到广泛的应用。C-W节约算法应用到采购物流领域中来，朱晓兰等人提出将配送路线优化的C-W算法应用到采购物流领域当中去，并且根据制造企业采购产品的特点，考虑在运输过程中不仅要考虑将车辆载重量约束条件，还要考虑货物所占用的容积约束条件，以满足采购物流的特殊要求。曹静霞将C-W节约算法应用到车辆调度优化问题研究领域中来^[10]，并在实际应用中验证C-W节约算法对于解决车辆调度有较强的适应性，指出使用C-W节约算法来解决车辆路线问题相比其他的现代启发式算法而言更加简单而实用。在实证分析中，又有学者针对节约费用值进行了深入研究分析。刘诚等人利用可能度的区间数排序方法对C-W节约算法进行改进，利用改进后的算法对运输费用区间参数进行排序，以配送网络点间的费用为研究对象，来研究车辆路径问题^[11]。徐兵运用改进C-W节约算法优化了连锁超市物流配送路线^[12]，改进后的C-W节约算法加入了时间窗，使得C-W算法应用起来更贴合企业实际情况。随着实际中的路线问题研究的复杂度越来越高，给予C-W算法适当地改进来解决实际问题已成为一种趋势。

3.目的及意义

随着人类社会进入21世纪，人们对于生活生产所需物资调配的认识，越来越深刻。根据物流配送系统中运输阶段的不同，人们习惯上将物流划分为一次物流配送、二次物流配送以及终端物流配送等类别^[1]。二次物流配送作为物流系统中的重要组成部分，近年来得到了国内外学者的广泛关注，他们在提升物流配送效率、降低物流配送成本、提升物流配送响应能力等方面，投入了巨大的精力，并业已取得了丰硕的成果^[7]。成品油二次配送作为石油石化企业供应链的终端部分，它是一个很好的突破口，通过改善和优化二次配送这一环节，可以为企业带来巨大的经营效益，降低配送成本，提高物流运作效率，从而提高企业竞争力。对于我国成品油销售企业而言，严峻的经营环境，激励的竞争态势，使得路径的合理优化配置工作变得更为重要^[14]。因此，探索现有条件下合理的配送路径和车辆组合，有效实现配送时间最短、配送历程最小、配送效率最高、配送成本最低等是本文研究的主要目的和重点。

不同石油石化企业自身的成品油配送系统具有不同的特点，但是都存在较大的管理漏洞和短板，如物流信息化水平偏低，网络设施布局不合理，油库车辆的配置不合理、物流调度严重滞后等^[7]，这些问题都给企业发展带来了严重的障碍。成品油作为一种关系国家生存和发展的重要战略能源，其二次配送作为成品油物流系统中重要的组成部分，如何实现成品油二次配送路线优化成为了企业从物流方面谋取利润的关键。

本文的理论意义在于建立了成品油二次车辆配送路线模型，提出将C-W节约算法来求解数学模型，使实际车辆配送路线问题各环节中的约束和目标模式化。在满足客户对产品配送服务的需求的前提下，建立科学、高效的车辆路线优化模型，提高配送车辆的使用效率，可减少企业资源浪费，降低企业货物运输成本，并且还可加速资金流通，保证企业财务健康以实现企业资源的最优化配置。本文提出给C-W节约算法来求解路线优化模型，给成品油二次配送提供了方法支撑，对于深入研究成品油二次配送具有一定的理论指导意义。