基于优化遗传算法的多配送中心车辆路径研究-科技创新论文

1、 基于优化遗传算法的多配送中 心车辆路径研究-科技创新论文2 作者: 日期:3 基于优化遗传算法的多配送中 L、车辆路径研究 -科技创新论 文 基丁优化遗传算法的多配送中心车辆路径研究 黄玉文 荷泽学院计算机与信息工程系，山东 荷泽274015 【摘 要】将遗传算法与模拟退火算法相结合，提出了一种基丁优化遗传算法 的多配送中心车辆路径调度方法，该调度方法不仅具有自适应遗传算法的强大全 局搜索能力，也具有模拟退火算法的强大局部搜索能力。通过对杂交率和变异率 进行自适应调整、对接受算子进行退火处理 ，有效地增强了全局寻优能力，通过 对适应值函数退火拉伸，加速了寻优过程。 关键词 遗传算法；模拟退火

2、；多配送中心；车辆路径 基金工程：山东省高等学校科技方案工程J13LN53 ;荷泽学院科学院科 研基金XY14KJ08 。 作者简介：黄玉文1978-,男，山东单县人，硕士，讲师，主要研究方向： 网络与信息平安、数据挖掘、算法分析。 0引言 当前,随着电子商务的快速兴起，物流业在市场经济中占有越来越重要的地位， 引起国家的高度重视和越来越多的企业的关注。 正确和高效的安排多配送中心车 辆路径调度有利丁提高配送速度，有利丁企业节约本钱，提高物流配送企业的经 济效率和顾客效劳水平。近年来，物流配送在国家的经济建设中扮演越来越重要 的作用，如何提高物流配送效率和降低物流本钱成为一个热门研究课题 1。

3、多 配送中心配送能够满足更广阔的地理范围内的顾客效劳需求， 配送车辆可以从多4 个配送中心出发去完成运输任务，到达提高车辆利用率、减少总的运输距离、节 约运输本钱，更快满足顾客需要的目的。车辆路径问题( Vehicle Routing Problem )在多配送中心物流调度中占有一个非常重要的环节， 这个问题的有效 解决，可以提高物流调度的科学化水平，降低运输本钱，提高经济效益 2。同 时物流配送车辆调度问题作为一个 NP难题，随着客户数量的增加，可选的配送 路径方案数量将以指数速度急剧增长3。因此，用启发式算法求解该问题就成 为人们研究的一个重要方向，本文提出了一种基丁 优化遗传算法的多配送

4、中心 车辆路径方案。 1优化遗传算法思想 遗传算法不依赖初始解，可以对问题参数的编码组进行计算，并且算法具有强 大的搜索能力，故很多研究者把遗传算法应用到解决多配送中心的调度问题中。 遗传算法强调的是两代之间的进化关系， 其交义有可能错过最好解，因而局部搜 索能力较弱，所以即使是在最优解附近，而要到达这个最优解，却花费较大的代 价。遗传算法在最优路径搜索过程中容易陷入局部最优， 搜索效率比拟低下，而 模拟退火算法容易脱离局部最优4。因此，考虑将模拟退火算法的思想引入遗 传算法，有效地缓解了遗传算法的选择压力。 退火遗传算法是集合了遗传算法和 模拟退火算法各自的优点，具有较好的全局搜索和局部搜索

5、能力， 本文把遗传算 法和模拟退火策略相结合以解决多配送中心车辆调度问题 5。 2基丁优化遗传算法的的多配送中心车辆路径算法 2 . 1 适应函数的退火拉伸 5 在遗传算法运算前期，由丁染色体的差异较大，轮盘赌选择容易使遗传算法进 入局部最优；进化后期，染色体的个体差异性较小，轮盘赌选择容易使遗传算法 6 进入终止状态。故变换适应度函数为： 广f 史林-时?力 1 / ， 1 式中：f X为适应度函数变换后的值，f max X适应度函数的最大 值，T代表退火温度，TO代表初始温度，g代表遗传代数，R为略小丁 1的 正数，本文取0. 99。 2. 2 交义和变异的自适应性 1交义操作 遗传算法通

