摘要：本文建立了带硬时间窗车辆路线问题的数学模型，并应用lingo软件检验了其正确性。设计了用遗传算法求解该数学模型的算法思路，即采用自然数编码的方法使得交叉和变异操作得以更加简便的进行；对于初始种群的选取采用随机构造初始解的方法，使解具有遍历性，以避免“早熟”现象的发生。对具有Solomon的测试数据进行仿真测算，所得结果表明与文献^[1]中的结果相比，本文提出的算法求解速度较快、解的质量较高，证明遗传算法解此类问题更具有效性。

关键字：车辆路径问题，硬时间窗，遗传算法

1 引言

自从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）每个客户要求的时间窗已知。

数学模型的决策变量和参数定义如下：