基于改进遗传算法的复杂网络路径优化问题说明书大学学位论文

《基于改进遗传算法的复杂网络路径优化问题说明书大学学位论文》由会员分享，可在线阅读，更多相关《基于改进遗传算法的复杂网络路径优化问题说明书大学学位论文（28页珍藏版）》请在装配图网上搜索。

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

2、，而从定量的角度对复杂网络下的路径优化问题进行研究，对于提高我国综合运输服务效率和水平，具有很强的理论价值和广阔的应用前景。讨论了考虑燃油消耗和碳排放的车辆路径优化问题，以燃油消耗与碳排放、成本最小化为目标，建立了问题的数学模型；根据问题的特点，设计了求解该问题的改进遗传算法。数据实例的实验计算结果分析表明，应用本文中的模型及其求解算法，可以得到环境友好的路径规划方案，有效降低运输过程中的碳排放量。该模型主要考虑运输时间和中转时间的影响，对参与送货的车辆路径进行优化，从而选取最短路径。设计了一种基于变长染色体改进的遗传算法对问题进行求解，该算法采用有效的编码方式和特定的交叉算子，成功地实现了对

3、该问题的求解。此外，应用仿真数据实例的实验计算验证了本文中所提出的方法的有效性，所得到的近似最优解能够为物流配送企业提供一个令人满意的车辆调度与路径规划的方案。关键词：碳排放 路径优化 遗传算法 燃油消耗Complex path optimization problem based on improved genetic algorithmABSTRACT Along with the accelerating of the globalization process, the various types of multinational companies in the world with

4、in 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 shi

5、pper 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 com

6、petitiveness 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

7、 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

8、, 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 th

9、e 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 transporta

10、tion. 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 al

11、gorithm 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

12、 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目 录第一章 绪论11.1研究背景及发展概况11.2研究目的和意义21.2.1研究目的21.2.2研究意义21.3国内外研究现状21.4本文的研究内容41.5本文的结构安排5第二章 系统关键技术介绍72.1遗传算法72.

13、1.1遗传算法的基本原理72.1.2遗传算法的基本步骤72.2 MATLAB仿真技术8第三章 复杂路径优化问题103.1问题的描述103.2问题的符号表示113.3问题的数学模型11第四章 改进遗传算法设计134.1染色体编码方式134.2初始种群的生成134.3适应度函数的建立134.4选择策略144.5交叉算子144.6变异算子144.7终止条件144.8算法步骤15第五章 算例分析175.1验证算法175.2仿真实验18第六章 总结20参考文献21致谢23- I -天津理工大学2015届本科毕业设计说明书第一章 绪论1.1研究背景及发展概况社会主义市场经济的发展带动了物流运输业的飞速发展

14、，物流运输业已经成为经济发展的主要推动力，因而被誉为“第三利润源泉”，越来越多的企业关注物流。在这其中，如何针对日趋复杂的运输网络制定最优的运输路线，无疑是提高物流公司竞争力和经济效益的关键所在。物流业融合多种产业形成一种复合型服务产业，是国民经济的重要组成部分，涉及领域广，吸纳就业人数多，促进生产、拉动消费作用大，在经济方式的转变和加快产业结构调整等方面发挥着重要作用。我国物流业已进入转型升级的新阶段。但是，物流业发展总体水平还不高，发展方式比较粗放。其物流成本较高、效率较低，条块分割严重，阻碍物流业发展的体制机制障碍仍未打破且政策法规体系还不够完善，市场秩序不够规范。已经出台的一些政策措施

15、有待进一步落实，一些地方针对物流企业的乱收费、乱罚款问题突出。信用体系建设滞后，物流业从业人员整体素质有待进一步提升1。在社会经济中，物流的位置是无法替代的，它是经济中的流通、经济中的物流以及运输。同时，随着经济的快速发展，环境问题越来越严重，许多国家开始实施节能减排政策，以减少对环境的污染，企业也更加关注在进行货物运输过程中车辆的燃油消耗和碳排放，减少车辆在运输过程中的碳排放有助于减少对环境的污染，绿色出行的观念已经深入人心，可以为企业带来巨大的社会效益，并且碳排放交易已经走进中国市场，减少碳排放就是在节约金钱。因此提升物流经济效益成为关键。遗传算法是由美国Michigan大学的J.Holl

