基于改进遗传算法的复杂网络路径优化问题毕业论文

基于改进遗传算法的复杂网络路径优化问题

摘要

随着全球化进程的不断加快，各类型跨国企业在世界范围内的生产、销售及售后服务推动了原材料、产品及配件在全球的有序流动，在这种全球供应链的大背景下，大型国际物流公司纷纷依托其覆盖全球的综合运输服务网络为货主提供“门到门”的物流服务，而各个中小型物流公司也依托该网络开展自己的业务。在这其中，如何针对日趋复杂的运输网络制定最优的运输路线，无疑是提高物流公司竞争力和经济效益的关键所在。而我国虽然在交通网的基础设施建设方面取得了一定进展，但是管理体制和信息化程度的落后严重制约着综合运输服务的进一步发展。随着我国的集装箱路径优化日趋国际化，这些问题导致的影响日益突出，而从定量的角度对复杂网络下的路径优化问题进行研究，对于提高我国综合运输服务效率和水平，具有很强的理论价值和广阔的应用前景。

讨论了考虑燃油消耗和碳排放的车辆路径优化问题，以燃油消耗与碳排放、成本最小化为目标，建立了问题的数学模型；根据问题的特点，设计了求解该问题的改进遗传算法。数据实例的实验计算结果分析表明，应用本文中的模型及其求解算法，可以得到环境友好的路径规划方案，有效降低运输过程中的碳排放量。该模型主要考虑运输时间和中转时间的影响，对参与送货的车辆路径进行优化，从而选取最短路径。设计了一种基于变长染色体改进的遗传算法对问题进行求解，该算法采用有效的编码方式和特定的交叉算子，成功地实现了对该问题的求解。此外，应用仿真数据实例的实验计算验证了本文中所提出的方法的有效性，所得到的近似最优解能够为物流配送企业提供一个令人满意的车辆调度与路径规划的方案。

关键词：碳排放路径优化遗传算法燃油消耗

Complex path optimization problem based on

improved genetic algorithm

ABSTRACT

Along with the accelerating of the globalization process, the various types of multinational companies in the world within the scope of the production, sale and after-sale service to promote the raw materials, products and accessories in the global orderly flow, in the context of the global supply chain, large international logistics companies are relying on its global integrated transport service network for the shipper to provide \"door to door\" logistics services, and various small and medium-sized logistics companies are relying on the network to carry out their business. In it, how to develop the optimal in view of the increasingly complex network of transport routes, is undoubtedly the key to enhance the competitiveness of logistics companies and economic benefits. And although in the network infrastructure construction in China has made some progress, but the backward management system and information level seriously restricts the further development of comprehensive transportation service. Along with the increasingly international container path optimization, these problems lead to the influence of the increasingly prominent, and from the Angle of quantitative research on the path optimization problem under complex network, to improve service efficiency and comprehensive transportation in China, has the very strong theory value and broad application prospects.

Discussed considering fuel consumption and emissions of VRP problems, in which the minimum fuel consumption and emissions, cost into the goal, to establish the mathematical model of the problem; According to the characteristics of the problem, the improved genetic algorithm is designed to solve the problem. Data instance analysis of the experiment results show that application model and its algorithm in this paper, can be environment friendly path planning scheme, effectively reduce carbon emissions in the process of transportation. This model mainly consider the influence of the transportation time and transit time, involved in the delivery of the vehicle routing optimization, so as to choose the shortest path. Designed a kind of improved genetic algorithm based on variable-length chromosomes to solve the problem, the algorithm adopts effective encoding and specific crossover operator, to successfully implement the solution of the problem. In addition, the application experiment of simulation data instance calculation to verify the effectiveness of the method proposed in this paper, the approximate optimal solution can be got by for logistics enterprise to provide a satisfactory

vehicle scheduling scheme with path planning.

Key Words:Carbon emission Fuel consumption Path optimization Genetic algorithm

目录

第一章绪论 (1)

