一种求解多车型CARP问题的高效进化算法

多车场多车型车辆路径问题的优化研究作者：朱晨晨来源：《企业科技与发展》2021年第02期【摘要】针对多车场多车型车辆路径问题，通过建立虚拟配送中心将多车场路径优化问题转化为单一车场路径优化问题。

文章建立了数学模型并利用遗传算法求解模型，同时根据问题性质对遗传算法的编码和解码方式进行改进。

基于企业实例的实证研究表明：文章提出的模型对求解多车场多车型车辆路径问题具有一定的优势，能够为企业实际的物流运输调度提供决策支持。

【关键词】多车场;多车型;遗传算法自1959年车辆路径问题（Vehicle Routing Problem，VRP）被Dantzig和Ramser[1]在文献中首次提出以来，越来越多的研究投入该领域[2]。

随着现代物流运输的发展，车辆路径问题及其变体的研究越来越深入，它描述的是在一个连通网络中拥有配送中心和客户两类节点，车辆需要从配送中心出发，在满足客户需求和实现优化目标的前提下，按照一定的行车路线将货物交付到客户手中。

货物从制造工厂或者配送中心通过运输网络流向消费者的这一过程中，运输路线是否合理对成本、效率至关重要。

经典VRP的诸多变体包括具有硬、软和模糊的服务时间窗口、客户同时具有取货和交付需求等。

多车场多车型车辆路径问题是在经典VRP的基础上添加了“多车场”和“多车型”两类约束，更加符合现实的物流配送情况，同时使得NP-hard的问题求解难度进一步加大。

1 文献综述多车场多车型车辆路径问题（Multi-Depot Vehicle Ro-uting Problem with a Heterous Fleet，MDHFVRP），是VRP问题的变体之一。

由于VRP为NP-hard难题，多车场和多车型的出现又提升了问题的求解难度。

多数学者采用启发式算法求解MDHFVRP。

例如，Cassidy等人[3]在1972年提出了求解MDHFVRP的迭代算法，他们的研究基于学校送餐的实际案例，该案例拥有600所学校、300个配送中心和100辆异质车队，该算法通过对随机的初始解不断迭代从而改进解的质量，从而实现减少车辆运输时间以尽快配送的优化目标;Wren等人[4]同样提出了迭代算法求解MDHFVRP，初始解依据节约里程法生成，在他们的方案中，算法会根据客户的优先级来满足客户需求;Saihi等人[5]在1997年引入多级启发式方法，在第一阶段利用边界客户建立初步可行解，第二阶段利用局部搜索策略对初始可行解进行改进，该方法被证明在拥有360个客户的大规模问题中具有较好的应用性能;A Willian Ho等人[6]通过两阶段方法求解，算法的第一阶段考虑随机生成的初始解，第二阶段通过最近邻启发式算法和节约里程法找到初始种群，在不同实例上的计算表明了该算法具有良好性能。

课程设计报告设计题目：基于进化算法的车辆路径问题求解学院：电子工程学院专业：电子信息工程班级： 020915 学号：学生姓名：电子邮件：时间： 20012年9月成绩：指导教师：刘静西 安 电 子 科 技 大 学 电 子 工 程 学 院 课 程 设 计（报告）任 务 书 学生姓名 指导教师 职称 教授 学生学号 专业 电子信息工程 题目 基于进化算法的车辆路径问题求解 任务与要求 了解进化算法（Evolutionary Algorithms ），介绍其基本思想、主要分支于基本流程。

了解车辆路径问题（Vehicle RoutingProblems ），介绍其基本分类、各类问题的具体模型与异同点。

最后给出一种进化算法求解某类车辆路径问题的基本方法。

开始日期 2012 年 8 月 27 日 完成日期 2012年 9 月 7 日 课程设计所在单位 智能信息处理所研究所 2102年 9月 7 日…………………………装………………………………订………………………………线………………………………………………………………摘要随着社会主义市场经济的发展，作为“第三利润源泉”的物流对经济活动的影响日益明显，物流配送业得到了迅速发展。