16、and教授于1975年首先提出的一种模拟自然界生物进化过程的全局随机优化算法。遗传算法结合了计算机科学与进化论思想，根据于生物进化机制与遗传学原理，依据“优胜劣汰”和“适者生存”的原则，通过模拟自然界中生物群体由低级、简单到高级、复杂的生物进化过程，使所要解决的问题从初始解逐渐逼近最优解或准最优解2。遗传算法是以自然选择和遗传理论为基础，以一种群体的所有个体为对象，将生物进化过程中适者生存规则与染色体信息交换机制有效的结合起来，利用随机化技术对一个被编码的参数空间进行高效搜索，能自动获得和积累搜索过程中的空间知识，是一种高效的全局寻优方法。在遗传算法中，问题不同解被假设成“种群”中不同个体（即

17、染色体），各染色体通过交叉、变异产生下一代染色体（即后代），适应值高的染色体具有比较高的选中概率，经过若干代操作将产生最好的染色体。遗传操作主要包括选择、交叉和变异，遗传算法的核心内容包括参数编码、初始群体设定、是适应度函数设计、遗传操作设计和控制参数设定3。1.2研究目的和意义1.2.1研究目的在车辆调度送货的作业中，大的物流公司一般提前若干时间，向收货点发货，物流公司根据计划期内，对车辆进行调度安排。每辆车为了顺利完成装卸任务，保证其在计划时刻到收货点，必然会出现选择较短的出行路线以减少路上消耗的能源等，这就要求对车辆路径进行合理的规划。由于遗传算法属于一种基于自然选择和遗传变异等生物进化

18、机制而发展起来的高度并行、随机、自适应的智能全局搜索算法，遗传算法（GA）的应用范围非常广泛4-5，用于来解决传统搜索方法无法解决的非线性问题。由于遗传算法能在解决组合优化问题上展现出良好的特性，将遗传算法应用到车辆调度与路径优化问题中去，有助于解决其车辆路径的复杂度，使得求解车辆最短路径问题得到很大进步。优化车辆路径，实现对现有资源合理分配、有效利用以及减少了环境污染，达到成本最低或效率最高的目标。本课题的研究目的是对车辆路径的选择与规划问题进行研究，以车辆的最短路径为研究对象，以车辆的碳排放量费用和成本为约束条件来确定最短路径，从而降低成本。1.2.2研究意义在送货过程中，核心内容就是送货

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

20、高经济效益。对社会来讲，随着全球气候变暖以及大气污染的不断加剧，人们对环境问题越来越关注，降低能源消耗、减少碳排放逐渐引起大家的重视。全球气候变暖的主要原因是来自于二氧化碳的排放，而二氧化碳的排放主要是来源于化石燃料的燃烧。研究车辆调度与路径规划问题，对于减少碳排放，抑制气候变暖以及缓解交通堵塞，减少噪声等有重要意义。1.3国内外研究现状车辆路径优化问题（Vehicle Routing Problem）是经典的优化组合问题，最早由Dantizing和Ramser6在1959年提出。涉及到很多领域和应用，而且VRP及其变种已经被广泛的研究，直到Min7意识到在实际情况中同一结点同时取送货的可能性

21、，介绍了同时取送货车辆路径问题（vehicle routing problem with simultaneous pickups and deliveries，VRPSPD）。同时取送货车辆路径问题已经成了物流运输中非常普遍的问题，例如快递员在送货的同时进行取货、配送对环境污染大的电子产品的同时，对废旧产品进行回收，这就要求企业在规划车辆路径时，同时考虑顾客的送货和取货需求，以最小化运营成本，以及减少环境污染。Montane和Galvao8研究了VRPSPD问题，提出了一个基于VRPSPD的货物流模型；DellAmico et al 9在Montane和Galvao提出的数学模型的基础上，采

22、用分支定价方法成功的对中小规模的VRPSPD问题进行了求解。对于规模较大的VRPSPD问题，目前的研究主要采用启发式或者元启发式的方法；Dethloff10研究了车辆行驶距离（TD），车辆剩余的负载量（RC），辐射附加费（RS）以及三者的组合（RCRS）这四种不同的插入准则；Nagy和Salhi11在考虑车辆路径变化和可行解之间关系的基础上，设计了一个综合启发式算法解决了VRPSPD问题。在算法运行过程中，先找到一个VRP问题的可行解，然后按照VRPSPD问题的特点进行修改，使其也适合于VRPSPD问题，最后采用复合的改进的启发式算法对解进行改进；Chen和Wu12采用成本最小化的启发式算法生

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

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

