多时间窗车辆路径问题可以表示成整数线性规划模型，对于小规模的问题，可以直接利用求解整数线性规划问题的软件（如Lingo等）编程求解，得到问题的精确最优解。

对于大规模的问题，本节将针对多时间窗车辆路径问题的特点，设计求解该问题的遗传算法。遗传算法描述如下：

1.编码方法

本节采用自然数编码方法表示解的结构，用0表示配送中心，1～10表示10个客戶，如（025803719406100）表示用三辆车完成配送任务，其中第一辆车的配送路径为0→2→5→8→0；第2辆车的配送路径为0→3→7→1→9→4→0；第3辆车的配送路径为0→6→10→0。为了计算方便，本节把配送中心0去掉，只用客戶编号序列表示解，如上面的解可以表示成（25837194610）。

2.解码方法

由于在编码过程中省略了配送中心，对于一个给定的编码，为了使之对应可行解，我们采用安排尽可能少的配送车辆依次为序列中的客戶提供服务的思想进行解码。如对于编码（25837194610），首先，安排第一辆车从配送中心0出发，到序列中的第一个客戶2处为其提供服务，服务完后再综合考虑车辆容量限制、行驶总路程限制以及序列中第二个客戶5的时间窗限制等条件，决定是否直接到客戶5处提供服务。假若条件允许，则到客戶5处为其提供服务，服务完再分析决定是否直接到第三个客戶8处提供服务，依次类推，假若不能为客戶8提供服务，则该辆车直接由客戶5处返回配送中心，形成一个配送回路0→2→5→0，接下来，安排第二辆车从配送中心0出发，直接到客戶8处为其服务，服务完再分析是否有能力到后续客戶3处为其服务，…，依次类推，直到所有的客戶都被服务为止，这时恰好将客戶序列拆分成了若干个满足约束条件的配送回路，对应一个可行解。在解码过程中应该使每辆车在满足各种约束条件的前提下为尽可能多的客戶提供服务。

注：为了使任何一个个体解码后都能对应可行解，本节假设从配送中心派一辆车单独为某一个客戶提供服务，都可以在该客戶的第一个时间窗内到达并完成服务。在实际中，假若从配送中心出发的车辆直接到某个客戶处服务，不能在该客戶的第一个时间窗内完成服务，则说明该客戶的第一个时间窗不可用，可以删掉该时间窗。因此这种假设是有意义的。

3.初始种群

设{1，2，…，n}为n个客戶的序号，根据设定的种群规模M，随机产生M个1，2，…，n的全排列，形成初始种群。

4.适应度函数

对于种群中的每个个体x_i（i=1，2，，N），首先，根据解码规则进行解码，得到一个可行解，然后，根据车辆路径问题的目标函数计算公式，求出种群中每个个体对应的总成本z（x_i）。紧接着，选用一个合适的数值（如最大目标函数值的两倍即2z_max）减去每个个体对应的目标函数值，得到f（x_i）（即f（x_i）=2z_max-z（x_i）），再根据下列公式计算每个个体的适应度函数值

5.选择

本节采用轮盘赌法进行个体选择，优先选择适用度函数值较大的个体进入下一代。同时，引入了最佳保留方法，以保证遗传算法终止时得到的最后结果是历代出现过的适应度函数值最大的个体。

6.交叉(www.daowen.com)

为了保持个体的优良性，避免大量劣质个体的产生，本节采用部分匹配交叉法。如：

在父代中随机生成两个交叉点，如上面例子中划线的位置。交换两个父代个体中交叉点之间的基因序列，并形成交叉映射关系，再按照交叉映射关系对其他位点的基因进行变换，得到两个新个体。上面的两个父代对于选定的交叉点可以形成如下交叉映射关系：4-5、8-7、2-10、11-3。按照这样的映射关系，交叉后得到两个新个体：

新个体1 11 6 9 5 7 10 3 4 8 2

新个体2 7 3 6 4 8 2 11 10 9 5

本节不设置交叉率参数，而是在每代种群中，优先在不同的个体中进行交叉，以便扩大种群的多样性。具体操作方法是：首先对种群里的所有个体进行随机排序（其中相同个体排在一起），然后对所有的i=1，2，…，，判断序列中的第i个和第n-i个个体是否相同，如果不相同，则进行交叉，如果相同则不交叉。

7.变异

为了避免产生不可行解、避免编码的重复，我们采用逆转变异方法，在选定的个体中随机产生两个逆转点，把两个逆转点之间的基因序列逆转，得到新的个体。如在下面变异前的个体中选择两个逆转位点，用“|”加以标注，然后把两个逆转点之间的基因序列6-4-8-2-11逆转，得到变异后的新个体。

变异前：7 3|6 4 8 2 11|10 9 5

变异后：7 3|11 4 8 2 6|10 9 5

本节不设置变异率参数，而是按照下列规则对交叉后的种群进行分析，决定是否对该种群的部分个体进行变异操作：如果交叉后种群整体质量（可以用种群适用度平均值表示）优于交叉前（上代）的种群，则不进行变异操作，直接进入下一代。如果交叉后种群整体质量低于交叉前（上代）种群，则按顺序对适应度值没有超过交叉前种群适应度平均值的个体进行变异，若对某个个体进行变异后种群整体质量优于交叉前种群整体质量，则对该个体执行变异操作后直接进入下一代；若对某个体变异若干次（本文设置次数为10）后其适应度值还是低于交叉前（上代）种群适应度的平均值，说明该个体不好，则淘汰该个体，并用交叉前（上代）的最优个体替换该个体；若替换后种群总体质量还是不如交叉前（上一代），则对下一个适应度值低于交叉前（上代）种群适用度平均值的个体再进行变异，依次类推，直到变异后种群整体质量优于交叉前（上代）的种群，进入下一代。

8.终止规则

本节采用一定的进化代数N作为终止规则，即当进化代数达到N时，终止计算，并把历代种群中出现的适应度最大的个体作为问题的最优解输出。