物流车辆路径优化调度，是物流配送中的关键环节，对企业提高服务质量、降低物流成本、增加经济效益的影响也较大。

在现实生产和生活中，邮政投递问题、公共汽车调度问题、电力调度问题、管道铺设问题、机器人路径规划、计算机网络拓扑设计问题等都可以抽象为物流配送车辆调度问题。

物流配送车辆路径调度问题作为一个NP难题，可选的配送路径方案计算量将随着客户数量的增加以指数速度急剧增长。

进化算法是基于生物进化机制的搜索算法，适合于求解复杂系统优化问题，特别是组合优化问题有明显的优势。

因此，用进化算法求解该问题就成为人们研究的一个重要方向。

本文在对国内外物流配送车辆调度现状及其实现技术对比的基础上，结合vRP(vehieleRoutingProblem)问题模型，研究了进化算法解决车辆路径问题的方法，并开发了基于进化算法的智能物流配送系统。

多起始点进化算法在容量约束弧路径问题上的应用林丹;梁桉洋【摘要】容量约束弧路径问题(CARP)是一类NP难的组合优化问题,通常采用启发式算法求解,计算时间较长.本文在竞争模因算法基础上采用多点同时搜索,构造了多点进化算法(MSEA).算法由多个初始解开始,同时进行局部搜索与遗传进化,再将结果合并,得到最终的解.在29个基准数据集上的数值试验表明,该算法可行有效,并可以节省大量计算时间.【期刊名称】《天津理工大学学报》【年(卷),期】2015(031)003【总页数】6页(P59-64)【关键词】容量约束孤路径问题;组合优化;进化算法;局部搜索【作者】林丹;梁桉洋【作者单位】天津大学理学院,天津300072;天津大学理学院,天津300072【正文语种】中文【中图分类】O229容量约束弧路径问题（CARP）可以描述如下[1]：在一个连通加权图G=（V，E）中，其中顶点集V={v0，v1，…，vn}，边集E={[vi，vj]∶vi，vj∈V，i＜j}，每一个边的权重为Ce且包含一个非负的需求量De.顶点v0代表车场，有一列容量限制为W的车队，W≥max{De，e∈E}，从车场v0出发，车队的车辆数N是一个决策变量.此外，每一个De＞0的边称为需求边，需要被车辆服务.问题的目标是寻找到总权重最小的路径并满足下列条件：1）每辆车从车场出发并最终到达车场.2）每一个需求边都必须被一辆且仅被一辆车服务.3）每辆车服务的总量不能超过它的容量W.CARP的求解一般采用启发式算法进行[2].近年来，出现了求解CARP的多个启发式算法，包括Hertz等人提出的禁忌搜索算法[3]，Polacek等人提出的变邻域算法[4-5]，Beullens等人提出的导向局部搜索算法[6]， Lacomme提出的竞争模因算法[7]，以及Santos等人提出的蚁群算法[8]等.竞争模因算法（Competitive Memetic Algorithm，CMA）是结合了局部搜索算法和遗传算法的一种启发式算法.在该算法中，局部搜索算法在搜索过程中需要进行大量的移动与交换，在搜索过程中耗时较长；同样，遗传算法也需要种群间大量交叉和变异以完成逐代进化，也较为费时.本文旨在通过多点同时交叉搜索以降低算法的计算时间，提高算法的效率.这部分给出了CARP的一个实例，对CARP问题进行说明，并列出了这个实例的一组解.图1描述了由DeArmon提供的CARP标准测试集[9]中的例子kshs4.该问题共包含8个顶点和15个服务边，其中点1表示车场，共含4辆容量限制为150的车辆，各个任务边权重（花费）与需求量在右侧的列表中列举.由CARP问题的描述可知，问题需要找到4条从顶点1出发并且最终回到该顶点的最短环路，这些环路涵盖了所有服务边，且每条环路上服务的总量不超过车辆容量.根据这些条件，表1中给出了该问题的一组可行解.需要注意的是，CARP解的每条路径可以仅通过车辆服务的边表示，也可以通过组成该路径的全部边表示.在表的第一列，使用第一种表示方式，组成解的边集中只出现服务边，不出现路过边.也可以将路径扩展为全路径，即将车辆在服务过程中通过的所有路径均予以显示，如表1中第2列所示，路径1用全部边表示为：3-5 4 7-2，用顶点表示为：1 7 2 3 5 1.2.1 局部搜索算法局部搜索算法[6，10-11]从一个初始解开始，在搜索过程中定义若干种邻域移动方式，通过邻域移动使得解在解空间中的进行搜索，在搜索过程中，如果找到更优的解则移动至该解并继续执行搜索.局部搜索算法易于实现，但容易陷入局部最优，并且局部搜索得到的解的质量与初始解的位置与定义的邻域移动方式（邻域结构）密切相关.常用的基于局部搜索的算法主要有模拟退火，禁忌搜索法，迭代局部搜素算法等.这类改进的局部搜索算法主要通过改变解的邻域结构以及接收劣解等方式实现解在解空间中的跳跃，从而避免了过早的陷入局部最优.在表2列出了局部搜索算法主要的搜索结构.开始时，局部搜索算法使用某种元启发式算法生成起始解并定义几种移动策略.在主循环中，该算法通过几种移动方式交替进行的方式来寻找到解Snew，若Snew满足接受条件#，则移动至该解并更新最优解S*，直到满足终止条件.2.2 竞争模因算法竞争模因算法是一类种群进化算法[12-14]，是种群遗传与个体自进化算法的结合，主要包含了局部搜索算法和遗传算法.在算法开始阶段，先经由一些启发式算法生成初始的种群，然后进入主循环，每次循环时先计算每个个体的适应值，然后选择其中的个体进行交叉并进行局部搜索，用得到的子代替换掉种群中的一些个体.反复执行，直到达到问题下界或最大迭代次数等终止条件.表3给出了该算法流程的伪代码.竞争模因算法在求解过程中每次只能得到一组可行解，这限制其计算速度.为提高运算效率，文中算法通过启发式算法生成多个起始种群，从这些起始点同时进行交叉与局部搜索，最后将得到的结果合并，从而构造出了求解CARP问题的多点进化算法（Multi-Start Evolutionary Algorithm，MSEA）.3.1 算法结构多点进化算法中也引入了一些其它算法，例如，算法通过RS、EPS两种启发式算法生成初始种群，父代采用LOX交叉算法[15]形成子代.MSEA算法由以下4个主要步骤组成.1）生成初始解：两种不同的方法被用来形成初始解的集合，形成多个初始种群. 2）遗传交叉策略：分别在多个种群上使用LOX算法得到子代，通过优胜劣汰生成最终的子代种群.3）局部搜索：在交叉完成后，每个种群以概率p进行局部搜索得到局部最优解. 4）替换与循环：随机的将种群中较差的50%中的一个替换为新生成的个体.然后重复2～4步直到最大迭代步长或得到最优解达到问题下界.3.2 种群初始化如表4所示，初始解通过下面的两种启发式算法生成.这里，规定种群大小为30，每次生成的初始解必须满足CARP的容量限制条件.此外，为了保持种群多样化，初始种群需保证每个个体适应值不同.随机选择算法（RS）：RS算法一次构造一辆车的路径，在构造过程中，每次从满足约束条件中的边集中随机选取一条边加入当前路径，只有未经服务的边才予以考虑，当没有满足条件的边，则开始构造下一条路径.路径扩展算法（EPS）：EPS算法一次构造一辆车的路径，令Q是一个按一定顺序排列的未经服务的需求边队列，每条路径从车场开始，将Q中的边依次加入路径，直到超过容量限制后开始构造下一条边，直到所有边全部加入为止，其中，队列Q采用以下5种排序策略：1）最大化当前边与车场的距离；2）最小化这一距离；3）使车辆路径花费与车辆容量的比值De/We最大化；4）最小化上述比值；5）当车辆容量没有超过其容积的一半时，使用规则1），否则使用规则2）.3.3 交叉策略在交叉之前算法先将每组解进行编码.首先，将每条路径编码并合并成一条长的基因序列，如表1中kshs4问题的解可以编码为-5 4 7-2 1-6-11-13 14 10-15 3-12 8-9.其次，算法使用构成CARP问题的图G的总边数τ加上边e的编号表示边e的反向边，最终该解可以编码为20 4 7 17 1 21 26 28 14 10 30 3 27 8 24.在遗传进化过程中使用LOX交叉策略，关于LOX在路径问题上的应用的可以参见文献[7].令P1和P2是包含有Ne个需求边的父代基因组，为了得到子代C，将父代编码为两条链，链上的每个元素表示一条服务边，然后从两条链中随机的选择两个切点位置p和q，首先使用P1（p），…，P1（q）填充到C（p），…，C（q）中，同时使用数组m进行标记，最后将P2复制到C（1），…，C（p-1）和C（q+1），…，C（Ne）中，这里，只有在m中未标记的边e才能被选择.表5是关于LOX的详细过程.在LOX交叉算法完成后，得到的是一条长的基因子代，需要使用Ulusoy切割算法[16]将得到的子代进行解码，以便进行局部搜索.3.4 局部搜索种群交叉完毕并且解码后，再对子代以概率p进行局部搜索，搜索过程中，算法使用了四种局部搜索的移动策略，这些移动方式在本段段末予以列举.搜素过程中，算法采取First-Move的方式更新解，即在每次搜索的迭代过程中，将得到的第一组改进解作为当前搜索结果.算法将这些搜索策略放在一个循环中，一旦解被改进，就将改进解作为当前解继续搜索，直到没有改进为止.为了加速计算，算法采取了矩阵标记法避免重复搜索，在搜索过程中，算法使用矩阵Mk记录搜索过的路径，其中，Mkij表示在边ei与ej上的第k个移动，矩阵Mkij被初始为0.如果定义在ei与ej上的第k种移动已完成且没有改进，将Mkij置为1，若得到改进解，就移动到新解并将矩阵Mk的第i、j行与第i、j列全部置0.当Mkij全为1时，标志着局部搜索的结束.Move 1：反向操作，将任务边e用任务边的反向边rev（e）取代.Move 2：交换操作，将两个任务边ei和ej或者各自的反向边进行交换.Move 3：插入操作，将一个边从当前位置移除，重新插入到路径中的另一个位置. Move 4：2-opt操作，将两个相邻边与另一对不属于当前路线的一对边进行交换，或者将两条边反向后再交换.3.5 多起始点进化算法结构为了简化编码，在算法的预处理阶段，使用邻接矩阵Dij表示有向图G，然后通过Dijkstra′s算法计算出每对边ei和ej间的最短路径，储存在矩阵Dij中，对每个CARP实例，这个矩阵Dij是固定不变的，在多次求解过程中，只需计算一次.此外，算法用一个包含需求边的链表表示车辆路径，默认的链表中的相邻需求边间的路径长度采用最短路径计算.对前面的几个部分进行总结，从而形成表6中的多起始点进化算法，算法使用多处理器同时完成种群进化.表中使用in parallel表示需要并行处理的部分，用reduce表示将结果归并.主函数包含4个参数值，分别表示最大迭代次数，解的下界，种群大小以及局部搜索概率.MSEA算法采用C++进行编程实现，并行部分通过POSIX线程库实现，程序在带有Core i5 3230M处理器的双核4线程PC机上运行，在CARP基准测试集中的29个实例上对算法进行测试，测试集可从www.uv.es/～belengue/carp.html处下载.测试时算法中主要参数取值如下：种群大小30，局部搜索概率0.2，最大代数50 000，各问题下界出自文献[18].表2中给出了多起始点进化算法（MSEA）与交叉迭代搜索算法（Crossover Iterated Local Search，COILS）的比较数据，最终的数据值是10次运行的平均结果.表7中前3列显示了问题名称以及问题的规模，之后给出了每个问题的下界值，第5列是这类问题当今的最好解的值，该值出自文献[19].最后给出了文中的MSEA算法与的CMA、COILS两算法的最优的结果比较，其中CMA的运算时间由文献[7]给出，该时间仅包含了进化时间.COILS运算时间是取多次计算的平均结果，该结果取自文献[20].在29个问题上的数据实验显示，文中算法可以求得所有的当今最好解，并且与COILS算法比较，计算时间得到了很大程度上的提升，平均计算时间由4.31 s提升至1.72 s，最差时间由68.6 s上升至16.3s，在gdb8、gdb23等问题上计算时间的提升尤为突出.这是因为，算法将遗传进化扩展成多起始种群间先进化再归并的步骤，使得种群进化可以同时以不同位置进行，与原算法相比，仅需要在初始阶段产生种群和最终的归并产生结果时付出少量的时间代价后就能得到很大程度的运算规模降低，这使得算法的总运算时间有了明显的改进.文中阐述的多起始点进化算法是一种使用多线程编程方式来完成种群进化的元启发式算法.实验表明，MSEA算法能够很好的解决CARP问题且可节省运算时间.今后的工作可以将该算法进行改造与推广，以用于求解其他组合优化问题，并在大型集群上对该算法进行测试，此外，随着待解决问题规模的加大，运输业的发展，这类算法也将得到更大更广的应用.【相关文献】［1］Golden B L，Wong R T.Capacitated arc routing problems［J］.Networks，1981，11（3）：305-310.［2］Dror M.Arc routing，theory，solutions and applications［M］. New York：Springer Verlag，2000.［3］Hertz A，Laporte G，Mittaz M.A tabu search heuristic for the capacitated arc routing problem［J］.Operations Research，2000，48（1）：129-135.［4］Polacek M，Doerner K F，Hartl R F，et al.A variable neighborhood search for thecapacitated arc routing problem with intermediate facilities［J］.Journal of Heuristics，2008，14（5）：405-423.［5］Hertz A，Mittaz M.A variable neighborhood descent algorithm for the undirected capacitated arc routing problem［J］. Transportation Science，2001，35（4）：425-434. ［6］Beullens P，Muyldermans L，Cattrysse D，et al.A guided local search heuristic for the capacitated arc routing problem［J］.European Journal of Operational Research，2003，147（3）：629-643.［7］Lacomme P，Prins C，Ramdane-Cherif petitive memetic algorithms for arc routing problems［J］.Annals of Operations Research，2004，131（1）：159-185. ［8］Santos L，Coutinho-Rodrigues J，Current J R.An improved ant colony optimization based algorithm for the capacitated arc routing problem［J］.Transportation Research Part B：Methodological，2010，44（2）：246-266.［9］Golden B L，DeArmon J，Baker E putational experiments with algorithms for a class of routing problems［J］. Computers and Operations Research，1983，10（1）：47-59.［10］Brandao J，Eglese R.A deterministic tabu search algorithm for the capacitated arc routing problem［J］.Computers and Operations Research，2008，35（4）：1112-1126. ［11］Lourenco H R，Martin O C，Stutzle T.Iterated local search［M］//Gendreau M，Potvin J Y.Handbook of Meta-heuristics.Heidelberg：Springer，2002：321-353.［12］Moscato P.On evolution，search，optimization，genetic algorithms and martial arts：towards memetic algorithms［R］.Pasadena，USA：California Institute of Technology，Caltech Concurrent Computation Program，1989.［13］Grard F，Lacomme P，Prins C.Evolutionary algorithm for stochastic arc routing problems［J］.Applications of Evolutionary Computing，2004，3005：501-512.［14］Handa H，Lin D，Chapman L，et al.Robust solution of salting route optimization using evolutionary algorithms［C］// IEEECongress：EvolutionaryComputation2006.Vancouver，Canada：CEC，2006.［15］Lacomme P，Prins C，Senaux M.A genetic algorithm for a bi-objective capacitated arc routing problem［J］.Computers and Operations Research，2006，33（12）：3473-3493.［16］Ulusoy G.The fleet size and mix problem for capacitated arc routing［J］.EuropeanJournalofOperationalResearch，1985，22（3）：329-337.［17］Tang K，Mei Y，Yao X.Memetic algorithm with extended neighborhood search for capacitated arc routing problems［J］.IEEETransactionsonEvolutionaryComputation，2009，13（5）：1151-1166.［18］Bartolini E，Cordeau J F，Laporte G.Improved lower bounds and exact algorithm for the capacitated arc routing problem［J］.Mathematical Programming，2013，137（1）：409-452.［19］Santos L，Coutinho-Rodrigues J.An improved heuristic for the capacitated arc routing problem［J］.Computers and Operations Research，2009，36（9）：2632-2637. ［20］Liang A Y，Lin D.Crossover iterated local search for SDCARP［J］.Journal of the Operations Research Society of China，2014，2（3）：351-367.。

