时变单车路径优化模型及动态规划算法.pdf

第 卷 第 期运 筹 与 管 理 ， 年 月 收稿日期：- - 基金项目：国家自然科学基金资助项目（）；重庆市教育委员会科学技术研究项目（） 作者简介：彭勇（- ），男，重庆市，副教授，博士，研究方向：运作管理与优化。 时变单车路径优化模型及动态规划算法 彭 勇 ， 殷树才 （ 重庆交通大学 交通运输学院，重庆 ； 永川供电局，重庆 ） 摘 要：车辆路径问题由于其广泛的应用领域及经济价值而成为学术研究热点。 然而，在已有的研究文献中，车 辆的速度时变与服务多任务特性很少被关注。 本文讨论了具有这两个特性的单车路径优化问题。 建立了以送 货完成时间最早为优化目标的时变单车送货路径优化模型。 由于很难获得该模型的精确解，本文提出了一种贪 婪补货策略压缩原问题解空间，设计动态规划算法给出了车辆行驶时间满足 规则的送货顺序近似最优解。 数值算例验证了该算法所得到的解仅是原问题的近似最优解这一结论。 算例同时表明优化配送时间随着车辆 装载能力的增大而缩短，并在车辆装载能力超过所有客户配送总需求时实现最短配送时间，即，使用较大装载能 力车辆能节约更多配送时间。 关键词：管理科学与工程；路径计划；动态规划；车辆路径问题 中图分类号： 文章标识码： 文章编号：- （）- - Time- dependent Single Vehicle Routing Problem and Dynamic Programming Algorithm with Greed Dispatching Restriction ， - （ Transportation Traffic School， Chongqing Jiaotong University， Chongqing ， China； Yongchuan power supply bureau， Chongqing ， China） Abstract： ， ， ， ， ， - ， - ， - ， Key words： ； ； ； 引言 车辆路径问题自 年提出以来，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者 的广泛关注 。 车辆行驶速度随时间、路段不同而变化的特点（时变特性），及车辆为多条优化路线上的 客户提供服务的问题在众多车辆路径优化研究文献中受到较少关注 。 考虑城市送货，送货企业对送 货区域进行划分，不同送货区域的客户由一辆车送货，对该车辆不要求一次完成所有客户（需求点）的送 货任务，送货过程中可以回货源点补货，这就形成单车路径优化问题 。 在现实世界中，特别是城市地 区，车辆行程时间同时依赖于两客户之间的距离和速度，交通拥堵等因素均会导致车辆不同时刻不同路段 行驶速度发生变化，从而使得车辆在路段上的行驶时间为一变化值 ， 。 本文综合这两个因素，研究有一 个货源点及多个需求点，且需求点由一辆运输能力有限的车辆提供送货服务的具有时变特性的车辆路径 优化问题。 时变单车路径优化模型 令图 G （N，E），顶点集合 N ，n，其中 为货源点，N N表示需求点集合；E （i，j）： ij；i，jN，为顶点间的连接弧，顶点间距离 D dij：i，jN，其中 dii 。 客户 i 需求为 qi，q ，表示 货源点需求为。 i 点服务时间为 tsi，当 iN 时，ts表示在相应需求点卸货等消耗时间，当 i 时，ts表 示车辆在货源点装载货物等消耗的时间。 令 tai为车辆到达点的时间。 函数 tij（tai tsi）表示从需求点 i 离开到达需求点 j 消耗的时间。 R 为送货路径集合。 Q为车辆最大装载量（即，车辆装载能力）。 定义决策变量 x r ij（i，jN，ij，rR），如果车辆在路径 r 中为点 i 完成服务后下一服务点为 j 时，x r ij ；否则，x r ij 。 则时变单车路径优化问题数学描述如下： Z rRrNjN，jitij（taitsi）x r ij（） rNqijN，jix r ij Q， 橙r R （） rRjN，jix r ij， 橙i N（） rN，ikx r ikjN，jkx r kj， 橙k N，橙r R （） rUjU，jix r kj U ， 橙U 彻 N，橙r R （） （tai tsi tij（tai tsi） taj）x r ij ，橙i，jN，ij（） 式（）给出模型优化目标为车辆从货源点装货开始为客户提供送货服务到完成所有客户送货服务返 回货源点时间最早。 式（）为车辆能力约束，即，车辆服务的任意一条路径上的客户需求总量不能超过车 辆装载能力。 式（）表示每个需求点仅由此车提供一次服务。 式（）为平衡条件，即，车辆到达某点次数 与车辆离开其点次数相同。 式（）确保送货回路通过货源点。 式（）为送货路径各点先后顺序时间逻辑。 满足 规则的行驶时间计算 为了便于计算，且不失一般性，将时间区间a，b分作个时间段，每个时间段分别记为 k ck， k） （k ，K），其中 a，k b。 对于不同实际问题可以按照实际情况进行时间段划分。 车辆在任 意时间段 k（k ，K）内，i 点到 j 点行驶速度为常数 v k ij（k ，K），且当 kK 时，i 点到点 j 行 驶速度为常数 v k eK ij（e 榾 K k ）；当 t k时，i 点到点 j 行驶速度为常数 v ij。 设车辆于 tk时刻离开点 i 驶往点 j，行驶时间为 tij（t），则 tij（t）计算方法为： （） tt，a d ij：t t d v k ij ； （） t kd，ddv k ij（k t），tk，kk ，t t d v k ij ； （） tij（t）t t。 上述方法保证了车辆行驶时间满足 规则。 动态规划优化方法 由于车辆在送货过程中的任意时刻均可能返回货源点进行补货，而车辆送货需求点顺序具有多种组 第 期 彭 勇，等： 时变单车路径优化模型及动态规划算法 合，因此，难于找到本文所给问题精确解。 可以对以上模型增加补货策略：在确定好一种车辆送货客户顺 序后，车辆在货源点总是装满货物，对未完成送货的客户按顺序进行送货，此时，车辆上装载货物也在不断 减少，当车辆装载货物不能满足下一送货客户需求时才返回货源点装满货再进行送货服务，送货服务目标 是找到一客户送货顺序，使满足该补货策略的送货时间最短。 在原问题模型中，没有约束要求车辆在不能 满足下一送货客户需求时才返回货源点装满货再进行送货服务，即，车辆完全可以在车上剩下的货物能满 足下一送货客户，甚至是下几个客户需求情况下提前回货源点补货（且补货也不需要一定要装满）。 通过 增加此补货策略，实际上限定了补货的多种可能性，但这一补货策略也符合现实中的送货实际。 由于在这 一补货策略下，送货人员总是尽量争取在回货源点补货之前能完成更多客户送货需求，而回到货源点补货 总是争取能尽量多装载货物，因此，本文将这一补货策略称之为贪婪补货策略。 本文设计如下动态规划算法给出增加贪婪补货策略车辆路径优化送货顺序。 但增加贪婪补货策略限 定了原问题多种补货可能性，因此，所给解对原问题仅为满意解。 路网中客户顶点集合 N N 。 定义第 k 阶段状态变量 sk为第 k 阶段完成送货的 k 个客户的集 合，其中，s表示车辆刚到货源点装好货尚未出发时的状态。 第 k 阶段从状态 sk出发允许的决策集合为 N sk。 定义函数 Tk（sk，j）为第阶段完成送货 k 个客户且最后完成送货的客户为 j 时总共消耗的送货时间。 定义 t k（i，j）为第 k 阶段车辆完成客户 i 送货后驶往客户 j 所消耗时间，若车辆剩余装载量不能满足 j，则车 辆将先到货源点 装满货物再到 j 点）。 令 Q left i为车辆完成客户 i 送货服务后剩余装载量，则有： t k（ij） tij（Tk （sk ，i） tsi）if Q left i qj ti（Tk （sk ，i） tsi） tj（Tk （sk ，i） ti（Tk （sk ，i） tsi） ts）if Q left i qj 令货源点 发车时间 T。 则完成所有客户送货总共消耗时间递推方程为： Tk（sk，j） isk （Tk （sk ，i） t k（i，j），橙jN s k，k ，n T（s，） T ts 所给问题优化目标可表达为： isn（Tn（sn，i） ti（Tn（sn，i） tsi）。 数值算例 假设装载能力为 Q的车辆在 T 到达货源点 开始装货为 n 个需求点提供送货服务，且需求点 之间的距离、需求及服务时间已知（见表、，若 n ，则在表 、 中大于 n 的数据无效）。 现实世界中， 不同路段不同时刻不同行驶方向行驶速度不一定相同，算法可以根据不同路段不同时刻不同行驶方向给 出不同速度函数，为减少给出的数据量，但并不影响分析，本算例假设不同路段不同行驶方向具有相同的 速度函数，并成周期性变化。 速度周期变化函数离散化为如图 所示函数，各路段沿不同方向函数为图 所示函数按表 所给位移量向左做相应位移（若 n ，则在表 中大于 n 的数据无效）。 比如，从需求点 到需求点 不同时刻路段行驶速度函数即为图 图形向左位移 个时间单位，形成需求点 到需求点 不同时刻行驶速度函数（见图 ），需求点 到需求点 不同时刻行驶速度函数见图 ，其它路段速度函数 同理可得。 表 1 需求点间距离（0 为货源点） Ii? i2? ?i2R? 2R? 2R? ?R? R R? R? 运 筹 与 管 理 年第 卷 表 2 客户需求量（0 为货源点） ? ? u s p m k h 表3 路段拥堵时间位移量 geb_fin eb_ fi Z geb_ fi Z gb_ fi Z geb_ fi Z ge_ fi Z geb_ fi Z geb fi Z geb_Z geb_ fi Z geb_ fi Z geb_ fi 图 各路段速度周期变化基准 图 需求点 到需求点 速度函数 图 需求点 到需求点 速度函数 图 个需求点不同装载能力送货时间 利用本文所给算法计算不同车辆服务客户数量与车辆最大装载能力情况下车辆总送货时间如表 所示。 表 4 不同客户数不同装载能力送货时间 Customer number Vehicle capacity F(? ? ? ? 倡 倡? 倡 倡 q 倡 倡：车辆装载能力超过客户总需求，大于等于此装载能力的车辆送货实际等于无能力约束车辆路径问题，结果不再发生变化。 第 期 彭 勇，等： 时变单车路径优化模型及动态规划算法 从计算结果来看，不同需求点数量的车辆送货路径优化送货时间都有随车辆装载能力增加而减少的 趋势，并且在车辆装载能力大于客户总需求的时候达到最小。 这一规律符合实际，车辆装载能力大的车辆 至少可以按照装载能力小的车辆使用，因此，车辆装载能力大的车辆优化的送货时间至少能够获得不差于 车辆装载能力小的车辆优化的送货时间。 根据这一规律，在不考虑车辆购置成本等影响因素下，在装载能 力小于客户总需求情况下，选用装载能力大的车辆总是会节约车辆送货时间。 但在不同需求点数量情况 下，都出现了在某一装载能力下车辆优化送货时间大于车辆装载能力较小时优化的送货时间情况，比如， 个需求点情况下，车辆装载能力等于 时，送货时间为 ，大于车辆装载能力等于 时的送货时间 。 分析原问题，出现该种情况的原因是我们设计的算法求解的模型增加了贪婪补货策略。 由于该策 略忽略了其它一些补货行为，如在此案例中，车辆装载能力为 时的贪婪补货策略即忽略了车辆装载能 力为 时的优化送货策略，这也验证了所给解为贪婪补货策略问题的最优解，但对原问题仅为满意解。 结束语 本文讨论了时变单车配送路径优化问题，建立了以送货完成时间最早为优化目标的时变单车送货路 径优化模型。 讨论了该问题与增加贪婪补货策略的单车送货路径问题解的关系。 在行驶时间满足 FIFO 规则下，设计了满足贪婪补货策略单车送货路径模型的动态规划求解方法。 数值算例表明不同需求点数 量的车辆送货路径优化送货时间都有随车辆装载能力增加而减少的趋势，并且在车辆装载能力大于客户 总需求的时候达到最小。 根据这一规律，在不考虑车辆购置成本等影响因素下，在装载能力小于客户总需 求情况下，选用装载能力大的车辆总是会节约车辆送货时间。 但由于增加了贪婪补货