时间窗混合共存下的车辆路径问题研究.doc

1、时间窗混合共存下的车辆路径问题研究摘要：配送中时常会忽略掉到其配送客户重要程度的不同，而其重要程度不同又导致各自时间窗的软硬区别共存。而现实中的硬时间窗往往没有那么严格，车辆早到达可以提前卸货而无需等待。在着重于配送节点不同软硬时间窗区别混合共存情况下的车辆路径问题研究，基于遗传算法的配送路径优化求解，并通过案例验证遗传算法求解此问题的有效性。 关键词：时间窗；车辆路径问题；遗传算法 Abstract: In distribution，diffidence of customers important degree often be ignored. The diffidence leads

2、to a coexistence of soft time windows and hard time windows. But in reality, hard time windows tend to be not strict, the vehicle can arrive early discharge in advance without waiting. Based on genetic algorithm to solve the vehicle routing problem, a case calculation could prove the effectiveness t

3、o solve this kind of problems by Genetic Algorithm. Key words: time window; vehicle routing problem; genetic algorithm 中图分类号：F407.472 文献标识码：A 文章编号： 1 前言 本文研究的带时间窗的车辆路径问题（Vehicle Routing Problem with Time Window, VRPTW） ，就是在客户时间窗的限制下，安排最优方案达到成本最低。时间窗按其对送达时间要求的严格程度不同，有软时间窗（Soft Time Window, HTW）和硬时间窗（

4、 Hard Time Window, STW）之分。近年来，有关带软时间窗或带硬时间窗的车辆路径问题方面的研究都比较多1-11。但当前，对节点带时间窗软硬不同且同时存在混合情况的车辆路径问题，还少有研究。而这种情况在现实的配送问题中时常出现，而在现实配送中，有硬时间窗要求的顾客往往可以忍受提前达到，但决不可迟到，这就产生软硬时间窗混合共存的配送路径问题。2 问题描述和模型 2.1 问题描述 本文的问题可描述为：车辆从某固定的配送中心出发，向处于不同地理位置的配送服务节点进行配送，假设每个节点只由一辆车进行服务，且可以满足该节点对货物的需求。每个节点带有被服务的时间窗，时间窗类型不同，并且已知。

5、配送中心和节点、每个配送点的需求量、车辆的载重量及最大的行驶时间都为已知。在车辆配送过程中还要受到以下基本约束：车辆不允许超载；带硬时间窗的，必须在配送点的时间窗范围内进行服务，但提前到达可以勉强收货；车辆的运行距离不能超过被允许的最大行驶距离间。 本文研究在所有约束条件都满足的情况下，如何确定配送的路线方案，以使目标成本最小。 2.2 模型假设与建立 根据上述对问题的描述，做如下假设： 1.设配送中心共有个服务节点（比如医药配送中的普通销售网点和医院） ，表示节点的编号，配送中心编号为 0； 2.节点时间窗为；若为软时间窗，惩罚函数为，其中为车到达节点是时间；若为硬时间窗，惩罚函数系数可取一

6、个很大的正数 M 来表达硬时间窗必须满足； 3.每个节点的需求量为，单车的平均最大装载量为；节点之间的距离；配送车辆的节点与之间的平均速度为；单车的单位行驶距离成本为；单车出车成本为；车辆数为；单次最大行驶距离为。 定义变量，为： （1） 则软硬时间窗共存条件下的车辆路径问题目标函数为： （2） 目标函数的三部分分别表示：1.车辆行驶成本；2.车辆未在时间窗要求时间段到达的惩罚值；3.车辆的出车成本。 约束条件： （3）表示每条线路上的节点货物需求总量小于车辆的最大载货量；（4）表示车辆的运行距离不能超过被允许的最大行驶距离；（5）表示每辆车出发到各节点服务后，离开并最终回到起始的配送中心；（

7、6）表示每个配送节点有且只有一辆车通过；（7）表示迟到或早到惩罚系数为一个非负数。 3 算法设计 遗传算法是 20 世纪 60 年代，美国密执安大学 Holland 教授受生物模拟技术启发，创造出的一种基于生物遗传和进化机制的适合于复杂系统计算优化的启发式算法。该算法具有较强的鲁棒性，广泛应用于车辆路径问题的寻优计算中，并在多数情况下能得到比较满意的解。下面设计遗传算法求解本文所给模型。 3.1 编码 采用自然编码方式。首先形成随机排列，如 1，4，6，3，5，2，0 ，其中 0 为配送中心。假设最大可用车辆数为 4 辆，即在形成的排列中随机插入 2 个节点 0，假设变为 1，4，0，6，0，