25、多车场VRPSPD问题，采用多阶段方法得到了最优解；龙磊，陈秋双等22研究了VRPSPD问题，并建立了数学模型，设计了改进的GA算法，算法采用特定的交叉算子和种群更新方法，成功解决了该问题。曹二保23研究了VRP-SPDTW问题，建立了问题的模型，对GA算法进行了改进，算法采用特殊的交叉变异操作；蓝伯雄24等人研究了VRP-SPDTW问题，并设计了一种改进的TS算法；殷佳林25等人在蚁群算法的基础上进行了改进，研究了VRP-SPDTW问题，最后进行了仿真实验，结果证明了算法可以成功的解决此类问题；段凤华26针对VRPSPDTW问题，考虑了硬时间窗约束条件，设计了改进TS算法；郎茂祥27采用了T

26、S算法和模拟退火算法对VRPSPDTW问题进行了研究，研究中考虑的是软时间窗约束；郭耀煌和李军28研究了车辆满载情况下，VRPSPDTW问题，并用启发式方法得到了车辆路线；张燕，周支力和翟斌29对传统标号算法进行了改进，研究了VRPSPDTW问题。遗传算法在车辆路径优化问题（VRP）中的应用十分有利，并且遗传算法是一种全局优化概率算法。 葛继科30等人介绍了遗传算法的基本工作原理和主要特点，概述了遗传算法的常见应用领域，分析了近五年国内对遗传算法的研究现状。赵振勇31等人给出了遗传算法的改进方法，并对系统进行了分析和研究。1.4本文的研究内容本课题从车辆路径的选择与规划问题进行研究，以车辆的最

27、短路径为研究对象，建立了考虑环境指标和经济指标的车辆路径优化问题的多目标数学模型，以车辆的运输时间和中转时间为约束条件来确定最短路径降低成本，之后设计了求解该问题的改进遗传算法，最后用标准的车辆路径优化问题算例做了仿真实验，通过对实验结果的分析验证了算法的正确性。本文结构路线图如图1.1所示：图1.1结构路线图1.5本文的结构安排本文共分为五章，各章的主要内容安排如下：第一章介绍了复杂网络下的路径优化问题的研究背景，相关技术的发展概况、研究的目的和意义以及国内外在遗传算法进化过程中等领域的研究现状。并分析了在这些前提下，基于改进遗传算法的复杂路径优化问题的优势。第二章介绍了实现基于改进遗传算法

28、的复杂网络路径优化问题时所使用的关键技术，详细地阐述了在遗传算法中编码，生成初始种群，适应性值评估，选择，交叉，变异，确定最优解等实现遗传算法等技术的工作原理以及仿真实验的介绍。第三章复杂网络路径优化问题的描述了该优化问题的符号含义，并设计了该优化问题所使用的数据模型，并深入地描述了该优化问题的求解方法。第四章具体地说明了对基于改进遗传算法的复杂网络路径优化问题进行了改进遗传算法的设计。第五章通过算例分析进行仿真实验，通过详细的测试对该问题进行了可行性验证以及对结果的分析。第六章总结了在开发基于改进遗传算法的复杂网络路径优化问题时所遇到的各种问题，在总结的过程中对这些问题进行深入的思考，提出了

29、未来可以进一步改进的解决方案。第二章 系统关键技术介绍2.1遗传算法2.1.1遗传算法的基本原理遗传算法（Genetic Algorithm，GA）是Holland和 Bagley于1975年提出，它是一种借鉴生物进化机制演化而来的自适应随机搜索算法。遗传算法从一定的初始群体开始进化，从中筛选出优良的染色体，通过一代一代的进化，使整个群体适应性更好，经过一定代数的进化之后，最终找到最优的个体。其中在每一代的群体中，按照每个染色体的适应性优劣，选择出一些良好的染色体复制到下一代种群中，接着通过染色体之间的交叉、变异生成新的染色体。2.1.2遗传算法的基本步骤在遗传（GA）算法中，首先通过一定的编

