论文部分内容阅读
[摘要] 对带时间窗约束的物流配送车辆路径问题，构造了一种两阶段启发式算法。算法第一阶段采用k-means算法将客户聚类分群，算法第二阶段对每一客户子类采用禁忌搜索算法优化车辆路径。仿真实验结果表明，该算法是有效的。
[关键词] k-均值 禁忌搜索算法 车辆路径问题
车辆路径问题（Vehicle Routing Problem, VRP）已被证明是NP-hard问题，随着客户数量的增加，可选的车辆路径方案数量呈指数级增长。随着生活水平的提高，企业越来越重视客户对货物送货时间的要求，因此必须考虑车辆路径问题达到配送最快且运输成本最小的目标，以满足消费者的需求，研究有时间窗车辆路径问题（Vehicle Routing Problem with Time Windows, VRPTW）具有十分重要的现实意义。
Solomon和Desrosiers等人（1987）最早对带时间窗约束的车辆路径问题进行了研究，Desrochers(1988)进一步对求解带时间窗的车辆路径问题的各种优化方法做了总结概括。谢秉磊、李军研究过有时间窗车辆路径问题，蔡延光、郎茂祥等曾用禁忌搜索算法求解车辆路径问题。本文构造了求解有时间窗车辆路径问题的两阶段启发式算法，根据客户分布情况将距离相近的客户分配在同一辆车中配送，可得到一初始可行解，然后采用禁忌搜索算法优化车辆路径，进一步求得最佳解。
一、问题描述及模型建立
有时间窗的车辆路径问题可描述为：从某物流中心用多台配送车辆向多个客户送货,每个客户的位置和需求量一定,将货物送到的时间窗一定,每台配送车辆的载重量一定,其一次配送的最大行驶距离一定,要求合理安排车辆配送路线和行车时间,使目标函数最优。
设物流配送中心有m辆容量为q的车辆，以物流配送中心的位置作为原点0，现有货物运输任务，以1，2，…n表示，已知任务i的货运量为，且，每辆车从物流中心出发，经过一系列客户点送货，最终回到物流中心。规定每个客户点的任务只能由一辆车完成，求以总费用最小化为目标的车辆行驶路线。
车辆优化模型可表述为：
Z为目标函数使总费用最小。约束(1)是车辆的容量限制；约束(2)每个顾客只有一辆车为其服务；约束(3)和(4)表示两个变量之间的关系；约束(5)和(6)为变量的取值约束。
决策变量表示车辆k是否从需求点（或配送中心）i行驶到点j，若是则为1，否则为0；表示点i的任务是否由车辆k完成，是则为1，否则为0。参数表示为从点i 到点j 的运输成本，可以是距离、费用、时间等，本文含义为距离。表示车辆到达任务点i的时间，表示在之前到达任务点i的单位时间等待成本，表示在之后到达任务点i的单位时间惩罚成本。
二、VRPTW问题的求解算法
考虑到在安排车辆路径的时候总是倾向于就近服务的原则，在求解VRP问题时，可先将客户分群，然后对每个客户群采用禁忌搜索算法求解。这样不仅可让车辆访问的总距离较小，而且使搜索时间缩短，从而优化目标函数。
1.聚类分析
聚类分析的基本思想是研究样品或指标（变量）之间存在程度不同的相似性。根据一批样品的多个观测指标，具体找出一些能够度量样品或指标之间相似程度的统计量，把一些相似程度较大的样品（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样品（或指标）又聚合为另一类，直到把所有的样品（或指标）聚合完毕。
聚类分析中，最基本的方法就是k-均值法。k-均值算法常采用误差平方和准则函数作为聚类准则函数，误差平方和准则函数定义为：
其中第k个聚类可以用集合来表示，假设包含个客户点｛｝，此聚类中心为，其中是属于第k个聚类的客户点，E为k个聚类的误差平方和。
2.禁忌搜索算法
禁忌搜索算法是近年来由局部邻域搜索扩展而来的一种全局逐步寻优算法, 通过模拟人的记忆过程, 达到整体寻优的效果。通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过特赦准则来赦免一些被禁忌的优良状态，进行多样化的有效搜索以最终实现全局优化。
具体实现技术如下：
（1)初始解的构造
本文引入了一种自然数编码的解的表示方法，即0表示车场，其余的自然数来表示各个送货点，这样就可以得到一串自然数编码，这串自然数编码代表了送货的路径。例如0-4-5-2-0-1-3-0，表示第一条路径是从车场出发，到4、5、2送货后返回车场；第二条路径是从车场出发，到1、3送货后返回车场。
由于禁忌搜索算法对初始解有较强的依赖性，好的初始解可使禁忌搜索算法在解空间中搜索到好的解，而较差的初始解则会降低禁忌搜索的收敛速度，因此本文采用了将聚类结果作为禁忌搜索算法的初始解。
（2）邻域的搜索
邻域搜索采用2交换（2-opt）产生，每变换一次，重新根据容量约束分配车场。例如路径0-4-5-2-0-1-3-0，如果选择5和1进行变换，则变换后的路径为：0-4-1-2-0-5-3-0，如果1送货点的货物比较多，根据容量约束条件分配车场后路线最终变为:0-4-1-0-2-5-3-0。所以路径的产生需要根据车辆容量的限制进行调整，同时还需要根据车辆的容量限制调整车辆的运行和配车的数目。
（3）禁忌表的处理
针对当前解，每搜索完一次邻域，都要对邻域解进行禁忌表处理，在当前解的邻域中确定若干路径，按路径总路程从小到大依次排列于一个数组中。若最优候选解对应的目标值优于当前路径的最佳状态，则忽视其禁忌特性，用其替代当前解和最优解，并将这条路径加入禁忌表，同时把禁忌对象的任期都加1；若不存在优于最佳当前路径的解，则在候选解中选择非禁忌的最佳状态为新的当前解。
（4）其他参数设置
本文采用目标函数值作为适配值函数，迭代指定步数为终止准则。
3.算法具体流程
Step1：读入车辆调度问题的原始数据：客户节点数目N、各节点的货运量，输入客户X、Y坐标值。
Step2：计算此问题至少需要的车辆数m，m等于所有客户的需求量之和除以车容量（取整）。
Step3：分群，直到所有客户点被分完为止。
Step4：检查各客户群内总需求量是否超出车容量限制。若是，执行Step5；否则执行Step9。
Step5：将最晚服务的客户剔除，直到符合容量限制。
Step6：检查是否有其他客户群有多余的车容量。若是，执行Step7，否则，执行Step8。
Step7：将剔除的用户加入距离最近且加入后不违反车容量限制的客户群，并执行Step9。
Step8：加派一辆车服务（m=m+1），回到Step3。
Step9：分群完成，得到一串自然数编码，将其作为禁忌搜索算法的初始解。
Step10:令最优解xbest=x，其中x是通过聚类算法得到的初始解。
Step11:构造邻域结构，得到邻域中的最优解y。
Step12:判断目标函数F(y)和F(x)的关系，若F(y) Step13:若F(y) Step14:判断是否满足终止条件，若满足则结束，输出结果；若不满足，重新更新禁忌表并返回step11，重新循环。
三、仿真实例分析
本文采用Solomon提供的标准测试问题进行计算结果验证。因为Solomon算例中C101中的送货点具有较好的聚类特性，所以选择在C101送货点上进行一次聚类算法的实验。
输入客户在坐标平面上所在的位置坐标及客户需求量，分群数以问题中客户需求量之和与单车最大容量的商取整值，得到最佳分群数为10。实验得到分群结果如图所示。具体每次分类包含的客户点，见表1。
C101类点聚类成10个客户群的情形图
表1 分类结果包含的客户点情况
分群后，发现每群客户无时间冲突。利用上述分群结果在每个群内随机产生一串自然数编码，然后在这10个群上进行禁忌搜索。对这10个群进行禁忌搜索时设迭代步数为50，禁忌表长度为5。通过20次随机实验，最后得到实验结果：车辆数为10，总里程828.94。经过实验计算的路线,见表2。
表2 实验结果
四、结语
本文构造的由聚类算法与禁忌搜索算法相结合的算法，是一种两阶段的启发式算法结构。相比随机产生初始解，利用聚类算法产生的初始解能较好的利用送货点分布信息，在此基础上利用禁忌搜索算法能有效地提高搜索效率，同时聚类可将原先规模比较大的VRP问题分解成一个相对小规模的VRP问题，降低了算法的复杂性。但是当客户点地理位置较分散时，如何将客户点的其他约束信息，如时间窗等应用到聚类中来，提前处理某些约束，将是一个值得进一步探讨的问题。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
[关键词] k-均值 禁忌搜索算法 车辆路径问题
车辆路径问题（Vehicle Routing Problem, VRP）已被证明是NP-hard问题，随着客户数量的增加，可选的车辆路径方案数量呈指数级增长。随着生活水平的提高，企业越来越重视客户对货物送货时间的要求，因此必须考虑车辆路径问题达到配送最快且运输成本最小的目标，以满足消费者的需求，研究有时间窗车辆路径问题（Vehicle Routing Problem with Time Windows, VRPTW）具有十分重要的现实意义。
Solomon和Desrosiers等人（1987）最早对带时间窗约束的车辆路径问题进行了研究，Desrochers(1988)进一步对求解带时间窗的车辆路径问题的各种优化方法做了总结概括。谢秉磊、李军研究过有时间窗车辆路径问题，蔡延光、郎茂祥等曾用禁忌搜索算法求解车辆路径问题。本文构造了求解有时间窗车辆路径问题的两阶段启发式算法，根据客户分布情况将距离相近的客户分配在同一辆车中配送，可得到一初始可行解，然后采用禁忌搜索算法优化车辆路径，进一步求得最佳解。
一、问题描述及模型建立
有时间窗的车辆路径问题可描述为：从某物流中心用多台配送车辆向多个客户送货,每个客户的位置和需求量一定,将货物送到的时间窗一定,每台配送车辆的载重量一定,其一次配送的最大行驶距离一定,要求合理安排车辆配送路线和行车时间,使目标函数最优。
设物流配送中心有m辆容量为q的车辆，以物流配送中心的位置作为原点0，现有货物运输任务，以1，2，…n表示，已知任务i的货运量为，且，每辆车从物流中心出发，经过一系列客户点送货，最终回到物流中心。规定每个客户点的任务只能由一辆车完成，求以总费用最小化为目标的车辆行驶路线。
车辆优化模型可表述为：
Z为目标函数使总费用最小。约束(1)是车辆的容量限制；约束(2)每个顾客只有一辆车为其服务；约束(3)和(4)表示两个变量之间的关系；约束(5)和(6)为变量的取值约束。
决策变量表示车辆k是否从需求点（或配送中心）i行驶到点j，若是则为1，否则为0；表示点i的任务是否由车辆k完成，是则为1，否则为0。参数表示为从点i 到点j 的运输成本，可以是距离、费用、时间等，本文含义为距离。表示车辆到达任务点i的时间，表示在之前到达任务点i的单位时间等待成本，表示在之后到达任务点i的单位时间惩罚成本。
二、VRPTW问题的求解算法
考虑到在安排车辆路径的时候总是倾向于就近服务的原则，在求解VRP问题时，可先将客户分群，然后对每个客户群采用禁忌搜索算法求解。这样不仅可让车辆访问的总距离较小，而且使搜索时间缩短，从而优化目标函数。
1.聚类分析
聚类分析的基本思想是研究样品或指标（变量）之间存在程度不同的相似性。根据一批样品的多个观测指标，具体找出一些能够度量样品或指标之间相似程度的统计量，把一些相似程度较大的样品（或指标）聚合为一类，把另外一些彼此之间相似程度较大的样品（或指标）又聚合为另一类，直到把所有的样品（或指标）聚合完毕。
聚类分析中，最基本的方法就是k-均值法。k-均值算法常采用误差平方和准则函数作为聚类准则函数，误差平方和准则函数定义为：
其中第k个聚类可以用集合来表示，假设包含个客户点｛｝，此聚类中心为，其中是属于第k个聚类的客户点，E为k个聚类的误差平方和。
2.禁忌搜索算法
禁忌搜索算法是近年来由局部邻域搜索扩展而来的一种全局逐步寻优算法, 通过模拟人的记忆过程, 达到整体寻优的效果。通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过特赦准则来赦免一些被禁忌的优良状态，进行多样化的有效搜索以最终实现全局优化。
具体实现技术如下：
（1)初始解的构造
本文引入了一种自然数编码的解的表示方法，即0表示车场，其余的自然数来表示各个送货点，这样就可以得到一串自然数编码，这串自然数编码代表了送货的路径。例如0-4-5-2-0-1-3-0，表示第一条路径是从车场出发，到4、5、2送货后返回车场；第二条路径是从车场出发，到1、3送货后返回车场。
由于禁忌搜索算法对初始解有较强的依赖性，好的初始解可使禁忌搜索算法在解空间中搜索到好的解，而较差的初始解则会降低禁忌搜索的收敛速度，因此本文采用了将聚类结果作为禁忌搜索算法的初始解。
（2）邻域的搜索
邻域搜索采用2交换（2-opt）产生，每变换一次，重新根据容量约束分配车场。例如路径0-4-5-2-0-1-3-0，如果选择5和1进行变换，则变换后的路径为：0-4-1-2-0-5-3-0，如果1送货点的货物比较多，根据容量约束条件分配车场后路线最终变为:0-4-1-0-2-5-3-0。所以路径的产生需要根据车辆容量的限制进行调整，同时还需要根据车辆的容量限制调整车辆的运行和配车的数目。
（3）禁忌表的处理
针对当前解，每搜索完一次邻域，都要对邻域解进行禁忌表处理，在当前解的邻域中确定若干路径，按路径总路程从小到大依次排列于一个数组中。若最优候选解对应的目标值优于当前路径的最佳状态，则忽视其禁忌特性，用其替代当前解和最优解，并将这条路径加入禁忌表，同时把禁忌对象的任期都加1；若不存在优于最佳当前路径的解，则在候选解中选择非禁忌的最佳状态为新的当前解。
（4）其他参数设置
本文采用目标函数值作为适配值函数，迭代指定步数为终止准则。
3.算法具体流程
Step1：读入车辆调度问题的原始数据：客户节点数目N、各节点的货运量，输入客户X、Y坐标值。
Step2：计算此问题至少需要的车辆数m，m等于所有客户的需求量之和除以车容量（取整）。
Step3：分群，直到所有客户点被分完为止。
Step4：检查各客户群内总需求量是否超出车容量限制。若是，执行Step5；否则执行Step9。
Step5：将最晚服务的客户剔除，直到符合容量限制。
Step6：检查是否有其他客户群有多余的车容量。若是，执行Step7，否则，执行Step8。
Step7：将剔除的用户加入距离最近且加入后不违反车容量限制的客户群，并执行Step9。
Step8：加派一辆车服务（m=m+1），回到Step3。
Step9：分群完成，得到一串自然数编码，将其作为禁忌搜索算法的初始解。
Step10:令最优解xbest=x，其中x是通过聚类算法得到的初始解。
Step11:构造邻域结构，得到邻域中的最优解y。
Step12:判断目标函数F(y)和F(x)的关系，若F(y)
三、仿真实例分析
本文采用Solomon提供的标准测试问题进行计算结果验证。因为Solomon算例中C101中的送货点具有较好的聚类特性，所以选择在C101送货点上进行一次聚类算法的实验。
输入客户在坐标平面上所在的位置坐标及客户需求量，分群数以问题中客户需求量之和与单车最大容量的商取整值，得到最佳分群数为10。实验得到分群结果如图所示。具体每次分类包含的客户点，见表1。
C101类点聚类成10个客户群的情形图
表1 分类结果包含的客户点情况
分群后，发现每群客户无时间冲突。利用上述分群结果在每个群内随机产生一串自然数编码，然后在这10个群上进行禁忌搜索。对这10个群进行禁忌搜索时设迭代步数为50，禁忌表长度为5。通过20次随机实验，最后得到实验结果：车辆数为10，总里程828.94。经过实验计算的路线,见表2。
表2 实验结果
四、结语
本文构造的由聚类算法与禁忌搜索算法相结合的算法，是一种两阶段的启发式算法结构。相比随机产生初始解，利用聚类算法产生的初始解能较好的利用送货点分布信息，在此基础上利用禁忌搜索算法能有效地提高搜索效率，同时聚类可将原先规模比较大的VRP问题分解成一个相对小规模的VRP问题，降低了算法的复杂性。但是当客户点地理位置较分散时，如何将客户点的其他约束信息，如时间窗等应用到聚类中来，提前处理某些约束，将是一个值得进一步探讨的问题。
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。