基于客户分类时间窗车辆路径问题的多种群遗传算法

来源:用户上传      作者:

　　[摘要] 本文从顾客差异化的角度出发，利用聚类分析对客户分类，提出了基于客户分类时间窗约束的车辆配送路径数学模型，该模型克服了传统时间窗车辆配送模型对各个客户不加区分的不合理性。根据此模型，本文设计了多种群并行遗传算法进行求解。实验结果表明，该算法相对于标准遗传算法，有效地克服容易早熟收敛的缺点，其结果更加接近最优解。
　　[关键词] 客户分类 时间窗 车辆路径问题 多种群并行遗传算法
　　
　　一、引言
　　
　　车辆路径问题（VRP）是1959年由Dantzig GB等首次提出，它是个NP难问题，只有当客户和路段较少时，才能求得精确解。启发式算法成了求解该问题的重要方向，国内外学者已经提出了多种求解该问题的启发式算法，如禁忌搜索算法、节约算法、蚁群算法、模拟退火算法、神经网络算法以及混合启发式算法。但是这些算法都只能求出该问题的某一特殊类型或规模较小时的近似最优解或最优解。由于VRP问题的特殊性，利用遗传算法的搜索能力解决此类问题是很自然的想法。
　　可是传统的标准遗传算法有两个严重的缺点：容易早熟收敛以及在进化后期搜索效率较低。为此，本文提出一种改进的遗传算法――多种群并行遗传算法。在大多数情况下，相比较于单种群遗传算法，多种群遗传算法得以实现多种群的协同进化，具有更好的全局搜索能力，有效地避免了早熟收敛。
　　本文从顾客差异化的角度出发，利用聚类分析对客户进行分类，研究基于客户分类的时间窗约束的车辆配送路径问题，根据其特点，构造了求解该问题的数学模型，该模型克服了传统时间窗车辆配送模型对各个客户不加区分，进行同等处理的不合理性，并使用多种群的并行遗传算法进行计算。通过实验计算，证明了该算法的良好寻优性能。
　　
　　二、基于客户分类的带时间窗VRP问题的数学模型
　　
　　有时间窗的车辆路径问题描述为:一个配送中心，拥有一定数量容量为q的车辆，负责对N个客户进行货物配送工作，客户i的货物需求为gi，且gi

　　根据问题的特点，本文在利用多种群并行遗传算法求解该问题时，算法参数设定如下:群体规模m=20;个体基因串长度为l=10;最大进化代数gmax=100;子种群数为nsub=10，每隔20代相邻的子种群中最适应的20%的个体进行交换；交叉概率pc=0.8；变异概率pm=0.03。
　　根据给出的例子，用Matlab编写程序来实现以上的遗传算法，我们进行了10次求解，计算结果如表2所示。10次费用的平均值为157，其中第3次和第6次的计算结果最好，满意解为6-7-4-9-1-5-3-10-8-2和1-5-3-9-6-7-4-10-2-8，费用为153，对应的车辆行驶路径均为0-6-7-4-0，0-1-5-3-0，0-8-2-0。将其结果与标准遗传算法做比较，可以发现多种群改进遗传算法可以得到较好的计算结果。
　　
　　五、结束语
　　
　　综上所述，本文对传统的带时间窗约束的车辆配送路径问题进行了改进，建立了基于客户分类的带时间窗约束的车辆配送路径模型，该模型相对于传统模型而言，可以更好地反映客户之间的差别，并且提高了车辆配送的灵活性。另外根据该问题的特点，我们应用多种群并行遗传算法进行求解。计算结果表明，该算法相比较标准遗传算法，搜索能力得到加强，收敛性也提高了，能够得到更好的结果。
　　
　　参考文献：
　　[1]Dantzig G B,Ramser J H. The Truck Dispatching Problem[J].Management Science,1959,10(6):80-91.
　　[2]陈湘州杨勇王俊年:一种改进的自然数编码遗传算法在非满载时间窗车辆优化调度问题中的应用[J].长沙电力学院学报,2004,19(2):57
　　[3]王 薇吴敏等：基于多种群并行遗传算法的原料库存的优化[J].控制工程,2003,10(1):33
　　[4]Eshelman L, Schaffer J D.Real-coded genetic algorithms and interval schemata[A].In Whitley L D (Ed.), Foundations of Genetic Algorithms 2[C].Los Altos，CA，Morgan Kaufmann，1993,187-202.
　　[5]雷英杰张善文李续武等:MATLAB遗传算法工具箱及应用[M].西安电子科技大学出版社,2005
　　[6]宋松柏蔡焕杰康艳:约束优化问题的遗传算法求解[J].西北农林科技大学学报(自然科学版),2005,33(1):152
　　[7]张文彤:SPSS统计分析高级教程[M].高等教育出版社,2004
　　[8]宋厚冰蔡远利:带时间窗的车辆路径混合遗传算法[J].交通运输工程学报,2003,3(4):114
　　[9]宋伟刚张宏霞佟玲:有时间窗约束非满载车辆调度问题的遗传算法[J].系统仿真学报,2005,17(10):2594
　　[10]Malmborg,Charles. Genetic Algorithm for Service Level Based Vehicle Scheduling[J].European Journal of Operational Research,1996,93(1)
　　
　　“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”

转载注明来源:https://www.xzbu.com/3/view-1496987.htm