浅谈成品油二次配送路径优化问题

(西南石油大学 四川 成都 610500)

一、成品油二次配送的概念

成品油二次配送是指将油品从油库配送至加油站的过程，属于车辆路径规划问题的一个分支。成品油二次配送属于末端配送，是成品油运输的最后一个环节，与末端客户(加油站)直接接触，其配送是否及时到位，对加油站的服务质量和城市居民的日常生活都有着重大的影响，建立合适的配送路径优化模型对公司相关信息系统的建设也有着理论上的指导意义。因此，通过科学合理的手段制定满意的配送路线，在现实和理论方面都有着重要的意义。

成品油配送的优化一般可以分为系统优化、库存管理优化、需求预测优化、配送中心选址优化、车辆调度优化等，各类方向均有学者进行了深入研究，如：系统优化方面，贺振更在研究和分析成品油的配送体系的基础上，设计了成品油配送的优化系统，以解决需求预测和车辆路径优化问题[1]；库存管理优化方面，陈乐群针对成品油配送过程中的库存管理方面的问题，引入了VMI思想，阐述了该模式的应用要点，建立了VMI库存管理方法[2]；需求预测优化方面，魏巧云等通过分析石化企业的配送实例，总结了成品油配送的需求特点，并基于此建立了需求预测模型，用以预测次日的配送需求及运力调配计划，为构建成品油主动配送模型提供了理论支持[3]；配送中心选址优化方面，吴勤旻等在油库选址问题中考虑油库的建设成本因素和二次配送成本因素，将该问题归纳为一个二层优化模型，提出了确定理想选址区域和可行点的选址方法[4]。

车辆调度优化是近年来成品油配送优化的主要研究方向，现有文献对车辆调度优化的研究主要集中在建立成品油配送车辆路径模型并利用相关求解方法进行计算方面，其核心思想是VRP问题。Cornillier等对带时间窗的成品油车辆路径问题进行了研究，设计启发式算法并进行求解，并通过实例验证了通过优化可以缩短20%以上的行程[5]；Lahyani等研究了不同级别橄榄油配送中的多车舱车辆路径问题，并利用分支界定法算法对问题进行了求解，证明了优化的有效性[7]。

苏娟等以配送路径最短为目标建立了多车型成品油二次配送优化模型，通过lingo软件和遗传算法进行求解，得出了合理的车型及路线安排；赵慧英等在研究成品油配送优化模型时，考虑了城区货车交通管制的约束，并以最低运输费用和风险为目标构建了多目标的路径优化模型；王博弘等对国内外成品油二次配送的研究成果进行了调研，详细叙述了成品油二次配送的常用模型、算法以及最新研究成果等，将VRP问题应用于成品油二次配送，探讨成品油二次配送算法改进与发展的空间，给出了优化建议。

二、车辆路径问题求解方法

由对于VRP问题直接求最优解耗时较长，20 世纪 80 年代以来，使用已知信息，在较短时间内求得VRP问题满意解的启发式算法成为学者研究的重点，经过多年的发展，研究者提出了许多VPR问题的求解方法，目前比较成熟的应用求解方法主要有精确算法和启发式算法两种，其中启发式算法在不断的发展中，又分为了传统启发式算法和智能启发式算法两种。

精确算法在客户数量不大时可以求解VRP问题，当客户点超50个时，其往往难以求得VRP问题的最优解。随着启发式算法的发展，智能启发式算法由于具有更大的搜索能力，被越来越多的学者用于VRP问题的求解之中，常见的智能启发式算法有FredGlover提出的禁忌搜索算法，Kirkpatrick等提出的模拟退火算法，Dorigo提出的蚁群算法，Kennedy和Eberhart提出的粒子群优化算法，Holland提出的遗传算法等。

在遗传算法求解VRP问题方面，Sivaram等建立了以最小行驶距离、最少配送车辆为目标函数的带时间窗VRP问题整数规划模型，在适应度函数和交叉算子等方面改进了遗传算法，并进行了求解验证；Mohammed等通过研究国际特赦组织利用公交车接送学生的路径规划问题，利用改进的遗传算法求解CVRP问题的最优路径，提出了基于混合交叉操作的最佳路径选择方法，发现以所有公共汽车每日总行驶距离为目标函数可以节约更多里程。

三、模型求解方法

(一)遗传算法的数学模型可以描述出实现遗传算法的整体性框架，但该描述是抽象化的描述，仍需要对模型中的各个要素进行具体明确，才能够实现遗传算法的优化功能。遗传算法求解计算的核心内容由编码、初始种群、适应度函数、遗传操作、控制参数五个要素组成，本节将结合国内成品油配送路径优化模型，对这几个要素进行具体的明确。

(二)本章根据国内成品油配送的现状及特点，建立相应的路径优化模型，并对用于求解的遗传算法相关要素进行了确定。首先对国内的配送需求进行了描述，以公司配送量最大的油品为对象，建立单配送中心下、汽油的成品油配送路径优化模型；然后根据 国内实际，建立总里程最短的优化目标并建立相应目标函数，同时，通过对国内成品油配送有关的条件进行假设，设立约束条件函数，基于此建立国内成品油配送路径优化模型；针对国内配送车型较多的特点，使用合理的多车型分配原则来提高车辆的实载率；对模型的遗传算法求解方法进行了分析，合理地确定了编码、初始种群、适应度函数、遗传操作、控制参数等要素，以与国内成品油配送路径优化模型相适应。