改进遗传算法的保定邮政车辆调度问题研究

张凡华北理工大学建筑工程学院

改进遗传算法的保定邮政车辆调度问题研究

张凡
华北理工大学建筑工程学院

为解决保定市邮政车辆调度的问题，基于传统遗传算法，建立数学模型。针对传统遗传算法存在的“早熟”问题，融入自适应变异算子，设计一种改进遗传算法。通过matlab仿真实验，对保定市各县区邮政局间配送车辆路径进行优化，实验证明改进遗传算法优于传统遗传算法。

邮政车辆调度；遗传算法；自适应变异算子；数学模型

近年来，民营企业发展迅速，给邮政带来一定的压力。邮政在民营快递面前价格竞争力不强，而且现在的客户对邮件配送的服务质量要求较高。进行成本控制是邮政物流企业所面临的挑战。保定市邮政车辆调度是由有经验的调度人员编制计划，根据经验拟订方案，计划编制劳动强度太大，难以保证方案最优。设计邮政车辆调度模型和算法用计算机来实现很有必要。

目前，专家针对车辆调度问题已经提到过一些方法，如上世纪六十年代，Balinski提到VRP的集分割[1]，而且对此作出了优化，构建了最基本的VRP模型；尹晓峰等人[2]就蚁群算法中的“早熟”问题，融入节省量以及车辆载重利用率对蚁群算法进行了完善。李嘉等人提出了混合车队求解框架，设计了基于遗传算法和禁忌搜索启发式的混合算法[3]。本文在传统遗传算法基础上融入自适应性变异算子，构造一种改进的遗传算法来进一步分析保定邮政车辆调度问题。

一、邮政车辆调度数学模型

（1）为目标函数，车辆完成调度任务的最少总运输里程；（2）为车辆能力约束，某车所访问的县区局的需求量不可超过自身的载重量；（3）为县区i由车辆k完成的唯一性；（4）为县区i由车辆k完成与否；（5）、（6）为到达某县区车辆唯一性；（7）为车辆k从县区i行驶到县区j与否。

二、改进的遗传算法

（一）传统的遗传算法容易出现过早收敛的现象，很难找到全局最优解。这就需要我们对传统的遗传算法加以改进，引入一些新的方法来增强全局搜索能力，防止出现局部最优。本文采用自适应变异方法，处理变异概率Pm,使之随个体适应度值变化.取Pc=0.85。Pm按如下方法动态调整。

若fmax＞f＞favg,对交叉和变异概率自适应调整.若f＜favg,进行大概率变异,以便迅速淘汰适应值较低的个体,来增大解间。

（二）基本数据。保定市邮政局到满城、顺平、望都、清苑、高阳、安新、容城、定兴、涞水、易县、徐水邮政局的距离（千米）为：26、34、34、12、35、45、47、57、77、63、25。满城邮政局到顺平、望都、清苑、高阳、安新、容城、定兴、涞水、易县、徐水邮政局的距离（千米）为：21、35、36、59、63、77、80、80、58、38.顺平邮政局到望都、清苑、高阳、安新、容城、定兴、涞水、易县、徐水邮政局的距离（千米）为：23、41、72、96、85、88、88、93、66.望都邮政局到清苑、高阳、安新、容城、定兴、涞水、易县、徐水邮政局的距离（千米）为：33、74、82、90、106、109、113、80.清苑邮政局到高阳、安新、容城、定兴、涞水、易县、徐水邮政局的距离（千米）为：31、18、65、37、87、63、35.高阳邮政局到安新、容城、定兴、涞水、易县、徐水邮政局的距离（千米）为：36、52、88、110、123、54.安新邮政局到容城、定兴、涞水、易县、徐水邮政局的距离（千米）为：19、49、72、80、37.容城邮政局到定兴、涞水、易县、徐水邮政局的距离（千米）为：32、54、62、21.定兴邮政局到涞水、易县、徐水邮政局的距离（千米）为：20、29、33.涞水邮政局到易县、徐水邮政局的距离（千米）为：20、49.易县邮政局到徐水邮政局的距离（千米）为48。

三、实验分析

用matlab对改进遗传算法进行仿真,结果如图.通过仿真结果,得出如下结论：随着迭代次数的增加，计算结果是逐步收敛于某个数值。相对于传统遗传算法，改进遗传算法是较优秀的，避免出现过早收敛；传统的遗传算法有很大可能找到的解是局部最优解。改进的遗传算法寻优能力相对较强，最终得到的解比传统的遗传算法得到的解还要优秀，更加说明融入自适应性变异算子的改进遗传算法在解决保定邮政车辆调度问题的有效性。

图1

最优路径为：保定——顺平县——望都县——清苑区——高阳县——保定——安新县——容城县——徐水区——保定——定兴县——涞水县——易县——满城区——保定。

四、结束语

本文针对传统遗传算法存在搜索能力差、易过早收敛的缺点,引入自适应变异算子，对传统遗传算法进行改进。仿真结果说明改进算法具备抗“早熟”、良好的寻优能力。改进的算法为保定邮政车辆调度问题提供了一个较为有效的解决方法。

[1]BalinskiM,Quand R.on an integer program fora delivery problem[J].OperationsResearch,1962.12：300-304.

[2]尹晓峰，杜艳萍.车辆路径问题的蚁群算法研究[J].太原科技大学学报，2005（4）：279-283.

[3]李嘉等.一类特殊车辆路径问题（VRP）[J].东北大学学报（自然科学版），2001.22（3）：245-248.

张凡（1994-），女，河北保定人，华北理工大学建筑工程学院，物流工程专业。