ICP策略下带软时间窗的动态车辆路径优化问题研究.docx

解决研究难题：问题拆解和解决方案策略 #生活技巧# #学习技巧# #学术研究指南#

1、 ICP策略下带软时间窗的动态车辆路径优化问题研究 鄢栋陈家琪Summary：针对动态车辆路径中出现新的客户请求时，输入信息（可能包括客户请求出现时的车辆位置、客户时间窗、服务时間、需求量等）也随着时间推移而动态改变，在服务客户时由于动态客户需要不停插入，导致不停地进行优化计算，致使车辆路径更新频繁的问题，提出了紧急动态客户和数据包的概念（简称ICP）。通过该策略并使用遗传方法（Genetic Algorithm，GA）与局部搜索方法（Local Search，LS）的混合算法（简称GALS），可提高车辆路径更新质量，降低车辆运输成本并控制配送中心管理成本，从而提高服务质量。通过实验证明了该策

2、略的有效性。Key：车辆路径优化；DVRPSTW；遗传算法；LS；数据包DOIDOI：10.11907/rjdk.172443：TP319：A：16727800（2018）003017204英文SummaryAbstract：For the new customer requests that appear in the dynamic vehicle path， the input information （which may include the location of the vehicle when the customer request appears， the customer

3、s time window， service time， demand， etc.） changes dynamically over time. In the service of customers， due to frequently inserting of dynamic customers demand and the vehicle path updating ，which leads to the nonestop optimal calculation.In this paper， the concept of emergency dynamic customer and d

4、ata packet （ICP） is proposed. Through using this strategy and GALS method ， the transportation cost of vehicle is reduced and the management cost of distribution center is controlled， then the quality of service is optimized.The validity of the ICP method is proved by experiments.英文KeyKey Words：vehi

5、cle routing optimization； DVRPSTW； genetic algorithm； LS；data package0引言动态车辆路径问题是指对一系列发货点（或收货点），组织适当的行车路径，使车辆有序通过，在满足一定约束条件（如货物需求量、客户需求、交发货时间、车辆容量限制、行驶里程限制、时间限制等）的情况下，达到一定目标（如路程最短、费用最少、消耗能源最少等）1。由于在现代社会中时间约束的重要性，出现了VRPTW（Vehicle Routing Problem with Time Window，有时间窗车辆路径问题）。在具有硬时间窗口（VRPHTW）的车辆路径和调度问题

6、中，根本不允许在时间约束窗口之外进行交付，这对于现实生活中的物流运输是不太合理的。因此，带有软时间窗（VRPSTW）的车辆路径和调度问题引起了人们关注，即其在约束时间窗口外仍然可以通过增加一些惩罚成本进行交付。但由于静态VRPSTW的有些约束条件是规定好的，并不能反映现实世界的真实情况。因此，更具有实际研究意义的DVRPSTW问题受到越来越多研究者的青睐。黄务兰、张涛2提出了基于事件触发（包括不需要调整路线车辆位置变化、完成节点服务，以及需要调整路线的，比如新的请求到达、因阻塞等原因路网发生了变化）的分解策略，根据系统的当前状态，构造一个系统的延迟快照，每个快照被视为一个VRPTW，从而把DV

7、RPTW分解成一系列的VRPTW问题。然后在LNS算法基础上，提出一个双缓冲区来改进LNS算法，求解静态VRPTW问题。洪联系3用混合节约算法与禁忌搜索算法优化动态车辆路径问题，目标为最小化车辆旅行距离与车辆数量。根据动态需求的特点，按照一定规则和策略，将整个配送过程分为若干个相等或不等的时间段进行处理。在每个时间段的结束时刻，实行动态需求的插入，并根据车辆当前位置和更新后的信息制定出新的路线方案。通过比较相同数据下单个节约算法、单个禁忌搜索算法、混合算法输出的总目标值，得出结论。刘霞等4研究的是带软时间窗的动态车辆路径问题，首先将计划周期划分为固定时间间隔的时间片段并设置一个中断时间作为算法

