混合遗传算法求解多中心联合配送路径问题
范厚明a,b， 徐振林a,b， 李 阳a， 刘文琪a， 耿 静a
(大连海事大学 a. 交通运输工程学院； b. 战略管理与系统规划研究所， 辽宁 大连 116026)
摘 要： 针对传统遗传算法在求解多中心车辆路径问题时存在：传统编解码方式引起的染色体长度不固定导致计算效率低下和易产生不可行解；扰动过程中双亲遗传算子计算效率较低；难以平衡不同进化时期种群中精英比例与种群多样性间、搜索深度与搜索广度间的关系等问题，本文设计一种混合遗传算法，在编解码方式上将配送网络信息分开表达，提高计算效率；在选择操作上引入平衡精英比例与种群多样性的控制参数；此外，还提出一种自适应搜索范围策略，以有效平衡搜索深度与搜索广度间的关系.通过实验例证和对比分析，验证了算法的有效性.研究成果为求解多中心联合配送车辆路径问题提供一种新思路，也可为相关的物流配送决策提供指导.
关键词： 联合配送； 多中心车辆路径问题； 混合遗传算法； 自适应搜索范围策略
面对激烈的市场竞争，物流配送企业追求的目标已经从仅要求完成配送任务转变为要求在保证配送任务完成的基础上，通过整合资源，提高资源利用率，降低配送总成本.车辆路径问题(Vehicle Routing Problem，VRP) 是物流配送企业运营管理的核心问题，VRP自提出以来，陆续有研究人员提出各种拓展模型并对其进行了深入研究.经典VRP是针对一系列已知地理位置的客户，设计出满足一定约束条件的行车路线进行送货服务(或收货服务)，以使得整个物流服务过程达到期望的目标(如费用最低、路径最短等).
随着业务的拓展，一些连锁超市、快递企业或快消企业等为降低远距离配送引起的高额成本以及提高配送时效，会选择在某一区域内设有多个配送中心联合完成企业的配送业务.此类配送模式可归结为多中心车辆路径问题(Multi-depot Vehicle Routing Problem，MDVRP)，MDVRP作为经典VRP的一类拓展问题，是工程技术、经济管理、信息科学等诸多领域内很多复杂问题的集中概括和简化形式，有着重要的实际利用价值.鉴于此，近些年许多研究人员对此类问题进行了深入研究.由于MDVRP属于非确定性多项式(Non-deterministic Po-lynomial, NP)完全类问题，传统的精确算法不太适用于较大规模问题的求解，而各类启发式算法则在此方面有着不错的表现，如Allahyari等[1]应用自适应贪婪随机算法、Oliveira等[2]应用合作进化算法、Jabir 等[3]应用混合蚁群变邻域算法对该问题进行了求解；Zhou等[4]对两级配送网络的MDVRP进行了研究，并采用多种群遗传算法进行求解；文献[5]和[6]分别利用变邻域算法和量子遗传算法对多车型MDVRP进行了求解；Mancini[7]利用大规模邻域搜索算法对多周期多车型MDVRP进行求解；文献[8]利用遗传算法对存在车辆租赁及共享且有时间窗的MDVRP进行了研究；此外，文献[9]和[10]则分别采用嵌入局部搜索的自适应邻域选择算法及粒子群算法对同时取送货MDVRP进行了深入研究.遗传算法是一种以自然选择和遗传理论为基础，利用生物进化过程中适者生存规则和种群内部染色体信息随机交换机制相结合的方式搜寻全局解的一种概率优化算法.仅利用适应性信息，以点集而非点在整个空间中做大范围并行搜索，具有很强的搜索能力.由于刚提出时的遗传算法还较为简单，现在通常称之为传统遗传算法，后来的研究人员不断探索，又提出了各种改进遗传算法.本文在传统遗传算法的基础上，针对MDVRP的特征设计了一种混合遗传算法(Hybrid Genetic Algorithm，HGA)，通过设计新型编解码方式、混合算子以及广度搜索与深度搜索平衡策略，有效地提升算法性能，旨在通过该算法以获得较高质量的满意解.
人们必须要充分认识到经营权登记工作的重要性，在具体实施过程中，可以将其核心放在县级，将关键阵地设置在乡村。将相关宣传工作做好，相关基层干部必须要从思想上提高对经营权确认项目的重视，从而真正将该项工作落到实处。加强向广大农户进行相关政策的分析和讲解工作，将村委会和村党支部的作用充分发挥出来，并进行深入的宣传指导。
1 问题描述及数学模型
现有的区域内多配送中心配送多采用分区域独立配送模式.多个配送中心虽同属于一家企业，但一般情况下，企业会根据行政区划为每个配送中心划分一个业务范围，各配送中心间相对独立.在分区域独立配送模式下，一个客户会固定从属于某一特定配送中心，而不会根据客户的地理分布和需求特性进行调整，易导致各配送中心间任务分配不均.从理论研究的角度来看，此类求解MDVRP的方法是“先分组后路径”，即分区域规划思想，将各配送中心割裂开来.分区的结果会直接影响区内路径的规划结果，不合理的分区算法常常会导致较差的路径规划.为避免此类问题的出现，本文采用整体配送模式，引入一个与所有的实际配送中心相连且距离为0的虚拟配送中心，所有车辆均从该虚拟配送中心出发，经过实际配送中心对客户进行服务，然后再经实际配送中心返回该虚拟配送中心.
多中心车辆路径问题可描述为：某物流网络中共有M 个实际配送中心、N 个客户以及K 辆相同车型的可用配送车辆.配送中心集合表示为D ={0,1,2,…,m ,…,M }，其中：编号0为虚拟配送中心；客户集合表示为C ={M +1,M +2,…,M +n ,…,M +N }；可用配送车辆集合表示为
配送中心与客户集合(即所有点的集合)表示为V =D ∪C ={0,1,…,M ,M +1,…,M +N }，所有配送车辆最大容量均为Q ，客户i 的需求为q i ，∀i ∈C ，且q i <Q .任一客户只允许由一个配送中心的一辆车进行一次配送服务，该配送车辆在完成配送任务后必须返回初始配送中心，且车辆装载量不得超过其最大容量，要求设计适当的配送路线，以达到运输总成本最低这一目标.
当i ≠j 时，假设节点i 到节点j 的运输成本
(用运输距离表示运输成本)，且c ij =c ji .定义决策变量如下：
则多中心车辆路径问题的数学模型如下：
(10)
图1 编解码方式示意图
Fig.1 Coding mode diagram
(1) 插入算子(Insertion Operator).选择一个客户并插入到某个客户后面.如图2(a)所示，选择路线A 上客户1，插入客户3之后的位置，形成插入后路线A ′.
2 混合遗传算法设计及实现
遗传算法一般由编解码、个体适应度评价以及遗传运算三大主要部分组成.在遗传算法中，常定义种群为所编码后的染色体集合，而个体是其相应染色体的表现型.
2.1 编解码方式
传统遗传算法的编解码方式多采用二进制编码，然而对于VRP，采用二进制编解码则可能需要额外的修复机制对产生的不可行解进行修复，从而导致问题的求解时间变长.为避免此类情况发生，现有文献对VRP多采用自然数编解码，如由1个配送中心(编号为0)、10个客户(编号为1～10)以及3辆车组成的配送网络中，编码0340278105690，解码后表示路径0-3-4-0、0-2-7-8-1-0以及0-5-6-9-0.考虑到车辆容量限制会导致车辆实际装载量不固定，进而致使所用车辆总数不固定.即在该编码方式下，染色体长度可能会因为配送方案的不同而不固定，从而导致计算效率下降.因此，本文在传统编解码方式的基础上，提出一种能够有效表达客户信息、配送中心信息以及车辆路径信息的编解码方式.
一个完整的配送网络信息由两部分组成：①编码：本文的编码采用全客户编码，这一部分记录所有客户的先后服务顺序，体现在染色体上，其长度固定(即客户数目)；②解码：为不改变编码长度，本文的解码分为两个阶段，第一阶段是对首尾客户位置进行解码，这一阶段记录每辆车第一个服务的客户以及最后一个服务的客户在染色体中的位置，解码长度与所用车辆数有关；第二阶段是路径解码，这一阶段记录每辆车所属的配送中心以及所服务的全部客户.如图1所示，现有2个配送中心(编号为1～2)、10个客户(编号为3～12)和3辆车的配送网络，全客户编码为8-3-7-12-9-5-4-10-6-11.首尾客户位置解码为[1,3]、[4,7]、[8,10]，即第1辆车从第1个客户(客户8)开始服务，服务完第3个客户(客户7)返回配送中心.同理，该染色体对应的路径解码则表示为R 1：1-8-3-7-1、R 2：1-12-9-5-4-1、R 3：2-10-6-11-2.
本文通过将配送网络信息分开表示，在遗传操作时，只对编码长度固定的第一部分信息进行操作，遗传操作完成后，第一部分全客户编码即已完成，此时根据车辆容量约束重新为每个车辆分配客户，解码获得第二部分的首尾客户位置，再根据首尾客户位置计算出最近的配送中心，从而再解码获得最终的路径.也就是说第一部分全客户编码决定了后面的解码，只要第一部分信息是正确的，则由其产生的最终路径编码也一定是正确的，即通过此编码方式产生的个体进行扰动产生的新个体一定为原问题的可行解.且该编码方式有利于计算机实现，运算效率较高.
2.2 扰动过程
对已经步入工作岗位的会计人员或已经取得会计专业技术资格证的会计人员进行专业培训，目的是为了提高会计人员的职业素质、业务能力、道德水平、思想政治素养，确保其更好的适应新时期经济发展的要求。为了切实提高会计人员的工作能力、专业素质和职业道德水平，确保会计人员能够紧跟国家经济发展动态，不断更新知识水平和专业能力，财政部规定会计人员每年必须进行定期的培训教育，在这一背景下，各个领域也都采取各种形式对会计人员进行定期的继续教育。
2.2.1 单亲遗传算子 单亲遗传算子一般有3种操作：
式(1)为最小化运输总成本；式(2)为车辆容量约束；式(3)为车辆数约束；式(4)为各节点进出平衡约束；式(5)为所有车辆均从虚拟配送中心出发并最终全部返回虚拟配送中心；式(6)为各配送中心间不能有车辆直接相连；式(7)保证任一客户由且仅由一辆车进行配送；式(8)为消除子回路约束；式(9)和(10)为决策变量属性.
(2) 互换算子(Reciprocal Exchange Operator).选择两个客户并交换两个客户位置.如图2(b)所示，选择线路A 上客户1与客户3，互换位置后形成路线A ′.
式中：N g 为第g 代个体的搜索范围，即第g 代个体进行邻域扰动的次数；r 1为最小搜索范围；r 2为自适应搜索范围.
图2 单亲遗传算子示意图
Fig.2 Partheno-genetic operator
2.2.2 双亲遗传算子 本文中的双亲遗传算子采用顺序交叉法，如图3所示：首先从父代A 2中随机选一片段，如(a)中片段“1-3-9”(“|”表示切割点)，复制到子代
对应位置，得到的子代如(b)所示，其他位置用“*”暂时代替，然后从父代A 1中依次删除片段“1-3-9”中各客户，如(c)所示，最后将(c)中剩余客户依次填充到(b)中位置“*”上，可得到如(d)所示的最终的子代
同理可得子代
图3 双亲遗传算子示意图
Fig.3 Parent genetic operator
在传统双亲遗传算法中，一般随机选取两个体进行交叉，此方式保证了所有个体间基因的充分交流，但也会导致优秀基因不能拥有更多的交流，故本文在采用传统交叉方式的同时，还模拟生物界繁衍模式——首领的基因拥有更多的机会传递给下一代，在双亲遗传算子中采用全局最优个体与父代中任意个体交配的方式产生子代个体.
以文献[13]中算例为例分析各遗传算子在求解时间和质量上的差异(设置种群规模 pop_size=200，最大遗传代数M =100)，对各算子分别求解10次，求解结果如表1所示，在表1的基础上分别对求解时间和求解质量进行对比，对比结果如图4和5所示.由图可知，单亲遗传算子(算子1～4)的求解时间明显较短，而在各单亲遗传算子中，混合单亲遗传算子较单个单亲遗传算子的求解质量要高.双亲遗传算子(算子5～7)的求解时间较单亲遗传算子而言求解时间明显较长，在求解质量上，由于随机交叉算子(算子5)的目的在于种群内的基因充分交流，使得解保持多样性，而忽略了优秀个体的基因对后代解的质量的影响，致使获得解的质量最低；首领交叉算子(算子6)注重于种群中最优秀个体(首领)
表1 各遗传算子求解结果统计表
Tab.1 Results of various genetic operators
图4 各算子求解时间对比
Fig.4 Efficiency comparison of operators
图5 各算子求解质量对比
Fig.5 Solution quality comparison of operators
各级政府要高度重视，统一认识，建立健全相应的组织机构，加强领导。要做到责任明确，任务明确，人员明确，把防治干旱灾害工作落实到千家万户。各级有关部门要有超前意识，变被动抗旱为主动抗旱，坚持以防为主，防抗并举。各相关部门要认真组织落实各项有关措施，建立健全适应岩溶石区现代农业发展要求的抗旱服务体系，及时做好旱情的监测预报与分析汇报工作，同时建立一支能适应岩溶石山地区恶劣环境条件的防旱、抗旱专业化服务队伍，不断壮大防旱抗旱实力。
总体上看，以上这些修辞格的运用，这让歌曲在整体上产生和谐统一的特殊美感，“中国风味”的馥郁香气扑鼻而来。
4月14日青海玉树地震发生后，水利部部长陈雷迅速作出安排部署，要求认真贯彻落实胡锦涛总书记、温家宝总理、回良玉副总理重要指示精神，立即组成工作组赶赴灾区，会同青海省水利部门迅速查清震损水利工程情况，及时采取措施，排除险情，抓紧做好排险避险预案，切实防范地震次生灾害，确保震损水利工程安全度汛。
2.3 选择操作
遗传算法选择操作有轮盘赌、锦标赛以及精英策略等多种方法，本文采用精英策略与轮盘赌混合选择策略.对每代种群pop_size条染色体先进行扰动操作，产生包含C_pop_size条染色体的子代种群，首先通过精英策略选择适应度值最高的αn 条染色体，之后从其余的C_pop_size-αn 条子代种群中采用轮盘赌策略选取(1-α )n 条染色体，通过控制参数α 可以调节子代种群中精英个体和非精英个体的比例，从而实现深度搜索与广度搜索的平衡.α ∈[0,1]，且α 的值越大，种群中精英个体越多，则算法偏向于深度搜索；反之，则偏向于广度搜索.根据pop_size大小，一般α 取 0.05～0.15.
此外，在利用轮盘赌选择子代个体时，为防止较差解进入子代，本文用参数β 控制C_pop_size-αn 条染色体中参与轮盘赌的个体比例，平衡种群多样性与种群质量.β ∈(0,1]，且β 的值越大，参与轮盘赌的个体越多，种群多样性越好；反之，则参与轮盘赌的个体越少，种群中精英个体越多，种群质量越好.根据C_pop_size-αn 大小，一般β 取0.05～0.15.
文献[13]中3个配送中心及30个客户组成的配送网络规模适中，故以文献[13]中算例分析不同选择操作对解的影响，除选择方式不同外，所用算法其他部分完全一致，对各选择操作分别求解10次，求解结果如表2第2～4列所示，从表中可知，3种选择方式策略中，解的质量从高到低依次为本文的混合选择策略、精英+轮盘赌方式策略、轮盘赌方式策略，图6为3种选择方式策略10次求解算例的结果，由图6可知，采用轮盘赌方式策略获得的解整体质量较差，且解的波动程度较大；采用精英+轮盘赌方式策略获得的解虽然在质量上有所提升，但依然不够稳定，本文采用的选择方式策略则能获得较高质量的解，且解的稳定性较好.
表2 不同选择策略下的求解结果
Tab.2 Results under different selection strategies
图6 不同选择策略下的求解结果对比
Fig.6 Result comparison under different selection strategies
2.4 自适应搜索范围策略
由于群体在进化过程中，各阶段需要的进化压力不同.需要平衡搜索深度与搜索广度之间的关系，故本文除在选择算子中采用精英机制与轮盘赌相结合的策略以外，还构造了一种自适应搜索范围策略来进一步平衡此种关系：
(11)
(3) 反序算子(Inversion Operator).选择两个客户并将两客户间所夹客户进行反序.如图2(c)所示，选择线路A 上客户1与客户5，将所夹客户2～4进行反序形成线路A ′.
显然子代种群规模C_pop_size=N g pop_size.图7所示为相应的示意图.
图7 自适应搜索范围策略
Fig.7 Adaptive search range strategy
由图7可知，在进化初期，由于种群朝着适应度值高的方向进化速度较快，以扩大搜索广度为主，故扰动次数较少，在每个个体的附近搜索范围较小；但随着种群的进化速度越来越慢，搜索广度已不是制约进化速度的主要因素，搜索深度则对种群进化的影响越来越大，故扰动次数越来越多，在每个个体的附近搜索范围越来越大.通过对每个个体的潜在进化能力进行激发，促使其跳出局部最优解.
1.3.3 血浆胆汁酸检测 取血浆样本20 μL加入1.5 mL离心管中，再分别加入20 μL内标和1 mL PBS（pH=7.4的0.1 mol/L磷酸氢氨缓冲溶液），震荡混匀3 min后，10 000 r/min离心5 min，待用；依次往96孔固相萃取板加入1 mL甲醇，1 mL蒸馏水进行活化，将已经处理好的1 mL样本上样，再依次加入1 mL蒸馏水和1 mL甲醇进行样品洗脱，并收集洗脱液，60℃氮气吹干；使用100 μL甲醇复溶氮吹残渣，震荡混匀，转移至96孔进样板，采用LC-MS/MS检测；LC-MS/MS Analyst 1.5®工作站进行各胆汁酸成分的含量计算。
为分析本文所提自适应搜索范围策略的效果，仍以文献[13]中算例为例与固定搜索范围策略相对比，在对比之前，先给出以下命题及其证明：
命题 采用如式(11)所示的自适应搜索范围策略进行搜索时，当最大遗传代数较大时，平均每代搜索的次数主要取决于最小搜索范围和自适应搜索范围.
基因的遗传，故而在解的质量上有所提高；混合交叉算子(算子7)是对算子5～6的混合，综合考虑了不同双亲遗传算子中对解的质量与解的多样性的影响，求解质量进一步提高；本文算子(算子8)则综合采用了单亲遗传算子与双亲遗传算子的优势，在求解时间和求解质量取得一定的平衡，使得整体效果最佳.
工业革命及其带来的巨大变革是法国成人教育的第二个关键发展时期。从19世纪起，法国开始萌发职业教育和成人教育。受工业革命的影响，大多数劳动力迫切需要算术、写作和阅读方面的基本技能，以便适应新的工作方式和工作场所的持续变革。因此，催生了以职业为导向的成人基础教育。
证明 证明过程如下：
例如，泰戈尔在《飞鸟集》中的诗句：“鸟翼上系上了黄金，这鸟便永不能再在天上翱翔了。[7]”我们可以把它当作一个类比。
当M 趋向于无穷大时，
趋向于0，则
(12)
证毕
由上述证明可知，当M 较大时，平均每代迭代次数
主要取决于参数最小搜索范围r 1和自适应搜索范围r 2.自适应搜索范围策略中设置参数r 1=20，r 2=30；当精度要求不高时，根据式(12)有
故可设置固定搜索范围策略中每代的搜索范围
不同搜索策略分别进行10次计算，结果如表2后两列所示，由表2可知，采用自适应搜索范围策略能够更好地平衡搜索广度与搜索深度之间的关系.
（4）新生古储成藏模式主要是指孔三段火山岩油藏成藏模式，孔二段烃源灶生成的油气通过断层、不整合面运移到孔三段火山岩有利圈闭中聚集成藏，形成火山岩油藏。
3 实验与结果分析
实验1 为验证本文所提出混合遗传算法的有效性，采用文献[13]算例，以MATLAB R2012a为编译平台，在双核奔腾G2020/2.9 GHz微机上运行程序.实验数据如表3所示，实验参数设定如下：种群规模pop_size=40，最大遗传代数M =100，控制参数α =0.15、β =0.1，最小搜索范围r 1=30，自适应搜索范围r 2=50.
在边长为20 km的正方形区域内的配送网络中有3个配送中心和30个客户，其中每个客户的货物需求均不超过2 t，每个配送中心有4辆最大装载量为10 t的车辆，车辆单次配送的最大行驶路程均为50 km.文献[11-12]均采用先分组后路径的配送方式将多中心车辆路径问题转化为一般车辆路径问题，然后分区配送，这本质上是一种局部优化求解思想；而本文采用先路径后分组的配送方式对配送网络整体进行考虑，进行全局优化.已知该算例的目前最优解为 116.01，图8所示为本文算法求解得到的最优路径安排图(图中括号内为该客户点的需求量)，表4给出了本文的混合遗传算法对该算例进行20次重复求解结果与文献[11]中的禁忌搜索算法、文献[12]中的聚类分层算法以及文献[13]中的云量子遗传算法的对比.
由表4可以看出，本文设计的混合遗传算法求得的最优结果为 115.39，相比禁忌搜索算法求得的最优结果 177.53 提高了 35.00%，比聚类分层算法以及云量子遗传算法求得的最优结果也分别有着 6.44% 和 0.53% 的提高.通过对最优解、最劣解、平均解以及计算时间等各项性能参数的统计可以发现：本文算法与其他3种算法相比，在求解时间方面至少缩短20倍以上，求解时间降幅达 95.58%，虽然考虑到计算机硬件等因素的不同，但也是很大的提升；在算法稳定方面的提升也超过了20%.即本文算法相较于禁忌搜索算法、量子遗传算法以及云量子遗传算法，无论是在求解时间上还是在解的质量上都有着明显的改进，说明本文算法的求解时间更短、全局寻优能力更强、算法稳定性更好.
传统遗传算法的扰动算子主要包括交叉和变异，其中交叉算子模拟自然界有性繁殖，采用两个父代个体繁殖子代个体，对于整数编码的问题，简单随机交叉产生的子代个体很可能不再是原问题的可行解，故在VRP中常使用部分匹配交叉(Partially Mapped Crossover，PMX)、顺序交叉(Order Crossover，OX)等复杂交叉算子.单亲遗传的所有遗传操作均在一条染色体上完成，计算效率能够得到很大提升，但由于各个体间缺乏基因交流，易陷入“进化瓶颈”；而双亲遗传中子代则能够继承父代两个体的优良基因，遗传过程中父代基因得到充分的交流，有利于突破“进化瓶颈”，然而双亲遗传也存在一些缺陷，如计算效率较低等.针对单亲遗传与双亲遗传各自的特点，本文算法的扰动过程采用单亲遗传算子与双亲遗传算子相结合的方式.
在本节课的设计中，热身的两个小题，探究一和探究二中的第一、二小问都是比较基础的问题，绝大部分同学都能上手做一做，即便是比较难的问题，如探究一的两个开放性问题，为了降低起点，教者特意设计了示例，给学生搭建了脚手架，对基础特别薄弱的学生“牵着走”，基础一般的学生“扶着走”，基础较好的学生“跟着走”，比较优秀的学生“目送走”，特别优秀的学生“独立走”，做到全员参与，各有所获．
表3 客户需求信息
Tab.3 Information of customer demand
图8 最优路径
Fig.8 Optimal path
表4 算法性能对比分析
Tab.4 Contrastive analysis of algorithm performance
注：本文算法性能提升幅度是指本文算法性能比其他3种算法中性能最好的算法性能提升幅度.
表5 MDVRP标准算例实验结果对比
Tab.5 Comparison of the experimental results for MDVRP standard examples
图9给出了相应的迭代收敛图，由图9可知：对该算例约在40代左右找到最优解，说明本文算法能够在较少的遗传代数内找到问题的最优解，收敛速度快.此外， 从迭代收敛图还可看出，在30代左右，
图9 迭代收敛图
Fig.9 Iterative convergence graph
进化进入瓶颈，通过本文所设计的进化策略可以有效逃脱局部最优解.
实验2 为了进一步测试本文所提出算法的性能，从标准算例库(来源：http:∥neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-instances/)中下载MDVRP的相关数据，表5第2列给出了算例P01～P06共6个算例的相关信息，客户规模为50～100.由于客户规模不确定，故实验参数设定如下：种群规模pop_size=40，最大遗传代数M =300～1000，控制参数α =0.05～0.15、β =0.05～0.15，最小搜索范围r 1=30～50，自适应搜索范围r 2=70～170.
图10 标准算例最优路径图
Fig.10 Optimal path of standard examples
表5第4列至结束给出了本文算法与其他5种算法对比的结果，图10所示为本文求解的最优路径图.从遗传算法改进的角度来看，本文提出的混合遗传算法明显比文献[16]中基本遗传算法解的质量要高，由此可见本文所设计的混合遗传算法是有效的，能够整体提升传统遗传算法解的质量.与其他算法相比，虽然部分解的质量并不是最好，但整体求解效果较好，平均误差较其他算法更低，且在所有6个算例中有3个算例达到了已知的最优解，其他未达到最优解的3个算例求解结果与已知最优解的误差最大也不超过2.5%，表明本文所提出的混合遗传算法属于具有一定竞争力的算法.
4 结语
针对传统遗传算法求解MDVRP问题，本文设计了一种混合遗传算法.主要在以下几个方面进行了改进：
(1) 提出一种新的编解码方式，该编解码方式能够解决传统遗传算法编码方式对多中心车辆问题编解码时染色体长度不固定导致的计算效率低下问题.
“之前做民营企业的总有一些不安全感，通过这次座谈会的及时召开，税务部门落实优惠政策的力度和不断优化的贴心服务，不仅及时给了我们‘安全感’，还增强了企业不断发展的信心。”云南神农农业产业集团股份有限公司副总裁何乔关道出了许多在座民营企业家的感受。
在停机大修过程中，利用二回路几个腐蚀产物主要分布的设备，对核电站二回路系统运行过程中腐蚀程度的评估，以此评定电站在运行过程中，采用AVT（R）控制二回路水质效果的方法，很好地结合了大修腐蚀检查数据，更进一步反映了电厂控制水质的实际效果。且大修产生的腐蚀产物评价参数，可为电厂的老化管理评估，提供十分重要的参数，对核电站安全运行具有十分重要的意义。
(2) 扰动过程中使用单亲遗传算子以提高传统遗传算法的计算效率，使用双亲遗传算子以促使个体间的基因交流.
(3) 在选择操作中引入两个控制参数以平衡种群中精英数量与种群多样性间的冲突；并设计一种自适应搜索范围策略，利用该策略可以有效平衡搜索深度与搜索广度间的关系.
通过测试算例并与其他文献进行对比，本文算法将实验1中的测试算例已知最优解提升了 0.53%，验证了本文算法的有效性；并通过实验2对6个不同标准MDVRP算例进行求解与对比，结果证明本文所设计的混合遗传算法能够对MDVRP进行有效的求解.
由患者因素的认知程度结果显示，医护人员对于患者接受手术与疾病对于血糖准确值的影响有较高的认知，临床科室或可考虑将该科室可能影响血糖值的疾病与手术方式做更紧密的血糖监测及更多的循证支持。
本文研究为求解多中心车辆路径问题这一组合优化难题提供了一种新思路，同时也为采用联合配送模式的企业进行配送方案决策提供一定的参考. 限于篇幅及精力，本文还存在一些不足，未来将从联合配送的时效性及算法的收敛速度两方面着手做进一步研究.
参考文献：
[1] ALLAHYARI S, SALARI M, VIGO D. A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem[J]. European Journal of Operational Research , 2015, 242(3): 756-768.
[2] DE OLIVEIRA F B, ENAYATIFAR R, SADAEI H J, et al . A cooperative coevolutionary algorithm for the multi-depot vehicle routing problem[J]. Expert Systems with Applications , 2016, 43: 117-130.
[3] JABIR E, PANICKER V V, SRIDHARAN R. Design and development of a hybrid ant colony-variable neighbourhood search algorithm for a multi-depot green vehicle routing problem[J]. Transportation Research Part D :Transport and Environment , 2017, 57: 422-457.
[4] ZHOU L, BALDACCI R, VIGO D, et al . A multi-depot two-echelon vehicle routing problem with deli-very options arising in the last mile distribution[J]. European Journal of Operational Research , 2018, 265(2): 765-778.
[5] SALHI S, IMRAN A, WASSAN N A. The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation[J]. Computers &Operations Research , 2014, 52: 315-325.
[6] 葛显龙, 许茂增, 王伟鑫. 多车型车辆路径问题的量子遗传算法研究[J]. 中国管理科学 , 2013, 21(1): 125-133.
GE Xianlong, XU Maozeng, WANG Weixin. Study on multi-types vehicle routing problem and its quantum genetic algorithm[J]. Chinese Journal of Management Science , 2013, 21(1): 125-133.
[7] MANCINI S. A real-life multi depot multi period vehicle routing problem with a heterogeneous fleet: Formulation and adaptive large neighborhood search based matheuristic[J]. Transportation Research Part C Emerging Technologies , 2016, 70: 100-112.
[8] 刘家利, 马祖军. 存在车辆租赁及共享且有时间窗的多配送中心开环VRP[J]. 系统工程理论与实践 , 2013, 33(3): 666-675.
LIU Jiali, MA Zujun. Multi-depot open vehicle routing problem with time windows based on vehicle leasing and sharing[J]. Systems Engineering :Theory &Practice , 2013, 33(3): 666-675.
[9] LI J, PARDALOS P M, SUN H, et al . Iterated local search embedded adaptive neighborhood selection approach for the multi-depot vehicle routing problem with simultaneous deliveries and pickups[J]. Expert Systems with Applications , 2015, 42(7): 3551-3561.
[10] KACHITVICHYANUKUL V, SOMBUNTHAM P, KUNNAPAPDEELERT S.Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO[J]. Computers &Industrial Engineering , 2015, 89: 125-136.
[11] 郎茂祥. 多配送中心车辆调度问题的模型与算法研究[J]. 交通运输系统工程与信息 , 2006, 6(5): 65-69.
LANG Maoxiang. Study on the model and algorithm for multi-depot vehicle scheduling problem[J]. Journal of Transportation Systems Engineering and Information Technology , 2006, 6(5): 65-69.
[12] 殷脂, 叶春明. 多配送中心物流配送车辆调度问题的分层算法模型[J]. 系统管理学报 , 2014, 23(4): 602-606.
YIN Zhi, YE Chunming. Study on the hierarchical model for multi-depot logistic vehicle scheduling problem[J]. Journal of Systems &Management , 2014, 23(4): 602-606.
[13] 葛显龙, 许茂增, 王伟鑫. 基于联合配送的城市物流配送路径优化[J]. 控制与决策 , 2016, 31(3): 503-512.
GE Xianlong, XU Maozeng, WANG Weixin. Route optimization of urban logistics in joint distribution[J]. Control and Decision , 2016, 31(3): 503-512.
[14] VILLEGAS J G, PRINS C, PRODHON C, et al . GRASP/VND and multi-start evolutionary local search for the single truck and trailer routing problem with satellite depots[J]. Engineering Applications of Artificial Intelligence , 2010, 23(5): 780-794.
[15] THANGIAH S R, SALHI S. Genetic clustering: An adaptive heuristic for the multidepot vehicle routing problem[J]. Applied Artificial Intelligence , 2001, 15(4): 361-383.
[16] KARAKATI
S, PODGORELEC V. A survey of genetic algorithms for solving multi depot vehicle routing problem[J]. Applied Soft Computing , 2015, 27: 519-532.
[17] STODOLA P, MAZAL J, PODHOREC M. Improving the ant colony optimization algorithm for the multi-depot vehicle routing problem and its application[C]∥1st International Workshop on Modelling and Simulation for Autonomous Systems . Rome, Italy: Springer, 2014: 376-385.
[18] TLILI T, KRICHEN S, DRIRA G, et al . On solving the multi-depot vehicle routing problem[C]∥3rd International Conference on Advanced Computing ,Networking and Informatics . India: Springer, 2016: 103-108.
Hybrid Genetic Algorithm for Solving Multi -Depot Joint Distribution Routing Problem
FAN Houming a,b,XU Zhenlin a,b,LI Yang a,LIU Wenqi a,GENG Jing a
(a. College of Transportation Engineering； b. Institute of Strategy Management and System Planning, Dalian Maritime University, Dalian 116026, Liaoning, China)
Abstract ： There are problems of traditional genetic algorithm in solving multi-depot vehicle routing problem. First, variable chromosome length produced by conventional coding techniques leads to low computation efficiency and easily produces infeasible solutions. Second, parental genetic operators have less efficient during perturbation. And it is difficult to balance the relationship between elite proportion and population diversity, search depth and search breadth in different evolutionary populations. This paper designs a hybrid genetic algorithm to solve the problem, and the distribution network information is separately expressed in the encoding and decoding method to improve the computational efficiency. The control parameters of balanced elite ratio and population diversity are introduced in the selection operation. In addition, an adaptive search range strategy is proposed to effectively balance the relationship in both search depth and breadth. Through experimental results and comparative analysis, the proposed algorithm is verified. The research results provide a new method to solve the multi-depot vehicle routing problem and can also provide guidance for related logistics distribution decisions.
Key words ： joint distribution; multi-depot vehicle routing problem; hybrid genetic algorithm; adaptive search range strategy
收稿日期： 2017-12-12
基金项目： 国家自然科学基金资助项目(61473053)，辽宁省社会科学规划基金重点项目(L16AGL004)，大连市科学技术计划项目(2015D12ZC181)
作者简介：
范厚明(1962-)，男，山东省蓬莱市人，教授，博士生导师，主要从事交通运输规划与管理等研究.
电话(Tel.)：0411-84725868；E-mail：fhm468@163.com.
文章编号： 1006-2467(2019)08-1000-10
DOI: 10.16183/j.cnki.jsjtu.2019.08.016
中图分类号： TP 18
文献标志码： A
(本文编辑：黄伟)
标签：联合配送论文; 多中心车辆路径问题论文; 混合遗传算法论文; 自适应搜索范围策略论文; 大连海事大学交通运输工程学院论文; 大连海事大学战略管理与系统规划研究所论文;