1.1研究背景及发展概况 (1)

1.2研究目的和意义 (2)

1.2.1研究目的 (2)

1.2.2研究意义 (2)

1.3国内外研究现状 (2)

1.4本文的研究内容 (4)

1.5本文的结构安排 (5)

第二章系统关键技术介绍 (7)

2.1遗传算法 (7)

2.1.1遗传算法的基本原理 (7)

2.1.2遗传算法的基本步骤 (7)

2.2MATLAB仿真技术 (8)

第三章复杂路径优化问题 (10)

3.1问题的描述 (10)

3.2问题的符号表示 (11)

3.3问题的数学模型 (11)

第四章改进遗传算法设计 (13)

4.1染色体编码方式 (13)

4.2初始种群的生成 (13)

4.3适应度函数的建立 (13)

4.4选择策略 (14)

4.5交叉算子 (14)

4.6变异算子 (14)

4.7终止条件 (14)

4.8算法步骤 (15)

第五章算例分析 (17)

5.1验证算法 (17)

5.2仿真实验 (18)

第六章总结 (20)

参考文献 (21)

致谢 (23)

第一章绪论

1.1研究背景及发展概况

社会主义市场经济的发展带动了物流运输业的飞速发展，物流运输业已经成为经济发展的主要推动力，因而被誉为“第三利润源泉”，越来越多的企业关注物流。在这其中，如何针对日趋复杂的运输网络制定最优的运输路线，无疑是提高物流公司竞争力和经济效益的关键所在。

物流业融合多种产业形成一种复合型服务产业，是国民经济的重要组成部分，涉及领域广，吸纳就业人数多，促进生产、拉动消费作用大，在经济方式的转变和加快产业结构调整等方面发挥着重要作用。我国物流业已进入转型升级的新阶段。但是，物流业发展总体水平还不高，发展方式比较粗放。其物流成本较高、效率较低，条块分割严重，阻碍物流业发展的体制机制障碍仍未打破且政策法规体系还不够完善，市场秩序不够规范。已经出台的一些政策措施有待进一步落实，一些地方针对物流企业的乱收费、乱罚款问题突出。信用体系建设滞后，物流业从业人员整体素质有待进一步提升[1]。

在社会经济中，物流的位置是无法替代的，它是经济中的流通、经济中的物流以及运输。同时，随着经济的快速发展，环境问题越来越严重，许多国家开始实施节能减排政策，以减少对环境的污染，企业也更加关注在进行货物运输过程中车辆的燃油消耗和碳排放，减少车辆在运输过程中的碳排放有助于减少对环境的污染，绿色出行的观念已经深入人心，可以为企业带来巨大的社会效益，并且碳排放交易已经走进中国市场，减少碳排放就是在节约金钱。因此提升物流经济效益成为关键。

遗传算法是由美国Michigan大学的J.Holland教授于1975年首先提出的一种模拟自然界生物进化过程的全局随机优化算法。遗传算法结合了计算机科学与进化论思想，根据于生物进化机制与遗传学原理，依据“优胜劣汰”和“适者生存”的原则，通过模拟自然界中生物群体由低级、简单到高级、复杂的生物进化过程，使所要解决的问题从初始解逐渐逼近最优解或准最优解[2]。

遗传算法是以自然选择和遗传理论为基础，以一种群体的所有个体为对象，将生物进化过程中适者生存规则与染色体信息交换机制有效的结合起来，利用随机化技术对一个被编码的参数空间进行高效搜索，能自动获得和积累搜索过程中的空间知识，是一种高效的全局寻优方法。在遗传算法中，问题不同解被假设成“种群”中不同个体（即染色体），各染色体通过交叉、变异产生下一代染色体（即后代），适应值高的染色体具有比较高的选中概率，经过若干代操作将产生最好的染色体。

遗传操作主要包括选择、交叉和变异，遗传算法的核心内容包括参数编码、初始群体设定、是适应度函数设计、遗传操作设计和控制参数设定[3]。

