《带多时间窗的实时车辆路径优化问题的研究》由会员分享，可在线阅读，更多相关《带多时间窗的实时车辆路径优化问题的研究（4页珍藏版）》请在金锄头文库上搜索。
1、欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 带多时间窗的实时车辆路径优化问题的研究 【摘要】考虑客户的多时间窗需求，建立 RTVRPMTW 问题模型。充分利用ACO 和 GA 的优势， 并采用了 3-opt 搜索、 车场交换及协同机制等策略进行改进，构造了 HACO。 对实例进行仿真表明该算法在收敛速度和寻优结果两方面都优于另外三种算法，而且稳定性较好。 【关键词】多时间窗;实时车辆路径优化;蚁群优化算法;协同机制 Research on real time vehicle routing problem with multiple time
2、 windows LIU Zhi-yong，CAI Yan-guang （School of Automation，Guangdong University of Technology，Guangzhou 510006，China） Abstract：Considering the multiple time windows，establishing real time vehicle routing problem with multiple time windows model.Making full use of the advantages of ant colony optimiza
3、tion and genetic algorithm，3-opt local search，depot exchange and collaborative mechanism were introduced to improved the algorithm s performance，then the hybrid ant colony optimization was constructed.Experiments show that the algorithm is better. Key words：multiple time windows;real time vehicle ro
4、uting problem;ACO;collaborative mechanism 引言 带时间窗的车辆路径优化问题（vehicle routing problem with time windows，VRPTW）属于车辆路径问题（vehicle routing problem，VRP）的范畴，也属于NP-h 问题，近年来，有不少学者1-3对 VRPTW 进行了深入研究，该问题一直是运筹学与组合优化领域的前沿和热点问题， 且在现实生产生活中有着相当广泛的应用，因而研究该问题具有现实意义。目前，国内外对于多时间窗 VRP 的研究文献不少， 但是考虑多时间窗的实时 VRP （real time v
5、ehicle routing problem with multiple time windows，RTVRPMTW）的研究文献还相当有限，本文通过提出的混合蚁群优化算法求解该问题模型。 1.问题描述及数学模型 客户 i（i=1，2，l）的需求量为 gi，客户时间窗的个数， ，客户要求送货的时间窗为，等待费用为 s1，延迟费用为 s2，车场个数为 n（n=1，2，N） ，车辆类型为 h（h=1，2，H） ，车辆载重为 qhgi<qh，每种类型的车辆数量为 Knh，车辆到达 i 的时间为 Ti，车辆在 i 服务的时间为 si，客户 i 与 j 之间欢迎您阅读并下载本文档，本文档来源于互联网
6、，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 的距离为 dij，单位运价为 cs，车辆启用成本为 cnh，行驶时间限制为 Tlimit，车辆从 i 到 j 的行驶时间为 t（i，j） ，车辆的最长行驶时间为 eval（Xs） ，司机工资w，路段 i 与 j 的速度为 vij，车场 n 的路径总数为 mr，路径 r 服务的顾客数为mp，最长驾驶时间为 Tmr，车场的位置为 p（0） ，第 s 个顾客被服务的位置为 p（s） ， 车场 n 中 h 类型的车辆 k 从 i 到 j 的运输成本为。车场编号：l+1， l+2，l+N。 决策变量如下： （1） （2） （3） 目标函数： （4）
7、约束条件： （5） （6） （7） （8） （9） （10） （11） （12） （13） （14） 2.混合蚁群算法求解流程 混合蚁群算法的求解流程框图如图1 所示。 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ 图 1 混合蚁群算法的求解流程框图 3.算例仿真 某企业有两车场，车场 A（40，30） ，两种类型车辆各 3 辆，载重分别为 35和 25，固定成本分别为 8 和 5，运输成本为 1 和 0.8;车场 B（80，45） ，三种类型车辆各 3 辆，载重分别为 35、20 和 25，固定成本分别为 8、4 和 5，运输成本分别为 1、
8、0.6 和 0.8。客户信息如表 1。最早和最晚发车时间分别为 480 和 600个时间单位。司机工资为 10 个单位，里程约束为 150 个单位，车辆最大行驶时间为 210 个时间单位。服务时间为 10 个时间单位，早到和迟到惩罚系数分别为1 和 4。v=50 千米/时。 表 1 客户信息 在 Intel （R） Core?i5 CPU3.0GHz、 内存为 8.0G、 win7 的 PC 机上采用 Matlab R2010b 编程实现。针对 RTVRPMTW 模型，分别采用 GA、TS、ACO 和 HACO进行仿真， 各运行 20 次。 GA 参数设计： 初始化种群 N=20， 最大迭代次
9、数为 800，交叉概率 pc=0.9，变异概率 pm=0.04，采用精英选择策略，算术交叉，均匀变异。TS 参数设计：最大迭代次数 800，禁忌长度为 10，候选解个数为 80 个，保留20个最小候选解。 ACO参数设计： 蚁群规模m=20， 最大迭代次数Nc=800， q0=0.8，Q=100。通过多次实验知当， ，时蚁群优化算法的性能最优。4 种算法求解RTVRPMTW 的结果是：GA 在第 50 代搜索到最好解为 566.38，TS 在第 12 代搜索到最好解 572.55，ACO 在第 60 代搜索到最好解 566.38，而 HACO 在第 13 代搜索到最好解为 566.38， 可以
10、看出本文算法的收敛速度和求解质量优于另外三种算法。 4.结语 本文提出了基于 GA 和 ACO 两种算法的优点及多种改进策略的 HACO，本文提出模型属于小规模模型，研究更大规模模型及包含多种扩展特性（多周期性、服务优先级等）的 VRP 及其求解方法将是下一步研究的方向。 参考文献 1Simchi-Levi D ， Chen X ， Bramel J.The VRP with Time-Window ConstraintsM/The Logic of Logistics.Springer New York，2014： 341-357. 2Cattaruzza D，Absi N，Feillet
11、D，et al.An Iterated Local Search for the Multi Commodity Multi Trip Vehicle Routing Problem with Time WindowsC/ROADEF-15me congrs annuel de la Socit fran?aise de recherche oprationnelle et daide la dcision.2014. 3Ko? ?，Bekta? T，Jabali O，et al.A Hybrid Evolutionary Algorithm for 欢迎您阅读并下载本文档，本文档来源于互联网，如有侵权请联系删除！我们将竭诚为您提供优质的文档！ Heterogeneous Fleet Vehicle Routing Problems with Time WindowsJ.2014. 蔡延光（1963） ，男，湖北咸宁人，博士，广东工业大学自动化学院教授，主要从事组合优化、人工智能、决策支持系统等的研究。
