《物流配送车辆调度模型.doc》由会员分享，可在线阅读，更多相关《物流配送车辆调度模型.doc（41页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一般配送费用由车辆费用、工资费用、延迟费用和等待费用组成。车辆费用由燃料费、折旧费和维修费等变动费用组成，中心根据经营情况可核算出每车公里应摊的车辆费用。工资费用根据途中工作时间计算，若工作时间超过8小时，则超时部分应按加班补助计算。客户通常要求货物在一定时间窗范围内送达，否则中心需支付惩罚费用。若提前到达，支付等待费用；若延迟到达，支付延迟费用。设单一配送中心向l个客户送货，第i个客户货运量g为，卸货时间为，时间窗为，,每小时延迟费用,中心与客户、客户与客户两两间的最短运距、平均车速和车辆费用分别为(i,j=0,1,2,l;0表示配送中心)；可用m类卡车送货，第p型卡车有辆，装载容量为(p=
2、0,1,2,，m)；每小时等待费用为r，行车补助和加班补助分别为每小时s和es；途中运行到中午12：00和下午6：00时安排30分钟吃饭时间，车辆当天返回配送中心，再设为第p类车的第q辆配送的需一求点数(=0表示未使用第p类车的第q辆车)，确定车辆调度方案。4.2.2物流配送车辆调度模型根据上述对问题的描述，可以构造数学模型，定义变量： 得到配送调度模型如下：目标函数：（4.3） 约束条件： （4.4） （4.5） （4.6） （4.7） （4.8）式中：（4.3）为目标函数，即使车辆在完成配送任务时的最小配送费用； （4.4）为顾客满意度约束，即：每一顾客满意度的平均值必须到80%以上； （
3、4.5）为车辆的能力约束，即：某一车辆所访问的全部客户的需求量不能超过车辆本身的载重量； （4.6）确保顾客i仅由第p类车的第q辆车完成配送任务；(4.7) (4.8) 为到达某一顾客的车辆唯一性约束，即每一顾客仅由一辆车服务；其中，表示当顾客i的开始时间为时，车辆在顾客i处的等待时间:,j为i的前一个站点，当12且12,或18且18，有；，为发车时间，为收车时间。从模型当中可以知道：本文所建的是一个单目标多约束条件的优化模型，以配送费最小化为目标，将车型、车辆装载量、服务到达的时间要求、午餐时间及加班费等考在内，更重要的是通过对顾客预约时间满意程度的了解，建立顾客平均满意度约束，使配送中心可
4、以在顾客心中留有好的效应，进而达到一种长期合作的效果，从而给配送中心带来长期效益，而不仅仅是一种短期效益。本论文模型的建立将大大的减少由于配送中心不能达到服务顾客的要求，而带来的信誉损失部分，同时还提高了企业的信誉做到“双赢”，这是任何一个企业或个人都希望得到的，通过本模型得到的优化方案，将更有益于配送中心的发展。4.3物流配送系统软硬件基本配置4.3.1物流配送系统的硬件配置在系统编码之前，为建立开发和测试环境，需要安装数据库服务器、WEB服务器、应用服务器和其他一些相关的支撑软件。1、WEB 服务器1 台。该服务器可利旧服务器，即借用现有WEB 服务器，其功能主要是公司局域网下的页面传输、
5、用户的访问与申请、物流中心车辆调度员的操作输入和使用、管理员的维护等。2、数据库服务器（DB服务器）1台。线路优化用数据库主要包括销售营业部信息数据库（包括客户静态数据和订货量动态数据），物流中心送货车辆、驾驶员、送货员数据库等。3、应用服务器1台。主要用来放置配送线路优化应用系统，实现从WEB服务器传来的信息和密码的验证、查询、获取、计算，同时调用数据库服务器的数据资源，进行应用系统决策模型的分析决策（需要时修改数据库服务器的数据）, 最终结果经WEB服务器反馈给客户端。4、其它一些网络连接器件。如集线器HUB、交换机等。4.3.2物流配送系统的软件配置软件系统应参照目前公司所采用的平台，如
6、Window 2003 版操作系统，SQLServe2000 以上数据库系统。1、操作系统。数据库服务器和Web 服务器性能要求比较高，操作系统选用Windows 2003。客户端工作站的操作系统可选用windows xp /2 000。2、GIS 平台选择。GIS 平台软件应考虑到软件的稳定性以及与其它系统集成的问题。根据前文确定的基于组件开发模式，选择MapInfo6.o 以上版本。3、数据库管理软件。选择关系型数据库Sql Server 2000的集成来实现数据库管理。Sql Server 2000提供海量数据存储，系统运行比较稳定，相对于市场上其它同类产品价格也较适中。4、可视化程序开
7、发工具。选择Visual Basic6.0。目前，VB和MO 的结合被认为是开发GIS 应用软件的最佳选择之一，VB的程序编写是可视化的。4.4本章小结本章以具有代表性的北大仓啤酒有限公司的一市多县物流配送拓扑结构为研究对象，参照实际工中的约束条件，针对有时间窗的车辆路径的优化问题，建立数学模型，采用遗传算法求解。第5章 物流配送优化的具体实现GPS、GIS、车辆调度的功能集成主要是根据北大仓啤酒有限公司物流配送需要，通过GPS实现车辆管理及数据采集功能，GIS实现电子地图显示功能和分析决策功能。5.1物流配送GPS功能实现5.1.1GPS系统总体架构本系统利用车辆终端设备GPS接收模块接收G
8、PS卫星信号，经过解算后得到车辆的动态位置，车辆终端设备的GPRS 模块将带有车辆位置信息通过中国移动网关发送到监控中心，监控中心接收到车辆终端发送来的信息，经解算后在监控中心的电子地图上显示车辆的动态位置及行车路线，监控中心可利用GSM通讯网向车辆司机发送语音短信等调度指示45。车载终端设备中国移动网关GPS天线GPS天线基站.GPS卫星定位系统公司中各业务部门GPS系统运输线路优化系统公司中各业务部门优化系统GIS卫星定位系统公司中各业务部门GIS系统 图5-1 GPS框架图Chart 5-1 GPS frame chart5.1.2 GPS 监控中心设置利用己经建设成的局域网，在其信息中
9、心机房设置服务器、交换机等硬件设备和相应系统管理和维护人员，在各管理职能部门或者各业务部门可以建立分监控中心，以网络终端与服务器相连来操作和应用系统。监控中心是整个系统的核心，是连接分中心与车辆移动终端的纽带，并对分中心和车辆进行数据管理和通信，事实上分中心只与总监控中心进行数据通信，而车辆终端也只和总监控中心通讯。5.1.3 GPS 系统功能设计（1）实时监控：监控中心可随时查询或跟踪所有配送中心车辆所在的当前位置，同时显示出车速，经纬度，车状态，司机及乘员等信息，对的车辆行踪了如指掌。电子地图可任意放大、缩小、移动，可多窗口显示、分别显示不同的地址区域、一个窗口可同时跟踪多个目标、将目标锁
10、定在某窗口自动漫游跟踪、固定区域内的监控、多个窗口跟踪多个目标以及可在不同的窗口显示不同的目标，或将目标锁定在某窗口，自动跟踪等。（2）地图及GIS 软件功能：（需要采集零售户经维度数据）完全数字化的地图，包含精确的路网信息、点状要素、面状要素和详细的属性信息。作为北大仓物流公司车辆监控平台的支撑，地图的无级放大、缩小、恢复和拖动。全城市地图与各城区地图之间的任意转换，每图各层之间的转换，地名模糊查询，零售户查询等，管理功能强大，操作及为方便。（3）鹰眼窗口：在进行车辆监控时，显示当前窗口在全图中的位置，当前窗口图变化时，鹰眼窗口自动进行相应变化。鹰眼窗口地图本身也可放大缩小、漫游。通过改变鹰
11、眼窗口位置框的尺寸和位置可改变相应的窗口地图显示区域。这样有利于监控中心更清楚的了解目前车辆的即时位置。（4）区域查询：为禁止公司车辆的随意跑岗，可对每一辆车划定送配区域。监控中心可以随时查询车辆的当时位置；当车辆跑处行驶区域时，即可对监控中心及时进行报警提示。技术实现方法是：中心把相应的查车区域参数通过广播（小区消息）向所有网内车辆发送，移动终端接收到此指令后，判断是否处在此区域，如果是在此区域，就立刻向中心反馈当前的位置和状态信息。（5）历史资料检索与历史轨迹回放：可随时查询某辆车的位置回报记录、某段时间接收的车辆位置回报信息、某段时间监控中心的车辆调度记录等详细记录。并可选定某辆车某时间
12、段的位置记录进行轨迹回放，便于考核和管理。（6）车辆档案管理：数据库录有车辆及司机的详细资料，包括维修记录等，能自动提醒车辆及时检修；利于公司对车辆的管理。（7）超速报警、超载报警处理：为保障送配人员以及公司车辆的安全，要避免驾驶人员超速驾驶。监控中心自动接受车辆的报警信号，在地图上将对该目标进行鲜明色彩及图标的突出显示并以声、光报警提醒值班员注意，同时在屏幕上显示该移动目标的用户卡片资料，如车辆编号、车牌号、车型、颜色及司机名等；具有报警确认、报警取消、遥控熄火、遥控恢复、分发报警、指定路线报警、超速报警、后车厢开报警、车门开报警等辅助决策功能。（8）异常状态处理：车辆异常状态的带车号列表显
13、示。异常状态包括：紧急求助、服务申请、医疗服务申请、公交车辆故障报告、异常入侵等。（9）紧急求助：监控中心可以设置车辆的最高时速。随着大配送后，随车人员的货物与现金的增加，要避免抢劫等意外情况。在目标遇到突发事件以及偷窃等情况时，其向中心发回紧急求助信号，在地图上将对该目标进行鲜明色彩及图标的突出显示并以声、光报警提醒值班员注意，同时在屏幕上显示出该移动目标的用户卡片资料，它包括车辆编号、车牌号、车型、颜色、发动机号、使用分类、司机名、驾驶证号、所属单位、负责人、电话、车辆位置（X , Y 坐标）、行驶速度、时间等信息，帮助值班员进行紧急处理。软件能提供紧急求助受理记录窗，供值班员记录受理情况
14、。5.2物流配送GIS功能实现5.2.1MapInfo应用Maplnfo 是美国MapInfo 公司的产品46-48。MapInfo Professional 是近两年来推出的主流地理信息系统产品，它吸取了传统GIS系统的精华，并借助于计算机技术的发展，及时地将GIS 的概念从大中型计算机的专用工作站引入到普通PC 机上，开创了一种崭新的地理信息系统模式，即桌面地理信息系统。MapInfo的推出吸引了越来越多的用户。该产品自90 年代初进入我国后，在各行各业得到普遍的应用，并收到良好的应用效果。用VB编写的客户端应用程序MapInfo Professional服务程序MapInfo数据维护Ma
15、pInfo数据维护OLE或者DDE物流信息数据库GIS空间数据库图5-2 MapInfo 在物流配送系统的应用Chart 5-2 MapInfo logistics delivers the system in the thing the applicationMapInfo 的主要开发过程有：（1）输入。在地理数据用于GIS 之前，数据必须转换成适当的数字格式。从图纸数据转换成计算机文件的过程叫做数字化。对于大型的项目，现代GIS 技术可以通过扫描技术来使这个过程全部自动化，对于较小的项目，需要手工数字化（使用数字化桌）。目前，许多地理数据已经是GIS 兼容的数据格式。这些数据可以从数据提供
16、商那里获得并直接装入GIS 中。（2）处理。对于一个特殊的GIS 项目来说，有可能需要将数据转换成或处理成某种形式以适应你的系统。例如，地理信息适用于不同的比例尺(街道中心线文件的比例尺也许是1:100,000；人口边界是1:50,000)。在这些信息被集成以前，必须转变成同一比例尺。这可以是为了显示的目的而做的临时变换，也可以是为了分析所做的永久变换。（3）管理。对于小的GIS 项目，把地理信息存储成简单的文件就足够了。但是，当数据量很大而且数据用户数很多时，最好使用一个数据库管理系统(DBMS)，来帮助存储、组织和管理数据。一个数据库管理系统DBMS 就是用来管理一个数据库（4）查询和分析
17、。一旦你拥有一个包含你的地理信息的多功能的GIS 系统，你可能开始提出向下面这样的一些简单问题：两个地方之间的距离是多少？工业用地的边界在哪里？（5）可视化。对于许多类型的地理操作，最终结果最好是以地图或图形来显示。地图显示可以集成在报告、三维观察、照片图像和例如多媒体的其他输出中。5.2.2数据准备及处理 地理信息系统的数据来源（数据源）是指建立地理信息系统所需的各种类型数据的来源，可以分为图形（地图）数据源和属性数据源49。图形数据源包括地图、测绘和遥感影像等；而属性数据源则包括统计数据、各种文字报告和立法文件、声音和图片等。（1）电子地图设计物流GIS 系统的需求决定了电子地图的内容。毫
18、无疑问道路网络应是本系统最重要的组成部分，其次是送货点分布信息，同时也应包含与车辆行驶相关的各类标志，除此之外，电子地图还应该包含与企业相关的出行、商务等非道路信息。下面重点讨论道路网络、送货点分布信息的具体内容 道路网络。道路网络是整个电子地图的基础，同时也是许多算法，最短路径算法、优化路径算法、地图匹配算法的数据来源，尤其是将这些算法作用于电子地图时，道路网络的设计显得更加重要。道路网络包含道路的物理属性，如一般道路、桥梁等。对于物流系统来说，还需要知道道路的属性数据，如道路等级、速度限制、通行车辆种类等。为了更接近实际道路情况，道路网络还应该包含道路的行驶属性，如单行道双行道、禁止通行等
19、信息。 送货点分布信息。送货点信息作为特殊信息，是物流GIS 系统中必不可少的重要内容，它是进行车辆调度的基础信息。一般而言，送货点信息必须包括可唯一判断其存在的地理属性（如常用的所处街道名称或坐标信息），除此之外，还应包含别的一些属性，如：送货点自身属性、送货点相关属性等信息。通常，如果送货点信息是己知的，可提前建立好它的数据，也可以在系统使用中间，随时添加、删除或修改送货点信息。依据上述电子地图需求和内容分析，进行电子地图设计。(2)拓扑结构设计。空间数据的拓扑关系模型是地理信息系统的基石。本文主要采用“空间实体十空间索引”的拓扑关系模型。“空间实体空间索引”模型的基础是“空间实体”。空间
20、实体是地理实体的抽象，主要包括点、线、面三种类型。每个空间实体对象都维护着自己的所有属性。多个空间实体组成一个图层。“空间实体十空间索引”模型的空间查询功能是通过“空间索引”技术来实现的。5.2.3GIS实现的主要功能1、图层控制功能：用户可以在地图上方便设置地图图层的可见、显示标注、可选择等。2、图漫游功能：用户可以方便地在地图上进行放大、缩小、移动电子地图。3、零售户搜索功能：用户可以采取单一选择、矩形选择、圆型选择的方式搜索一定区域内的零售户对象并且对这些对象的信息进行统计、分析。4、数据分析功能： 客户基本信息； 销售量、销售额分析； 毛利分析； 客户获利分析； 卷烟销售结构分析； 销
21、售数据分布分析； 品牌销售分布分析；其它应用功能的数据挖掘和分析。5.3物流配送车辆调度和优化功能实现5.3.1物流配送系统的流程设计本文研究的北大仓啤酒有限公司物流配送系统的优化问题，而且主要研究多点、小批量、有时间窗约束的配送问题。根据配送系统的特征，工作流程设计如下：（1）根据现有设施点的位置，综合考虑配送半径，配送量，对客户进行分区处理，将复杂的优化问题简化。（2）将呼叫中心收集到的订单信息输入系统，经过有效性检验合格后传递到配送网络子系统；（3）选择“配送车辆安排模块”检验传递过来的数据并进行计算，确定需多少车辆负责配送哪些客户；（4）将结果传递到“车辆路线安排算法模块”。调用GIS
22、子系统，获取客户之间距离信息，根据道路情况计算配送路程时间，在客户停留时间按照配送量统一计算（初次实行人工配合修正）。该模块针对各区域每部车辆，规划各自的配送路线；（5）最后进行配送方案的评价。如果满意，则进入地图显示子系统，将结果以文字的方式在窗口显示，然在电子地图上进行路线显示并保存方案。若不满意，则返回配送网络子系统，按如上步骤重新求解。主要工作流程图如图所示。GPS、扫描等数据采集数据库GIS空间数据物流信息数据数据接口空间数据分析GIS显示配送车辆调度配送线路设计车辆管理客户信息可视配送网络建立配送方案实施配送方案评价图 5-3 GPS、GIS、车辆调度的主要工作流程图Chart 5
23、-3 GPS, GIS, the vehicles dispatch main work flow chart5.3.2物流配送系统的功能设计GIS 子系统物流配送优化子系统客户、空间信息查询电子地图显示GIS统计分析配送车辆调度配送路线设计GPS子系统车辆管理人员管理物流信息管理子系统仓储管理信息接口订单信息接口客户关系信息接口物流配送系统根据系统设计的基本思路和框架结构，主要包括电子地图、决策分析、车辆监控三个子系统，其中电子地图子系统包括电子地图显示和空间信息查询等模块，决策分析子系统包括GIS 统计分析、配送区域划分、配送车辆安排和配送路线设计等功能模块。主要模块如图：图5-4 车辆调
24、度主要功能模块图Chart 5-4 vehicles dispatcher main function module chart 车辆调度模块主要的作用：1、通过GPS 实现车辆安全保障及监控。2、根据每天不同的订货需求，配送车辆尽量装满配送货物，这样动态生成线路，也就是在同样完成配送任务的前提下每天派出的车辆尽量的少，工作时间尽量短的工作时间。3、根据生成的不同线路，给出车辆行驶的最优路径，使得配送同样的零售点所用的时间最短，里程油耗及车辆损耗最少。4、路径分配考虑周全，符合现场实际情况：比如工作量分配系统要求总成本最低而各条线工作平衡，即不强调每条线路工作量平衡的平均主义，因为如果那样安排
25、配送方案的话，必将使总体工作量增加。所以，我们动态分配线路时各条线路的工作量允许不同，只要在8 小时工作时间范围内，有的线路工作量比其他线路大很多，但这样多条线路相加，总和必须是绕行里程和时间最短，同时又完成了任务，为单位最大限度地降低了配送成本；为了解决司机间工作量平衡的问题。我们设计在工作排班制度上，每周轮换跑最远的路线。在最优路径的生成中，我们综合考虑了道路等级、不同方向和时段的交通阻抗、交叉口左、右、直行以及不同时段的时间延误、路段是否允许中途掉头和是否可以过街送货等情况。5、运行效率高，生成结果准确合理。系统采用了当今高效合理的数学模型：遗传算法与神经网络算法。两种方法结合使用，运算
26、速度大大提高。6、生成每条线路，在电子地图线路上标注线路行驶的顺序号并打印成图，方便司机工作。同时，还为每条线路的司机按行驶顺序打印出清单。7、建立客户信息及数据分析可视化功能。有利于经营管理人员直观掌握客户有关情况，为服务拓展提供基础。如客户投诉，能及时显示客户位置及基本情况，计算服务响应时间，以便最有效地实施服务补救。5.4车辆调度遗传算法的求解5.4.1遗传算法的运行步骤遗传算法在整个进化过程中的遗传操作是随机的但它所呈现出的特性并不是完全随机搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的最优点集。这样一代代地不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。遗传
27、算法的运行为一个典型的迭代过程，其基本执行过程如下：（1）编码：遗传算法在进行搜索之前先将解集合的解的数据表示成遗传空间的基因型串数据，这些串结构的不同组合便构成了不同的点。（2）初始群体的生成:随机产生N个初始串结构，每个串结构称为一个个体(或叫染色体)，N个个体构成了一个群体，群体内个体的数量N就是群体规模。群体内每个染色体必须以某种编码形式表示，编码的内容可以表示染色体的某些特征。随着求解问题的不同，它所表示的内容也是不同。通常染色体表示被优化的参数，每个初始个体就表示着问题的初始解。（3）适应值评估检测:适应值函数表明个体或解的优劣性。对于不同的问题，适应值函数定义的方式也不同。（4）
28、选择：从当前群体中选择适应值高的个体以生成交配池的过程，其目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。按照一定的选择策略选择合适的个体，选择实现了达尔文的适者生存原则。根据群体中每个个体的适应值，从中选择具有最好的个体作为父代重新繁殖下一代群体。（5）交叉:交叉是两个染色体之间随机交换信息的一种机制。以事先给定的交叉概率在选择出的个体中任意选择两个个体进行交叉运算或重组运算，产生两个新的个体，重复此过程直到所有要求交叉的个体交叉完毕。交叉操作是GA中最主要的遗传操作。通过交叉操作可以得到新一代个体，新个体结合了其父辈个体的特性。交叉体现了信息交换的思想。（6）变
29、异：变异操作是模拟自然界生物进化中染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。它首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机的改变串结构数据中某个串的值。同生物界一样，GA中发生变异的概率很低，通常取值在0.0010.01之间。变异为新个体的产生提供了机会。根据需要可以以事先给定的变异概率，在最好的个体中选择若干个体，并按一定的策略对选中的个体进行变异运算。变异运算增加了GA找到最优解的能力。(7)终止循环条件，若满足收敛条件或固定迭代次数则终止，若不满足条件则转(3)重新进行进化过程。每一次进化过程就产生新一代的群体。群体内个体所表示的解通过进化最终达到最
30、优解。5.4.2遗传算法的参数设置的选择遗传算法中需要选择的运行参数主要有群体规模N、迭代次数、交叉概率、变异概率、终止代数T等。这些运行参数对遗传算法运行的性能有着较大的影响，需要认真选取。（1）群体规模N。群体规模表示群体所含个体的数量。当取值较小时，可以提高遗传算法的运算速度，但会降低群体的多样性，有可能引起算法的早熟现象；而当N较大时，又会使得遗传算法的运行效率降低。一般建议取值范围是20100。（2）迭代次数。迭代次数的设置分为固定和不固定两种设置。固定迭代次数有利于遗传算法的处理，但设置选择困难，并且不利于产生最优解。不固定迭代次数通过对个体解的判断自动进行迭代有利于产生最优解，并
31、且解决了参数选择的困难，但容易增加遗传算法的处理时间。（3）交叉概率和变异概率。对交叉概率和变异概率的设置，由于它们关系到遗传算法的收敛性和群体中个体的多样性，因此倍受重视。传统的和的设置是静态人工设置。现在有学者提出动态参数设置的方法，以减少人工选择参数的困难和盲目性，来维持群体的多样性和保证遗传算法的收敛。由于交叉算子是产生新个体的主要方法，所以一般交叉概率取值较大。但若取的过大，又会破坏群体中的优良模式，对进化计算反而产生不良的影响。一般建议的取值范围是0.40.99。另外，也可以使用自适应的思想来确定交叉概率，随着遗传算法在线能的大大提高，以加大交叉概率的取值。变异概率取值较大时，虽然
32、能够产生较多的新个体，但也有破坏很多较好模式的可能，使得遗传算法的性能近似于随机搜索算法的性能但若其取值太小，则变异操作产生新个体和抑制早熟的能力就会较差。一般建议其取值范围是0.0010.01。另外，也可以使用自适应的思想来确定，随着遗传算法在线性能的下降，可以减小的取值。（4）终止代数T。终止代数T是表示遗传算法结束的一个参数，遗传算法运行到指定的代数T就停止运行，并将当前群体中的最佳个体作为所求问题的最优解输出。一般建议的取值范围为1001000。另外，遗传算法的终止条件，还可以利用某种判断准则，当判断出群体已经进化成熟且不再有进化趋势时就可终止算法的运行。常见判断准则有：连续几代个体平
33、均适应度的差异小于某个极小的阀值；或群体中所有个体适应度的方差小于某一个极小的阀值。5.4.3遗传算子（1）选择算子。模仿自然界的“优胜劣汰”选择操作用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体的一种遗传运算，也就是从当前群体中选择适应值高的个体以生成交配池的过程。选择操作建立在对个体的适应度进行评价的基础之上，需要指出的是，选择算子只是从当前群体中选择较好的个体形成交配池，本身并没有产生新的个体目的主要是为了避免群体中有效基因缺失或成熟前收敛，以及为了GA提高的全局收敛性和搜索效率。最常见的选择算子是基本遗传算法中的比例选择算子，即轮盘赌选择，其基本思想是：个体被选中的概率
34、与其适应度大小成正比。但对于不同的问题，它并不都是最合适的选择算子，所以又发展了其它选择算子。最优保留选择是使当前群体中适应度最高的个体不参与交叉运算和变异运算，并用它来替换掉本代群体中经过交叉、变异等遗传操作后所产生的适应度最低的个体；确定式采样选择的基本思想是按照一种确定的方式来进行个体选择；无放回随机选择又叫期望值选择方法，它的基本思想是根据每个个体在下一代群体中的生存期望来进行随机选择运算；排序选择的着眼点是个体适应度之间的关系，它将群体中的所有个体按其适应度大小进行排序，基于这个排序来分配个体的被选中的概率；随机联赛选择同样基于个体适应度的大小，基本思想是每次选取几个个体，适应度最高
35、的一个个体将遗传到下一代群体中。（2）交叉算子。交叉操作是遗传算法具备的原始性的独有特征。GA交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。在交叉运算之前，首先必须对群体中的个体进行配对。常用的配对策略是随机配对，即将群体中的N个个体以随机的方式组成N/2对配对个体组，交叉运算在个体组的两个个体之间进行。两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉算子的设计和实现与所要解决的问题密切相关，一般要求它既不要太多的破坏个体编码串中表示优良险状的模式，又能够有效的产生出一些较好的新的个体模式。
36、交叉算子的设计就是要确定交叉点的位置，然后进行部分基因交换。最常见的交叉算子是单点交叉算子，它是指在个体编码串中随机设置一个交叉点，然后在该点互换两个配对个体的基因。但单点交叉算子有一定的适用范围。双点或多点交叉是指在个体串编码中随机设置了两个或多个交叉点，然后再进行部分基因的互换；均匀交叉是指两个配对个体的每一个基因座上都以相同的交叉概率进行交换，从而形成两个新的个体。（3）变异算子。在生物遗传过程中，其细胞分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，导致某些基因的变异，从而产生新的染色体。模仿这个环节，在遗传算法中也引入了变异算子来产生新的个体。变异是随机改变某个个体遗传
37、信息的一种操作。遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这一对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力，才能以良好的搜索性能完成最优化问题的寻优过程。在遗传算法中使用变异算子主要的目的是：改善遗传算法的局部搜索能力，维持群体的多样性，防止出现早熟现象。变异的思想同交叉一样，也是先确定变异点的位置，再进行基因值的替换。最简单的变异算子是基本位变异算子，它是指对个体编码串中以变异概率随机指定的某一位或某几位基因座上的基因值作变异运算。为适应不同的应用问题的求解需要，还有其它的变异算子。均匀变异是指分别用
38、符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因。非均匀变异是对原有基因值作以随机扰动，以扰动后的结构作为变异后的基因值。5.4.4编码、初始群体生成及适应度函数的设定（1）编码:由于VRP问题用二进制处理具有先天性的不足，为了弥补这一不足，本文采用自然数编码，并用一个简单的例子加以分析。设0代表配送中心，自然数表示顾客点的编号，假设有5个顾客，随机产生一个染色体，表示调度方案为2台车给5个顾客送货，车辆11线路是“中心顾客1顾客4中心”，车辆21是“中心顾客2顾客3顾客5中心”。这种编码方式能够保证每辆车行驶线路的连通性。染色体长度=车辆总数+顾客数+
39、1。车辆总数需要事先试算，一般要求车辆总装载容量是总货物量的1.051.3倍，会产生几种不同的车辆组合方案，然后针对不同方案进行下一步优化工作。（2）初始群体生成：任意给顾客和车辆排序；从左向右累计顾客需求量，若第一辆车容量大于前a个顾客需求量之和且小于前个a+1顾客需求量之和，则得第一辆车子串1“12a0”；删去排序中前a个顾客，同理可得第二辆车子串2;如此反复，直到车辆和顾客被安排完;把子串顺序连接,左端加0就得到一条初始染色体,重复操作,直到符合群体规模N。（3）适应度函数：适应度函数由目标函数转化得到，是染色体k的适应度函数，是同代群体中最佳染色体的费用，是染色体的费用。适应度最大的染
40、色体对应配送成本最低的调度方案。5.4.5群体更新过程群体更新过程就是更新当前解群体，产生新一代解群体的过程：具体的讲是从当前解群体中选择适应度大的个体，进行交叉、变异，生成新的解群体的过程，该过程是GA模拟自然进化过程的重要体现，是促成算法逐步实现搜索到最优解的根本原因。具体操作方法如下：（1）选择算子。给N条染色体排序；计算适应度；计算选择概率；计算累积概率；产生0，1区间均匀分布随机数R，若R，则选择染色体1，否则选择染色体K，使得重复进行，直到符合群体规模n.为提高算法性能，保留上代群体中最佳染色体。 （2）交叉算子。按2个一串将双亲“”和“”基因分组，得0 14 02 350 和0
41、24 50 130 ；双亲中子串“14”两端都为0，把“14”和所有“0”基因保留，填充到空白染色体相同位置上；删去双亲2基因1和4，把剩余基因按顺序填入空白位置，得后代1“”。同理得后代2“”。若所有子串两端不全为0，则左移或右移“ ”，直到存在两端为0子串。3点交叉算子操作原理类似。（3）变异算子。对2交换变异算子，在染色体中任意确定两个非零基因，交换其位置，就得到1条新染色体。对交3换变异算子，任意确定3个非零基因，把它们位置按不同方式交换，可得到5条新染色体，选择其中适应度最大的染色体作为运算结果。确定实际问题参数对参数编码初始化群体确定评价群体满足停止准则（1）染色体编码；（2） 计
42、算目标函数寻找最优个体遗传操作群体更新解码得最优解三个基本算子：（1） 选择（2） 交叉（3） 变异No遗传算法设计最后一步是确定控制参数和算法终止条件。推荐控制参数取值范围是：群体规模n=20100，交叉率=0.40.99，变异率=0.0010.01，详细根据具体情况确定，其流程图如图4-638所示。Yes图 4-6 遗传算法的基本流程Chart 4-6 heredity algorithm basic flow由以上步骤可以看出，可行解的编码方法、遗传算子的设计是构造遗传算法时需要考虑的两个主要的问题，也是两个关键的步骤，而对所求问题的理解是遗传算法应用成功的前提。5.5算例分析本论文的算
43、例资料采用长安大学龚延成等在数学的实践与认识2004年06月发表的，题目为：基于遗传算法的物流配送车辆调度问题研究，是迄今为止我认为比较全面的研究，他不仅综合了以往的带能力约束问题、带时间窗限制的问题，还追加了多车种服务问题，可以说适用性更加广泛，他的不足之处就是对顾客服务质量没有一个衡量的标准，只是通过惩罚成本来限制，在某些情况下，配送费用虽然达到了最小化，但是顾客的满意程度却是较低的，这严重影响了以后的顾客服务源，给配送中心的长远利益带来了无形的损失。而本文则结合实际、考虑到顾客长远的服务需求，在满足上述约束条件的基础上，将顾客满意度作为约束条件引入模型当中，使其更合理，因此本文采用这一算
44、例，并且加入了模糊预约时间，即顾客在可以容忍的服务时间范围中最满意的时间段，通过计算将二者计算结果进行比较分析，从而验证本文模型构建的合理性。资料如下：某配送中心经营啤酒配送业务，每天向个客户运送箱装的啤酒，有关数据如表1所示。测量比例为1：，得到地图中心坐标为(60,140)，客户坐标，由于实际距离与空间测量距离有一定的差异性，根据经验知：中心与客户、客户与客户的最短运距通过公式近似计算。平均速度间，送货车辆有两类，A类装载容量是500箱，每公里车辆费用3元，B类的装载容量为400箱，每公里车辆费用为2.5元。驾驶员正常工作每小时10元，加班补助每小时20元，途中运行到12：00或18：00
45、时安排30分钟吃饭时间。车辆等待费用每小时10元，客户延迟费用均为每小时100元。若最早发车时间为早晨6：30，试运用本文所建模型确定路径优化方案。详细的数据见表5.1客户情况一览表42。表5.1 客户情况一览表顾客啤酒箱数顾客位置（毫米）卸货时间（分钟）时间窗模糊预约时间X坐标Y坐标112030114608：0017：009：0011：3022004036908：0010：308：3010：3031204896608：0017：009：0015：00415052120808：0012：008：3011：30514092154708：008：308：008：306609266408：0017：
46、0010：0015：00711094100608：0017：008：3011：308180108100908：0010：459：3010：3099044160508：008：308：008：30101602054908：0013：008：0012：001114010832608：0013：0010：3012：001215013088708：0017：009：0015：00合计1620820首先根据单车容量和1620箱的总运量。车辆行驶路线可初步确定两种派车方案。方案1：A型车2台和B型车2台，车辆总容量为1800箱；方案2：A型车1台和B型车3台车辆总容量为1700箱，染色体长度12+4+1=17，采用2和3交叉算子，以及2和3交换变异算子，取群体规模n=20，交