成品油配送路径优化问题研究[摘要]成品油配送路径优化问题是指在加油站需求量已知的情况下，石油公司利用多种型号的油罐车，从油库出发为各个加油站配送成品油以满足各个加油站需求的路径优化问题。文章主要研究某石油公司的成品油配送车辆调配和路径规划问题，在车辆数量充足、每辆车需从油库出发在完成供油任务后回到油库的前提下，考虑车辆的容量限制、加油站需求量、需求时间窗、卸油服务时间等条件，以系统运行成本的最小化为目标建立相应问题的数学模型。然后，利用1个油库、10个加油站的算例对模型的正确性进行了验证。[关键词]成品油配送；路径优化；时间窗；数学模型[DOI]1013939/jcnkizgsc2017181841引言库存和运输是物流系统最重要的功能要素，是物流获得“时间价值”和“空间价值”的两大主要环节，它们的耗费约占物流总成本的2/3。[1]库存路径问题主要是研究一个供应商向多个顾客提供配送服务时，在满足顾客的需求量、配送时间窗以及库存容量限制等约束条件的情况下，使总成本达到最小。BirgerRaa[2-3]等人于2007年在研究库存路径问题（InventoryRoutingProblem）时，假设顾客的需求率是恒定的，在不引起缺货的情况下，以平均配送和库存成本最小化为目标得出周期性补货策略，并运用粒子群算法对该模型进行了求解。2008年又在模型中加入了车辆使用成本，同时运用插入遗传算法对模型分步进行求解。KunpengLi[4]等人在解决成品油配送问题时，考虑车辆容载量、加油站?齑嫒萘俊⒊盗臼?量等因素的情况下以最大路径遍历时间的最小化为目标函数建立数学模型，并设计了禁忌搜索算法。赵达[5]等人在2006年以零售商系统下随机需求的IRP为研究对象，提出了一种基于马尔科夫决策过程与修正的C-W节约算法的启发式分解算法。我们在2016年以工作量均衡为目标，研究了带硬时间窗约束的成品油二次配送路径优化问题，建立了整数规划模型并设计了求解模型的算法。[6]成品油配送问题是一种典型的库存路径问题，由于各个加油站的成品油均储存在容量有限的油罐中，为加油站配送成品油的车辆也是特定的油罐车，为了满足加油站的日常销售，油库需要每天向加油站配送成品油，才能保证销售过程中不出现断货。在研究成品油库存路径问题时，如果加油站的销售速率为常数，则可以根据加油站当前的存储量确定出一段时间内的需求量，进一步根据配送车辆的容量以及油罐的容量限制，确定出配送时间窗。这种条件下成品油配送库存路径问题就简化成了带容量和时间窗限制的车辆路径问题。本文主要研究简化以后的成品油配送车辆路径优化问题，建立该问题的数学模型并设计求解模型的蚁群算法。2问题描述成品油的配送路径优化问题可以描述为：有一个油库，同时向多个加油站提供某一种型号的成品油；已知加油站在某一时间段内对成品油的需求量；每个加油站有对应的硬时间窗，成品油配送车辆不能早于也不能晚于加油站时间窗进行供油；配送车辆在每个加油站卸油均需要消耗一定的时间；为加油站配送成品油的油罐车为单舱车，且油罐车的数量充足；每辆油罐车的容载量、固定使用成本、单位距离行驶成本均不相同；每辆车可以同时向多个加油站供油，每个加油站只能接受一辆油罐车为其供油；每辆油罐车的平均行驶速度相同，均为50km/h。系统的目标就是在已知各个加油站的需求量以及相互之间的距离的情况下，求使得系统总运行成本最小的配送方案。在成品油配送过程中，假设配送车辆从油库出发为若干个加油站配送成品油，完成配送任务后返回油库。同一辆配送车服务的若干个加油站的总需求量不能超过车辆的容载量。由于每个加油站只能接受一辆油罐车为其供油，因此为加油站供油的油罐车在该加油站的卸油量与加油站的需求量相等。油罐车在到达加油站时开始卸油，开始卸油的时刻应处于该加油站的时间窗内。每辆车在卸油时会耗费一定的时间，卸油耗费的时间与卸油量成正比，且当车辆在一个加油站完成卸油时会立即驶往下一个加油站。由于油库的车辆数量充足以及每辆车的容量、固定成本及可变成本不同，因此，需要从可用车辆中选择一部分为加油站送油，并进一步确定出每一辆油罐车服务的加油站集合及配送路径，使得总配送成本最低...