30、码方式生成初始群体，然后在每个染色体上执行选择算子（Selection Operator）、交叉算子（Crossover Operator）、变异算子（Mutation Operator）这些操作，并从中选出适应度高的染色体进化，从而实现优胜劣汰的进化过程，算法的具体操作过程如下：（1） 染色体编码：GA不能对问题的一些参数进行直接处理，所以需要将问题的解通过一定的编码方式编码为染色体，染色体编码的好坏直接影响计算消耗的时间，算法运行的快慢，所以一般情况下为节省算法运行时间采用自然数直接编码的方式。（2） 初始化：对问题的参数进行初始化，并按照一定的方法生成初始的染色体群体，一个染色体对应着一

31、个配送方案。（3） 计算适应度值：适应度函数用来判定染色体的优良程度，常常根据问题的特点，选取一定的函数作为适应度函数。为了能迅速判定染色体的优良程度，就要拉大优良个体的适应度值，基于序的评价函数就有利于拉大个体之间的适应度值，基于序的评价函数首先就是对种群中所有的个体按照总距离的大小进行排序，每一个个体要给与一个队列序号，总的距离越小，序号越靠前。（4） 选择策略：其是为了从当前的群体中选出优良的染色体复制到下一代群体中，染色体的适应度越高，被复制到下一代的可能性就大，适应度差的染色体被遗传到下一代的可能性就越小。（5） 交叉算子：根据选择操作得到的两个染色体个体，以一定的概率按照某种方式互

32、换一些基因，从而得到子代染色体的过程即形成新的子代种群。（6） 变异算子：对染色体个体的某些基因按照一定的概率进行变换即改变自身染色体的基因位。（7） 终止条件：染色体群体经过选择、交叉、变异，在进化一定的代数后，满足终止的条件就停止计算，并输出所得到的结果。否则返回步骤（3）。GA算法的流程图如图2.1所示：图2.1 遗传算法流程图2.2 MATLAB仿真技术MATLAB是一种以矩阵作为基本数据单远的程序设计语言，其具备数据分析、算法实现以及应用开发的交互式开发环境。MATLAB分为总包和若干个工具箱，具有强大的数值计算能力、数据可视化能力与符号计算能力，逐步发展成为各种学科、多种工作平台下

33、功能强大的大型软件，可以方便实现数值分析、优化分析、数据处理、自动控制、信号处理等领域的数学计算，也可以快捷实现计算可视化、图形控制、场景创建和渲染、图像处理、虚拟现实和地图制作等分析处理工作。MATLAB已经成为线性代数、自动控制理论、概率论及数理统计、数字信号处理、时间序列分析、动态系统仿真等课程的基本教学工具。其中MATLAB仿真技术在工程上和科学实验上起到很大影响，可以用来完成系统的设计、性能评估、测试、进行数学模型、专业模型的模拟，复杂数值计算等工作。同时在经济领域，可以进行数据评价，高等数值计算、数值分析和预测等。这些功能强大的仿真软件,使得物流系统仿真的设计和分析过程变得相对直观

34、和便捷,由此也使得车辆路径优化系统仿真技术得到了更快的发展。 车辆路径优化系统仿真贯穿着车辆路径优化系统工程设计的全过程,对车辆路径优化系统的发展起着举足轻重的作用。车辆路径优化系统仿真具有广泛的适应性和极好的灵活性,有助于我们更好地研究车辆路径优化系统性能。第三章 复杂路径优化问题3.1问题的描述车辆路径优化问题可以描述为：从发货中心用一辆汽车向一个收货点送货，这个收货点的位置和需求量一定，这辆汽车的负载重量一定，运输方式有三种车1运输，车2运输，车三运输，合理安排汽车路线，使总运距最短，并满足一下条件：每天送货路径上只有一个收货点和送货点，且只能由一辆汽车送货。通过分析上述车辆路径优化问题

35、的约束条件和优化目标可知，车辆路径优化问题可以归结为最短路径问题。本问题为单量汽车的送货路径优化，求得满足经济指标和环境指标的单辆汽车的最优送货路径后。因此，为便于问题的讨论，本文对单辆汽车的送货路径优化进行研究。其模型如图3.1所示：a：车1运输 b：车2运输 c：车3运输图3.1车辆路径优化VRP模型为了更清楚地描述车辆路径问题，我们可以用来表示联运网络结合图3.1的VRP模型，其中表示各个节点的集合，而表示节点之间的运输方案集合，表示节点之间的中转方案集合，以图3.1为例，节点有、 、以及，运输方式有车1运输，车2运输和车3运输，中转方案包括中转时间和中转成本，每条路径上的数字表示各运输