多种群协同进化的并行遗传算法多种群协同进化并行遗传算法（Multi-population Cooperative Coevolutionary Parallel Genetic Algorithm, MCCPGA）是一种基于群体协作的进化算法，通过将一个大问题分解为多个子任务，并使用多个种群并行地进行进化，以提高算法效率。

本文将对多种群协同进化并行遗传算法的原理、优点以及应用进行详细介绍。

首先，多种群协同进化并行遗传算法的基本原理是将一个大问题分解成多个子任务，每个子任务由一个种群独立进化。

不同子任务之间通过共享信息交流、协作进化来改善效果。

算法的基本步骤为：初始化多个种群，每个种群为一个子任务的解空间；进行进化操作，包括选择、交叉、变异等；定期进行群体间信息交流，如共享精英个体、最优个体传递等；直到满足终止条件为止。

多种群协同进化并行遗传算法具有以下几个优点。

首先，通过并行计算，同时进行多个种群的进化，加快了算法的速度和收敛速度。

其次，多种群之间的信息交流可以引入不同种群的优势，提高了群体的多样性和整体的能力。

此外，不同子任务的粒度可以根据问题的特点进行调整，灵活性较高，适用范围广。

多种群协同进化并行遗传算法已经在多个领域得到了广泛应用。

例如，在优化问题中，可以将每个种群看作是一个决策变量的子集，通过不同种群的协作进化来求解全局最优解。