6、过交义操作能够产生下一代新个体，由丁遗传算法在运算过程中容 易陷入局部最优，交义操作通过产生的新个体和上一代个体的差异性较大， 使遗 传算法具有较强的全局搜索能力。本文采用如下的交义操作方式： 二1-。0 洛Xg 矿二探必exJ (2) 4AT VL rhjn ,4 */J*二人 H I I / - W 出 5 nsi二犬 / 久、 在上式中， AB和分别为上一代个体A和B产生的新一代个体，a和6分别 是0, r上的随机数，交义系数r的取值范围为0 , 1。L和R代表寻优参数的 范围，如进行交义操作后超过了寻优参数范围，那么重新进行交义操作。 2变异操作 变异操作采用如下形式 1 (0)=0

7、C-k普I 1 ) = 1 (4) 上式中，C为父个体， C为变异操作产生的新个体，随机数的范围为0,1, 变异系数k的取值范围为0,1, 随机函数U0,1的值为0或1 2 . 3 接受算子的退火处理 杂交和变异运算后的个体中的最优解被保存，这故遗传算法容易陷入局部最优 解，出现早熟现象。本文提出以 Metropolis 准那么保存个体，其保存概率为 式中:fold为杂交(变异)前的父代个体适应值，fnew为杂交(变异)后的 子代个体适应值，T为退火温度。 2 . 4 算法的实现 将自适应遗传退火算法应用到多配送中心车辆路径优化中， 具体的实现步骤如 ： (1) 设置初始参数，包括种群规模M,

8、最大遗传代数Tmax，退火初始温度T0, 温度下降系数精,最小新解接受次数Nmin,最大内循环次数Cmax,随机产生初始 种群 Gi (1,2,，n)。设定 H、M、qi (i = l,2，M+H)、Q k (k=l, 2，K)、Dk (k=l, 2，K)、dij (i, j=l, 2， u u I( / - A | | M, M+ 1 , M+ 2 ,，M+H)、时间J 惩罚系数c和d的值。 (2) 计算种群中各个个体的适应度值，记录最优个体。对种群中的每一个染色 体Gi ( 1 , 2 ,，n),求得对应的目标函数值f 1 ;假设染色体对应的是不可 行解，那么届丁其目标函数一个很大的整数。

9、并采用如下方法进行适应度拉伸 / 公式中f 为拉伸后的适应度值。 (3) 选择操作8 采用轮盘选择策略进行个体选择，进行染色体的复制，具体过程如下：对各个染 I F二九 色体u k ,计算适应值f k ;计算种群中n个染色体适应值的和 ，对各 I & . _ J I 染色体u k,计算选择概率川妇 2对各个染色体u k，计算 适应值 。在区间0, 1 内产生一个随机数r,假设rv q 1 ,那么选择第一个染色体r V u 1 ;否那么选择第k个染色体u k (k=l, 2, n),使得q k 1 V r V q k成立。将当前群体中适应度最高的个体结构完整的 复制到下一代群体中。 (4

10、) 交义操作。按照式(2)、式(3)进行自适应交义操作。 (5) 执行Metropolis 准那么，对交义后的算子进行接收退火处理。 (6) 变异操作。对个体的每个参数进行自适应变异操作。 (7) 执行Metropolis 准那么，对变异后的算子进行接收退火处理。 (8 )删除子代种群中的任意一个个体，并替换成步骤 (2)记录的最优个体。 (9)如果当前遗传代数T ?刍Tm a x，那么按进行降温,T=T+1,并返回步骤(2); 否那么结束整个优化过程。 3 结论 本章对杂交率和变异率的个体进行自适应的接受， 有利丁提高遗传算法的收敛 性。对适应值函数的退火拉伸，能够使遗传算法加快收敛速度，能够更好的寻找 多配送中心车辆路径。 参考文献 1 葛显龙，王旭，邓蕾.基丁联合配送的开放式动态车辆路径问题及算法研究 J.管理工程学报，2021,3:44-48. 10 2 丁滨，靳鹏欢,杨忠振.两阶段启发式算法求解带时间窗的多中心车辆路径 问题J.系统工程理论与实践,2021,8:32-37. 3 孙国华.带时间窗的开放式满载车辆路径问题