36、方式所需要花费的运输成本，如车1运输成本1（万元），车2运输成本4（万元），车3运输成本6（万元）。而本文研究的是将运输任务分解成一系列的有顺序的分段运输任务，每个分段运输任务有多个运输者。相邻的分段运输任务之间存在任务的中转和衔接。用图表示联运网络；表示节点集合，表示中转节点、表示起点、表示终点；表示节点间的运输方案的集合，表示节点、之间的一个运输方案，其中，表示运输方式集合（同一种运输方式下，若有多个运输者可选择，可表示不同的运输者）；当节点处发生转运时，需要一定的中转时间和中转成本，不同运输方式之间的中转时间、成本存在差异，表示中转方案集合，表示在节点的承运方式和进行转运的中转方案。在对

37、问题进行进一步研究之前，根据问题的特点，作以下假设：（1）只有一个车场且车场与收货点的位置是确定的。（2）收货点的需求量己知。（3）每辆车在进行送货时，其装载量不能超过其最大容量。（4）车场的车辆是同一车型，车辆数目和车辆最大容量事先知道。（5）忽略不确定性因素的影响，认为运输方案和中转方案是已知的、确定性的。（6）不考虑由于受天气状况、交通状况、路况、节点能力等因素的影响。3.2问题的符号表示：运输方式在节点、之间运输的碳排放量（g）；：燃油消耗量（kg）； ：运输方式的碳排放因子（g/kg-fuel）； ：运输方式、之间的平均运输速度； ：节点、之间的距离；：运输任务时间窗约束，即货物运达

38、的时刻应处在时间窗内；：在节点处自到的中转成本；：运输者针对节点、间的运输成本；：在节点处自到的中转时间；：运输者针对节点、间的运输时间；：0-1变量，若经营者选择运输方案，则=1，否则=0；：0-1变量，若在处和之间存在中转，则=1，否则，=0；3.3问题的数学模型（1）碳排放计量为：， （3.1）（2）对于一种给定的运输方式，其单位距离下的燃油消耗量和速度的二次方成正比32-33，所以燃油消耗和运输速度之间的非线性关系为： （3.2）则目标函数为： （3.3） （3.4）s.t.； （3.5）； （3.6），； （3.7）=，； （3.8），； （3.9），； （3.10），； （3.11

39、）其中：模型包含两个指标，式（3.3）表示考虑成本指标，式（3.4）表示考虑碳排放指标；式（3.5）表示关于时间窗的约束；式（3.6）表示节点流量平衡约束；式（3.7）、（3.8）表示每个节点至多被访问一次；式（3.9）表示在起点、终点处不计时间和成本；式（3.10）、（3.11）表示决策变量的取值约束。 第四章 改进遗传算法设计4.1染色体编码方式染色体的编码对遗传算法的实现尤为重要，不同的染色体编码决定了算法的运行时间，以及解码的难易程度。常用的编码方式有两种：用二进制数表示和用自然数表示。用二进制表示染色体，解码很困难，运算消耗时间长，算法效率低，本文根据所要研究问题的特点采用自然数来进

40、行染色体编码，自然数编码比二进制编码更加简单、直接，路径中节点数目的不确定性也要求染色体的长度具有可变性。处于简单表示，计算机处理方便这里运用整数编码方式，假设为中从到的一条路径，为一个染色体编码。如图4.1所示，其染色体编码包含了运输方式和中转方式的选择。 图4.1网络图G4.2初始种群的生成为了保持个体的多样性，使初始种群尽可能均匀地分布在整个解空间，采用随机方式生成初始种群。采用基于通道最短路径法，具体步骤如下：（1）以、作为网络G中边和节点上的时间参数，求解出条时间最短路，即条染色体。（2）以、作为网络G中边和节点上的成本参数，求解出条成本最短路径。（3）随机生成条路径。（4）初始种群