1.2研究目的和意义

1.2.1研究目的

在车辆调度送货的作业中，大的物流公司一般提前若干时间，向收货点发货，物流公司根据计划期内，对车辆进行调度安排。每辆车为了顺利完成装卸任务，保证其在计划时刻到收货点，必然会出现选择较短的出行路线以减少路上消耗的能源等，这就要求对车辆路径进行合理的规划。

由于遗传算法属于一种基于自然选择和遗传变异等生物进化机制而发展起来的高度并行、随机、自适应的智能全局搜索算法，遗传算法（GA）的应用范围非常广泛[4-5]，用于来解决传统搜索方法无法解决的非线性问题。由于遗传算法能在解决组合优化问题上展现出良好的特性，将遗传算法应用到车辆调度与路径优化问题中去，有助于解决其车辆路径的复杂度，使得求解车辆最短路径问题得到很大进步。优化车辆路径，实现对现有资源合理分配、有效利用以及减少了环境污染，达到成本最低或效率最高的目标。

本课题的研究目的是对车辆路径的选择与规划问题进行研究，以车辆的最短路径为研究对象，以车辆的碳排放量费用和成本为约束条件来确定最短路径，从而降低成本。

1.2.2研究意义

在送货过程中，核心内容就是送货了。在物流活动中，货物的运输就是送货的实际形态。可是远距离的运输和配送运输还是有本质的区别，他们的送货路程是不相同的，远距离运输属于长途运输，也就是不同区域之间的运输。配送运输是属于短途运输，送货路线短但较繁杂。即便是同一条线路的短途运输可能会因为线路复杂，碳排放量多等问题造成总成本过高，所以合理规划运输路线对送货成本的影响要比一般的运输大很多，合理的规划配送路线有利于对送货速度，成本等实现有效的控制。因此，设计合理有效的路径方案对企业和社会具有十分重要的意义。

对企业来讲，（1）合理规划了送货路径有利于节省成本。（2）降低了碳排放量，减少了环境污染，有利于提高企业的社会形象。（3）有利于企业提高经济效益。

对社会来讲，随着全球气候变暖以及大气污染的不断加剧，人们对环境问题越来越关注，降低能源消耗、减少碳排放逐渐引起大家的重视。全球气候变暖的主要原因是来自于二氧化碳的排放，而二氧化碳的排放主要是来源于化石燃料的燃烧。研究车辆调度与路径规划问题，对于减少碳排放，抑制气候变暖以及缓解交通堵塞，减少噪声等有重要意义。

1.3国内外研究现状

车辆路径优化问题（Vehicle Routing Problem）是经典的优化组合问题，最早由Dantizing和Ramser[6]在1959年提出。涉及到很多领域和应用，而且VRP及其变种已经被广泛的研究，直到Min[7]意识到在实际情况中同一结点同时取送货的可能性，介绍了同时取送货车辆路径问题（vehicle routing problem with simultaneous pickups and deliveries，VRPSPD）。同时取送货车辆路径问题已经成了物流运输中非常普遍的问题，例如快递员在

送货的同时进行取货、配送对环境污染大的电子产品的同时，对废旧产品进行回收，这就要求企业在规划车辆路径时，同时考虑顾客的送货和取货需求，以最小化运营成本，以及减少环境污染。Montane和Galvao[8]研究了VRPSPD问题，提出了一个基于VRPSPD的货物流模型；Dell'Amico et al [9]在Montane和Galvao提出的数学模型的基础上，采用分支定价方法成功的对中小规模的VRPSPD问题进行了求解。对于规模较大的VRPSPD问题，目前的研究主要采用启发式或者元启发式的方法；Dethloff[10]研究了车辆行驶距离（TD），车辆剩余的负载量（RC），辐射附加费（RS）以及三者的组合（RCRS）这四种不同的插入准则；Nagy和Salhi[11]在考虑车辆路径变化和可行解之间关系的基础上，设计了一个综合启发式算法解决了VRPSPD问题。在算法运行过程中，先找到一个VRP问题的可行解，然后按照VRPSPD问题的特点进行修改，使其也适合于VRPSPD问题，最后采用复合的改进的启发式算法对解进行改进；Chen和Wu[12]采用成本最小化的启发式算法生成初始解，接着采用TS算法和车辆路径改进程序对解进行了改进；Bianchessi和Righini[13]进行了大量的数值仿真实验，提出了一些比较新颖的TS算法，然后对这些算法进行了比较。