在机器学习中，不同种群可以分别学习不同任务的特征，通过信息交流来提高整体的分类准确率。

在智能控制中，可以构建多个控制子系统，通过种群之间的协同来优化整体的控制性能。

总而言之，多种群协同进化并行遗传算法是一种通过多个种群的协作进化来求解复杂问题的进化算法。

通过并行计算和信息交流，该算法能够加快速度、提高能力，已经在优化问题、机器学习、智能控制等领域取得了良好的效果。

未来，随着计算力的提升和算法的改进，多种群协同进化并行遗传算法有望在更多的应用领域发挥重要作用。

CARP问题混代并行遗传算法的研究
陈未如;马超;王翠青
【期刊名称】《沈阳化工大学学报》
【年(卷),期】2013(027)004
【摘要】遗传算法因为具有直接对结构对象进行操作、具有内在的隐并行性和更好的全局寻优能力、自适应地调整搜索方向等优点,已被人们广泛地应用于组合优化、函数优化、机器人学、信号处理等领域.但是随着传统遗传算法暴露出来的收敛速度慢且具有最优值无趣的缺陷等缺点,并行遗传算法得到了广泛的研究与发展.本文在现有CARP遗传算法基础上进行并行性改进,提出并实现全新的并行遗传算法——混代并行遗传算法(MGPGA算法),理论分析及实验结果表明:并行遗传算法较非并行遗传算法有更快的求解速度,混代并行遗传算法可行且更有效.
【总页数】7页(P364-370)
【作者】陈未如;马超;王翠青
【作者单位】沈阳化工大学计算机科学与技术学院,辽宁沈阳110142;沈阳化工大学计算机科学与技术学院,辽宁沈阳110142;沈阳化工大学计算机科学与技术学院,辽宁沈阳110142
【正文语种】中文
【中图分类】TP301
【相关文献】
1.基于多群体并行遗传算法的混流混合车间模糊调度研究 [J], 胡恒;鲁建厦;李英德
2.CARP问题混代并行遗传算法的研究 [J], 陈未如;马超;王翠青;
3.基于MapReduce和并行遗传算法的大数据聚类问题研究 [J], 郭晨晨;朱红康
4.CARP问题的构造型启发式算法研究 [J], 李庆华;林丹
5.基于粗粒度并行遗传算法的车间制造单元构建问题的研究 [J], 周正一
因版权原因，仅展示原文概要，查看原文内容请购买。

