基于泰森多边形的油库优化配送研究

马国光，刘源海，何方舟，黄 坤，蒋茂琴

1.西南石油大学石油与天然气工程学院(四川成都610500)

2.中国石油集团工程设计有限责任公司青海分公司(甘肃敦煌736202)

基于泰森多边形的油库优化配送研究

马国光1，刘源海1，何方舟1，黄 坤1，蒋茂琴2

1.西南石油大学石油与天然气工程学院(四川成都610500)

2.中国石油集团工程设计有限责任公司青海分公司(甘肃敦煌736202)

油库作为仓储物流链条中最重要一环，起着调节成品油供应链资源“蓄水池”的作用。随着成品油销售企业传统获利空间不断被挤压，市场压力不断增加，基于大仓储大物流的规划，通过优化措施来降低物流成本、完善物流管理、提高企业核心竞争力已成为所有成品油销售公司不可回避的课题。运用现代物流理论、运筹学、图论并结合XX销售成品油库配送典型现状相结合，归纳了当前油库配送存在的问题，通过模型的建立与求解确定出了成品油库优化配送方案，为现代油库优化配送提供一定的指导作用。

油库;泰森多边形;优化配送

油库的配送对成品油的物流有着举足轻重的作用。目前国内大部分成品油销售公司都存在按照行政区域划分各自油库的管辖范围，即根据油库与二级公司的从属对应关系进行配送区域划分。这种划分模式经常导致“近库配远站，远库配近站”的现象出现，使得上级公司调运处无法集中调度，出现局部区域运力紧张、油库油品配送不合理，既浪费了人力、物力和时间，又增加了企业运营成本［1-3］。本文以XX销售公司为例，采用从炼油厂—油库—加油站的二级配送模型进行分析，建立了两个约束模型，运用运筹学、图论学对模型求解，最后采用多目标优化理论将多个约束条件转化为单一约束条件进行求解，最终得到油库的油品配送，保证油库“高效、高利、高稳”运营。

1 模型建立

通过确定模型的假设条件，并确定出参数与决策变量，可以建立成品油库优化配送的模型(图1)。文中建立两个模型:包括一次配送量(最小库存量模型)、二次配送费用模型。

成品油一次资源的摆放到位将影响二次配送的最大效益，二次配送是整个物流活动的终端，但它同时也是物流优化工作的起点，因此必须以满足加油站的需求为前提。而油库是连接这两个活动的枢纽环节，所以需要对一次配送的量建立最小库存模型，对二次配送的路径建立最短路径模型。

1.1 模型条件假设

假设1:一个成品油物流系统由I个炼厂，J个油库和K个加油站组成;

假设2:油库和加油站的位置分布已确定;

假设3:省级公司与炼厂确立的合同量稳定，炼厂能够满足省级销售公司与其所签订的输油计划，且炼厂油库能够通过不同的集输方式满足销售公司所需的供货量;

假设4:每个加油站的第m种油品只由一个油库配送，即各油库的m种油品能满足所配送区域加油站的需求;

图1 成品油物流模型

假设5:油库运送不同种油品的费用单价相同;

假设6:不考虑意外事故，油库能保证安全运行，且油罐车在配送路径中运行正常，没有出现油罐车故障问题;

假设7:成品油二次配送中加油站的单次需求量不大于油罐车的最大载重量;

假设8:各油库的配送车辆完全能满足配送要求。

1.1.1 最小库存模型

对于XX销售公司的油库，油品可能通过3种途径运至:即公路，铁路，管输。对于公路运输，可能存在2种情况:一是通过炼厂专用公路运输;二是其它油库公路运输。由于每种配送费用的价格不同，要使得油库的一次配送的来油量最合理，即库存量最小，就要对未来销量进行预测，并优化油库所存库的油品种类，所以本文建立的最优库存模型如式(1)所示。

式中:s为油库的库存量(t);i为炼油厂数量，i= 1，2……I;j为油库数量，j=1，2……J;k为加油站数量，k=1，2……k;m为油品种类，m=1，2……m;qimj为由第i个炼厂向第j个油库的运送的第m种产品的数量;qjmk为油库j向加油站k对第m种油品的配送量(t);

1.1.2 油品二次配送费用模型

在油库油品资源的合理配送中，二次配送是一个重要的影响因素，对于任何一个油库，需要存放哪种油，每种油的存放量是多少，都与油品配送的量及种类密不可分，因此以油品的运输费用最小为目标来建立二次配送模型，如式(2)所示。

式中:z2为成品油二次配送的费用;c0为运距小于30km的油品单位吨价格(元/t);c1为运距大于30km油品单位运距的单位吨价格(元/t);dkmj为油库j向加油站k配送第m种油品的运距(km);Cpi为配送车辆i的通行费用;Wi为配送车辆的其他费用;X为运距小于30km的加油站数量;K为油库配送加油站的总数量;Y为配送车辆的数量。