8、终止条件之一，从而将问题静态化；然后利用插入法求解DVRPTW的初始线路（初始解），采用线路间局部搜索和线路内局部搜索对初始解进行优化。对于违反时间窗的车辆，增加一个延迟时间惩罚参数；最终通过Solomon的算例，进行实验并分析结果，求得最优路线。对于DVRPSTW问题的求解，大多是将时间窗进行划分，把DVRPSTW问题转换为一系列的静态子问题，从而求解VRPSTW问题。对于动态需求，大多数是在当前时间段（一般是结尾处）插入一个动态客户，并计算插入的必要条件，插入后进行路径实时优化，最后得出最优路径，接着再插入下一个动态客户。这样由于不断地进行插入和优化计算，从而导致不停地更新车辆路径，进而增

9、加了车辆运输成本与配送中心管理成本。因此，为了减少动态过程中的插入和优化计算负载，提高车辆路径更新质量，减少车辆运输成本（车辆数量）并控制配送中心管理成本（车辆行驶总距离），本文基于插入（紧急需求插入）和数据包（用来存放非紧急客户的动态客户暂存区）的概念，提出一种紧急需求插入和数据包的求解新方法。 1DVRPSTW问题描述与数学建模带软时间窗的动态车辆路径问题（DVRPSTW）可以描述如下：G=（I，E）是有向图，其中I = （1，2，N）是顶点集，表示客户。E=（i，j）：iji，jI是弧集。顶点0（Distribute Center）表示有M个容量为Q的相同车辆的配送中心，且是路线的起点和

10、终点。顶点集I = （1，2，N）指定一组N个客户的位置。I中的每个顶点具有相关联的需求qi0，服务时间si0，以及服务时间窗口ei，li。每个弧（i，j）具有相关联的恒定距离dij0和行驶时间tij（tij=dijv），v是车辆速度。车辆到达客户i的时间表示为Ri（Reach），车辆m访问客户i时的剩余容量表示为gim，且gimQ。T是车辆工作时长。在对车辆进行路径规划时，将工作日T划分为Nt个不同长度的时间片段。那么当在某一时刻Tl：（1）设G=（ITl，ETl）。（2）车辆m最终确定服务的客户集记为Csd，即包括已知的静态客户和即将服务的动态客户，如图1所示。（3）用NTl表示工作日之前

11、和工作日内接收的动态客户。（4）则ITl=NTlo，Csd，NTlo，Csd=，其中o是Tl时刻的配送起点，不同于配送中心0。（5）定義决策变量xijm=0，1，表示如果存在车辆m从客户i到客户j的路线时，xijm=1，其他情况xijm=0。本文目标是最小化车辆数量（在路径图中体现为路径数）和最小化配送中心的运输成本（在路径图中体现为路径总距离）。采用线性加权权重法5衡量目标子函数，则本文的目标函数可以定义为：minf=iNTlmMxi0m+io，Csdj0o，CsdmMdijxijm（1）满足如下约束条件：（1）车辆从配送中心出发，服务客户后必须返回配送中心。用公式表示为：i0o，CsdjN

12、Tlxijm=1，mM（2）iNTlxi0m=1，mM（3）（2）每个客户有且只能由一辆车为其服务，用公式表示为：jNTlmMxijm=1，iITlij（4）iITlxikm=jNTlxkjm，kNTl，mM（5）（3）每辆车运输量不能超过车辆本身的装载能力，即：iNTlj0NTljiqixijmgim，mM（6）（4）时间参数计算。等待时间：Wi=ei-Ri，若eiRi0，否则 ，iNTl（7）客户j的到达时间：Rj=iITlmMxijm*（Ri+Wi+Si+tij），j0NTlji（8）车辆必须在客户i的时间窗口关闭前到达，否则增加一个惩罚参数Pi，并重新分配路径，即：Rili，iITl（

13、9）Pi=Ri-li，Rili（10）2紧急需求插入与数据包求解方法描述在时刻Tl，假设某辆车的配送路径为（v0，v1，vk，vK），vkITl（该路径作为初始路径，用遗传算法求解），如果一个顾客v*插入到该路径中，而路径仍是有效的，且满足需求公式：qv*+Kv=1qvkgvkm，vkITl（11）并且满足：（1）当v*插在上述配送路径的最后一个，则：Wvk+Rvk+Svk+tvk，v*Lv*（12）（2）当v*插在上述配送路径中间，假设在vk和vk+1之间（k0，k-1），则：Wvk+Rvk+Svk+tvk，v*Lv*（13）maxWvk+Rvk+Svk+tvk，v*，Ev*+Sv*+tv*

