下载文档原格式
![[doc]基于改进遗传算法的VRP问题研究](https://uimg.taocdn.com/41e72e72793e0912a21614791711cc7931b778b5.webp)
摘要随着现代经济的快速发展，网络应用的广泛普及，物流配送这个“第三利润源泉”产业在日常生活中发挥着越来越大的作用，受到国内外各大企业的极大重视，如家乐福、沃尔玛、卓越亚马逊这些国际化企业，它们之所以在市场上拥有具大的垄断优势，以很低的价格吸引了越来越多的国内人士消费，除了企业本身拥有雄厚的资金和强有力的品牌效应外，更是由于其现代化的物流配送方式，而车辆调度问题(Vehicle Routing Problem，简称VRP)是物流配送中的重中之重。
解决了车辆调度问题，在一定程度上已经有效解决了物流配送问题，节省物流运输成本，从而提高企业的生产率，因此，此项研究在解决实际问题中具有非常重大的意义，如何有效的节省运输成本、降低企业成本，吸引更多的顾客，越来越受到人们的关注。
由于车辆调度问题是NP-hard问题，属于组合优化问题，该问题的复杂度与问题的规模成正比，至今没有找到精确的最有效解决方法，目前求解的算法有很多种，大致上可以分为精确算法和启发式算法两种，在本文中主要采用遗传算法这种特别适合于解决组合优化领域问题的全局搜索算法来求解车辆调度问题，遗传算法是一种基于达尔文“适者生存、优胜劣汰”进化原则的生物进化理论，通过模拟进化机制，具有较好的全局搜索能力，对于解决很多问题具有广泛的适用性。
本文首先介绍了车辆调度问题的研究背景、意义以及国内外发展现状，对车辆调度问题进行了相关的了解。
然后重点描述了车辆调度问题，简要分析了VRP 和TSP的区别、车辆调度问题数学模型的建立，并给出了车辆调度问题的分类以及求解方法。
第三章详细阐述了遗传算法的相关知识，包括遗传算法的产生发展、工作原理、基本概念操作特征、应用情况、研究动态以及未来的发展趋势，对遗传算法有了系统全面的了解。
在接下来的第四章采用了遗传算法来设计车辆调度问题，第五章给出了改进的遗传算法在车辆调度问题上的具体实验研究，同时分析了实验结果。
最后，本文对改进的遗传算法的实现进行了简单的阐述，并对遗传算法求解车辆调度问题的前景进行了展望，指出了以后的研究方向。
遗传算法求解VRP的种群初始化改进
正文
删除线
行内代码
上标
下标
清除格式
默认字号
默认字体
默认行高
左对齐
右对齐
居中对齐
两端对齐
增加缩进
减少缩进
遗传算法求解VRP的种群初始化改进
传统的遗传算法求解VRP时,初始种群多半采取随机生成法形成染色体方案,以致于迭代开始就可能形成许多不可行的方案,要进行大量的计算后才能得到优化的方案,这在很大程度上降低了算法的运算效率.论文提出的遗传编码策略,对初始种群给予基于知识型启发策略,使得初始种群一开始就表现为一种较优的状态.
王雷,张文义,Wang Lei,Zhang Wenyi(河海大学交通学院,江苏,南京,210098)。
文章编号:167326338(2006)062396204基于改进遗传算法的多约束V RP 求解吴升1,2,王钦敏1,彭国勇1,励惠国1,2(1.福州大学福建省空间信息工程研究中心,空间数据挖掘与信息共享教育部重点实验室,福建福州 350052;2.中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京 100101)摘要:建立了多约束条件车辆路径问题的数学模型和求解流程。
先采用最近插入法生成初始解,然后基于遗传算法和模拟退火算法改进初始解。
实验结果表明:结合模拟退火与遗传算法求解车辆路径问题,可以在一定程度上解决遗传算法易“早熟收敛”问题,从而得到更优的解。
关 键 词:车辆路径问题;最近插入法;遗传算法;模拟退火中图分类号:O223;P208 文献标识码:ASolving Multi 2restriction VRP by an Improved G enetic AlgorithmWU Sheng 1,2,WAN G Qin 2min 1,PEN G Guo 2yong 1,L I Hui 2guo 1,2(1.S patial I nf ormation Research Center ,Fuj ian Province ;Key L aboratory of S patial Data Mining and I nf ormation S haring ,M inist ry of Education ,Fuz hou Universit y ,Fuz hou 350052,China ;2.L R EI S ,I nstitute of Geog raphic S ciences and N atural Resources Research ,CA S ,B ei j ing 100101,China )Abstract :This paper established the mathematic model and solving flow of multi 2restriction vehicle routingproblem.After obtained the original results with “nearest insertion heuristic"algorithm ,a hybrid solution which combined “genetic algorithm"and “simulated annealing"was designed to improve the results.The nu 2merical analysis showed this solution overcame the problem of premature convergence of genetic algorithm ,and so the results were more optimized.K ey w ords :vehicle routing problem ;nearest insertion heuristic ;genetic algorithm ;simulated annealing 最近20多年来,国内外对V RP (Vehicle Routing Problem )问题作了大量而深入的研究,归纳起来,V RP 的求解方法基本上可以分为精确算法和启发式算法两大类。
遗传算法的VRP模型建模及求解由于经济全球化、物流在国民生产总值中的份额、生产模式的改变、企业竞争（成本、效率）、环境、现代信息技术对于传统物流的冲击，研究物流具有重要意义。
物流配送作为物流系统中一个不可分割的部分，对于物流路径优化将会使物流系统变得更加完善。
于是车辆调度就成为一个急需解决的关键问题， VRP模型也应运而生。
目前有不少研究者都运用遗传算法解决了一些物流领域的问题。
2 VRP问题的产生现代物流研究是由多种多样的方面构成的，而车辆调度问题VRP（Vehicle Routing Problem）是其中的一个关键，VRP问题很大程度上影响着现代物流的发展。
物流配送就是卖家根据用户的订货需求, 将货物集中在配送中心，再由配送中心进行货物的分装、搭配, 并将配好的货物按照卖家的要求及时安全送交给买家。
因为在物流配送业务中，存在着很大的不确定性，所以就有许多优化决策问题亟待解决。
国内外许多学者为运输车辆路线安排问题（VRP）构建了优化模型，并形成了许多解决问题的算法。
车辆调度问题（VRP）是为使用车辆（车辆数量确定或者不确定）访问客户而产生的路径，路径的和（即总成本）最小的一个问题。
VRP问题的条件是：每一客户只被车辆访问一次，且每条路径上的客户需求量之和不超过车辆的能力。
3遗传算法（GA）的优点由美国Michigan大学的John Holland教授创建的遗传算法(Genetic Algorithms 简称GA)是解决这一问题的一个方法。
遗传算法是从达尔文的物种进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说三种生物学上的理论演变而来的。
遗传算法就是将自然界中的遗传机制和生物进化论进行模拟，从而形成的一种搜索过程最优解的算法。
对于求解物流配送路径优化问题，遗传算法的出现为解决这个问题提供了一种全新的方法。
按照遗传算法的规则，设置一个初始种群，并从其开始，采用基于适应值比例的选择策略在当前的种群中选择个体，使用算法中杂交策略和变异规则产生第二代种群，通过不断的杂交和变异，产生一代代种群，直至产生满足最终期望值的终止条件。
遗传算法求解VRP问题的策略与技术分享在物流领域，车辆路径规划（VRP）问题一直是一个重要的挑战。
VRP问题的目标是找到一条最优路径，使得一组车辆能够在给定的时间窗口内，最大限度地满足一系列的需求点。
为了解决这个问题，许多优化算法被提出，其中遗传算法是一种被广泛应用的方法。
遗传算法是一种模拟自然进化过程的优化算法。
它通过模拟自然选择、交叉和变异等过程，逐步优化问题的解。
在VRP问题中，遗传算法可以通过以下几个步骤来求解：1. 个体编码：首先，需要将问题的解表示为一个个体。
在VRP问题中，每个个体可以表示为一条路径，其中包含一系列的需求点。
2. 初始种群生成：生成一个初始的种群，其中包含多个个体。
可以使用随机生成的方法，或者根据问题的特点设计一个启发式算法来生成种群。
3. 适应度评估：根据问题的目标函数，对每个个体进行适应度评估。
在VRP问题中，适应度可以表示为路径的总长度或者满足需求点的程度。
4. 选择操作：根据适应度评估的结果，选择一部分个体作为父代。
常用的选择方法有轮盘赌选择和竞争选择等。
5. 交叉操作：对选择出的父代进行交叉操作，生成新的个体。
在VRP问题中，可以使用交叉点来切割路径，并将路径的一部分交换到另一个个体中。
6. 变异操作：对交叉后的个体进行变异操作，引入新的解。
在VRP问题中，可以通过随机选择需求点，并将其插入到路径中的其他位置。
7. 新种群生成：根据选择、交叉和变异操作的结果，生成一个新的种群。
可以使用保留最优个体的策略，确保种群的多样性和收敛性。
8. 终止条件判断：判断是否达到终止条件，如果满足则结束算法，否则返回步骤3。
遗传算法求解VRP问题的关键在于个体编码和适应度评估。
在个体编码方面，需要设计一个合适的表示方法，使得路径的结构和约束能够得到满足。
在适应度评估方面，需要根据问题的特点设计一个合适的目标函数，能够准确地评估路径的优劣。
此外，遗传算法还可以通过一些策略和技术来提高求解效果。
文章编号:167326338(2006)062396204基于改进遗传算法的多约束V RP 求解吴升1,2,王钦敏1,彭国勇1,励惠国1,2(1.福州大学福建省空间信息工程研究中心,空间数据挖掘与信息共享教育部重点实验室,福建福州 350052;2.中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室,北京 100101)摘要:建立了多约束条件车辆路径问题的数学模型和求解流程。
先采用最近插入法生成初始解,然后基于遗传算法和模拟退火算法改进初始解。
实验结果表明:结合模拟退火与遗传算法求解车辆路径问题,可以在一定程度上解决遗传算法易“早熟收敛”问题,从而得到更优的解。
关 键 词:车辆路径问题;最近插入法;遗传算法;模拟退火中图分类号:O223;P208 文献标识码:ASolving Multi 2restriction VRP by an Improved G enetic AlgorithmWU Sheng 1,2,WAN G Qin 2min 1,PEN G Guo 2yong 1,L I Hui 2guo 1,2(1.S patial I nf ormation Research Center ,Fuj ian Province ;Key L aboratory of S patial Data Mining and I nf ormation S haring ,M inist ry of Education ,Fuz hou Universit y ,Fuz hou 350052,China ;2.L R EI S ,I nstitute of Geog raphic S ciences and N atural Resources Research ,CA S ,B ei j ing 100101,China )Abstract :This paper established the mathematic model and solving flow of multi 2restriction vehicle routingproblem.After obtained the original results with “nearest insertion heuristic"algorithm ,a hybrid solution which combined “genetic algorithm"and “simulated annealing"was designed to improve the results.The nu 2merical analysis showed this solution overcame the problem of premature convergence of genetic algorithm ,and so the results were more optimized.K ey w ords :vehicle routing problem ;nearest insertion heuristic ;genetic algorithm ;simulated annealing 最近20多年来,国内外对V RP (Vehicle Routing Problem )问题作了大量而深入的研究,归纳起来,V RP 的求解方法基本上可以分为精确算法和启发式算法两大类。
遗传算法在VRP问题中的应用
遗传算法在VRP问题中的应用
配送是物流系统中一个直接与消费者相连的重要环节,对配送系统进行优化,可以提高物流经济效益、实现物流科学化,因此配送系统的优化问题显得尤为重要.进行配送系统优化,主要是配送车辆调度的优化.文章在全面分析研究物流配送业务特点的基础上,针对配送中的核心问题--车辆调度优化问题进行了深入的研究,建立了单源点物流配送车辆调度优化问题的数学模型,并运用遗传算法对其进行求解,仿真实例证明了该方法的有效性.
作者：张国英林贤茂 ZHANG Guo-ying LIN Xian-mao 作者单位：山东大学现代物流研究中心,山东,济南,250061 刊名：物流科技英文刊名： LOGISTICS SCI-TECH 年，卷(期)： 2009 32(5) 分类号： U116.2 关键词：物流配送车辆调度遗传算法。
遗传算法求解VRP 问题的技术报告摘要：本文通过遗传算法解决基本的无时限车辆调度问题。
采用车辆和客户对应排列编码的遗传算法，通过种群初始化，选择，交叉，变异等操作最终得到车辆配送的最短路径。
通过MA TLAB 仿真结果可知，通过遗传算法配送的路径为61.5000km,比随机配送路径67km 缩短了5.5km 。
此结果表明遗传算法可以有效的求解VRP 问题。
一、 问题描述1.问题描述车辆调度问题（Vehicle Scheduling/Routing Problem,VSP/VRP ）的一般定义为[1]：对一系列送货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量，送发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。
问题描述如下[2]：有一个或几个配送中心),...,1(n i D i =，每个配送中心有K 种不同类型的车型，每种车型有n 辆车。
有一批配送业务),...,1(n i R i =，已知每个配送业务需求量),...,1(n i q i =和位置或要求在一定的时间范围内完成，求在满足不超过配送车辆载重等的约束条件下，安排配送车辆在合适的时间、最优路线使用成本最小。
2.数学模型设配送中心有K 台车，每台车的载重量为),...,2,1(K k Q k =，其一次配送的最大行驶距离为k D ，需要向L 个客户送货，每个客户的货物需求量为),...,2,1(L i q i =，客户i 到j 的运距为ij d ，配送中心到各个客户的距离为),...,2,1,(0L j i d j =，再设k n 为第K 台车配送的客户数（k n =0表示未使用第K 台车），用集合k R 表示第k 条路径，其中ki r 表示客户ki r 在路径 k 中的顺序为 （不包括配送中心），令 0k r 表示配送中心，若以配送总里程最短为目标函数，则可建立如下数学模型：∑∑==•+=-K k k rk r n i r r n sign d d Z k kn k ki i k 101)]([min )1( (1)k n i ki Q qr k ≤∑=1 (2) k k rk r n i r r D n sign d dk kn k ki i k ≤•+∑=-)(01)1( (3)L n k ≤≤0 (4)L nK k k =∑=1 (5)},...,2,1},,...,2,1{{k ki ki k n i L r r R =∈= （6）21,21k k R R k k ≠∀∅=⋂ （7）⎩⎨⎧⎭⎬⎫≥=其他01n 1)(k k n sign （8）上述模型中，式（1）为目标函数，即要求配送里程最短；式（2）保证每条路径上各个客户的货物需求量之和不超过配送车的载重；式（3）保证每条配送路径的长度不超过配送车的最大行驶距离；式（4）表明每条路径上的客户数不超过总客户数；式（5）表明每个客户都得到配送服务；式（6）表示每条路径的客户组成；式（7）限制每个客户仅能由一台配送车送货；式（8）表示当第 k 辆车服务的客户数大于等于1时，说明该台车参加了配送，则sign(n)的值取1，否则为0。
基于遗传算法的VRP问题求解研究在物流配送领域中，VRP（Vehicle Routing Problem，车辆路径问题）一直是一个困扰着企业的难题。
当企业需要将海量的物品送到不同客户处时，如何在最短时间和最小成本内完成配送任务是一个非常重要的问题。
而遗传算法（Genetic Algorithm，GA）作为一种自适应的优化算法，能够有效地解决VRP问题。
本文将介绍基于遗传算法的VRP问题求解的相关研究。
一、VRP问题的概念与特点VRP问题是指在一定数量的车辆和客户点之间，找到一种方案，使得所有客户点都能够被唯一的车辆进行服务，并且所有车辆的行驶路程最小或成本最小。
VRP 问题的主要特点有以下几点：1. 复杂性高：VRP问题是一个NP硬问题，在实际情况下很难通过贪心算法或动态规划算法求解，并且数据的规模非常大。
2. 约束条件多：VRP问题还存在许多约束条件，如车辆容量限制、时间窗口限制等等，进一步增加了问题的难度。
3. 解的多样性：VRP问题存在多种解决方案，并且不同解决方案的具体路线和成本都不同，为问题的求解带来了更大的挑战。
二、遗传算法的基本原理遗传算法是一种通过模拟生物进化过程，寻找问题最优解的智能算法。
其基本流程如下：1. 初始化种群：按照问题的要求初始化一定数量的个体作为初代种群。
2. 个体编码：将每个个体进行某种编码方法，形成一个码字串。
3. 适应度评估：依据问题的特定要求，对每一个个体进行适应度评估，并确定一个适应度函数。
4. 选择操作：根据适应度函数，筛选出优质个体。
5. 交叉操作：将优质个体进行随机交叉，生成新个体。
6. 变异操作：对新个体中的部分编码进行变异操作。
7. 新一代种群生成：将经过交叉和变异处理的新个体，按照一定规则生成新一代种群。
8. 终止条件满足：若满足终止条件，则终止算法；否则返回步骤3。
三、基于遗传算法的VRP问题求解策略基于遗传算法的VRP问题求解策略主要分为初始化种群、个体编码、适应度评估、选择操作、交叉操作、变异操作、新一代种群生成等几个步骤。
基于免疫遗传算法的物流配送VRP求解的开题报告一、研究背景和意义近年来，随着物流业的快速发展，物流配送问题成为了当前亟待解决的难题。
物流配送中的车辆路线规划问题，通过优化车辆路线，可以降低运输成本，提高物流配送效率，进一步推动物流行业的发展。
由于物流配送问题具有复杂性、约束性、多目标性等特点，传统的优化算法难以有效解决这些问题。
目前，遗传算法等基于进化策略的方法被广泛应用于物流配送问题求解中，并取得了良好的效果。
然而，传统的遗传算法容易陷入局部最优解，对解决复杂的物流配送问题存在局限性。
因此，本研究将结合免疫算法的思想，提出一种基于免疫遗传算法的物流配送VRP（Vehicle Routing Problem）求解方法，以提高物流配送问题的求解效率和质量。
二、研究内容和思路本研究旨在解决物流配送VRP问题，提出基于免疫遗传算法的VRP 求解方法，具体思路如下：（1）对物流配送VRP问题进行建模，确定优化目标与约束条件。
（2）提出一种基于免疫遗传算法的物流配送VRP求解方法，并优化算法中的关键参数。
（3）通过实验验证，对比分析提出的算法与传统算法的求解效率和求解质量。
三、初步的研究计划和时间表1.文献调研（1个月）（1）收集物流配送VRP问题相关的文献和研究现状；（2）学习免疫遗传算法相关的基础知识和原理。
2.问题建模与算法设计（2个月）（1）确定问题优化目标和约束条件；（2）设计基于免疫遗传算法的VRP求解方法；（3）优化关键参数。
3.实验设计与结果分析（2个月）（1）设计实验对比传统算法与本研究提出的算法的求解效率和求解质量；（2）分析实验数据。
4.论文撰写（2个月）（1）撰写论文草稿，并与导师和专家进行交流和修改；（2）完成论文并提交。
四、存在的问题和挑战1.免疫遗传算法在解决VRP问题中的应用研究较少，需要针对实际问题进行改进和优化。
2.免疫遗传算法本身也存在问题，如算法收敛速度较慢、算法参数设置需要较高的技术水平等。
基于免疫遗传算法的物流配送VRP问题研究的开题报告题目：基于免疫遗传算法的物流配送VRP问题研究一、选题背景随着物流信息化和自动化的快速发展，物流配送的效率和质量得到了显著提升。
虽然VRP问题已被广泛研究和应用，但是针对复杂的实际物流配送情况，VRP问题仍面临着很多难题。
免疫遗传算法是一种有效的优化算法，它可以通过模仿人类免疫系统和遗传机制来解决优化问题。
通过将免疫遗传算法应用于VRP问题中，可以得到更好的解决方案，从而提高物流配送效率和质量。
二、研究目的和意义本研究旨在探究免疫遗传算法在解决物流配送VRP问题中的应用，寻求更优的配送方案。
通过研究，可以得到以下几个方面的意义：1.提高物流配送效率和质量，降低成本，增强企业竞争力。
2.为相关企业和组织提供参考和借鉴，促进物流业的健康发展和技术进步。
3.丰富运筹学和智能算法在物流配送领域的应用，推动相关理论发展。
三、研究内容和方法本研究将以免疫遗传算法为基础，探究其在物流配送VRP问题中的应用。
具体内容包括：1.分析VRP问题的基本概念和特点，分析VRP问题在实际物流配送中的应用场景。
2.介绍免疫遗传算法的原理和优缺点，对免疫遗传算法进行改进以适应VRP问题的优化需求。
3.设计并实现基于免疫遗传算法的物流配送VRP问题求解模型，对模型进行实验和验证，并与其他算法进行比较。
4.对实验结果进行分析和总结，进一步探究免疫遗传算法在VRP问题中的应用优势和不足。
本研究将采用文献调研和深度分析、数学建模、算法实现和优化、实验验证和数据分析等方法，全面探究免疫遗传算法在VRP问题中的应用。
四、研究进度和计划本研究的进度和计划如下：1.前期调研和准备（1个月）：研究相关文献，了解VRP问题的基本概念和免疫遗传算法的原理，明确研究思路和方法。
2.模型设计和算法实现（3个月）：设计并实现基于免疫遗传算法的物流配送VRP问题求解模型，对模型进行实验和验证。
3.分析和总结（2个月）：对实验结果进行分析和总结，进一步探究免疫遗传算法在VRP问题中的应用优势和不足。
遗传算法求解VRP 问题的技术报告摘要：本文通过遗传算法解决基本的无时限车辆调度问题。
采用车辆和客户对应排列编码的遗传算法，通过种群初始化，选择，交叉，变异等操作最终得到车辆配送的最短路径。
通过MA TLAB 仿真结果可知，通过遗传算法配送的路径为61.5000km,比随机配送路径67km 缩短了5.5km 。
此结果表明遗传算法可以有效的求解VRP 问题。
一、 问题描述1.问题描述车辆调度问题（Vehicle Scheduling/Routing Problem,VSP/VRP ）的一般定义为[1]：对一系列送货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量，送发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。
问题描述如下[2]：有一个或几个配送中心),...,1(n i D i =，每个配送中心有K 种不同类型的车型，每种车型有n 辆车。
有一批配送业务),...,1(n i R i =，已知每个配送业务需求量),...,1(n i q i =和位置或要求在一定的时间范围内完成，求在满足不超过配送车辆载重等的约束条件下，安排配送车辆在合适的时间、最优路线使用成本最小。
2.数学模型设配送中心有K 台车，每台车的载重量为),...,2,1(K k Q k =，其一次配送的最大行驶距离为k D ，需要向L 个客户送货，每个客户的货物需求量为),...,2,1(L i q i =，客户i 到j 的运距为ij d ，配送中心到各个客户的距离为),...,2,1,(0L j i d j =，再设k n 为第K 台车配送的客户数（k n =0表示未使用第K 台车），用集合k R 表示第k 条路径，其中ki r 表示客户ki r 在路径 k 中的顺序为 （不包括配送中心），令 0k r 表示配送中心，若以配送总里程最短为目标函数，则可建立如下数学模型：∑∑==•+=-K k k rk r n i r r n sign d d Z k kn k ki i k 101)]([min )1( (1)k n i ki Q qr k ≤∑=1 (2) k k rk r n i r r D n sign d dk kn k ki i k ≤•+∑=-)(01)1( (3)L n k ≤≤0 (4)L nK k k =∑=1 (5)},...,2,1},,...,2,1{{k ki ki k n i L r r R =∈= （6）21,21k k R R k k ≠∀∅=⋂ （7）⎩⎨⎧⎭⎬⎫≥=其他01n 1)(k k n sign （8）上述模型中，式（1）为目标函数，即要求配送里程最短；式（2）保证每条路径上各个客户的货物需求量之和不超过配送车的载重；式（3）保证每条配送路径的长度不超过配送车的最大行驶距离；式（4）表明每条路径上的客户数不超过总客户数；式（5）表明每个客户都得到配送服务；式（6）表示每条路径的客户组成；式（7）限制每个客户仅能由一台配送车送货；式（8）表示当第 k 辆车服务的客户数大于等于1时，说明该台车参加了配送，则sign(n)的值取1，否则为0。
二、 研究现状车辆调度问题在目标和范围方面有很大差别，主要是研究的目标和限定条件不同。
在研究目标方面有的是最短路线，有的是最短时间，有的是客户的方便程度等等。
在限定条件方面，有配送中心方面的区别，和有单配送中心的，有多配送中心；有配送车辆的数量、种类方面的区别，如车辆数有限、无限、单一车型和多种车型；在业务种类方面，有的是集货任务，有的是送货业务，有的是集送一体化业务，有的是各种业务混合情况。
有时间窗的车辆调度问题是最为普通的问题，以成为研究热点。
遗传算法在搜索过程中能够自动获取和积累有关搜索空间的知识，并能利用问题固有的知识来缩小搜索空间，自适应地控制搜索过程，动态有效地降低问题的复杂度，从而求得原问题的真正最优解或满意解，因此我来选用遗传算法来求解VSP 问题。
三、 解决方法遗传算法的流程图如下：初始化群体个体评价t<T?终止NY选择交叉变异基于车辆和客户对应排列编码的遗传算法的基本步骤：（1）编码：采用车辆和客户对应排列的编码方法，其基本思路是：用车辆数间的任意自然数（可重复）的排列表示车辆排列，用客户数间的互不重复的自然数排列表示客户排列，两者相对应，构成一个解，并对应一个配送路径方案。
例如：对于一个用3台车向9个客户送货的车辆调度优化问题，设某解为（122131223）（456712398），即车辆排列为122131223，客户排列为456712398，两个排列相对应。
（2）适应度函数：直接采用公式（1）作为适应度评估函数。
对不可行路径进行权重惩罚。
（3）选择策略：采用最佳个体保存与赌轮相结合的选择策略。
其具体操作为：将每代群体中的N个个体按适应度由小到达排列，排在首位的个体性能最好，将它直接复制到下一代。
下一代群体的令N-1个体需要根据上一代群体的N个个体的适应度采用赌轮选择。
（4）交叉操作：在该编码方式下有几种编码方式：仅对车辆编码进行交叉、仅对客户编码进行交叉和同时对客户编码和车辆编码进行交叉。
本方法中采用仅对车辆编码的方式来交叉。
（5）变异操作：本程序中对于变异操作，采用对客户编码变异的方式。
用MA TLAB编程，在内存为2G，CPU 2.10GHz的微机上运行。
采用运行参数：种群规模为100，交叉概率为0.9，变异概率为0.2，进化代数100。
变异仅对客户编码，对不可行路径的惩罚权重去100km，具体程序代码见附录。
四、仿真结果某配送中心有2台车，其载重量均为8t,车辆每次配送的最大行驶距离均为50km，配送中心与8个客户之间及8个客户之间相互距离及货物需求见下表：表1 客户需求表2 点对间距表运行结果如下：五、结论从以上仿真结果可知，用遗传算法通过选择，交叉，变异等操作最终求得配送车辆物流问题中的最短路径，减少了车辆资源和时间的浪费，缩短了运输成本。
同时，在车辆调度问题中，进一步加入时间窗等参数的车辆调度问题的遗传算法的求解，还需要进一步的学习研究。
六、参考文献[1]施朝春，王旭，葛显龙。
带有时间窗的多配送中心车辆调度问题研究[J] 。
计算机工程与应用，2009；45（34）：21—24[2]程世东，刘小明，王兆赓。
物流配送车辆调度研究的回顾与展望[J]。
交通运输工程与信息学报，2004；2（3）：93—97七、附录：程序clear all;close all;D=[ 0 6.5 4 10 5 7.5 11 10 4;6.5 07.5 10 10 7.5 7.5 7.5 6;4 7.5 0 10 5 9 9 15 7.5;10 10 10 0 10 7.5 7.5 10 9;5 10 5 10 0 7 9 7.5 20;7.5 7.5 9 7.5 7 0 7 10 10;11 7.5 9 7.5 9 7 0 10 16;10 7.5 15 10 7.5 10 10 0 8;4 6 7.5 9 20 10 16 8 0];n=40;C=100;Pc=0.9;Pm=0.2;N=8;family=zeros(n,N);ticfor i=1:nfamily(i,:)=randperm(N);endGt=family(1,:);Ln=zeros(n,1);for kg=1:1:Ctime(kg)=kg;%------------------------------计算路径长度-----------------------------for i=1:1:nLn(i,1)=fitness1(D,family(i,:)); %计算每条染色体的适应度值EndMinLn(kg)=min(Ln);minLn=MinLn(kg);rr=find(Ln==minLn);Gt=family(rr(1,1),:);%更新最短路径Family=family;kg;minLn;%--------------------------------选择复制-------------------------------K=30;aa=0;bb=0;[aa,bb]=size(Family);Family2=Family;Ln2=Ln;[Ln]=sort(Ln);for i=1:aatt=find(Ln2==Ln(i,1));Family(i,:)=Family(tt(1,1),:);endfor i=1:Kj=aa+1-i;Family(j,:)=Family(i,:);end%---------------------------------交叉---------------------------------[aa,bb]=size(Family);Family2=Family;for i=1:2:aaif Pc>rand&&i<aaA=Family(i,:);B=Family(i+1,:);[A,B]=intercross(A,B);Family(i,:)=A;Family(i+1,:)=B;e ndend%-------------------------------变异-----------------------------------Family2=Family;for i=1:aaif Pm>=rand %变异条件Family(i,:)=mutate(Family(i,:));EndendFamily=[Gt;Family]; %保留上一代最短路径[aa,bb]=size(Family);if aa>nFamily=Family(1:n,:);endfamily=Family;clear FamilyendtocGtRL=fitness1(D,Gt)plot(time,MinLn);xlabel('times');ylabel('MinLn');（1）适应度函数function len=fitness1(D,p)N=8;len=0;for i=1:(N-1)len=len+D(p(i),p(i+1));endlen=D(N,p(1))+len+D(p(N),N);b=0;total=[0 0];volume=8;demand=[1 2 1 2 1 4 2 2 0];b=find(p==8);if b==1total(1)=0;for i=2:Ntotal(2)=demand(p(i))+total(2);endelseif b==9total(2)=0;for i=1:(N-1)total(1)=demand(p(i))+total(1);endelsefor i=1:(b-1)total(1)=demand(p(i))+total(1);endfor i=(b+1):Ntotal(2)=demand(p(i))+total(2);endendif total(2)>volume|total(1)>volumelen=len+100;end（2）交叉操作函数function [a1,b1]=intercross(a1,b1)L=length(a1);w=[0 0];w(1)=unidrnd(L-2);w(2)=L-w(1);if w(2)<w(1)[w(1),w(2)]=exchange(w(1),w(2));elsew(1)=w(1);w(2)=w(2);endfor i=w(1):(w(2)-1)xx=find(a1==b1(i+1));yy=find(b1==a1(i+1));[a1(i+1),b1(i+1)]=exchange(a1(i+1),b1(i+1));[a1(xx),b1(yy)]=exchange(a1(xx),b1(yy));end（3）对调操作函数function [x1,y1]=exchange(x1,y1)temp=x1;x1=y1;y1=temp;（4）变异函数function c=mutate(c)L1=length(c);rray=randperm(L1);[c(rray(1)),c(rray(2))]=exchange(c(rray(1)),c(rray(2)));。
