郑明物流公司物流网络系统设计 - 图文

极小并最终趋于全局最优；GA 则通过概率意义下的基于“优胜劣汰”思想的群体遗传操作来实现优化。对选择优化机制上如此差异的两种算法进行混合，有利于丰富优化过程中的搜索行为，增强全局和局部意义下的搜索能力和效率。

2.优化结构的互补

SA 算法采用串行优化结构，而GA采用群体并行搜索。两者相结合，能够使 SA成为并行SA算法，提高其优化性能；同时SA作为一种自适应变概率的变异操作，增强和补充了GA的进化能力。

3.优化操作的结合

SA算法的状态产生和接受操作每一时刻仅保留一个解，缺乏冗余和历史搜索信息；而GA的复制操作能够在下一代中保留种群中的优良个体，交叉操作能够使后代在一定程度上继承父代的优良模式，变异操作能够加强种群中个体的多样性。这些不同作用的优化操作相结合，丰富了优化过程中的邻域搜索结构，增强了全空间的搜索能力。

4.优化行为的互补

由于复制操作对当前种群外的解空间无探索能力，种群中各个体分布“畸形”时交叉操作的进化能力有限，小概率变异操作很难增加种群的多样性，所以，若算法收敛准则设计不好，则GA经常会出现进化缓慢或“早熟”收敛的现象。另一方面，SA的优化行为对退温历程具有很强的依赖性，而理论上的全局收敛对退温历程的限制条件很苛刻，因此 SA优化时间性能较差。两种算法结合，SA的两准则可控制算法收敛性以避免出现“早熟”收敛现象，并行化的抽样过程可提高算法的优化时间性能【6】。

5.削弱参数选择的苛刻性

SA和GA对算法参数具有很强的依赖性。参数选择不合适将严重影响优化性能，SA的收敛条件导致算法参数选择较为苛刻，甚至不实用；而 GA的参数又没有明确的选择指导，设计算法时均要通过大量的试验和经验来确定。GA和SA的相混合，使算法各方面的搜索能力均有提高，因此对算法参数的选择不必过分严格。研究表明，混合算法在采用单一算法参数时，优化性能和鲁棒性均有大幅度提高，尤其对较大规模的复杂问题【5】。 4.5.2算法步骤

Step1：设定群体规模pop? size、初温时的系数T0、退温系数?，交叉和变异的概率系数Pc、Pm，终止规则中的q，迭代计数器数n?0；

Step2：利用 PHIF 方法产生pop? size个染色体作为初始种群pop(0)，通过计算目标函数值来得到初始温度，且令S?fmin、p?0；

19

Step3：计算出染色体的适应值，保证下一代是优质的；

Step4：对染色体的目标函数进行重新计算，实施最优保留的执行条件； Step5：复制产生下一代群体pop(n?1)，这个过程要严格按照Metropolis 判别准则进行；

Step6：执行退温操作，即T(n?1)??T(n)，令n?n?1； Step7：计算出新一代的群体的目标函数值，令S'?fmin；

Step8：对S'和S的大小进行比较，若S'小于S，令S?S'，p?0，否则p?p?1； Step9：比较p和q的大小，若p?q，则S为最终解，并输出，否则回到Step3； 4.5.3算法描述 1.染色体的编码

种群中的成员用字符串实体表示，对长度为N的字符串进行求解，每个实体需求点用染色体中的一个数字表示，货车行驶的路径和方向用染色体基因顺序表示。解码过程是在新的路径中按顺序插入基因，要减少费用则必须尽量减小路径。

2.生成初始种群

产生初始种群的过程要借助于PHIF方法，种群数量为pop?size，即在网络边上插入需求点，且要保证需求点的费用最低，产生部分初始解S0，随机产生剩余部分的可行解S1。这个过程能保证种群多样性。

3.确定初温和退温

设fmax和fmin分别为初始种群中的最大和最小目标函数值，??fmax?fmin，初温可以表示为T0?k?，其中k为常数。退温函数表示为T(n?1)??T(n)，其中0???1。

4.适应度函数

适应函数是遗传算法的关键。首先需要根据个体目标函数值从大到小排列，适应函数定义为：

eval(xi)??(1??)i?1（4-11）

其中，xi为排序后的第i个个体，i?1,2???pop?size，0???1。 货车运输的最低费用可以表示为：

f(Si)??Ni?0j?0,j?ik?1??dNKijijkx，?i,j?{0,1,???N}，k?{1,2,???K}（4-12）

5.选择算子

采用比例选择算子，该算子是一个随机采样的方法。选中父代个体xi的概率为：

pop?sizep(si)?eval(xi)/?i?1eval(xi)（4-13）

6.交叉和变异算子

20

物流配送路径中的染色体编码是定长且有序的，且每条染色体的整数基因只出现一次，单点或双点操作并不适用于这种情况。PMX交叉方法能够避免交叉操作后出现不合格染色体，PMX是随机对染色体编码中的两个交叉点进行基因交换。

变异操作使父代种群产生随机的、无关联的性状，维持种群的多样性。为减小范围迁移和增加多样性，选择INV作为变异算子。

7.新个体的复制策略及终止规则

首先执行最优保留策略，然后在染色体i中随机产生个体j，i和j竞争能力强的进入下一代。令?f?f(xj)?f(xi)，若?f?0成立，则将xj复制到下一代群体中，否则，以exp(??f/T(n))?random|0,1|作为复制xj到下一代群体的条件。并通过监控每代进化群体中最小目标函数值fmin的变化情况来判断算法是否终止。当连续q代没有发生变化时，即可认为算法收敛并终止计算。

4.6本章小结

本章介绍了物流配送路径优化模型，其中简要介绍了物流配送过程，以及一些配送的基本要求。再基于这些要求建立物流配送路径优化数学模型。遗传算法（GA）和模拟退火算法（SA）是两种解决物流配送路径优化问题的两种算法，这两种算法都有其各自的优点和不足。本章第五节着重介绍了将模拟退火算法的思想引入遗传算法中，将两种算法很好的结合在一起，能起到很好的互补的作用，这种遗传退火混合算法在优化物流配送路径方面已显示出很好的特性。

21

第五章郑明物流公司物流网络设计及配送路径优化

本实例是以郑明物流公司为重庆市永辉超市提供物流配送服务为背景，进行介绍郑明物流公司在物流网络设计及配送路径优化方面的操作流程。

5.1重庆市永辉超市简介

永辉集团创建于1998年，是一家以经营生鲜农产品为主，日用百货、服装鞋帽为辅的商业零售企业。目前，集团投资总额逾10亿元，现有员工15000名（其中安置下岗职工3000多名），拥有多种业态的连锁超市150家，连锁经营面积超过四十万平方米。 永辉集团自2004年底进入重庆以来，已经在江北区金源不夜城、五里店、渝北区加州花园、东和春天、黄泥滂、两路镇、渝中区大坪、长寿协信、南岸区四公里、大渡口香港城、两路双龙路、梁平、杨家坪、綦江、壁山、南坪东路、万盛、石桥铺开设了39家大型生鲜超市。

永辉超市作为重庆市几家大型连锁超市之一，是郑明公司开展物流运输服务的主要目标之一，因此将以重庆市永辉超市为服务对象，对其配送中心进行选址于分析。

5.2 基于重心法的郑明物流公司的配送中心选址分析

5.2.1坐标分析

图5-1 重庆市永辉超市分布图

22