41、的染色体数量。4.3适应度函数的建立GA算法通过适应度函数来判定一个染色体的好坏程度。而本问题中，目标函数是最小化总成本，即适应度函数值越小，对应的染色体的适应度就越大，所以直接采用目标函数值的倒数作为适应度函数。设、分别表示路径h的运输成本、运输时间和碳排放量，、分别表示、的上限、下限。路径h的适应度函数为 （4.1）其中： （4.2） 4.4选择策略选择策略是为了从当前的群体中选出优良的染色体复制到下一代群体中，染色体的适应度越高，被复制到下一代的可能性就就大，适应度差的染色体被遗传到下一代的可能性就越小，本论文采用轮盘赌和最佳保留相结合的方法为选择个体的依据。4.5交叉算子交叉算子又称重

42、组（Recombination），是用根据选择操作得到的两个染色体个体，以一定的概率按照某种方式互换一些基因，从而得到子代染色体的过程。当有2个以上的公共节点时，按照等概率选择其中之一作为交叉点。本文采用的交叉算子，在进行交叉过程中进行互换的最小整体为线路。如：父染色体为： ； ；交叉点为，子染色体为： ； ；4.6变异算子变异算子是通过一定的方式改变染色体个体的一些基因位，从而产生新的染色体。在GA算法中，变异可以扩大算法的搜索空间，保持群体中染色体个体的多样化，从而避免了局部最优解的产生。本文针对送货车辆路径问题的特点，采用基因插入、新网络删除、变换等操作，设中是从到的一条路径，具体的操作

43、如下：1. 基因插入：若、，则；2. 基因删除：若，则；3. 基因变换：若、且，则。4.7终止条件本文设计的算法终止条件如下：当某一解连续进化一定的代数后，其适应度值仍然没有变化，就终止算法，把得到的结果输出。如果一直进化，当算法运行到预先设定的最大的进化代数时，就终止算法，把得到的结果输出。4.8算法步骤改进遗传算法的步骤如下：（表示当前代数，表示个体计数器）Step 1：把车辆的可行的路径按照本文的编码方式编码为染色体；Step 2：初始化算法的参数；Step 3：生成初始的染色体种群；Step 4：= 0；Step 5： = 0；Step 6：计算群体中第个染色体个体的适应度；Step

44、7：= + 1；Step 8：若 = n，回到 Step 6，否则跳转到Step 9；Step 9：根据适应度选择父代；Step 10：进行交叉和变异操作；Step 11：= + 1；Step 12：如果满足算法的终止条件，则停止，否则跳转到Step 5。改进GA算法的流程图如图4.2所示：图4.2改进遗传算法流程图第五章 算例分析5.1验证算法本文是依据实际数据的取值范围，问题实例随机产生，对随机模型以及求解方法的有效性进行验证。实验以中国内陆A城市到中国内陆城市B的综合网络为例，参考某集团的近期中国交通网络数据，运输路线为中国交通网络运输，在节点数为16的情况下，生成综合网络拓扑结构，如图

45、5.1所示。承运人。其中，表示车1运输承运人；表示中国内陆铁路承运人；表示车2运输承运人；、表示中国内陆公路承运人；、表示车3运输承运人。为简化计算，将一小时作为一个时间单位，十公里作为一个距离单位。图5.1综合网络拓扑结构按照实际距离的取值范围，生成节点间的距离。某集团采用了表1给出的IPCC国家温室气体清单指南发布的不同运输方式的排放因子。（单位为g/kg-fuel）表1 各种运输方式的碳排放因子IPCC运输方式车1车2车3311031473185根据上述情景进行仿真实验，在BT,FT=500,560的情况下，按照均匀分布在指定参数区间内随机生成10实例、，表示随机生成的一组、，即联运网络

46、。算法采用Matlab7.0编程实现，所得结果在平台下测试得到。本文为验证算法的有效性，采用贪婪算法和遗传算法，利用适应度函数公式（4.1）、（4.2）来进行验证，当=0时，即不考虑碳排放量，比较贪婪算法和遗传算法的求解时间和方案成本，time表示求解时间，cost表示方案成本，则验证算法如表2：表2 贪婪算法与遗传算法相比较实例贪婪算法遗传算法timecosttimecost13.66544.673.70518.7321.17565.941.18538.9933.70588.053.74560.0544.35571.804.39544.5753.11557.043.14530.5163.10