随着物流业的高速发展，国内越来越多的学者和专家开始研究VRP问题以及其变种问题，一些主要的研究如下：肖健梅，李军军，王锡淮[14]研究了VRP问题，设计了一种新颖的编码方式，并通过对微粒群算法进行改进，成功对该问题进行了求解；符桌[15]研究了开放式的VRP问题，考虑了车辆的装载容量的约束，并用禁忌搜索算法对问题进行了求解；马建华，房勇，袁杰[16]以最快完成为目标研究了VRP问题，考虑了多种车辆型号和多个配送中心等约束条件，用变异的蚁群算法对问题进行了求解。

彭春林，梁春华，周泓[17]研究了VRPSPD问题，并设计了改进的遗传算法，算法采用边重组的交叉操作，成功对该问题进行了求解；张涛，余绰娅，刘岚[18]等人建立了VRPSPD问题的机会约束规划模型，并根据问题的特点，设计了改进的分散搜索算法对问题进行了求解；张涛，田文馨，张杰，刘士新[19]研究了VRPSPD问题，考虑了车辆的最大行程约束条件，建立了问题的混合整数规划数学模型，并设计了改进的蚁群算法，对该问题进行了求解；张涛，张春梅，张玥杰[20]针对VRPSPD问题，建立了问题的数学模型，设计了协同粒子群-模拟退火算法，成功对该问题进行了求解；胡大伟，陈诚和郭晓汾[21]研究了多车场VRPSPD 问题，采用多阶段方法得到了最优解；龙磊，陈秋双等[22]研究了VRPSPD问题，并建立了数学模型，设计了改进的GA算法，算法采用特定的交叉算子和种群更新方法，成功解决了该问题。

曹二保[23]研究了VRP-SPDTW问题，建立了问题的模型，对GA算法进行了改进，算法采用特殊的交叉变异操作；蓝伯雄[24]等人研究了VRP-SPDTW问题，并设计了一种改进的TS算法；殷佳林[25]等人在蚁群算法的基础上进行了改进，研究了VRP-SPDTW问题，最后进行了仿真实验，结果证明了算法可以成功的解决此类问题；段凤华[26]针对VRPSPDTW问题，考虑了硬时间窗约束条件，设计了改进TS算法；郎茂祥[27]采用了TS算法和模拟退火算法对VRPSPDTW问题进行了研究，研究中考虑的是软时间窗约束；郭耀煌和李军[28]研究了车辆满载情况下，VRPSPDTW问题，并用启发式方法得到了车辆路线；张燕，周支力和翟斌[29]对传

统标号算法进行了改进，研究了VRPSPDTW问题。

遗传算法在车辆路径优化问题（VRP）中的应用十分有利，并且遗传算法是一种全局优化概率算法。葛继科[30]等人介绍了遗传算法的基本工作原理和主要特点，概述了遗传算法的常见应用领域，分析了近五年国内对遗传算法的研究现状。赵振勇[31]等人给出了遗传算法的改进方法，并对系统进行了分析和研究。

1.4本文的研究内容

本课题从车辆路径的选择与规划问题进行研究，以车辆的最短路径为研究对象，建立了考虑环境指标和经济指标的车辆路径优化问题的多目标数学模型，以车辆的运输时间和中转时间为约束条件来确定最短路径降低成本，之后设计了求解该问题的改进遗传算法，最后用标准的车辆路径优化问题算例做了仿真实验，通过对实验结果的分析验证了算法的正确性。