求解车辆路径问题的协同进化遗传算法作者：姚卫粉来源：《软件导刊》2015年第01期摘要：通过对车辆路径问题的分析，建立车辆路径问题数学模型。

针对遗传算法优化车辆路径问题易陷入局部最优解以及收敛速度慢等问题，引入基于动态小生境的协同进化模型。

最后，将动态小生境协同进化算法应用于所建立的模型中。

实验结果表明：动态小生境协同进化遗传算法可有效避免遗传算法的早熟现象，并在一定程度上提高优化车辆路径问题的求解效率。

关键词：车辆路径问题；协同进化遗传算法；动态小生境；早熟DOIDOI：10.11907/rjdk.143490中图分类号：TP312文献标识码：A 文章编号文章编号：16727800（2015）0010057020 引言车辆路径问题（Vehicle Routing Problem，VRP）由Dantzig 和Ramser[1]于1959年第一次提出。

该问题是指在客户需求位置已知的情况下，确定车辆在各客户间的行程路线，然后使得车辆路线最短或运输成本最低。

车辆路径问题是个NP难题，在寻找满足约束条件最优解的过程中，需要很大的设计空间。

设计空间是多维而非连续的，所以用来系统的搜索整个空间的规范搜索集很难找到，导致很难得到全局最优解。