47、552.813.13526.4973.36591.113.39562.9682.54554.352.57527.9593.19580.513.22552.87100.43565.620.43538.69从表2可以看出，在求解时间方面，贪婪算法和遗传算法求解时间相接近，但在方案成本方面，相比采用贪婪算法，采用遗传算法的方案成本明显较低。5.2仿真实验根据验证算法的比较结果得出采用遗传算法更具有效性，则设初始种群为10，进化次数为50，交叉、变异概率分别为0.7和0.1，在考虑碳排放指标（=0）和不考虑碳排放指标（=1）情况下进行模拟。M_C表示运输成本(单位为万元)，M_S表示碳排放量（单位为k

48、g）。结果如表3所示：表3 求解质量实例考虑碳排放指标不考虑碳排放指标M_CM_SM_CM_S1523.9235263.98518.7343535.772544.3829926.30538.9929376.713554.5019185.25560.0526645.794550.0224519.77544.5731843.885535.8241214.64530.5143845.366531.7537778.89526.4943423.947557.3922683.14562.9631948.088533.2330885.80527.9542896.969558.4020849.78552.87

49、23965.2110544.0822372.89538.6930647.80图5.2考虑与不考虑碳排放量的成本比较图5.3考虑与不考虑碳排放量的比较从仿真结果可以看出，一方面考虑碳排放指标下求解结果可以减排2.63-12.02吨；另一方面由于碳排放指标中对运输速度的考虑，而导致相比不考虑碳排放的情况，运输成本增加幅度较小。第六章 总结随着经济的发展，环境问题严峻，全球各国日益重视碳排放，车辆在运输过程中碳排放量被更多消费者和物流企业所关注，如何合理安排车辆的路径，在不显著改变物流企业运作成本的情况下，使得燃油消耗和碳排放成本得到明显的降低，已经成为多数企业的选择。本文针对考虑燃油消耗和碳排放的

50、VRP问题进行了研究，主要的研究工作总结如下：（1）首先针对考虑燃油消耗和碳排放的VRP问题，然后建立了相应的数学模型，并设计了改进TS算法，算法中采用有效的解的表示方式、初始解的产生、解的评价方法、终止条件以及算法的框架，最后进在标准的VRP算例上行了仿真实验，并对结果进行了分析。（2）接着在前人的工作基础上，着重研究了带时间窗的同时取送货绿色车辆调度与路径规划问题，重点关注了燃油消耗和碳排放成本。（3）以燃油消耗与碳排放、成本的最小化为目标，建立了取送货绿色车辆调度与路径规划问题的数学模型，该模型主要考虑行驶距离对燃油消耗和碳排放量的影响，对以车辆的运输时间和中转时间为约束条件来确定最短路

51、径降低成本进行决策。（4）设计了一种改进的遗传算法对取送货绿色车辆调度与路径规划问题进行求解，该算法采用有效的编码方式和特定的交叉算子，成功的实现了该问题的求解。（5）仿真实验结果表明该方法可以得到一个令人满意的车辆调度与路径规划的方案，此方案可以在不显著改变物流企业运作成本的情况下使得燃油消耗和碳排放成本得到了明显的降低，为企业在进行车辆调度时提供了有益的参考思路。- 22 -参考文献1 2015-2020年中国物流行业市场前瞻与投资战略规划分析报告.中国政府网.20152 温显斌，张桦，张颖等. 软计算及其应用.北京：科学出版社，2009.833 徐金明. MATLAB应用基础.北京：清华

52、大学出版社，2012.1724 陈国良，王煦法，庄镇泉等.遗传算法及应用M.北京：人民邮电出版社.1996:137-1575 刘敏，郑金华，蒋浩.基于多目标遗传算法求解时间窗车辆路径问题J.计算机工程与应用.2006,42（9）：186-189.6 Dantizing G, Ramser J. The truck dispatching problem J. Management Science, 1959, (6): 80-91.7 Min H. The multiple vehicle routing problems with simultaneous delivery and pick

53、-up points J. Transportation Research, 1989, 23A: 377-386.8 F. Montane and R. Galvao. Vehicle routing problems with simultaneous pick-up and delivery service J. Operational Research Society of India, 2002, 39(1): 19-33.9 M. Dell Amico, G. Righini, and M. Salani. A branch-and-price approach to the ve

