《基于遗传算法的车辆路径优化研究的相关的基础理论综述》7700字

基于遗传算法的车辆路径优化研究的相关的基础理论综述目录TOC\o"1-2"\h\u20563基于遗传算法的车辆路径优化研究的相关的基础理论综述 1231021.1车辆路径问题 189851.1.1车辆路径问题的一般描述 1279421.1.2车辆路径问题的分类 2224841.1.3车辆路径问题要素 3228391.1.4时间窗的相关理论 5319901.2遗传算法 754901.1.1遗传算法的定义 737171.1.2遗传算法的特点 8129621.1.3遗传算法的步骤 91.1车辆路径问题1.1.1车辆路径问题的一般描述车辆路径问题（VehicleRoingProblem,简称VRP），是从旅行商问题TravelingSalesman，简称TSP）演变过来，在TSP中加入约束条件的路径优化问题。VRP一般描述为：在配送中心和客户需求点位置已知的基础上，配送中心具有一定数量的车，在车辆装载量、货物需求量、时间窗等约束条件下，达到成本最少或者总时间最少、车辆总里程最少、配送车辆数最少、客户满意度最大等目标，车辆从配送中心出发按照顺序为客户提供服务，最后回到配送中心，一般情况下会引入惩罚函数，将惩罚函数与上述若干个目标函数进行组合。设计车辆合理的行使路径，使目标函数达到最优。为了更清楚地描述车辆路径优化问题，基础VRP如图2-1所示。定义完全图，其中为配送节点集合，当为配送中心，为弧集合，为客户点集合，配送中心拥有辆额定载重量为Q的车，当配送节点，表示客户点，客户的需求为，路径弧表示客户点到客户点，配送成本为。有向图中的各个节点用有向的线段进行连接，节点必须有车辆进行配送，且配送车辆从配送中心出发只能从一个节点到另一个节点，不能进行返回，最后回到配送中心。图2-1车辆路径优化问题示意图Figure2-1Schematicdiagramofvehicleroutingoptimizationproblem1.1.2车辆路径问题的分类按照车辆路径问题各个研究要素的不同特征和特点可以将路径问题分成不同类型，依据己有的研究成果，可将其归纳如表2-1所示：表2-1车辆路径问题分类Table2-1Classificationofvehicleroutingproblems配送任务特征纯配送纯取货送取混合周期周期配送非周期配送服务方式车辆一次服务单个客户车辆一次服务多个客户车辆约束车型单车型、多车型容量有容量限制、无容量限制是否返回配送中心开放式（不返回）、封闭式(返回）载货情况满载、非满载、满载和非满载混合时间窗约束有时间窗硬时间窗软时间窗混合时间窗无时间窗客户和配送网络的特点确定性问题不确定性问题随机车辆路径问题模糊车辆路径问题目标个数单一目标多目标1.1.3车辆路径问题要素车辆配送问题涉及货物、车辆、客户、物流据点、配送网络等多个研究要素，各个研究要素是车辆路径问题分类的主要依据，各个研究要素具体特征如下：（1）货物配送中心配送客户需求的货物，货物的特征影响车辆配送的路线。如货物是否需要冷藏，决定了车辆是否使用冷藏车；客户要求货物的送达时间，即客户的服务时间窗，决定货物什么时间开始进行配送，选择什么样的路径进向配送，要求在时间窗内进行服务；货物的包装、体积和重量决定了车辆的类型、数量和是否能够进行混装。（2）车辆车辆根据货物的特征、数量、体积和重量进行选择，车辆是货物进行配送的工具。车辆有不同类型，根据配送中心的配置、货物的特征和客户的位置进行选择，如生鲜产品需要冷藏车进行配送，化学危险品和液化石油气等易燃易爆货品需要采用专门的车辆进行配送，并且对配送的车辆有很高的要求。车量的装载量，包括车辆的装载重量和装载体积，车辆的类型不同，装载量也不同，配送中心一般有多种不同装载辆的车，对需求量不同的客户进行配送。车辆的行使距离，根据车辆类型的不同，进行划分，行驶距离远转载量大的车辆能够服务多个距离较远的客户。（3）客户客户作为物流服务的对象，它的地理位置是运输网络的节点。客户对物流服务的要求体现在配送货物是否能在保证完好无损的前提下，在规定的时间内送达。根据客户对货物的需求，可以将车辆路径问题划分成不同的类型，客户对货物送达的时间的要求，是时间点还是时间窗，时间窗分为软时间窗和硬时间窗；客户对货物的需求有确定性的、不确定性的、静态或者动态，客户的要求构成车辆路径优化建模的重要约束条件和目标函数。客户会根据地理位置和货物特殊性对车辆的种类进行限制。客户的类型包括零售店、分销商、连锁店和单个消费者等。（4）配送中心配送中心是运输网络的出发节点和终止节点，不单单局限是一个仓库，拥有处理客户订单，并对货物进行包装、分拣、仓储、流通加工的能力，根据客户的要求，设计合理的配送路线，选择合适车辆进行配送。配送中心具有装卸搬运的工具、不同类型的车、流通加工的设备、处理信息的设备等。在信息化的时代，利用计算机对客户的需求进行预测，存储一部分的货物，一方面更好的满足客户需求，另一方面应对突然的需求剧增；一般以最少的配送中心服务更多的客户，减少建设配送成本。此外配送中心是连接生产者和客户的关键节点，因此配送中心对配送需求的反应速度越快，客户快速的得到物流服务，客户的满意度越高。能够提高企业的竞争力。（5）配送网络配送网络的节点包括配送中心和客户，配送中心的数量可以是一个，也可以是多个，各个节点之间的弧线有无相、单向和双向，取决于车辆行使方向是单向还是双向，可以在配送网络中的弧线赋予配送线路的费用、客户的需求、车辆的行驶距离和时间等的权重。（6）约束条件车辆配送路径的约束根据客户的具体需求而定，包括是否有时间窗约束，时间窗是硬时间窗还是软时间窗；配送车辆是单车型还是多车型；车辆的行使距离和装载量约束；每个客户被服务的次数；车辆配送结束后是否返回配送中心等约束。（7）目标函数车辆路径问题的优化目标根据实际情况的不同而不同，有单目标函数和多目标函数，多目标函数由多个单目标函数构成。目标函数一般有配送总成本最小，配送总成本包括车辆的行使成本、油耗成本、车辆的折损成本、人工成本等；车辆装载率最大，减少行使车辆的数量，减少成本；客户的满意度最大，客户的满意度越高，客户的数量越多，企业的利润就越高；还包括总配送时间最短、配送效率最高等目标。1.1.4时间窗的相关理论在现实物流活动中，客户对配送时间的要求越来越注重，衍生出带时间窗的车辆路径问题，简称VRPTW是以VRP为基础加上时间窗的约束，传统的VRP考虑车辆装载量、配送中心、客户的需求量等约束条件之外，还要考虑进行配送任务的车辆在客户规定的时间窗内送达，车辆对客户服务的时间也有约束。带时间窗的车辆路径问题具体内容有，每一个客户点都有车辆服务的时间，是一个时间段不是一个时间点，时间段随着客户点的不同而不同。车辆从配送中心出发，在客户规定时间段内送达并进行服务，满足客户的需求，企业或者配送车辆不会受到惩罚；配送车辆在客户规定的时间段之前到达，不能立即对客户进行服务，需要等到客户规定的时间段内进行服务，会产生一定的等待成本，企业和车辆要承担这部分等待成本；配送车辆在顾客规定的时间段之后到达，错过了为客户服务的时间，客户可以拒收或者在下个时间段内进行服务，不但会影响下一个客户点的配送，客户对企业的好感度也会下降，车辆会因为晚到受到惩罚，产生惩罚成本。配送车辆早到或者晚到都会受到惩罚，产生惩罚成本，企业和车辆要承担这部分费用，导致企业的利润下降。对时间窗的分类一般有两种，分别包括以下内容：（1）根据客户对时间段的要求不同，可以将时间窗划分为两种。分别是双边时间窗和单边时间窗。双边时间窗指客户要求车辆在规定的时间窗内进行服务，分别规定了最早进行服务的时间和最晚进行服务的时间即时间窗的上下限。单边时间窗指客户规定一个时间，在这个时间之前进行服务就可以，不需要等待时间。（2）根据配送车辆在时间段内送达可以将时间窗分为硬时间窗、软时间窗和混合时间窗：1．硬时间窗的车辆路径问题是指客户要求必须在规定的时间段内进行服务，不能早于或者晚于规定的时间段，早到或者晚到都不接受服务，会受到很高的惩罚。硬时间窗的车辆路径问题对时间的要求很高。如图2-2所示，客户规定的时间窗为[a，b]，惩罚函数为P(t)，硬时间窗的客户不能有超过时间窗的情况出现，设计很高的惩罚成本M，配送车辆到达客户点的时间在a之前或者b之后，都会有一个很高的成本M。严格按照客户规定时间进行服务，一般在冷链物流、JIT生产等对时间要求很高的行业的配送中出现。图2-2硬时间窗车辆路径问题惩罚成本Figure2-2Penaltycostofvehicleroutingproblemwithhardtimewindows2．软时间窗的车辆路径问题，如图2-3所示，配送车辆在客户规定的时间窗[a，b]内不会产生惩罚成本，在客户规定的最早到达时间a之前到达，或者在客户规定的最晚到达时间b之后到达，企业对违反时间窗的车辆进行惩罚。与硬时间窗的车辆路径问题相比，软时间的车辆路径问题对时间窗的要求较宽容，无论早到或者晚到客户都允许车辆进行服务，早到的车辆需要等到客户规定的时间段内进行服务，会产生相应的等待成本；晚到的车辆客户会根据实际情况接受服务，影响下一个客户的配送；早到的车辆对客户的影响较小，一般早到的惩罚小于晚到的惩罚，在时间窗内到达企业的成本最小，配送效率最高，在本文实例研究中惩罚函数采用软时间窗。图2-3软时间窗车辆路径问题惩罚成本Figure2-3Penaltycostofvehicleroutingproblemwithsofttimewindows3．混合时间窗融合了硬时间窗与软时间窗，如图1.4客户规定的时间窗为[a，b]，配送车辆在[c，a)和(b，d]内送达会受到惩罚，早到和晚到的时间越长惩罚成本越大；配送车辆在c之前或者在d之后到达，客户不接受服务，受到一个很大的惩罚成本M；配送车辆在[a，b]内到达不会产生惩罚成本。图1.4混合时间窗车辆路径问题惩罚成本Figure2-3Penaltycostofvehicleroutingproblemwithmixedtimewindows软时间窗在现实生活中的意义比硬时间窗和混合时间窗的大，硬时间窗在现实的使用比较少，只有在对配送时间有严格要求的企业或者行业中使用，例如报纸、新鲜牛奶和生鲜冷链物流的配送等，配送成本高，不允许早到或者晚到，司机要承受一定的配送压力，容易对配送产生厌恶的情绪，导致工作效率低。软时间窗的车辆早到或者晚到客户都允许进行物流服务，但是要接受相应的惩罚，车辆在配送过程中会遇到各种影响正常配送的情况，如果车辆违反时间窗，只需要承担很少一部分罚金，能够减少配送压力，增加配送的灵活性、提升配送效率。1.2遗传算法1.1.1遗传算法的定义遗传算法（GeneticAlgorithm,GA）起源于对生物系统所进行的计算机模拟硏究，由Michigan大学的约翰·霍兰德（J·Holland）教授于1975年首先提出来的，并撰写了《AdaptationinNaturalandArtificialSystems》一书，其学生在论文“Ananalysisofthebehaviorofthebehaviorofaclassofgeneticadaptativesystems”中通过大量的试验，尝试将遗传算法的思想运用到最优化问题当中,创造出的一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化的技术，循着自然选择的规律，能在搜索过程中自我调节适应，个体通过选择、交叉、变异等过程生成新的个体，而新的个体就是适应能力最强的解，也就是最接近最优的解。而这一过程令中群众个体进化，得到更适应环境的新个体，就如同自然界物竞天择、适者生存的基本法则,不断优化、遗传，最终得到目标问题的最优解。1.1.2遗传算法的特点遗传算法在模拟自然界生物进化机制的过程中，将实际问题进行编码转换成计算机能够识别的语言，编码形成的字符串被称为染色体，其模仿生物进化的过程，进行选择、交叉和变异形成新的染色体，新的染色体保留了父代染色体优秀的适应度基因，比父代更加适应环境，新的染色体再进行选择、交叉和变异，不断的形成带有优秀适应度基因的子代种群，新的子代种群比上一代更优秀。遗传算通过种群的不断迭代，在种群中寻找最优解。遗传算法与精确算法相比，遗传算法能够计算更加复杂的问题，精确算法适用与于简单问题的计算。与经典启发式算法相比，遗传算法不易陷入局部最优、计算速度快和容易操作等特点，遗传算法具体的特点包括：（1）遗传算法具有可操作性强、应用领域广泛，能够快速解决比较复杂的问题的特点。遗传算法解决复杂问题的方式是通过模仿自然界的进化机制，用对决策变量进行编码、字符串或者问题的解来对运算对象进行定义。遗传算法能够对图、集合、矩阵、数列等进行操作，不需要对决策变量本身进行操作，有利于选择、交叉、变异算子模拟生物染色体遗传进化的进程，方便遗传算法解决定性而无具体数值描述的优化问题，例如生产调度、图像处理、函数优化等。（2）遗传算法在搜索最优解的过程中不容易陷入局部最优。遗传算法具有群体搜索特性，在寻找最优解的过程中，遗传算法从多个染色体构成地初始种群开始，从多点同时开始进行搜索，不是从单点开始进行搜索，无论搜索空间为单峰或者多峰分布时，都能够快速地寻找到最优解。传统的启发式算法从单点开始搜索最优解，当搜索空间为多峰时，容易陷入某个单峰的最优值，然而遗传算法能避免这种情况发生。当遗传算法的适应度函数是不规则、不连续时，也能寻找到全局的最优解。（3）遗传算法进行计算时无需其他辅助信息，遗传算法进行运算时，用适应度函数作为判断个体的优良程度，不需要用目标函数作为搜索的信息。现实中许多目标函数很难求导，或者不存在导数。用适应度函数作为搜索最优解的依据，不受函数连续可微的影响，可以随意设定函数的定义域。遗传算法对适应度进行编码时，需要与适应度函数的可行解空间对应，不能存在死码。传统的优化算法没有适应度函数或者其他能够作为搜索最优解的依据，需要其他的辅助信息，遗传算法不需要其他辅助信息。（4）遗传算法在进行选择、交叉和变异时，通过一定的随机概率来进行。采用随机概率的变迁不断调整遗传算法的搜索方向，产生更多的优良个体，而不是采用确定性规则，遗传算法这种概率性规则，搜索最优解时更加灵活，变量对搜索过程的作用很小。1.1.3遗传算法的步骤遗传算法是一种全局搜索算法，首先将实际问题的初始解进行编码，组成多个字符串即染色体，染色体经过选择、交叉、变异后形成新的染色体，新形成的染色体比之前的染色体更接近最优解。再经过不断的迭代，一直得到最优解，遗传算法的主要步骤是编解码、确定初始种群、确定适应度函数、选择、交叉和变异。（1）编码解码遗传算法的编码是实际问题进行优化的首要步骤。遗传算法的编码方式，是将实际问题的可行解进行编码组成基因字符串，基因字符串构成染色体。遗传算法的操作对象是染色体或者个体，不能对染色体或者个体的单个基因进行优化。编码的方法有二进制编码、格雷码编码、浮点数编码、多参数级联编码、多参数交叉编码等。编码的优劣影响后续染色体的选择、交叉和变异，从而影响最优解的获得，所以在设计编码策略时需要遵循非冗余性、完备性、健全性等原则。解码则是将字符串恢复为原始信息的过程。（2）确定初使种群确定初始种群是进行遗传算法的第一步，是编码完成的一个个独立的个体，这些个体构成了遗传算法的初始解。初始种群大小会影响遗传算法的计算速度和最优解的质量，初始种群的数量一般在30-200之间，种群太小，遗传算法在求解过程中容易过早的收敛，陷入局部最优；种群太大，用遗传算法求解的计算量增大，增加求解的时间，降低求解的速度。初始种群的选择，经常用的方法有以下两种：第一种是根据实际建立优化模型，考虑规模的大小，选择适合优化模型可行解的规模，选择的可行解均匀分布在整个可行解的规模内，使得可行解不集中在一个地方。第二种是，首先选择一个较小规模的种群，进行不断地迭代，优秀个体会逐渐进入到初始种群，使得初始种群越来越接近最优解，种群的规模会不断的增大。虽然种群的优良性会随着迭代次数的增加逐渐升高，但是种群规模的上限不容易控制。（3）确定适应度函数适应度函数是由目标函数或者将目标函数进行转化而构成，目标函数可以是正数，也可以是负数。适应度函数是非负的，当目标函数为正数时，可以直接作为适应度函数；当目标函数为负数时，需要先将目标函数转化乘正数，再作为适应度函数。适应度越高种群的优良性越好，遗传给下一代的可能性越大，此时的解越接近最优解。（4）选择选择又称复制，是从群体中选择优秀个体并淘汰劣等个体的过程。是确定重组或交叉个体。选择优秀个体指的是，每个个体有对应的适应度值，根据适应度值的大小判断个体是否优秀，适应度值越大的个体越优秀，适应度值越大被选择将优秀个体的基因遗传给下一代的概率越大，随着种群进行不断的迭代，更多优秀的基因遗传给下一代得到适应度最大的后代，得到的解最接近最优解。因此选择合适的算子进行迭代，可以增加所求解的质量，每一次迭代遗传给下一代的基因更靠近最优解，可以将这种通过种群不断迭代得到最优解的过程称为试根的过程。选择的方法经常用的有比例选择法，比例选择法被称为蒙特卡罗法或者轮盘赌法，根据个体适应度值的大小决定被选择进行复制的概率的随机选择方法，适应度大的个体被选择的概率大，适应度小的个体被选择的概率的小，按照个体适应度与个体总适应度的比值划分轮盘，比值是被选择的概率，个体被选择的概率相加为1，转动轮盘指针可以大概率的指到适应度大个体，进行复制产生适应度更高的个体，提高种群的适应度。（5）交叉交叉又称重组，是在选择复制操作之后，将两个父代染色体以一定的交叉概率，进行最佳部分基因的替换、重组形成两个新的染色体，新的染色体不仅具有父代优秀的基因，而且能够使优秀基因不断地遗传给下一代，保证子代的染色体更加优秀，通过迭代得到的子代更接近问题的最优解。交叉将父代看成起点，结合父代染色体的特征形成新的染色体的过程，可以看成通过已知最优解的规模，根据一个解，寻找未知最优接