基于遗传算法的无时限多配送中心车辆调度问题研究
来源:用户上传
作者: 田秋荣 李仲兴
[摘 要] 针对多配送中心车辆调度问题的复杂性特点，提出用最近距离分配法和遗传算法分两步求解多配送中心车辆调度问题,并进行了试验计算。
[关键词] 多配送中心 车辆调度 最近距离分配法 遗传算法
一、 引言
车辆调度是物流系统优化中关键的一环。对配送车辆的调度进行科学优化，可以降低运输成本，提高物流企业经济效益。根据配送中心数目的多少，配送车辆优化调度问题有单配送中心车辆调度问题和多配送中心车辆调度问题之分。目前，我国一些大中型城市的物流体系中存在有多个配送中心的情况。因此，对多配送中心车辆调度问题的研究有重要的现实意义。
本文提出了用最近距离分配法将多配送中心车辆调度问题分解为多个单配送中心车辆调度问题进行求解的策略，利用求解单配送中心车辆调度问题的遗传算法，设计了求解多配送中心车辆调度问题的算法，最后通过案例计算验证了该算法的良好性能。
二、多配送中心问题转化成单配送中心的问题
本文采用最近距离分配法将多配送中心车辆调度问题转化成单配送中心车辆调度问题。
根据距离最近原则，决定为某客户提供服务的配送中心。鉴于多配送中心车辆调度问题以总配送里程最短为优化目标，计算某客户与各配送中心的距离，该客户离那个配送中心最近，就将其分配到那个配送中心，由该配送中心为其提供服务。
三、混合遗传算法求解单配送中心的车辆调度问题
遗传算法是一种“生成+检测”的迭代搜索算法。该算法以群体中的所有个体为操作对象，每个个体对应研究问题的一个解。选择，交叉和变异是遗传算法的三个主要操作算子。该算法包括以下6个基本要素:（1）编码;(2)初始群体生成;(3)适应度评估;(4)选择;(5)交叉;（6)变异。
针对单配送中心无时间窗车辆路径优化问题的特点，构造了求解该问题的遗传算法。
1.自然数编码
本文采用表示比较直观的，容易产生可行解的自然数编码方法。这种方法是直接产生L个1~L间的互不重复的自然数的排列，该客户排列就构成一个解，并对应一个配送路径方案。
2.初始群体的生成
本文采随机生成的方法生成初始群体
3.适应度函数
本文以距离最短作为目标函数，适应度函数为目标函数的倒数,显然适应度越大,距离越短,被选入下一代操作的机率就越大。
4.选择操作
本文采用最优个体保留与赌轮选择相结合的方法。将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位。下一代群体的另N-1个个体需要根据前代群体的N个个体的适应度，采用赌轮选择法产生。
5.交叉操作
本文采用顺序交叉(OX）。首先选择一个匹配区域，设两父代个体及其匹配区域为:A=58|742|361、B=25|831|746;然后根据匹配区域的映射关系,在其区域外的相应位置标记H,得到:A’=5H|742|H6H、B’=H5|831|HH6；再移动匹配区域至起始位置，且在其后预留相等于匹配区域的空间（H的数目），然后将其余的码按其相对次序排列在预留区后面，得到：A”=742|HHH|65、B”=831|HHH|65；最后将父串A、B的匹配区域相互交换，并放置到A”、 B”的预留区内，即可得到两个后代个体：A”’=74283165、B”’=83174265。
6.变异操作
物种变异的可能性较小，所以在遗传算法中变异操作只起辅助作用。对每代种群以变异概率Pm=0.001进行染色体变异。在此引入一种新的变异策略：逆转变异。具体过程如下：随机产生一染色体E和两个变异点，将变异段进行逆转得新个体E1。
E=12|5836|29→E1=12|6385|29
四、 实验计算和结果分析
案例:某城市有3个配送中心和33个客户，分布在一个边长为30km的正方形地域内，每个客户的货物需求量都在2t及其以下，每个配送中心有4台车辆，车辆的载质量均为10t，车辆一次配送的最大行驶距离均为60km。其中3个配送中心的坐标分别是:配送中心1(9.56km，6.03km)配送中心2(6.44km，11.28km）配送中心3(21.14km，21.10km）,33个客户的坐标及其货物需求量见表.要求合理安排配送车辆的行车路线，使配送总里程最短。为简便起见，本文设各客户相互之间及配送中心与客户之间的距离按照公式dij=1.2[(xi-xj)2+(yi-yj)2]1/2(km)近似计算。
采用最近距离分配法，在MATLAB里通过编程计算得到如下的分区结果：
配送中心1为9个客户服务,客户编号为:30，2，4，7，1，27，16，21，23;
配送中心2为13个客户服务，客户编号为:17，31，12，8，29，25，26，13，15，18，14，32，9；
配送中心3为11个客户服务，客户编号为：3，6，24，20，22，33，5，28，10，11，19。
设定交叉概率pc=0.7，变异概率pm=0.001，使用遗传算法分别对三个配送分区构成的单配送中心车辆调度问题随机求解50代，得到的最优解分别是：
配送中心1:使用一辆车，对应的配送路径为配送中心1-21-23-30-2-4-7-1-27-16-配送中心1，配送路径总长度为55.07km。
配送中心2:使用两辆车，对应的配送路径分别为配送中心2-12-8-29-25-26-13-15-配送中心2和配送中心2-18-14-32-9-17-31-配送中心2,配送路径总长度为81.68km.
配送中心3:使用两辆车，对应的配送路径分别为配送中心3-10-11-19-3-6-24 -20-配送中心3和配送中心3-22-33-5-28-配送中心3，配送路径总长度为80.75km.
将上述三个配送中心的最优解合并，即可得到该多配送中心车辆调度问题的解，该解对应的配送方案共使用了5辆车,5条配送路线的总长度为217.5km。
五、 结束语
本文首先用最近距离分配法将复杂的多配送中心车辆调度问题转化为简单的单配送中心车辆调度问题，然后用遗传算法有效地求解了单配送中心车辆调度问题。这种求解策略将复杂的问题简单化，提高了计算效率，适用于求解大规模的多配送中心车辆调度问题。
参考文献:
[1]郎茂祥:多配送中心车辆调度问题的模型和算法研究[J].交通运输系统工程与信息,2006(5）:65～69
[2]李 军，郭耀煌:物流配送车辆优化调度理论与方法[M].北京:中国物资出版社,2001.93～96
[3]陈国良 王熙法 庄镇泉 王东生:遗传算法及其应用[M]. 北京:人民邮电出版社，1996，101～106
[4]周 明 孙树栋:遗传算法原理及应用[M].北京：国防工业出版社,1999.18～58
“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”
转载注明来源:https://www.xzbu.com/3/view-1492096.htm