14、，vk+1Rvk+1+Wvk+1+Dvk+1（14）其中Dvk+1表示顾客vk+1的最大延迟时间，为：Dvk=Lvk-（Rvk+Wvk），k=KminLvk-（Rvk+Wvk），Dvk+1+Wvk+1，k1，k-1（15）如果动态客户发送动态需求的时刻记为t0，t1，（t0t1），在这些时刻，按照公式（11）（15）把动态需求插入路径中。如果某个动态客户在t（r）时刻后发送了请求，并且该请求可以在下一个t（r+1）时刻被成功地调度，则把该动态需求放到t（r+1）时刻处理。像这样的动态需求对应的动态客户称为“非紧急动态客户”。所以，如果动态客户在时刻t，ttr，tr+1（t（r）和t（r+1）是

15、相邻两次优化的时间）发送了动态需求，并且该动态客户可以在t（r+1）时刻插入到当前计划的路径中，即满足该动态客户自身的时间窗约束，则称该动态客户为“非紧急动态客户”；如果不能在t（r+1）时刻插入到当前计划路径中，则称该动态客户为“紧急动态客户”。对于紧急客户，按照上述公式对当前紧急动态客户进行插入，并对dvrpstw数学模型在时刻t0，t1，（t0t1“紧急动态客户”采用实时插入的方法，“非紧急动态客户”采用数据包策略，即把“非紧急顾客”都放到数据包里，待达到优化条件时，再一起发送给优化模块。整体方法流程如图2所示。3DVRPSTW算法描述带软时间窗的动态车辆路径问题（DVRPSTW）算法采

16、用了结合遗传算法和局部搜索算法的混合算法。其思想是第一步采用遗传算法产生路径初始解，然后使用该解作为局部搜索搜索算法的初始值，然后用重定位法和2-opt法进行优化运算。在该混合算法中，时间窗被划分为不同长度的时间片段，在每个时间片段的结尾处收集静态和动态客户集，如果是紧急动态客户，则立即插入线路中并优化，如果是非紧急动态客户，则先加入到数据包中，待达到优化条件再进行优化，直到优化模块更新信息，输出最优路径。在每个时间片中，该问题类似于静态VRPTW。因此，通过已经描述的混合算法，对于具有不同起始位置的车辆，该问题在每个时间片结束时作为部分静态问题来解决。算法步骤如下：首先获取车辆m的实时数据，

17、设其初始数据在配送中心，开始时间为0；确定车辆m最终服务的客户集Csd；判断当前时间是否超过了时间片与惩罚参数Pi（即最大延迟时间）之和，如果超过，则结束，转步骤；否则，还有动态客户的需求没有到达或未到时间片的结尾，执行步骤；在每个时间片的结尾处构成了静态子问题。在时间片开始之前，静态子问题中的客户集是由当前时间片还未提交的客户以及上一个时间片内出现的即时新客户组成（这里不考虑上一个工作日）；采用遗传算法的精英策略产生线路初始值；采用重定位法和2-opt法对步骤中产生的初始值进行优化。如果时间片结束，终止优化计算，到下一步骤，否则，循环执行；提交已优化的线路给下一个时间片内的车辆，并移除已优化

18、线路中的客户节点；更新信息；配送任务完成，车辆返回配送中心，并输出最优路径解。 /t1），在这些时刻，按照公式（11）（15）把动态需求插入路径中。如果某个动态客户在t（r）时刻后发送了请求，并且该请求可以在下一个t（r+1）时刻被成功地调度，则把该动态需求放到t（r+1）时刻处理。像这样的动态需求对应的动态客户称为“非紧急动态客户”。所以，如果动态客户在时刻t，ttr，tr+1（t（r）和t（r+1）是相邻两次优化的时间）发送了动态需求，并且该动态客户可以在t（r+1）时刻插入到当前计划的路径中，即满足该动态客户自身的时间窗约束，则称该动态客户为“非紧急动态客户”；如果不能在t（r+1）时刻