8、3，5，2，0 ，这样，该染色体的解码后含义为：派发 3 辆车，运行 3 条回路分别为：0140； 060； 03520。 3.2 适应函数 这里以目标函数作为适应函数，个体所对应目标函数值即为此个体的适应值。 3.3 选择操作 取种群各染色体适应值倒数除以倒数之和，作为各染色体被选择的概率，如，第条染色体被选择概率为： ；采用轮盘赌的方式选择染色体复制到新种群，直到新种群规模与父代相同为止。 3.4 交叉、变异操作 本文采用部分映射交叉法，从种群第一个染色体开始，两两成组，对每组染色体，以交叉概率随机一段进行交叉互换，否则，该组染色体不进行交叉操作。 而变异操作则是对种群每一个染色体，以变异

9、概率随机取染色体两个数字并交换位置，形成新染色体，否则，该染色体不进行变异操作。 3.5 计算过程 Step1：各参数初始化，并设置达到最大迭代次数为算法终止条件； Step2：时，随机产生初始群体； Step3：计算种群各个个体的适应值，并选出得到最优的适应值和最优的个体； Step4：根据轮盘赌选择法，复制染色体生成新的种群； Step5：对新的种群进行交叉、变异操作； Step6：采用精英策略，取上一代最优个体替代新一代对应位置染色体； Step7：； Step8：若满足终止条件，转到 step 9，否则转到 step 3； Step9：取种群最优的适应值即为最优成本，对应个体解码后为最

10、优方案。 4 算例分析 C 城市某民营医药物流中心，常年向城区医院及医药销售网点配送药品，配送车辆数未定，车辆的最大载荷为 18，单次的最大行驶距离为300，担任所辖区域内主要的 14 个客户的配送业务，各个节点的间距见表 1，时间窗、惩罚参数见表 2。 表 1 各配送节点的间距（0 为配送中心） 表 2 客户需求量、时间窗及惩罚系数 算法中设置初始群体规模为 40，遗传迭代次数为 1000，节点3，6，10 的硬时间窗迟到惩罚系数 M 取为 1000，交叉概率取 0.6，变异概率取 0.05。在 CPU2.0GHz，内存 2GB 的计算机上，采用遗传算法连续计算 10 次，计算结果见图 1。

11、 图 1 连续 10 次计算结果对比 10 次计算的最优解平均值为 634.31，其中最好解为 628.13，相对偏差 0.76%；耗时平均约 11.57s。从两图中可以看出 10 次计算的结果较接近，而其相对偏差也较小，用时也较少，证明遗传算法求解此类问题比较稳定有效。10 次计算中获得最好解的一次计算种群最优适应值变化曲线如图 2 所示。图中，达到终止迭代次数后，最优适应值为 628.13，最优解为： 06101340114111257038920 。 即最优方案为：配送中心安排 3 辆车，配送线路分别为： 06101340； 01141112570； 038920 。 图 2 连续 10

12、 次计算最好解遗传算法种群最优适应值变化过程 5 结论 本文探讨了一种考虑不同软硬时间窗共存情况下的配送路径的优化问题，建立了软硬时间窗共存条件下的配送路径优化模型，设计了求解该优化模型的遗传算法。数值算例表明本文所设计遗传算法的有效性，为现实中类似的医药配送的成本最小化提供一种可行的、有效的优化方法。 参考文献： 1 Sun Guohua. Research on Open Vehicle Routing Problem with Full load and Soft-Time WindowsJ. Computer Engineering and Applications, 2011, 47

13、(17):13-17. 2 ric Taillard, Philippe Badeau, Michel Gendreau, Franois Guertin, Jean- Yves Potvin. A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time WindowsJ. Transportation Science, 1997, 31:170-186 3 George Ioannou, Manolis Kritikos, Gregory Prastacos. A problem generator-solve

14、r heuristic for vehicle routing with soft time windowsJ. Omega，2003, 31(1): 41-53 4 乔均俭，王爱茹，周静. 带时间窗车辆路径问题的最优解J. 商场现代化，2007， （2）：128-129 5 赵彤，范厚明，王桂琳，张婧瑶，董国松，李佳书. 带时间窗的应急救助物资配送车辆路径优化模型研究J. 物流技术，2010，63-65，68 6 朱树人. 软时间窗配送车辆路线优化算法及应用J. 湖南师范大学自然科学学报，2008，31（4）：58-61 作者简介：史昊（1987-） ，男，汉族，籍贯山东威海，重庆交通大学交通运输学院 2010 级研究生，研究方向：物流优化与管理