论文部分内容阅读
【摘要】：随着城市交通的不断发展，对物流配送中心提出了更高的要求，如何实现配送路径的最优化摆在了物流企业的面前。对物流配送路径进行优化可以缩短配送时间，确保货物更为快捷的送到目的地，从而提高了企业运作效率，同时快速地将货物配送到位也可以提高客户满意度。由于实际配送节点与路段数目非常巨大，且交通状况较为复杂，因此采用智能路径优化算法容易陷入局部最优，从而导致不能获得全局最优解;同时各条路段上的交通流时刻处于动态变化中，在路径优化的过程中如何将实时的交通状态考虑在内，对提高辽宁物流配送水平具有举足轻重的作用，以上都是目前优化算法亟待解决的问题。本文针对物流配送路径优化问题提出基于最优保存策略
【关键词】：物流配送;遗传算法;路径优化
物流配送路径规划可以归根为NP完全问题类型的旅行商问题（TSP），一般很难用搜索法得到最优解，因此求解为最优或近似最优解不失为一种解决办。算法大体可以分为两类：传统路径优化算法和仿生智能路径优化算法。传统优化算法包括Dijkstra、floyd算法以及它们相应的改进算法等。目前研究热门的仿生智能路径优化算法主要有遗传算法、粒子群优化算法以及蚁群算法等。
一、优化辽宁物流配送路径的改进遗传算法
1.改进遗传算法的基本思想。改进的遗传算法，继承了传统遗传算法的基本思想。其中，编码、选择、交叉和变异是4个主要操作。该算法包括以下6个基本要素：第一，编码：采用自然数直接编码的方法。第二，初始化种群：初始种群的染色体是通过随机方法产生，一个染色体對应一个配送方案。第三，评估适应度：遗传算法在搜索过程用适应度评估每个染色体的优劣，作为下一代种群更新的依据，即把它作为遗传操作的依据，并确保适应度增大的方向与目标函数的优化方向一致。第四，选择：从当前的种群中选择生命力强的染色体，产生新一代的种群。即适应度高的染色体被选中的机会就越大，但并不意味适应度高的染色体一定被选中。第五，交叉：对种群的染色体，按一定的交叉概率，用随机不重复的方法，每次选择两个染色体相互交叉，产生新一代染色体。从而，形成新的子代种群。第六，变异：按一定的变异概率，在交叉的基础上，对种群的染色体进行变异，即改变自身染色体的基因位。
2.改进遗传算法在优化辽宁物流配送路径中的构造
（1）编码方法。采用自然数直接编码的方法，即对客户点的编号进行排列编码。设客户共有L个，用0表示配送中心，对这些客户进行编号，直接产生L个1-L的互不重复的自然数，它们的随机排列就构成一条染色体，对应一种配送方案，但不能仅从这点就分辨出每辆汽车的路径，需结合每辆汽车的载量和客户的需求量来决定。如：对于一个有8个客户，1个配送中心，3辆汽车完成配送任务。设随机一个染色体对应的路径为83456217，根据每个客户的需求量和汽车的载量，首先顺序选择前若干个基因对应的客户，若选83;再在剩余的基因中，顺序选择若干个基因对应的客户，若选456;剩余的若干个基因对应的客户，完全由第3辆汽车来完成，即选217。这里不考虑是否超载，也不考虑是否超出了汽车的最大行驶距离，其配送路径方案的优劣完全由适应度来评估。则此染色体83456217表示的配送3條配送路径分别为：0-8-3-0，0-4-5-6-0，0-2-1-7-0。
（2）初始化种群。随机产生L个1- L的互不重复的自然数，由它们构成的任一序列，形成一条染色体，M条不同的染色体构成了初始种群。
（3）适应度评估。要判断某条染色体对应的配送路径方案的优劣，完全由适应度决定。既要满足配送的约束条件，又要计算目标函数值。要满足的约束条件有：保证每个客户都得到配送服务;每个客户仅有一辆汽车配送完成，但不能满足每条配送路线上个客户需求量之和不超过汽车载量及每条配送路线的长度不超过汽车一次配送的最大行驶距离;对每一条染色体对应的配送路径方案，一一判断是否满足约束条件。如果不满足，表示该条染色体对应的配送路径方案是不可行的，仍要计算其目标函数值，
（4）选择操作。采用最优染色体保留策略和轮盘赌法。由适应度函数来评估每代种群中的M条染色体的适应度，并把每个染色体按适应度从大到小的顺序排列。首先对适应度最高的染色体，直接复制进入下一代。然后，再根据染色体的适应度，采用轮盘赌法产生下一代种群的令M-1个染色体。从而，又形成了含有M个染色体的新种群。这样就可以保证最优质的染色体在下一代继续生存，又可以保证适应度大的染色体有较大的机会进入下一代。
（5）变异操作。在交叉操作形成子代种群的基础上，根据变异概率Pm，适度的变异，既能保持种群内染色体的多样化，又能提高遗传算法的效率。如：种群中某个染色体为：C =81623457，随机产生两个基因变异位置2，5，交换染色体C上第2个和第5个基因，形成新的染色体Cc=83621457。从而，形成新的子代种群。
三、实例
1.例子：某配送中心用2辆汽车对8个客户配送货物。设汽车的载量为8@103kg，每次配送的最大行驶距离为40km，配送中心与客户、客户与客户之间的距离及各客户的需求量（0代表配送中心，1-8代表8个客户点）。
2.实验初始参数：种群大小M取50，交叉概率Pc=0.6，变异概率Pm=0.005，终止迭代次数T=100，超出最大行驶距离的单位距离成本惩罚权重M1=100，超出最大载量的单位载量成本惩罚权重M2=100，单位行驶距离的成本权重C=1。程序运行求解10次，计算结果见表1。从表1数据可以得出，改进后的遗传算法比传统的遗传算法，具有更好的收敛性，在10次的实验结果中，多次接近或达到最优解67.5km，最优解对应的最佳配送路径为：0-4-7-6-0;0-2-8-5-3-1-0。而且，还可以看出改进后的遗传算法有更好的鲁棒性。
实验表明，通过对遗传算法编码方式改进，减少了编码的复杂度和难度，同时精简了对适应度计算，使得种群的更新有更好的收敛性。可见，改进后的遗传算法在求解辽宁物流配送路径优化问题上，取得很好的效果，这也是一种性能优良的启发式搜索方法，也可应用到其他领域。虽然改进后遗传算法取得了一定成果，但还有许多改进空间，仍需进一步完善。
参考文献：
[1]贾庆轩，陈钢，孙汉旭，等.基于A*算法的空间机械臂避障路径规划[J].机械工程学报，2010，（13）：109-115.
[2]马超，郭军.遗传算法在动态权值路径寻优中的应用[J].广西大学学报（自然科学版），2012，37（3）：588-593.
作者简介：马毅（1969—），男，沈阳工业大学，硕士，研究方向：物流管理和数学，职称：副教授。
基金项目：2015年中国物流学会（面上课题）研究课题：振兴辽宁老工业基地辽宁物流产业集群发展策略研究。
【关键词】：物流配送;遗传算法;路径优化
物流配送路径规划可以归根为NP完全问题类型的旅行商问题（TSP），一般很难用搜索法得到最优解，因此求解为最优或近似最优解不失为一种解决办。算法大体可以分为两类：传统路径优化算法和仿生智能路径优化算法。传统优化算法包括Dijkstra、floyd算法以及它们相应的改进算法等。目前研究热门的仿生智能路径优化算法主要有遗传算法、粒子群优化算法以及蚁群算法等。
一、优化辽宁物流配送路径的改进遗传算法
1.改进遗传算法的基本思想。改进的遗传算法，继承了传统遗传算法的基本思想。其中，编码、选择、交叉和变异是4个主要操作。该算法包括以下6个基本要素：第一，编码：采用自然数直接编码的方法。第二，初始化种群：初始种群的染色体是通过随机方法产生，一个染色体對应一个配送方案。第三，评估适应度：遗传算法在搜索过程用适应度评估每个染色体的优劣，作为下一代种群更新的依据，即把它作为遗传操作的依据，并确保适应度增大的方向与目标函数的优化方向一致。第四，选择：从当前的种群中选择生命力强的染色体，产生新一代的种群。即适应度高的染色体被选中的机会就越大，但并不意味适应度高的染色体一定被选中。第五，交叉：对种群的染色体，按一定的交叉概率，用随机不重复的方法，每次选择两个染色体相互交叉，产生新一代染色体。从而，形成新的子代种群。第六，变异：按一定的变异概率，在交叉的基础上，对种群的染色体进行变异，即改变自身染色体的基因位。
2.改进遗传算法在优化辽宁物流配送路径中的构造
（1）编码方法。采用自然数直接编码的方法，即对客户点的编号进行排列编码。设客户共有L个，用0表示配送中心，对这些客户进行编号，直接产生L个1-L的互不重复的自然数，它们的随机排列就构成一条染色体，对应一种配送方案，但不能仅从这点就分辨出每辆汽车的路径，需结合每辆汽车的载量和客户的需求量来决定。如：对于一个有8个客户，1个配送中心，3辆汽车完成配送任务。设随机一个染色体对应的路径为83456217，根据每个客户的需求量和汽车的载量，首先顺序选择前若干个基因对应的客户，若选83;再在剩余的基因中，顺序选择若干个基因对应的客户，若选456;剩余的若干个基因对应的客户，完全由第3辆汽车来完成，即选217。这里不考虑是否超载，也不考虑是否超出了汽车的最大行驶距离，其配送路径方案的优劣完全由适应度来评估。则此染色体83456217表示的配送3條配送路径分别为：0-8-3-0，0-4-5-6-0，0-2-1-7-0。
（2）初始化种群。随机产生L个1- L的互不重复的自然数，由它们构成的任一序列，形成一条染色体，M条不同的染色体构成了初始种群。
（3）适应度评估。要判断某条染色体对应的配送路径方案的优劣，完全由适应度决定。既要满足配送的约束条件，又要计算目标函数值。要满足的约束条件有：保证每个客户都得到配送服务;每个客户仅有一辆汽车配送完成，但不能满足每条配送路线上个客户需求量之和不超过汽车载量及每条配送路线的长度不超过汽车一次配送的最大行驶距离;对每一条染色体对应的配送路径方案，一一判断是否满足约束条件。如果不满足，表示该条染色体对应的配送路径方案是不可行的，仍要计算其目标函数值，
（4）选择操作。采用最优染色体保留策略和轮盘赌法。由适应度函数来评估每代种群中的M条染色体的适应度，并把每个染色体按适应度从大到小的顺序排列。首先对适应度最高的染色体，直接复制进入下一代。然后，再根据染色体的适应度，采用轮盘赌法产生下一代种群的令M-1个染色体。从而，又形成了含有M个染色体的新种群。这样就可以保证最优质的染色体在下一代继续生存，又可以保证适应度大的染色体有较大的机会进入下一代。
（5）变异操作。在交叉操作形成子代种群的基础上，根据变异概率Pm，适度的变异，既能保持种群内染色体的多样化，又能提高遗传算法的效率。如：种群中某个染色体为：C =81623457，随机产生两个基因变异位置2，5，交换染色体C上第2个和第5个基因，形成新的染色体Cc=83621457。从而，形成新的子代种群。
三、实例
1.例子：某配送中心用2辆汽车对8个客户配送货物。设汽车的载量为8@103kg，每次配送的最大行驶距离为40km，配送中心与客户、客户与客户之间的距离及各客户的需求量（0代表配送中心，1-8代表8个客户点）。
2.实验初始参数：种群大小M取50，交叉概率Pc=0.6，变异概率Pm=0.005，终止迭代次数T=100，超出最大行驶距离的单位距离成本惩罚权重M1=100，超出最大载量的单位载量成本惩罚权重M2=100，单位行驶距离的成本权重C=1。程序运行求解10次，计算结果见表1。从表1数据可以得出，改进后的遗传算法比传统的遗传算法，具有更好的收敛性，在10次的实验结果中，多次接近或达到最优解67.5km，最优解对应的最佳配送路径为：0-4-7-6-0;0-2-8-5-3-1-0。而且，还可以看出改进后的遗传算法有更好的鲁棒性。
实验表明，通过对遗传算法编码方式改进，减少了编码的复杂度和难度，同时精简了对适应度计算，使得种群的更新有更好的收敛性。可见，改进后的遗传算法在求解辽宁物流配送路径优化问题上，取得很好的效果，这也是一种性能优良的启发式搜索方法，也可应用到其他领域。虽然改进后遗传算法取得了一定成果，但还有许多改进空间，仍需进一步完善。
参考文献：
[1]贾庆轩，陈钢，孙汉旭，等.基于A*算法的空间机械臂避障路径规划[J].机械工程学报，2010，（13）：109-115.
[2]马超，郭军.遗传算法在动态权值路径寻优中的应用[J].广西大学学报（自然科学版），2012，37（3）：588-593.
作者简介：马毅（1969—），男，沈阳工业大学，硕士，研究方向：物流管理和数学，职称：副教授。
基金项目：2015年中国物流学会（面上课题）研究课题：振兴辽宁老工业基地辽宁物流产业集群发展策略研究。