最新【精品】范文 参考文献 专业论文
时间窗混合共存下的车辆路径问题研究
时间窗混合共存下的车辆路径问题研究
摘要：配送中时常会忽略掉到其配送客户重要程度的不同，而其重要程度不同又导致各自时间窗的软硬区别共存。而现实中的硬时间窗往往没有那么严格，车辆早到达可以提前卸货而无需等待。在着重于配送节点不同软硬时间窗区别混合共存情况下的车辆路径问题研究，基于遗传算法的配送路径优化求解，并通过案例验证遗传算法求解此问题的有效性。
关键词：时间窗；车辆路径问题；遗传算法
Abstract: In distribution，diffidence of customers important degree often be ignored. The diffidence leads 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 to 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）和硬时间窗（Hard Time Window, STW）之分。近年来，有关带软时间窗或带硬时间窗的车辆路径问题方面的研究都比较多[1-11]。但当前，对节点带时间窗软硬不同且同
最新【精品】范文 参考文献 专业论文
时存在混合情况的车辆路径问题，还少有研究。而这种情况在现实的配送问题中时常出现，而在现实配送中，有硬时间窗要求的顾客往往可以忍受提前达到，但决不可迟到，这就产生软硬时间窗混合共存的配送路径问题。 2 问题描述和模型 2.1问题描述
本文的问题可描述为：车辆从某固定的配送中心出发，向处于不同地理位置的配送服务节点进行配送，假设每个节点只由一辆车进行服务，且可以满足该节点对货物的需求。每个节点带有被服务的时间窗，时间窗类型不同，并且已知。配送中心和节点、每个配送点的需求量、车辆的载重量及最大的行驶时间都为已知。在车辆配送过程中还要受到以下基本约束：①车辆不允许超载；②带硬时间窗的，必须在配送点的时间窗范围内进行服务，但提前到达可以勉强收货；③车辆的运行距离不能超过被允许的最大行驶距离间。
本文研究在所有约束条件都满足的情况下，如何确定配送的路线方案，以使目标成本最小。 2.2模型假设与建立
根据上述对问题的描述，做如下假设：
1.设配送中心共有个服务节点（比如医药配送中的普通销售网点和医院），表示节点的编号，配送中心编号为0；
2.节点时间窗为；若为软时间窗，惩罚函数为，其中为车到达节点是时间；若为硬时间窗，惩罚函数系数可取一个很大的正数M来表达硬时间窗必须满足；
3.每个节点的需求量为，单车的平均最大装载量为；节点之间的距离；配送车辆的节点与之间的平均速度为；单车的单位行驶距离成本为；单车出车成本为；车辆数为；单次最大行驶距离为。 定义变量，为： （1）
则软硬时间窗共存条件下的车辆路径问题目标函数为： （2）
目标函数的三部分分别表示：1.车辆行驶成本；2.车辆未在时间
最新【精品】范文 参考文献 专业论文
窗要求时间段到达的惩罚值；3.车辆的出车成本。 约束条件：
（3）表示每条线路上的节点货物需求总量小于车辆的最大载货量；（4）表示车辆的运行距离不能超过被允许的最大行驶距离；（5）表示每辆车出发到各节点服务后，离开并最终回到起始的配送中心；（6）表示每个配送节点有且只有一辆车通过；（7）表示迟到或早到惩罚系数为一个非负数。 3 算法设计
遗传算法是20世纪60年代，美国密执安大学Holland教授受生物模拟技术启发，创造出的一种基于生物遗传和进化机制的适合于复杂系统计算优化的启发式算法。该算法具有较强的鲁棒性，广泛应用于车辆路径问题的寻优计算中，并在多数情况下能得到比较满意的解。下面设计遗传算法求解本文所给模型。 3.1编码
采用自然编码方式。首先形成随机排列，如[ 1，4，6，3，5，2，0 ]，其中0为配送中心。假设最大可用车辆数为4辆，即在形成的排列中随机插入2个节点0，假设变为[ 1，4，0，6，0，3，5，2，0 ]，这样，该染色体的解码后含义为：派发3辆车，运行3条回路分别为：0→1→4→0； 0→6→0； 0→3→5→2→0。 3.2适应函数
这里以目标函数作为适应函数，个体所对应目标函数值即为此个体的适应值。 3.3选择操作
取种群各染色体适应值倒数除以倒数之和，作为各染色体被选择的概率，如，第条染色体被选择概率为： ；采用轮盘赌的方式选择染色体复制到新种群，直到新种群规模与父代相同为止。 3.4交叉、变异操作
本文采用部分映射交叉法，从种群第一个染色体开始，两两成组，对每组染色体，以交叉概率随机一段进行交叉互换，否则，该组染色