2 油库配送优化

2.1 最小库存优化

对于最小库存模型式:将油库摆放总量(即油库来油总量)确定为。即油库的配送区域的需求量和油库应急库存，区域需求量可以根据文中确定的配送区域的加油站需求量确定，对于应急库存主要从油库的来油方式受到的限制，保证能应急供应需求量所需要的库容，考虑到管道来油、铁路来油和公路来油方式的特点［4］，将管道来油的油库应急库存确定为1天销售量，将公路来油的油库应急库存确定为2天的销量，将铁路来油的油库应急库存确定为4天销售量。

2.2 配送运距优化

要使配送距离最短就必须找到与所配送加油站距离最近的油库。本文采用泰森多边形(又叫冯洛诺伊图)［5］对油库配送区域进行初步划分，以打破油库配送区域按照行政管理区域划分的界限，采用电子地图的API功能进行基于实际路线的修正，最终得出油库配送区域图。

2.2.1 泰森多边形构建

油库坐标点导入后，采用格雷厄姆法将点集生成凸壳，如图2连接最外围的离散点，删除非凸壳点(根据凸壳的每个顶点必须在凸壳任意一条边的同一侧这一原理)，完成凸壳的绘制;在凸壳形成之后，采用点插法构建初始Delaunay三角网如图2～图4所示。

由图2～图5可以看出基于泰森多边形初步划分出每个油库的配送区域，由于该配送区域是基于直线距离最短的，现实中的路径距离并不是直线距离，所以必须根据实际道路对该配送区域图进行修正。

图2 格雷厄姆方法构建凸壳过程图

图3 优化后的Delaunay三角网

图4 泰森多边形(配送区域的划分)

2.2.2 基于实际道路的修正

通过Voronoi图划分出油库的配送区域，在电子地图上进行运距的调整。首先在地图上标示出油库和加油站的位置信息，结合电子地图API功能，寻找两点(油库与加油站)之间行车路径最短的距离。如图6～图7所示，在地图上可以找出B加油站到A、C油库的最短路径。

图5 Voronoi图的配送区域划分

图6 A油库到B加油站的距离

图7 C油库到B加油站的距离

对A油库和C油库配送区域边界上所有加油站进行实际距离分析，可以确定出两油库的配送区域划分边界，因此对A油库和C油库配送区域的边界进行如图8～图10所示的调整。

图8 基于Voronoi图的配送区域边界

图9 调整后的配送区域边界

3 优化结果分析

由于本文中所涉及的油库和加油站数目较多，所以这里只对优化后每个油库所覆盖加油站的运距进行对比说明该方法的准确性(表1)。

图10 基于实际路径的配送区域划分图

表1 优化前后运距对比表

加油站配送库的重新确定，打破了行政区域，合理的划分了油库的配送范围。2013年XX销售平均运距从73.74km下降到66.71km，减小了10.54%，吨油加油站送货费从45.99元下降至44.94元，同比降低1.05元，全年公路配送费用共节约798万元。

4 结论

成品油库配送涉及的面广点多，本文采用配送区域的划分与图论学的结合，较好规划出了油库的配送区域，从优化结果可以看出，该方法的应用性强，效果较好，适用于成品油库配送区域划分。

［1］宋国理.国内成品油价格形成机制研究［D］.长春:吉林大学，2012:38-45.

［2］张亚雄，李继峰.成品油价格上涨、行业补贴与我国经济发展的关联度［J］.改革，2010，198(8):49-57.

［3］邱法聚.成品油销售企业物流配送决策支持系统的研究与应用［D］.武汉:武汉理工大学，2007:2-4，15-16.

［4］朱珊珊.兰—成—渝成品油输油管线生产运行方案优化［D］.成都:西南石油学院，2005:52-54.

［5］Amenta N.Bern M.Surface reconstruction by Voronoi filtering［J］.Discrete&Computational Geometry.1999，22(4):481-504.

As the most important part of warehousing--logistics chain，depot plays the role of＂tank＂in the supply chain of refined oil products to adjust the supply of the oil products.With the continuous reduction of the traditional profit space and the continuous increase of market pressure of refined oil product sales enterprises，it will become the problem to which the refined oil product sales enterprises must face to reduce logistics cost，to improve logistics management and to enhance the core competitiveness of the enterprises through optimization measures.The current problems existing in terminal distribution are summarized based on the modern logistics theory，operations research and graph theory and the current distribution situation of some oil depot.The optimized oil depot distribution program is determined through the establishment and solving of optimization model，which can provide the guidance for the optimal distribution of oil depots.

oil depot;Thiessen polygon;optimizing distributing

张箫铃

2014-12-16

马国光(1964-)，男，博士，主要从事石油天然气储运教学、设计、科研工作。