以工作量均衡为目标的成品油配送路径优化问题研究
陈伟峰１０１１４９） （北京物资学院，北京
Ｒｅ ［摘要］文章以成品油配送路径优化问题为背景，研究了以工作量均衡为主要目标的成品油配送路径优化问题 （ ｆｉｎｅｄｏｉｌｄｉｓｔｒｉｂｕｔｉｏｎｒｏｕｔｅｏｐｔｉｍｉｚａｔｉｏｎｐｒｏｂｌｅｍ）。在考虑车辆容载量、加油站允许卸油时间窗、加油站服务时间、加油站需求量等约束的前提下，将各个车辆的工作时间尽可能均衡作为主要目标，建立了以车辆的最大工作时间最小化为目标函数的Ｌｉｎｇｏ １０成品油配送路径优化问题的整数规划模型，编写了求解模型的程序。文章进一步用随机生成的方式，产生了 个加油Ｌｉｎｇｏ Ｌｉｎｇｏ站的计算实例，利用 软件求出了局部最优解。通过软件求得的局部最优解表明了模型的可行性。文章的研究结果为调度部门制订成品油配送计划提供了理论依据。［关键词］工作量均衡；硬时间窗；库存路径优化；数学模型ＤＯＩ １０ １３９３９／ ｊ ｃｎｋｉ ｚｇｓｃ ２０１７ １５ ２４１ ［ ］
库存和运输是物流系统最重要的功能要素，是物流获得“时间价值”和“空间价值”的两大主要环节，它们的耗费２／ ３ １ ［ ］约占物流总成本的。经典的库存路径问题主要研究一个供应商向多个顾客提供配送服务时，在保证顾客的需求量、顾客的配送时间窗以及库存容量限制等约束条件的前提ＩＲＰ下，使总成本达到最小。对于 问题，国内外已经有较多Ｃｌａｕｃｌｉａａｒｃｈｅｔｔｉ ２ ［］的学者去研究并得出了丰富的理论。 等人提出了离散时间下的配送问题，以库存和运输成本最小化作Ｐｉｅｔｅｒｖａｎｓｔｅｅｎｗｅｇｅｎ ３ ［］为目标函数。 等人研究了单车辆循环库存路径问题，考虑单车辆循环配送问题，不考虑有无限车辆可以使用的情况，是以总成本的最小化作为主要考虑因Ｋｕｎｐｅｎｇｌｉ ４ ［］素。 等人研究了成品油配送过程中的库存路径问题，在每个加油站只能被服务一次且采用最大补货量原则的前提下，以总运输时间最小化作为主要的目标函数，建立了数学模型并设计了禁忌搜索算法对模型进行求解。李相２００７ ５ ［ ］勇于年提出了带时间窗和随机旅行时间车辆路径问６ ［ ］题，并设计了基于随机模拟的禁忌搜索算法。蒋波 在研究带时间窗车辆路径优化问题时，给出了以配送总成本最小ＶＲＰＴＷ化为目标的带惩罚函数的 优化模型，并用遗传算法进行了求解。
１问题描述
本文主要以油库向各个加油站配送成品油作为主要的研究背景。考虑由加油站管理库存的成品油配送物流系统，基于工作量均衡的成品油配送库存路径优化问题可以描述为：
ｎ一座油库为个加油站供应某种型号的成品油，假设油库的
Ｋ库存量足够大，已知油库拥有辆运输车，每辆运输车辆的容载量已知；一辆运输车在油库装满成品油以后，由油库出发依次为若干个加油站配送成品油，配送结束后返回到油库；每个加油站都有一个固定的卸油时间窗，运输车必须在加油站的规定时间窗内为加油站卸油；如果运输车辆早于加油站最早服务时间到达，则运输车必须等待；如果运输车晚于加油站的最晚时间到达，则会造成加油站断货，因此不允许车辆晚于加油站最晚服务时间到达加油站；同一加油站的需求量可以由多辆运输车进行配送；已知每辆运输车的容载量、加油站对成品油的需求量、油库和加油站之间以及各个 加油站之间的最短运输距离、每个加油站卸油（服务）所需时间以及加油站的时间窗。如何安排运输车的运输路径及运输量才能使各辆运输车的工作时间尽可能均衡？
２基于工作量均衡的库存路径优化问题的数学模型
首先定义如下符号和变量： Ｉ＝｛ ０，１，２，…， ｎ， ｎ＋ １｝ ０油库和加油站的集合，其中 、ｎ＋ １表示油库，为了建立模型方便，我们把油库用两个点０ ｎ＋ １表示，表示车辆的出发油库， 表示车辆的返回油库； １，２，…， ｎ表示加油站； ｑｉ ｉ加油站的需求量； Ｋ Ｋ＝{ １，２，…， ｋ}；车辆的集合ｐｋ ｋ车辆的额定载重量； ｄｉｋ ｋ ｉ车辆运送到加油站的成品油数量； ｘｉｊｋ ＝ ０ ｋ ｖｉ， ｖｊ）， １，如果车辆 经过路径 （ 则为 否则０；为ｔａｉ ｉ
加油站接受服务的最早时间； ｔｂｉ ｉ加油站接受服务的最晚时间； ｋ ｋ
ｒｎ＋ １， ｋ 表示车 辆返回油库的时间； ｉ加油站 卸油（服务）所需时间；
Ｙ所有车辆完成任务后回到油库的时间； ｍｉｎｙ １） （ Ｋ ｎ＋ １ ｓ ｔ ｘｉｊｋ≥ １ ｉ＝ １，２，…， ｎ ２） （ ｋ＝ １ ｊ＝ １， ｊ≠ ｉ ｎ ｘ０ｊｋ ＝ １ ｋ＝ １，２，…， Ｋ ３） （ ｊ＝ １ ｎ
ｋ＝ １，２，…， Ｋ ４） ｘｉ， ｎ＋ １， ｋ ＝ １ （ ｉ＝ １ ｎ ｎ＋ １ ｘｉｈｋ － ｘｈｊｋ ＝ ０ ｋ＝ １，２，…， Ｋ ５） （ ｉ＝ ０ ｊ＝ １ ｎ ｎ＋ １ ｄｉｋｘｉｊｋ≤ ｐｋ ｋ＝ １，２，…， Ｋ ６） （ ｉ＝ １ ｊ＝ １
－ Ｍ（ １－ ｉ＝ １，２，…， ｎ， ｊ＝ １，２， ｎ， ｋ＝ １，２，…， Ｋ ７） …， （ ｎ ｎ ｘｉｊｋｔ ≤ ≤ ｘｉｊｋｔ ｊ＝ １，２，…， ｎ， ｋ＝ １，２， ｉ＝ ０ ｉ＝ ０ Ｋ ８） …， （ ｎ＋ １ Ｋ ｄｉｋｘｉｊｋ ＝ ｉ＝ １，２，…， ｎ ９） （ ｊ＝ １ ｋ＝ １ ｒｎ＋ １， ｋ≤ ｙ ｋ＝ １，２，…， Ｋ １０） （ ０， ｉ＝ １，２，…， ｎ， ｊ＝ １，２，…， ｎ＋ １， ｋ＝ １， ２，…， Ｋ １１） （ ｘｉｊｋ∈ ０ １ ｉ＝ ０，１，…， ｎ， ｊ＝ １，２，…， ｎ＋ １， ｋ＝ １， } ２，…， Ｋ １２） （ １）目标函数 （表示极小化所有车辆完成配送任务的最长时间； ２）约束 （表示每个加油站至少被一辆运输车服务； ３） ～ ４）约束 （ （表示每一辆运输车的运输路径起点和终点都必须是油库； ５）约束 （表示一辆运输车进入某个加油站，则必然要从该加油站离开； ６）约束 （表示运输车辆所装载的成品油的总量不超过运输车的容载量；
７）约束 （表示同一运输路径上相继两个加油站的车辆到达时间之间的关系；
８）约束 （表示车辆到达加油站的时间必须在加油站的时间窗内；
９）约束 （表示所有车辆运至某一加油站的成品油数量等于其需求量；
１０）约束 （表示所有车辆回到油库的时间均不超过最长时间；
１１） ～ １２）约束 （ （ 表示变量的取值约束。
３算例及求解
１０ ０假设有一油库为个加油站配送成品油，序号 表示１～ １０ ３油库，序号 表示加油站，油库共有辆运输车，运输５０ｋｍ／ ｈ，车的行驶速度均为 每辆运输车的容载量不相同。１，每辆车的容载量见表每个加油站的需求量、服务时间及２，硬时间窗见表每个加油站之间以及加油站与油库之间的３，距离见表每个加油站之间以及加油站与油库之间的车辆４， ３行驶时间见表 问如何安排配送路径才能使 辆车的工作时间尽可能均衡？
Ｌｉｎｇｏ根据本文建立的整数规划模型，利用 软件编程求Ｌｉｎｇｏ ３０解，当求解选项设置为全局最优解时， 经过 个小时的程序运行之后得到全局最优解，具体结果如下所示： ３辆运输车的配送路线分别为：
４ 结 论
Ｌｉｎｇｏ通过求得局部最优解的用时较长，无法满足短时间内求得最优解的要求。
库存路径优化问题是制订成品油配送计划的关键问题，在实际安排成品油配送方案的时候，经常需要考虑各个配送车辆的工作时间的均衡问题。本文研究的基于工作量均衡的库存路径优化问题的目标就是尽可能使配送车辆的工作时间均衡。本文首先建立了该问题的数学模型，并
Ｌｉｎｇｏ编写了求解模型的 程序，进一步设计了求解模型的启发式算法。本文的模型和算法为制订成品油配送计划提供了理论依据。 参考文献： １ Ｈｅｒｅｒｙ Ｌｅｖｙｒ Ｔｈｅｍｅｔｅｒｅｄｉｎｖｅｎｔｏｒｙｒｏｕｔｉｎｇｐｒｏｂｌｅｍ， ［ ］ ， ０— １— ４— ６— ９— ０ ０— ８— ７— ５— ０ ０— １— ２— ３— １０— ０ ５每辆车到达配送点的时刻具体如表 所示。 ａｎｉｎｔｅｇｒａｔｉｖｅｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ Ｊ ． Ｉｎｔｅｒｎａｔｉｏｎａｌｊｏｕｒｎａｌｏｆｐｒｏｄｕｃ ［ ］ ｔｉｏｎｅｃｏｎｏｍｉｃｓ， １９９７，５１（ １）： ６９－ ８１ ２ Ｃｌａｕｃｌｉａ Ａｒｃｈｅｔｔｉ， Ｎｉｃｏｌａ Ｂｉａｎｃｈｅｓｓｉ， Ｓｔｅｆａｎ Ｉｒｎｉｃｈ， ｅｔ ［ ］ ａｌ Ｆｏｒｍｕｌａｔｉｏｎｓｆｏｒａｎｉｎｖｅｎｔｏｒｙｒｏｕｔｉｎｇｐｒｏｂｌｅｍ Ｊ ． Ｉｎｔｅｒｎａｔｉｏｎａｌ ［ ］ Ｔｒａｎｓａｃｔｉｏｎｓｉｎｏｐｅｒａｔｉｏｎａｌｒｅｓｅａｒｃｈ， ２０１４（ ２１）： ３５３－ ３７４ ３ Ｐｉｅｔｅｒｖａｎｓｔｅｅｎｗｅｇｅｎ， Ｍａｎｕｅｌｍａｔｅｏ Ａｎｉｎｔｅｒａｔｅｄｓｅａｒｃｈａｌｇｏ ［ ］ ｒｉｔｈｍｆｏｒｔｈｅｓｉｎｇｌｅ－ Ｖｅｈｉｃｌｅｃｙｃｌｉｃｉｎｖｅｎｔｏｒｙｒｏｕｔｉｎｇｐｒｏｂｌｅｍ Ｊ ． Ｏｐ ［ ］ ｅｒａｔｉｏｎａｌｒｅｓｅａｒｃｈ， ２０１４，２３７（ ３）： ８０２－ ８１３ ４ Ｋｕｎｐｅｎｇｌｉ， Ｂｉｎｃｈｅｎ， Ａｐｐａｌｙｅｒｓｉｒａｋｕｍａｒ， ｅｔａｌ Ａｎｉｎ ［ ］ ｖｅｎｔｏｒｙ－ Ｒｏｕｔｉｎｇｐｒｏｂｌｅｍｗｉｔｈｔｈｅｏｂｊｅｃｔｉｖｅｏｆｔｒａｖｅｌｔｉｍｅｍｉｎｉｍｉｚａｔｉｏｎ Ｊ Ｅｕｒｏｐｅａｎｊｏｕｒｎａｌｏｆｏｐｅｒａｔｉｏｎａｌｒｅｓｅａｒｃｈ， ２０１３，２３６ ３）： ［ ］ （ ９３６－ ９４５ ５ Ｄ． ［］李相勇车辆路径问题模型及算法研究 ［］上海：上海２００７： ９１－ １０５ 交通大学， ６ ［］蒋波基于遗传算法的带时间窗车辆路径优化问题研究Ｄ ． ２０１０： ８－ ４４ ［ ］ 北京：北京交通大学，