摘 要：为了应对于当前物流业急速的膨胀发展，深入分析物流配送车辆路径问题，建立了带有送货时间窗的物流配送车辆路径问题的整数规划模型。采用遗传算法对该模型进行求解，得到了最优物流配送车辆路径方案。通过对实例进行计算分析，表明该模型对于解决有时间窗要求的物流配送车辆问题有一定的适用性，该求解方法计算效率高，能够得到较优的带有送货时间窗的物流配送车辆路径。 

　　关键词：车辆路径问题；时间窗；整数规划；遗传算法 

　　Abstract： According to the rapid development of the current logistics industry， deep analysis logistics distribution vehicle routing problem， set up a integer programming model for the vehicle routing problem with time windows. And using genetic algorithm to solve the problem， find a initial optimal distribution scheme. Through the calculation and analysis for the instance， shows that the model for solving logistics distribution vehicle problem with time windows has certain applicability， the method is of high calculation efficiency， it can get better vehicle routing for vehicle routing problem with time windows. 

　　Key words： vehicle routing problem； time windows； integer programming； genetic algorithm 

　　引 言 

　　物流配送管理的核心问题就是配送车辆路径问题，而带有时间窗的配送车辆路径问题是由此演化而来的。此类问题要求车辆必须在用户规定的时间窗内对客户进行服务，每个顾客仅被服务一次，如果不能在用户规定的时间窗内完成服务则引入适当的延误惩罚。问题具有极强的现实意义，如银行运钞车调度问题、接送学生校车问题、冷鲜蔬菜海鲜配送问题[1]等，已经在配送问题的研究领域引起了很大的关注度。郭建红[2]建立了带时间窗的动态车辆路径优化模型，提出了采用两阶段法求解策略和改进型遗传算法。张炯，郎茂祥[3]建立了该问题的基于直观描述的数学模型，通过设计新的解的表示方法构造了求解该问题的禁忌搜索算法。对于带有时间窗的配送车辆路径问题采用节约算法[4-5]进行求解，混合算法[8]进行求解，论文[6-7]对此问题采用改进的遗传算法求解。 

　　为了解决带有送货时间窗的配送车辆路径问题，本文建立了该问题的整数规划模型，并用遗传算法对模型进行求解，对实例进行计算得到最优路径配送方案。 

　　1 带有送货时间窗的物流配送车辆路径模型 

　　约束（2）、（3）表示每个用户只被一辆车服务一次，约束（4）表示车辆驶入用户i，必定会驶出用户i，约束（5）表示载重量约束，分配给k车辆的载重量不能超过车辆载重量Q，约束（6）为用户节点时间窗约束，约束（7）为惩罚函数。 

　　2 遗传算法对模型求解 

　　遗传算法是模拟生物进化规律基于适者生存的一种自适应全局优化概率搜索算法。遗传算法构造一个适应度函数对种群进行不断的选择、交叉、变异等操作，最终获得最优解。利用该算法可以较好地解决VRP问题。 

　　2.1 编码。遗传算法的编码都是可理解为解的代码表现形式，VRPTW问题的编码可以采用自然编码的方法，直接产生一组不重复的自然数的排列，该排列构成了问题的一个解，并且对应一种配送方案。根据约束可按顺序依次划分各辆车的配送路径。 

　　2.2 适应度函数。适应度函数是评价每个染色体优劣的函数，是获得最优染色体的基本依据，一般与目标函数有密切的联系，一般目标函数为Zx，设计的适应度函数为： 

　　2.3 遗传操作。评价函数是遗传过程中优胜劣汰的基本依据，选择优良的染色体以较大的概率进入种群，反之劣质的染色体被选入种群的概率较小。采用轮盘赌选择操作，评价函数越大，在轮盘中所占比例越大，该染色体选入种群的概率也越大。其具体选中概率为： 

　　2.4 交叉规则。交叉是种群中的个体为父代，依照一定的规则互相交换特定位置的基因信息，从而产生继承父代大部分信息又不同于父代的子代染色体，这里具体采用双点交叉操作，在个体编码串中随机设置两个交叉点，然后再进行部分基因交换。 

　　2.5 变异规则。采用倒位变异操作，是指随机选定连续排列中的一部分客户，将这部分客户的排列进行倒置。假设个体为123|4567|8，选中4567部分，进行倒位操作，则通过倒位变异操作后个体就变成了123|7654|8。