54、hicle routing problem with simultaneous distribution and collection J. Transportation Science, 2006, 40(2): 235-247.10 J. Dethloff. Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up J. OR spectrum, 200l, 23(1): 79-96.11 G. Nagy and S. Salhi. He

55、uristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries J. European Journal of Operational Research, 2005, 162(1): 126-141.12 J.-F. Chen and T-H. Wu. Vehicle routing problem with simultaneous deliveries and pickups J. Journal of the Operational Research

56、Society, 2006, 57(5): 579-587.13 N. Bianchessi and G. Righini. Heuristic algorithms for the vehicle routing problem with simultaneous14 肖健梅, 李军军, 王锡淮. 求解车辆路径问题的改进微粒群优化算法J. 计算机集成制造系统, 2005, 11(4): 578-581.15 符桌. 带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究J. 系统工程理论与实践, 2004, 3: 123-128.16 马建华, 房勇, 袁杰. 多车场多车型最快完成车辆路径问

57、题的变异蚁群算法J. 系统工程理论与实践, 2011, 31(8): 1509-1516.17 彭春林, 梁春华, 周泓. 求解同时取货和送货车辆路径问题的改进遗传算法J. 系统仿真学报, 2008, 20(9): 2266-2270.18 张涛, 余绰娅, 刘岚, 邵志芳等. 同时送取货的随机旅行时间车辆路径问题方法J. 系统工程理论与实践, 2011, 31(10): 1913-1920.19 张涛, 田文馨, 张杰等. 带车辆行程约束的VRPSPD问题的改进蚁群算法J. 系统工程理论与实践, 2008, 1: 133-140.20 张涛, 张春梅, 张玥杰. 协同粒子群-模拟退火算法求解

58、VRPSPD问题J. 系统管理学报, 2009, 18(6): 682-685.21 胡大伟, 陈诚, 郭晓汾. 带集货和配送的多VRP优化算法研究,数学的实践与认识J. 2007, 37(2): 98-105. 22 龙磊, 陈秋双, 华彦宁. 具有同时集送货需求的车辆路径问题的自适应混合遗传算法J. 计算机集成制造系统, 2008, 14(3): 549-558. 23 曹二保. 物流配送车辆路径问题模型及算法研究D. 长沙: 湖南大学, 2008.24 蓝伯雄, 张跃. 求解带时间窗的装一卸载问题的概率式禁忌搜索法J. 中国管理科学, 2004, 24(3): 66-72.25 殷佳林,

59、 蒋泰. 基于蚁群算法求解带硬时间窗的VRPSDPJ. 计算机系统应用, 2009, 8: 152-157.26 段凤华, 符卓. 有软时窗约束带取送作业的车辆路径问题及其禁忌搜索算法研究J. 计算机工程与科学, 2009, 3(31): 68-70.27 郎茂祥. 物流配送车辆调度问题的模型和算法研究D. 北京: 北方交通大学, 2002.28 李军, 郭耀煌. 物流配送车辆调度理论与方法M. 北京；中国物资出版社, 2001.29 张燕, 周支立, 翟斌. 集货送货一体化的物流配送车辆路线问题的标号算法J. 运筹与管理, 2007, 16(3): 12-19. 30 葛继科，邱玉辉，吴春明

60、等.遗传算法研究综述J.计算机应用研究.2008（10）.31 赵振勇，王力，王保华等.遗传算法改进策略的研究J.计算机应用.2006(S2).32 Fagerholt K，Laporte G，Norstad I. Reducing fule emissions by optimizing speed on shipping routes. Journal of the Operational Research，2010，61(3)：523-529.33 Fihliozzi M A. The impacts of congestion on time-definitive urban frei

61、ght distribution networks CO2 emission levels：Research Part C，2011，19(5)：766-778.致谢谨在本实验以及毕业设计说明书完成之际，向所有在学习上和生活上帮助过我的老师们和同学们致以最诚挚的谢意！首先要感谢我的毕业设计指导教师老师。在此仿真实验的全过程中，从毕业设计选题的确定，本实验的技术选型，再到毕业设计说明书的撰写，老师都给了我很大的帮助。在此过程中，我收获的不仅仅是一份毕业设计，还从老师这里学到了很多工作方法与习惯，我对技术的理解也得到了更进一步的提升。然后要感谢的是我的同学们。在大学本科四年的生活与学习中，同学们之间有着良好的学习氛围与融洽的关