19、插入到当前计划路径中，则称该动态客户为“紧急动态客户”。对于紧急客户，按照上述公式对当前紧急动态客户进行插入，并对dvrpstw数学模型在时刻t0，t1，（t0t1其中、构成优化模块。算法流程如图3所示。4实验结果分析本文测试采用Lackner的benchmark数据c101、r101、rc101、c201、r201、rc201 这6类数据集，取=1 000，=1，T=1/205，优化计算5次，选择5次运行中的最优解进行分析，成本距离与车辆数分别如图4、图5所示。从图4的成本距离数据看，本文采用的基于ICP策略得出的结果比其它插入后进行实时优化的策略更优，而且整体数据较为稳定。本文平均使用的车

20、辆数大约为10辆，平均成本距离为1 057.68（车速为1）。设想在大规模车辆调度的实际问题中，优化效果会更明显。另外可以看到，201数据集的数据中，车辆数明显少于101数据集的数据，这是由于其数据集的特点所造成的。201的数据集时间窗宽，但客户坐标是随机的；101数据集时间窗窄，客户坐标也是随机的。这说明车辆使用数量与时间窗大小有关，时间窗越宽，使用的车辆数越少；反之，车辆使用越多。同時，实时插入策略虽然在平均车辆数的趋势上减少，在201数据集上使用的车辆数也大大减少，但是距离成本却很高。这说明实时插入虽然时效性很好，企业花费的距离成本却大幅上升。总体来看，本文的ICP策略减少了企业的服务成

21、本，提高了总体服务质量。所以，可以根据具体的企业需求选择策略，如果企业要求的是在可控成本内的时效性以及尽量减少车辆使用，则选择实施插入策略；如果企业要求总体减少服务成本输出，则最好选择ICP策略，这样既保证了时效性，又能减少企业服务成本。5结语本文研究带软时间窗的动态车辆路径问题，在动态车辆路径问题的基础上添加了时间窗，可更加贴近现实生活中车辆早到或延迟的情况，采用时间片的方法收集动态客户需求，将问题静态化，同时针对紧急动态客户采用即时插入方法，非紧急动态客户采用数据包策略，这样既保证了运输系统的实时性，又减少了优化模块的优化计算，从而减少车辆使用数量和企业管理成本。在未来研究中，可以考虑多个

22、中心仓库的DVRPSTW问题，或者考虑在车辆损坏、天气变化以及多个工作日中的DVRPSTW问题，以求解更复杂的现实情况。另外，对于共享资源以及绿色路径的优化也是未来的一个研究方向。ReferenceReference：1潘莹，陈家琪.基于MultiAgent仿真的动态车辆路径算法研究J.信息技术，2015（5）：121124.2黄务兰，张涛.基于改进遗传算法的带时间窗车辆路径问题研究J.微型机与应用，2016，35（13）：2124.3洪联系.带时间窗口动态车辆路径规划模型及其求解算法J.计算机工程与应用，2012，48（4）：244248.4刘霞，齐欢.带时间窗的动态车辆路径问题的局部搜索算

23、法J.交通运输工程学报，2008，8（5）：114120.5王君，李波，卢志刚.带时间窗动态车辆路径问题的优化调度策略J.计算机工程，2012，38（13）：137141.6XIAO J， LU B. Vehicle routing problem with soft time WindowsM. Advances in Computer Science and Information Engineering. Springer Berlin Heidelberg，2012：317322.7MAK K L， GUO Z G. A genetic algorithm for vehicle routing problems with stochastic dema

网址：ICP策略下带软时间窗的动态车辆路径优化问题研究.docx https://www.yuejiaxmz.com/news/view/631181

相关内容

【创新未发表】基于鱼鹰OOA求解带时间窗的骑手外卖配送路径规划问题，最优路径成本附Matlab代码
铁路电力机车节能优化操纵研究
动态交通环境下的纯电动车辆多目标出行规划
优化时间管理的工具与策略.docx
【电力系统】基于分时电价条件下家庭能量管理策略研究附MATLAB代码
节约法用于车辆路径问题的综述和分析
【动态规划/路径问题】变形「最小路径和」问题 & 常见 DP 空间优化技巧 ...｜刷题打卡
【电力系统】考虑动态能效的园区综合能源系统优化调度策略设计附matlab代码和模型
旅行商问题，车辆路径问题的数学规划模型
【优化调度】基于多时间尺度的电动汽车光伏充电站联合分层优化调度附Matlab代码

随便看看