原创《成品油配送路径优化问题》
该文是问题研究毕业论文题目范文和成品油和优化和配送类毕业论文范文。
金骁
(北京物资学院物流学院,北京101149)
［摘 要］成品油配送路径优化问题是指在加油站需求量已知的情况下,石油公司利用多种型号的油罐车,从油库出发为各个加油站配送成品油以满足各个加油站需求的路径优化问题.文章主要研究某石油公司的成品油配送车辆调配和路径规划问题,在车辆数量充足、每辆车需从油库出发在完成供油任务后回到油库的前提下,考虑车辆的容量限制、加油站需求量、需求时间窗、卸油服务时间等条件,以系统运行成本的最小化为目标建立相应问题的数学模型.然后,利用1个油库、10个加油站的算例对模型的正确性进行了验证.
［关键词］成品油配送；路径优化；时间窗；数学模型
［DOI］10.13939/j.cnki.zgsc.2017.18.184
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配送成品油,配送结束后返回油库.
3模型的建立
3.1模型的符号说明
{0,1,2,…,n｝：油库或加油站序号集合,其中0表示油库；1,2,…,n表示加油站；
{1,2,…,K｝：可用车辆序号集合；
qi:加油站i的需求量；
Ei：加油站i允许卸油的最早时间；
Li：加油站i允许卸油的最晚时间；
pik：车辆k在加油站i处的卸载量；
Qk：车辆k的最大容载量；
Dij：加油站i到j之间的行驶距离；
tij：加油站i到j之间的行驶时间；
xijk：如果车辆k从加油站i直接行驶到加油站j,则xijk等于1；否则,xijk等于0;
si：车辆在加油站i的卸油时间；
rik：车辆k开始为加油站i卸油的时刻；
Ck：车辆k的固定使用费用；
fk：车辆k每行驶1公里的费用；
yk：如果车辆k被使用,则yk等于1；否则,yk等于0.
3.2成本的结构
对于加油站而言,影响其库存的因素主要是加油站的油罐最大物理容积以及油罐的停泵库容.为了简化问题,本文只考虑满足加油站的需求量,不考虑加油站的库存持有成本.因此系统的总成本主要由两方面构成,即车辆的固定使用成本uk和车辆的可变使用成本vk.车辆的固定使用成本uk与车辆是否被使用有关,如果车辆k被使用,则需要支付固定使用费Ck；如果车辆未被使用,则不需要支付固定使用费Ck；由于yk用于表示车辆k是否被使用,即
目标函数(1)表示系统运行成本最小化,系统运行成本包含两部分：一部分是车辆的固定使用费用；另外一部分是车辆运行途中所产生的费用.
约束(2)表示被使用的车辆数量不能超过车队所拥有的车辆数量.
约束(3)表示车辆容载量约束,即配送到各个加油站的油量总和不能超过车辆的容载量.
约束(4)代表每一辆被使用的运输车均从油库出发.
约束(5)表示一辆运输车进入某个加油站,则必然要从该加油站离开.
约束(6)表示每个加油站只能被一辆运输车服务.
约束(7)表示加油站i的需求量刚好得到满足.
约束(8)表示同一运输路径上相继两个加油站的车辆到达时间之间的关系.
约束(9)表示车辆到达加油站的时间必须在加油站的时间窗内.
约束(10)-(11)表示变量的取值约束.
4算例分析
本文以1个油库、10个加油站和5辆油罐车作为算例对模型和设计的蚁群算法进行验证.各个车辆的额定容载量、固定使用成本和可变使用成本如表1所示.
各个加油站的需求量、卸油时间和服务时间窗如表2所示.
油库与加油站之间以及各个加油站之间的最短行驶距离和最短行驶时间如表3和表4所示.
根据本文建立的整数规划模型运用Lingo软件编程对其求解.经过了50个小时的运行得到了该模型的精确最优解.计算结果显示在成品油配送过程中一共使用了4辆车,分别是第1、2、4、5辆车.每辆车的具体路径如下：
V(1)：0——2——10——0；
V(2)：0——9——4——1——0；
V(4)：0——7——5——0；
V(5)：0——6——8——3——0.
所有车辆行驶的总距离为300km,系统最低运行成本为4287元.
5结论
成品油配送路径优化问题是成品油二次配送过程中的关键的问题.当制订成品油配送计划时,在保证加油站不断油的情况下,降低配送成本是最主要的考虑因素之一.本文研究了各个加油站的需求量确定的情况下,在满足各个加油站需求量及服务时间窗限制的前提下,使系统的运行成本最低的成品油配送路径优化问题.建立了以系统总运行成本最低为目标的整数规划模型,最后通过算例对模型进行了验证.
本文只考虑了确定需求下单一品种成品油的配送问题,未考虑车辆的分舱及满载约束限制.在实际的成品油配送中,各个加油站的需求量往往是一个随机变量,并且不同品种的成品油需求量服从的随机变量分布不同,油罐车的容量和隔舱数也不同,而且要求满载运输.另外,在本文为了简化问题,假设一个加油站只能被一辆车服务,实际中一个加油站可以被多辆车服务.在后续的研究中,我们将逐渐加入这些约束条件,建立更加符合实际情况的成品油配送路径优化模型,为解决实际问题提供理论依据.
参考文献：
［1］Herer Y,Levy R.The Metered Inventory Routing Problem,an Integrative Heuristic Algorithm［J］.International Journal of Production Economics,1997,51(1):69-81.
［2］BirgerRaa,El-HoussaineAghezzaf.A Practical Solution Approach for the Cyclic Inventory Routing Problem［J］.European Journal of Operational Research,2007,1922：429-441.
［3］BirgerRaa.New Models and Algorithms for the Cyclic Inventory Routing Problem［J］.4OR,2008,61∶97-100.
［4］Kunpeng Li,Bin Chen,AppaIyer Sivakumar,Yong Wu.An Inventory–routing Problem with the Objective of Trel Time Minimization［J］.European Journal of Operational Research,2014：936-945.
［5］赵达,李军,马丹祥,李妍峰.求解硬时间窗约束下随机需求库存-路径问题的优化算法［J］.运筹与管理,2014,23(1)：27-37.
［6］Zhenping Li,Zhiguo Wu.Study 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.
赵紫龙,等：浅析施工顺层钻孔瓦斯超
问题研究论文参考资料：
汇总,该文是关于问题研究方面的大学硕士和本科毕业论文以及成品油和优化和配送相关问题研究论文开题报告范文和职称论文写作参考文献资料。