本文结构路线图如图1.1所示：

VRP问题优化研究

研究背景、意义和

现状

VRP求解方法

VRP问题概述VRP模型构建

VRP描述组成、模型、分类

求解算法设计遗传算法介绍

遗传算法原理、工

作过程、特点

GA具体方案：染色

体、种群、适应

度、遗传算子等算例分析

时间窗描述、分类

总结及展望

图1.1结构路线图

1.5本文的结构安排

本文共分为五章，各章的主要内容安排如下：

第一章介绍了复杂网络下的路径优化问题的研究背景，相关技术的发展概况、研究的目的和意义以及国内外在遗传算法进化过程中等领域的研究现状。并分析了在这些前提下，基于改进遗传算法的复杂路径优化问题的优势。

第二章介绍了实现基于改进遗传算法的复杂网络路径优化问题时所使用的关键技术，详细地阐述了在遗传算法中编码，生成初始种群，适应性值评估，选择，交叉，变异，确定最优解等实现遗传算法等技术的工作原理以及仿真实验的介绍。

第三章复杂网络路径优化问题的描述了该优化问题的符号含义，并设计了该优化问题所使用的数据模型，并深入地描述了该优化问题的求解方法。

第四章具体地说明了对基于改进遗传算法的复杂网络路径优化问题进行了改进遗传算法的设计。

第五章通过算例分析进行仿真实验，通过详细的测试对该问题进行了可行性验证以及对结果的分析。

第六章总结了在开发基于改进遗传算法的复杂网络路径优化问题时所遇到的各种问题，在总结的过程中对这些问题进行深入的思考，提出了未来可以进一步改进的解决方案。

第二章系统关键技术介绍

2.1遗传算法

2.1.1遗传算法的基本原理

遗传算法（Genetic Algorithm，GA）是Holland和Bagley于1975年提出，它是一种借鉴生物进化机制演化而来的自适应随机搜索算法。遗传算法从一定的初始群体开始进化，从中筛选出优良的染色体，通过一代一代的进化，使整个群体适应性更好，经过一定代数的进化之后，最终找到最优的个体。其中在每一代的群体中，按照每个染色体的适应性优劣，选择出一些良好的染色体复制到下一代种群中，接着通过染色体之间的交叉、变异生成新的染色体。

2.1.2遗传算法的基本步骤

在遗传（GA）算法中，首先通过一定的编码方式生成初始群体，然后在每个染色体上执行选择算子（Selection Operator）、交叉算子（Crossover Operator）、变异算子（Mutation Operator）这些操作，并从中选出适应度高的染色体进化，从而实现优胜劣汰的进化过程，算法的具体操作过程如下：

（1）染色体编码：GA不能对问题的一些参数进行直接处理，所以需要将问题的解通过一定的编码方式编码为染色体，染色体编码的好坏直接影响计算消耗的时间，算法运行的快慢，所以一般情况下为节省算法运行时间采用自然数直接编码的方式。

（2）初始化：对问题的参数进行初始化，并按照一定的方法生成初始的染色体群体，一个染色体对应着一个配送方案。

（3）计算适应度值：适应度函数用来判定染色体的优良程度，常常根据问题的特点，选取一定的函数作为适应度函数。为了能迅速判定染色体的优良程度，就要拉大优良个体的适应度值，基于序的评价函数就有利于拉大个体之间的适应度值，基于序的评价函数首先就是对种群中所有的个体按照总距离的大小进行排序，每一个个体要给与一个队列序号，总的距离越小，序号越靠前。

（4）选择策略：其是为了从当前的群体中选出优良的染色体复制到下一代群体中，染色体的适应度越高，被复制到下一代的可能性就大，适应度差的染色体被遗传到下一代的可能性就越小。