关于车辆路径问题的优化算法大致可以分为两类，一类是精确算法，另一类是启发式算法。

目前，针对车辆路径问题，主要采用启发式算法。

比如，树状搜寻法[2]、节省法[3]、扫描法[4]、遗传算法[5]等。

由于精确算法难以用于求解复杂的车辆路径问题，而启发式算法也只是基于直观或经验构造的算法，所以只能求出问题的某一特殊类型或者是规模较小时的近似最优解。

由于这些问题的存在，本文将基于动态小生境的协同进化遗传算法引入到车辆路径问题中，从而更好地解决车辆路径优化问题。

1 车辆路径问题数学模型对于单配送中心问题，设配送中心共有N个客户，1个中心仓库，K辆车。

每个客户的需求量和时间窗都有固定的限制，且均只被某辆车服务一次，每辆车只服务于一条路径。

多车场CARP问题的改进遗传算法求解
李小花;朱征宇;夏梦霜
【期刊名称】《计算机工程与应用》
【年(卷),期】2009(45)11
【摘要】带有容量限制的弧路径规划问题来源于城市垃圾回收、街道清扫、邮件投递、校车路线安排和洒水车路线安排等实际问题.多车场CARP问题是具有多个车场的CARP问题.提出了一种先划分区域后进行路径规划的方法来求解多车场CARP问题.该方法先将各服务弧按照离车场距离的远近归并到距离最近的车场,从而转化为单车场CARP问题,然后用改进的遗传算法进行求解;在求解过程中,用模拟退火算法对部分服务弧进行局部调整,使服务弧在一定的范围内在不同的车场之问进行调换,从而避免局部收敛,达到全局优化的效果.以洒水车路线安排为实例,实验结果表明,该算法能有效求解一定规模的多车场CARP问题,为实际应用奠定了基础.【总页数】5页(P230-234)
【作者】李小花;朱征宇;夏梦霜
【作者单位】重庆大学,计算机学院,重庆400044;重庆大学,计算机学院,重庆400044;重庆大学,计算机学院,重庆400044
【正文语种】中文
【中图分类】TP301.6;N945.15
【相关文献】
1.求解CARP-RP-ML问题的改进算法 [J], 胡珊;林丹
2.单车场多送货点车辆路径问题的改进遗传算法 [J], 屈援;汪波;钟石泉
3.多车场多车型车辆路径问题的改进遗传算法 [J], 杨元峰
4.求解CARP车场选址问题的混合随机搜索算法 [J], 刘琳;朱征宇;许林;陈飞
5.求解双层CARP优化问题的演化学习型遗传算法 [J], 邢立宁;姚锋
因版权原因，仅展示原文概要，查看原文内容请购买。

