基于遗传算法的带时间窗车辆路径问题模型

苏扬

摘 要：通过引入惩罚函数，建立适应度函数的带时间窗车辆路径问题的遗传算法模型，确认先后级与编码、得到原始集体、确定终止准则，得出带时间窗车辆路经问题最优解。结果表明：遗传算法因为提升了检索速度，并通过不断的轮换、穿插、变形获取最佳适应度，不断完善初始解，使得在解决带时间窗车辆路径问题取得了很好的成效。

关键词：遗传算法；带时间窗；车辆路径问题

中图分类号：TB

文献标识码：A

doi：10.19311/j.cnki.1672-3198.2017.03.096

0 引言

近些年随着现代物流业的崛起，交通运输方式、传统批发模式和仓储正在向现代物流方向转变，特别是不同配送模式的应用、有效控制运输时间和成本逐渐成为城市配送车辆路径问题的一个重要目标。车辆路径问题一直是车辆调度研究的重要方向，也是车辆路调度研究的重大难题之一，一直是国内外学术界和工程界关注的重要研究课题。文献[1]第一次提出车辆路径问题集分割，考虑到可行解集，基于先前的研究构建了最简单的车辆路径问题模型。文献[2]提出动态规划方法用于解决车辆路径问题的车辆数量的固定，通过递归方法来解决。文献[3]提出修改搜寻启发式算法中可以用于TSP的最近的距离搜索，构建相关评估函数，然后寻求出了一个启发式算法用来求解带时间窗的车辆路径问题。

但上述研究中带时间窗的车辆路径问题尚未获得完全解决。因此为了达到最低总成本费用车辆得遴派，设计货运工具、时间、线路的组合，确保每辆车服务的对象和运输路线，以实现成本的最小化，并且使整个车辆行驶路程最合理，本文通过实际案例证明多目标遗传算法来处理车辆路径优化问题的有效性。结果表明：通过实际案例通过设计基于遗传算法的程序可求解出带有时间窗车辆路径的最优解。

1 带时间窗车辆路径问题概述

1.1 概述

带时间窗的车辆路由问题从一般车辆路由问题演变而来，它是对一般车辆路由问题的进一步扩展，在客户指定的时间范围内分配货物的一种车辆路径问题。基于包含在一般车辆路径问题中的约束条件，每个客户又增加时间窗口约束的条件。一些具有时间窗的车辆路线优化问题允许车辆在时间窗服务时间之前或之后到达客户时间点，但必须接受某些惩罚。具有时间窗的车辆路线问题有两个目的：一个是最小化车辆行进的距离；二是尽量减少客户处罚现象的发生。

1.2 带时间窗车辆路径问题解决思路

依据本文基于车辆路径问题相关理论知识建立了带时间窗的车辆路径优化模型，通过遗传算法模型来求出带时间窗车辆路径问题案例的最优解。

2 遗传算法模型的建立

2.1 遗传算法概述

遗传算法是基于生物优胜劣汰和无规律挑选的全局搜索算法，其通过挑选，交织，突变等遗传算子来模仿生物的基本演化进程，适应度函数用于表示个体问题的解决方案的质量。遗传算法提供了一个解决复杂的系统优化问题的一般框架，这不依赖于问题的特定领域。

2.2 构建带时间窗的车辆路径问题遗传算法模型

基于上述，本文将建立一种改进的车辆路线优化模型，在传统车辆配送成本最小化为目的，考虑到客户的交货时间得要求，使车辆达成最短的等待时间。目标A表示车辆操作的最小总成本，目标B表示车辆操作等待延迟的最小。

在模型中，至少需要[Σm_i/Q]车辆来达成目标。从模型中我们可以知道，上述公式建立了一种多个选择和多个约束的改进模板。客户可以了解时间满意度，使接收场所在客户心中形成良好的效果，从而达到长期的合作效果，从而为接收区带来长期利益，而不仅仅是短期利益。

2.3 模型的程序设计

本文的设计，使用MATLAB進行设计。由于MATLAB最小的数据结构是一个具有不受限大小的矩阵点，并且体系中列举了大量的处理矩阵点函数，因此，应用MATLAB语言编程遗传算法解决带时间窗的车辆路径问题，人口可以看作是一个矩阵处理，也有助于对计算问题的整体考虑和描述。

3 案例介绍

某企业有1个始发地和8个收货点，每个收货点的需求量为mi（吨），配送时间为si（时间），车辆运输的时间点限定在ei，li如表1。配货点有五辆相同的运货车，车辆可承担的运货量均为6吨，车辆运行时速为40千米。

在该示例中，车辆的负载容量是均匀的，均为8t，即mi=8。由于要使用的车辆的数量M是未知的，因此有必要估计M以布置路线。在这种情况下，参与运输的车辆的数量可以由用户选择，或者所需的车辆的数量可以从相关文献中的公式确定：

实际操作中受制约束条件增加，装货卸货步骤越繁琐，η值越小，实际应用中，人机对话可以用来确定η的值，此处定义η值为0.85。

据此，可计算N=[（2+1.5+4.5+3+1.5+4+2.5+3）/（0.85×6）]+1=4，k=1，2，3，4。

初始种群数m=3，需求点n=8，初始种群S=50，进化代100，种群数9，随机概率0.9和骤变概率0.04，经过100次的运行计算，结果如表2。

所有路径都满足时间窗口和车辆容量的约束。此时，适应度函数f（A，B）是通过权重系数法变换的无量纲函数，表2中的数据代入公式：

4 结论

使用遗传算法后，路径长度，负载，等待时间，延迟时间都得到了改进。一般来说，为所有客户提供服务所需的车辆数量越少，解决方案的性能越好。对于为客户服务的相同数量的车辆，总行驶距离，总等待时间和总延迟时间较少，解决方案性能越高。可以看出，遗传算法已经获得了良好的结果，因为该算法通过自然数不断更新，重新择优，交叉，突变和最佳拟合的选择来提高搜索效率并优化初始解。

在本章中，给出了案例的简要介绍和分析。该模型应用于情况并通过遗传算法求解。这种情况的最优解是通过用MATLAB软件编程并通过程序运行获得的，遗传算法解决车辆路由问题与时间窗的优点。

参考文献

[1]Balinski M L， Quandt R E. On an integer program for a delivery problem[J]. Operations Research， 1964， 12（2）： 300-304.

[2]Eilon S， Watson-Gandy C D T， Christofides N. Distribution management[M]. London： Griffin， 1971.

[3]李大卫，王莉.一个求解带有时间窗口约束的车辆路径问题的启发式算法[J].系统工程，2008，16（4）：20-24.

[4]周生伟，蒋同海，张荣辉.改进遗传算法求解VRP问题[J].计算机仿真，2013，30（12）：140-143.

[5]蒋波.基于遗传算法的带时间窗车辆路径优化问题研究[D].北京：北京交通大学，2010.

[6]Calvete H I， Galé C， Oliveros M J， et al. A goal programming approach to vehicle routing problems with soft time windows[J]. European Journal of Operational Research， 2007， 177（3）： 1720-1733.

[7]改进遗传算法下的车辆路径问题研究[J].电子测试，2016，（2）：56-57.

[8]蔡菂迪.改进遗传算法在车辆路径问题中的研究应用[D].哈尔滨：哈尔滨工程大学，2013.