（5）交叉算子：根据选择操作得到的两个染色体个体，以一定的概率按照某种方式互换一些基因，从而得到子代染色体的过程即形成新的子代种群。

（6）变异算子：对染色体个体的某些基因按照一定的概率进行变换即改变自身染色体的基因位。

（7）终止条件：染色体群体经过选择、交叉、变异，在进化一定的代数后，满足终止的条件就停止计算，并输出所得到的结果。否则返回步骤（3）。

GA算法的流程图如图2.1所示：

开始

产生初始种群

计算个体适应度值

选择

交叉

变异

满足终止条

件？

输出最优解

结束否

是

图2.1 遗传算法流程图

2.2 MATLAB仿真技术

MATLAB是一种以矩阵作为基本数据单远的程序设计语言，其具备数据分析、算法实现以及应用开发的交互式开发环境。MATLAB分为总包和若干个工具箱，具有强大的数值计算

能力、数据可视化能力与符号计算能力，逐步发展成为各种学科、多种工作平台下功能强大的大型软件，可以方便实现数值分析、优化分析、数据处理、自动控制、信号处理等领域的数学计算，也可以快捷实现计算可视化、图形控制、场景创建和渲染、图像处理、虚拟现实和地图制作等分析处理工作。MATLAB已经成为线性代数、自动控制理论、概率论及数理统计、数字信号处理、时间序列分析、动态系统仿真等课程的基本教学工具。

其中MATLAB仿真技术在工程上和科学实验上起到很大影响，可以用来完成系统的设计、性能评估、测试、进行数学模型、专业模型的模拟，复杂数值计算等工作。同时在经济领域，可以进行数据评价，高等数值计算、数值分析和预测等。这些功能强大的仿真软件,使得物流系统仿真的设计和分析过程变得相对直观和便捷,由此也使得车辆路径优化系统仿真技术得到了更快的发展。车辆路径优化系统仿真贯穿着车辆路径优化系统工程设计的全过程,对车辆路径优化系统的发展起着举足轻重的作用。车辆路径优化系统仿真具有广泛的适应性和极好的灵活性,有助于我们更好地研究车辆路径优化系统性能。

第三章 复杂路径优化问题

3.1问题的描述

车辆路径优化问题可以描述为：从发货中心用一辆汽车向一个收货点送货，这个收货点的位置和需求量一定，这辆汽车的负载重量一定，运输方式有三种车1运输，车2运输，车三运输，合理安排汽车路线，使总运距最短，并满足一下条件：每天送货路径上只有一个收货点和送货点，且只能由一辆汽车送货。

通过分析上述车辆路径优化问题的约束条件和优化目标可知，车辆路径优化问题可以归结为最短路径问题。本问题为单量汽车的送货路径优化，求得满足经济指标和环境指标的单辆汽车的最优送货路径后。因此，为便于问题的讨论，本文对单辆汽车的送货路径优化进行研究。其模型如图3.1所示： v0v2

v1v3v4

v5v6v7c b c b c b a a b

c b a a

a a

b

c b c 6

5534323632242

4

2314

—a —：车1运输 —b —：车2运输 —c —：车3运输

图3.1车辆路径优化VRP 模型

为了更清楚地描述车辆路径问题，我们可以用(,,)G V A B =来表示联运网络结合图3.1的VRP 模型，其中V 表示各个节点的集合，而A 表示节点之间的运输方案集合，B 表示节点之间的中转方案集合，以图3.1为例，节点有0V 、1V 、2V 3V 、4V 、5V 、6V 以及7V ，运输方式有车1运输，车2运输和车3运输，中转方案包括中转时间和中转成本，每条路径上的数字表示各运输方式所需要花费的运输成本，如0V →1V 车1运输成本1（万元），车2运输成本4（万元），车3运输成本6（万元）。

而本文研究的是将运输任务分解成一系列的有顺序的分段运输任务，每个分段运输任务有多个运输者。相邻的分段运输任务之间存在任务的中转和衔接。用图(,,)G V A B =表示