1、什么是有时间窗车辆路径问题?
车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的Paolo Toth，Daniele Vigo。THE VEHICLE ROUTING PROBLEM[M]。Society for Instrial and Applied Mathematics philadephia.2002。在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同[2]。Bodin[4]和Solomon[5]分别对VRP及其变形问题和VRPTW问题作了较详细的综述。生产实际中许多问题都可以归结为VRPTW来处理, 如钢铁厂编制热轧带钢轧制计划问题实际上就是一个VRPTW问题。一些服务性行业中也普遍存在这样的问题, 如邮政投递，飞机、火车及公共汽车的调度等。自从Savelsbergh[6]证明了VRPTW是一个NP难问题之后, 对其算法的研究就主要集中到各种启发式算法上。遗传算法、禁忌搜索法和模拟退火法等智能化启发式算法的出现为求解VRPTW问题提供了新的工具。Thangiah[7]和Joe[8]都曾应用遗传算法求解VRPTW问题, 前者的目标是使总的服务成本最小, 而后者的目标有两个, 首先是使用最少的车辆, 其次是在使用最少车辆的前提下使总成本最小[3]。时间窗车辆路径问题的求解方法[2]含时窗限制之车辆途程问题（VRPTW）相对于车辆途程问题（VRP），必须额外考虑到运送时间与时间窗口，其主要的原因来自顾客有服务时间的最后期限和最早开始服务时间的限制。故在此限制条件之下，原本VRP问题除了空间方面的路径（Routing）考虑之外，还必须要加上时间上的排程（Scheling）考虑，同时由于场站也有时间窗的限制，也间接造成路径长度的限制，由此可知VRPTW的总巡行成本不仅包含运送成本，还需要考虑时间成本，以及未在时间窗限制内送达的处罚成本。因此，若要得到一个好的解答，时间和空间（Temporal andSpatial）问题的探讨是非常重要的。由于VRPTW比VRP问题多考虑了一样时窗的因素，因此在解法上较VRP问题更为复杂，而根据Taillard（1997）等人的分类，求解VRPTW的方法可以分为六种，分述如下。1、以分枝界限法求算之精确解法（Exact Algorithm Based on Branch-and-BoundTechniques）：Kolen（1987）利用这种方式可以求得精确解，但是只能解决六至十五个节点的问题，因此求解的范围过小，仅适用于小型问题。2、途程建构启发式算法（Route Construction Heuristics）：在一问题中，以某节点选择原则或是路线安排原则，将需求点一一纳入途程路线的解法。如Soloman（1987）的循序建构法（Sequential Insertion Heuristics）。3、途程改善启发式算法（Route Improvement Heuristics）：先决定一个可行途程，也就是一个起始解，之后对这个起始解一直做改善，直到不能改善为止。而常见的是节线交换法（Edge Exchange Procere），如Lin（1965）所提出的K-Optimal，以及Potvin与Rousseau（1993）提出一考虑旅行方向的交换算法。4、合成启发式算法（Composite Heuristics）：此种解法混合了途程建构启发式算法与途程改善启发式算法，如Russell（1995）所提出的Hybrid Heuristics便是混合了Potvin与Rousseau（1993）所提出的平行插入法，并在之中加入路线改善法的合成启发式算法；Roberto(2000)也提出的属于平行插入法与内部交换改善法的合成启发式解法来求解VRPTW的问题。5、依据最佳化之启发式算法（Optimization-Based Heuristics）：如Koskosidis（1992）等人利用混合整数规划模块，再透过启发式算法，将原始问题分解成指派/分群的子问题的一系列的巡行以及排程问题。6、通用启发式算法（Metaheuristics）：传统区域搜寻方法的最佳解常因起始解的特性或搜寻方法的限制，而只能获得局部最佳解，为了改善此一缺点，近年来在此领域有重大发展，是新一代的启发式解法，包含禁忌法（Tabu Search）、模拟退火法（Simulated Annealing）、遗传算法（Genetic Algorithm）和门坎接受法（Threshold Accepting）等，可以有效解决局部最佳化的困扰。
2、带时间窗的货物配送问题
自从1959年Danting 和Rasmer[2]首次提出了车辆路径问题（Routing Vehicle Problem, VRP）以来，该问题一直为众多的研究者所关注。而带时间窗的车辆路径问题（Vehicle Routing Problems with Time Window , VRPTW）是一般车辆路径问题的扩展,其简单的描述如下：用于服务的若干车辆从站点出发，为处在不同地理位置、具有不同货物需求和不同服务时间窗要求的所有顾客提供服务，然后返回站点，其中为每个顾客仅提供一次服务。其目标是在时间窗内为顾客提供服务时，使车辆的行驶时间和等待时间之和最短。
根据时间约束的严格与否，VRPTW分为两类：软时间窗VRP和硬时间窗VRP。软时间窗VRP要求尽可能在时间窗内到达访问，否则将给予一定的惩罚，即车辆在要求地最早到达时间之前到达时，必须在任务点处等待时损失的成本或是车辆在要求的最迟到达时间之后到达时被处以的罚值；硬时间窗VRP则要求必须在时间窗内到达访问，否则服务被拒绝。本文讨论的是硬时间窗车辆路径问题。
2 数学模型及其检验
2.1、数学模型的建立
根据具体问题需要，本文作以下基本假设：
（1）只有一个站点；
（2）站点和客户点的位置坐标已知；
（3）客户点的需求量已知；
（4）车辆在配送过程中不得超过其额定载质量；
（5）必须满足每个客户的配送需求；
（6）车辆为同种车型，且容量已知；
（7）每个客户必须且只能被访问一次；
（8）每个客户要求的时间窗已知。
数学模型的决策变量和参数定义如下：
I 表示站点和客户的集合，即 ，0表示站点；
J 表示客户集合，即 ；
K 表示车辆集合，即 ；
C 表示车辆的额定载质量；
表示从客户i到客户j的运输成本；
表示客户i的需求量；
为决策变量，车辆k从i到j时取1，否则取0；
为决策变量，车辆k为客户j服务时取1，否则取0；
表示客户i接受服务的最早时间，i＝0时表示车辆从站点出发时间；
表示客户i接受服务的最迟时间，i＝n＋1时表示车辆回到站点的最迟时间；
表示车辆k服务客户i的开始时间，要求尽可能落在区间 内；
表示完成i点任务所需时间；
表示车辆从客户i行驶到客户j的行驶时间；
根据问题描述，建立带时间窗车辆路线问题的数学模型如下：
Min (2-1)
(2-2)
(2-3)
(2-4)
(2-5)
(2-6)
(2-7)
(2-8)
(2-9)
(2-10)
式（2-1）为目标函数，表示不考虑时间约束时经典配送费用（配送总路程）的最小值。式（2-2）表示一个客户只能由一个车辆提供服务；（2-3）、（2-4）和（2-5）表示车辆从站点0出发，服务完所有客户后，最后回到站点n+1；式（2-6）表示若车辆正在从客户i到客户j途中，它不能先于时间 到达客户j ；式（2-7）保证满足每辆车的额定载质量限制；式（2-8）（2-9）为0、1约束；(2-10)为时间窗约束。
2.2 数学模型的检验
本文应用Ling10.0软件对以上数学模型进行检验。数据采用文献【3】同类问题的测试数据，具体如表1和表2所示,其中车辆数为3，各车额定载质量均为8，运行速度为50，计算中假定各客户点间运输成本等于距离。
表1 各客户点及站点之间距离
0 1 2 3 4 5 6 7 8
0 0 40 60 75 90 200 100 160 80
1 40 0 65 40 100 50 75 110 100
2 60 65 0 75 100 100 75 75 75
3 75 40 75 0 100 50 90 90 150
4 90 100 100 100 0 100 75 75 100
5 200 50 100 50 100 0 70 90 75
6 100 75 75 90 75 70 0 70 100
7 160 110 75 90 75 90 70 0 100
8 80 100 75 150 100 75 100 100 0表2 各客户点需求量以及所需服务时间
任务i 1 2 3 4 5 6 7 8
2 1.5 4.5 3 1.5 4 2.5 3
[ ]
[1，4] [4，6] [1，2] [4，7] [3，5.5] [2，5] [5，8] [1.5，4]
Si 1 2 1 3 2 2.5 3 0.8
说明：di为各任务的货运量，[ ]为每项任务开始执行的时间范围，Si为服务时间。
用Lingo计算上述数学模型的结果为：
路线一：0、8、5、7、0；
路线二：0、6、4、0；
路线三：0、3、1、2、0；
目标函数总成本为910，与文献[3]给出的结果一致，表明了本文中数学模型的正确性。
3、基于遗传方法的VRP问题解法
3.1 遗传算法简介[3]
遗传算法是由美国Michigan大学的John Holland教授于20世纪60年代末创建的。它来源于达尔文的进化论和孟德尔、摩根的遗传学理论，通过模拟生物进化的机制来构造人工系统。 遗传算法主要借助于生物进化中“适者生存”的规律，即最适合自然环境的群体往往产生更大的后代群体。以这个循环圈的群体为起点，经过竞争后，一步分群体被淘汰而无法再进入这个循环圈，而另一部分则成为种群。优胜劣汰再这个过程中起着非常重要的作用，因为自然天气的恶劣和天敌的侵害，大自然中很多动物的成活率是非常低的。即使再成活群体中，还要通过竞争产生种群。种群则通过婚配的作用产生新的个体，综合变异的作用，子群成长为新的群体而取代旧的群体，在新的一个循环过程中，新的群体将替代旧的群体而成为循环的开始。
3.2算法描述
step 1: 初始化, 设置种群规模n ,用自然数法对染色体进行编码;
step 2: GenN ∶= 0, 生成初始种群Pop (0) ;
step 3: 对种群中的每一个染色体, 计算适应值，并记录当前最优适应度函数值；
step 4: 若满足算法终止条件, 则停止并输出结果； 否则转step5；
step 5: 据精英选择及轮盘赌选择法, 从Pop (GenN ) 中选择Pop (GenN + 1) , 即复制下一代个体;
step 6: 进行最大保留交叉和交换变异操作, 重组Pop (GenN + 1) ;
step 7: GenN ∶= GenN + 1;转步骤3。
算法的具体描述过程如图1.
是
否
图1 遗传算法流程
3.3 构造染色体、产生初始种群[4]
本文采用客户直接排列的编码方式。用1～N间的自然数表示客户，这些自然数的任意排列就是一个解，按照问题的约束条件，依次将解的每个数（客户）纳入车辆的配送路径中。如12346789，首先，将客户1纳入第一条配送路径中，判断是否满足问题的约束条件，如能够满足，则构成配送路径0-1-0，再将客户2纳入这条配送路径中，再计算是否满足问题的约束条件，如仍能满足，则构成配送路径0-1-2-0，接着再将客户3纳入到这条配送路径中，再计算是否满足约束条件，如不能满足，说明客户3不能由第一条配送路径配送，则重新开始一条新的配送路径0-3-0；一直重复这个过程，直到把每个客户都纳入到配送路径中。
这种编码方式虽然没有表示各条路线分界点的基因位，但这有利于将来的交叉操作，不仅排除了不可行解存在的可能性，而且所占用的计算机存储量也较小。
关于初始种群的选取，一些学者提出了采用启发式算法选择较好的染色体作为初始种群的方法，然而其种子的选取有一定的偏见和缺乏代表性，可能产生早熟而无法求出最优解，为了避免这种缺陷，本文采用随机产生初始解的方法，只有这样才能达到所有状态的遍历，因而最优解在遗传算法的进化中得以生成。
3.4 适应度函数
本文选取适应度函数为fitness（ ）=M-( )，其中M为一个很大的值，M后为目标函数值， 为一条染色体，其中i=1，……,m.
3.5 选择算子的确定
将每代种群n 个染色体按适应度函数值排序,将适应度函数值最大的染色体复制一个直接进入下一代。下一代种群中剩下的n - 1 个染色体用轮盘赌选择法产生。这样,首先可以保证最优个体可以生存到下一代,既给了适应度较大的个体较大的机会进入下一代,又避免了个体间因适应值不同而被选入下一代的机会悬殊。
3.6 交叉概率、变异概率的确定[5]
在遗传算法中, 对其收敛性起决定作用的是交叉和变异算子。在现有的求解VRP 的遗传算法中, 对交叉和变异概率通常的处理办法是: 交叉概率 随机地选择一个较大的值, 通常取0. 5～ 1. 0; 而变异概率 取一个较小的值, 一般为0. 001～ 0. 05。为了避免发散或陷入局部最优点, 并保持种群中“好”的个体, 以及加快优化进程, 本文引入自适应机制, 动态地调整 和 , 即通过对高适应值的解降低 和 的值, 而对低适应值的解提高 和 来实现。具体为
其中, = 0. 5, = 0. 05, = 1, = 0. 1; 为种群中的最大适应值, f ′表示交叉的两个个体中较大的适应值, 为种群的平均适应值, f 是变异个体的适应值。交叉概率随着适应值趋向于而 减少, 当适应值等于 时, 即对具有最大适应值的解, 其 和 为零, 这样, 种群中最好的解就直接复制到下一代(即精英选择)。
3.7 交叉算子、变异算子的确定
本文选用顺序交叉法[3]（Order Crossover，OX），其具体交叉方法如下：
step1:从第一双亲中随机选一个子串；
step2:将子串复制到一个空子串的相应位子，产生一个原始后代；
step3:删去第二双亲中子串已有的客户，得到原始后代需要的其他客户的顺序；
step4:按照这个客户顺序，从左到右将这些客户定位到后代的空缺位置上。
过程说明见图2，同样步骤可用同一对双亲得到另一个后代[7 9 3 4 5 6 1 2 8]. 5 7 4 9 1 3 6 2 8
双亲1
*
*
4 9 1 3
*
*
* 原始后代
1 2 3 4 5 6 7 8 9
双亲2
2 5 4 9 1 3 6 7 8
后代
图2 交叉过程
本文选择基于易位变异[3]中的2－交换变异方法，即：
随机选取个体编码串中的两个基因，然后交换它们的位置，如：
12345678 12375648
3.8 终止规则
事先确定算法的迭代次数能有效控制算法的运行时间和算法的求解精度，因此本文采用事先确定迭代次数的终止规则,即判断迭代的代数是否为要求代数N ,若是,停止进化,选性能最好的染色体所对应的路径集合,作为原VRPTW 问题的优化解输出；若不是，继续执行循环迭代。
4、算例分析
Solomon[6]中给出的56个数据集R1、R2、C1、C2、RC1和RC2是VRPTW问题数值实验的经典数据集。每个数据集的客户数有25、50和100，客户间的距离为欧式距离，并且满足三角不等式。R1和R2的客户位置是随机分布的，C1和C2的客户呈聚集状态，RC1和RC2呈半聚集状态。R1、C1和RC1类数据集具有较短时间窗，因而在每条路线上，允许服务的客户数较小；R2、C2和RC2则具有较长时间窗，每条路线上允许服务的客户数较多。而在实际问题中，客户的分布在多数情况下更接近于R类、RC类数据集所反映的随机和半聚集状态。为了更接近实际情况，本文选用较短时间窗的数据R101中25个客户集的数据来对本文提出的遗传算法进行编程验证，并与文献[1]中的结果进行比较。
表3 算例结果对比
算法 文献[6]的算法 本文的算法 本文的算法
使用的车辆数 8 8 10
运行总距离 617.1 580.352 563.292
表中采用10辆车时最优解的运行路线为：0—7—6—2—0；0—18—15—9—4—1—0；0—14—22—21—0；0—12—23—0；0—3—8—0、0—11—0；0—5—10—0、0—16—0；0—13—0、0—17—0、0—19—0；0—25—0；0—24—0；0—20—0。运行时间为0.482秒。
采用8辆车时最优解的运行路线为：07—11—21—0；0—8—4—1—0；0—17—10—9—2—0；0—13—14—22—0；0—24—19—16—6—0；0—20—18—15—23—0；0—3—12—0；0—5—25—0。运行时间为0.437秒。
经过反复验证，当种群数小于100时，运行结果总是趋向于局部最优的；而当种群数取为150时，便可以跳出局部最优，从而得到全局性的最优解。当迭代代数取为50时，解的平均值为670.4,平均运行时间为0.246秒；当迭代代数取为100时，解的平均值为643.7，平均运行时间为0.532秒；当迭代代数取为200时，解的平均值为636.8，平均运行时间为1.021秒。这说明迭代代数大于100后对于解的优化影响不是很大，但运行时间却大大增加，所以本文迭代代数取为100。经过验证，当种群数为150、迭代代数为100时，相应的选取交叉概率为0.5、变异概率0.02时，可以得到如表3所示的优化解（AMD Athlon(tm)64）。
5、结论
本文试验中随机运行了30次，其中最优解出现的概率为40％，优于文献[1]中的最优解8.7％，而且求解时间较短，这说明本文采用的遗传算法对带硬时间窗车辆路线问题的适应性，这对于该问题的进一步研究具有重要的参考价值。
3、vrptw车辆路径问题中，solomon标准测试数据，带有时间窗，请问车速应该设置为多少？
车速应该为1，具体见网页链接 最后一段话里有提到行驶时间即是距离。