成品油配送路径优化问题研究

金骁

[摘要]成品油配送路径优化问题是指在加油站需求量已知的情况下，石油公司利用多种型号的油罐车，从油库出发为各个加油站配送成品油以满足各个加油站需求的路径优化问题。文章主要研究某石油公司的成品油配送车辆调配和路径规划问题，在车辆数量充足、每辆车需从油库出发在完成供油任务后回到油库的前提下，考虑车辆的容量限制、加油站需求量、需求时间窗、卸油服务时间等条件，以系统运行成本的最小化为目标建立相应问题的数学模型。然后，利用1个油库、10个加油站的算例对模型的正确性进行了验证。

[关键词]成品油配送；路径优化；时间窗；数学模型

[DOI]1013939/jcnkizgsc201718184

1引言

库存和运输是物流系统最重要的功能要素，是物流获得“时间价值”和“空间价值”的两大主要环节，它们的耗费约占物流总成本的2/3。[1]库存路径问题主要是研究一个供应商向多个顾客提供配送服务时，在满足顾客的需求量、配送时间窗以及库存容量限制等约束条件的情况下，使总成本达到最小。BirgerRaa[2-3]等人于2007年在研究库存路径问题（Inventory Routing Problem）时，假设顾客的需求率是恒定的，在不引起缺货的情况下，以平均配送和库存成本最小化为目标得出周期性补货策略，并运用粒子群算法对该模型进行了求解。2008年又在模型中加入了车辆使用成本，同时运用插入遗传算法对模型分步进行求解。Kunpeng Li[4]等人在解决成品油配送问题时，考虑车辆容载量、加油站庫存容量、车辆数量等因素的情况下以最大路径遍历时间的最小化为目标函数建立数学模型，并设计了禁忌搜索算法。赵达[5]等人在2006年以零售商系统下随机需求的IRP为研究对象，提出了一种基于马尔科夫决策过程与修正的C-W节约算法的启发式分解算法。我们在2016年以工作量均衡为目标，研究了带硬时间窗约束的成品油二次配送路径优化问题，建立了整数规划模型并设计了求解模型的算法。[6]

成品油配送问题是一种典型的库存路径问题，由于各个加油站的成品油均储存在容量有限的油罐中，为加油站配送成品油的车辆也是特定的油罐车，为了满足加油站的日常销售，油库需要每天向加油站配送成品油，才能保证销售过程中不出现断货。在研究成品油库存路径问题时，如果加油站的销售速率为常数，则可以根据加油站当前的存储量确定出一段时间内的需求量，进一步根据配送车辆的容量以及油罐的容量限制，确定出配送时间窗。这种条件下成品油配送库存路径问题就简化成了带容量和时间窗限制的车辆路径问题。本文主要研究简化以后的成品油配送车辆路径优化问题，建立该问题的数学模型并设计求解模型的蚁群算法。

2问题描述

成品油的配送路径优化问题可以描述为：有一个油库，同时向多个加油站提供某一种型号的成品油；已知加油站在某一时间段内对成品油的需求量；每个加油站有对应的硬时间窗，成品油配送车辆不能早于也不能晚于加油站时间窗进行供油；配送车辆在每个加油站卸油均需要消耗一定的时间；为加油站配送成品油的油罐车为单舱车，且油罐车的数量充足；每辆油罐车的容载量、固定使用成本、单位距离行驶成本均不相同；每辆车可以同时向多个加油站供油，每个加油站只能接受一辆油罐车为其供油；每辆油罐车的平均行驶速度相同，均为50km/h。系统的目标就是在已知各个加油站的需求量以及相互之间的距离的情况下，求使得系统总运行成本最小的配送方案。

在成品油配送过程中，假设配送车辆从油库出发为若干个加油站配送成品油，完成配送任务后返回油库。同一辆配送车服务的若干个加油站的总需求量不能超过车辆的容载量。由于每个加油站只能接受一辆油罐车为其供油，因此为加油站供油的油罐车在该加油站的卸油量与加油站的需求量相等。油罐车在到达加油站时开始卸油，开始卸油的时刻应处于该加油站的时间窗内。每辆车在卸油时会耗费一定的时间，卸油耗费的时间与卸油量成正比，且当车辆在一个加油站完成卸油时会立即驶往下一个加油站。

由于油库的车辆数量充足以及每辆车的容量、固定成本及可变成本不同，因此，需要从可用车辆中选择一部分为加油站送油，并进一步确定出每一辆油罐车服务的加油站集合及配送路径，使得总配送成本最低。每辆选中的油罐车的配送路径可以用油库及加油站的序号按照配送顺序依次表示。如0-1-5-3-0表示一辆配送车辆从油库0点出发，依次为加油站1、5、3配送成品油，配送结束后返回油库。

5结论

成品油配送路径优化问题是成品油二次配送过程中的关键的问题。当制订成品油配送计划时，在保证加油站不断油的情况下，降低配送成本是最主要的考虑因素之一。本文研究了各个加油站的需求量确定的情况下，在满足各个加油站需求量及服务时间窗限制的前提下，使系统的运行成本最低的成品油配送路径优化问题。建立了以系统总运行成本最低为目标的整数规划模型，最后通过算例对模型进行了验证。

本文只考虑了确定需求下单一品种成品油的配送问题，未考虑车辆的分舱及满载约束限制。在实际的成品油配送中，各个加油站的需求量往往是一个随机变量，并且不同品种的成品油需求量服从的随机变量分布不同，油罐车的容量和隔舱数也不同，而且要求满载运输。另外，在本文为了简化问题，假设一个加油站只能被一辆车服务，实际中一个加油站可以被多辆车服务。在后续的研究中，我们将逐渐加入这些约束条件，建立更加符合实际情况的成品油配送路径优化模型，为解决实际问题提供理论依据。

参考文献：

[1]Herer Y，Levy RThe Metered Inventory Routing Problem，an Integrative Heuristic Algorithm[J].International Journal of Production Economics，1997，51（1）：69-81

[2]BirgerRaa，El-HoussaineAghezzafA Practical Solution Approach for the Cyclic Inventory Routing Problem[J].European Journal of Operational Research，2007，1922：429-441

[3]BirgerRaaNew Models and Algorithms forthe Cyclic Inventory Routing Problem[J].4OR，2008，61∶97-100

[4]Kunpeng Li，Bin Chen，AppaIyer Sivakumar，Yong WuAn Inventory–routing Problem with the Objective of Travel Time Minimization[J].European Journal of Operational Research，2014：936-945

[5]赵达，李军，马丹祥，李妍峰求解硬时间窗约束下随机需求库存-路径问题的优化算法[J].运筹与管理，2014，23（1）：27-37

[6]Zhenping Li，Zhiguo WuStudy on the Inventory Routing Problem of Refined Oil Distribution Based on Working Time Equilibrium[J].American Journal of Operations Research，2016，6（1）：17-24