一种求解多车型CARP的有效memetic算法张玉州;刘晓飞;黄师化;梅俊【期刊名称】《中国科学技术大学学报》【年(卷),期】2017(047)007【摘要】In view of wider application background,heterogeneous vehicle capacitated arc routing problem (HVCARP)and approach for it are investigated in this paper.First,the cost of any route in HVCARP is divided into two parts,i.e.,variable cost and fixed cost,and penalty coefficients for vehicles keep the routes and their vehicles close.In view of the characteristic of HVCARP,we propose a local search operator,namely exchanging vehicles among same group routes (EVSGR)for the vehicle,which adjusts the vehicles for routes based on the loads and vehicles of the routes so as to minimize the cost.Then,the EVSGR operator is integrated into memetic algorithm (MA),and the resultant algorithm is used to solve HVCARP.Finally,the proposed algorithm is run on the instances modified from the instances of the benchmark data sets for CARP,and a large number of experimental results show that the EVSGR operator based memetic algorithm is effective for HVCARP.%鉴于多车型限量弧路由问题(heterogeneous vehicle capacitated arc routingproblem,HVCARP)广泛的应用,研究了其优化模型及求解算法.首先将HVCARP的路径费用分为可变费用和固定费用,通过车辆惩罚系数将车型和路径紧密相连,形成费用计算公式.针对HVCARP的特点,提出了一种针对车型的同档路径交换车辆算子,该算子根据路径负载以及车队情况,调整服务车型,以实现服务费用的最优化;然后以其为局部搜索算子,设计了用于求解HVCARP的memetic算法;最后,以CARP 标准测试集的修改算例进行实验验证,实验结果表明,基于同档路径交换车辆算子memetic算法是有效的.【总页数】11页(P583-593)【作者】张玉州;刘晓飞;黄师化;梅俊【作者单位】安庆师范大学计算机与信息学院,安徽安庆 246133;安庆师范大学计算机与信息学院,安徽安庆 246133;安庆师范大学计算机与信息学院,安徽安庆246133;安庆师范大学计算机与信息学院,安徽安庆 246133【正文语种】中文【中图分类】TP301【相关文献】1.求解带软时间窗多车场多车型车辆路径问题的一种改进蚁群算法 [J], 汤雅连;蔡延光;杨期江2.一种求解多校多车型校车路径问题的元启发算法 [J], 侯彦娥;孔云峰;党兰学;王玉璟3.一种求解多车型CARP问题的高效进化算法 [J], 朱征宇;杨永;邓欣;谢志华;夏梦霜;李小花4.一种基于Memetic算法的非线性方程组求解算法 [J], 屈爱平5.一种多车场多车型VSP问题的求解算法 [J], 骆正清;肖鸿庆因版权原因，仅展示原文概要，查看原文内容请购买。