洪盛物流公司之物流配送车辆优化调度.docx

《洪盛物流公司之物流配送车辆优化调度.docx》由会员分享，可在线阅读，更多相关《洪盛物流公司之物流配送车辆优化调度.docx（32页珍藏版）》请在三一文库上搜索。

1、儿前言现代物流业是把握竞争优势的有效方式，将为国民经济在高起点上持续发展，提供基础动力。在经济全球化和信息化的推动下，现代物流业已从为社会提供传统运输服务，拓宽到以现代科技、管理和信息技术为支柱的综合物流系统。目前，许多发达国家和地区已形成了比较成熟的物流管理理念、先进的物流技术和高效的物流运营系统。处于经济高速发展的中国，必将加快现代物流的发展，以此增强企业竞争能力，优化资源配置，提高经济运行质量，实现中国经济体制与经济增长方式的两个根本性转变，从而推动中国经济的持续健康的发展。物流配送车辆优化调度，是物流系统优化中关键的一环，也是电子商务活动不可缺少的内容。对配送车辆进行优化调度，可以提

2、高物流经济效益、实现物流科学化。物流配送车辆优化调度理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。本文给出了物流配送车辆优化调度常见问题，通过对洪盛物流公司物流配送车辆优化调度问题的调研，然后根据蚁群算法在车辆优化调度应用，运用混合蚁群算法求解洪盛物流公司车辆优化调度问题及其效果预测。最后，建立一个车辆优化调度计算机系统。其主要工作如下：首先，包括选题的背景、研究意义、发展状况和本文研究的内容等；其次，进行物流配送车辆优化调度概述，介绍一些常见的物流配送车辆优化调度问题，有一个初步的认识；再其次，对洪盛物流公司物流配送

3、车辆优化调度问题的调研，可优化的原则，问题和困难等；再次，蚁群算法概述、发展及其现状，基本蚁群算法在车辆优化调度中的应用；运用混合蚁群算法求解洪盛物流公司车辆优化调度问题，混合蚁群算法求解洪盛物流公司车辆优化调度问题，算法设计及步骤。最后，利用计算机建立车辆优化调度系统，主要是运用地理信息系统对车辆进行可视化管理；建立一个社会车辆资源网络等，处理紧急情况下车辆优化调度；结论与展望：总结本人所做的研究工作，所用到方法的优缺点，以及有待未来在物流配送车辆优化调度发展。19第1章绪论1.1 课题研究背景和意义1.1.1 课题的背景在经济全球化的推动下，作为邛三利润源泉的物流，对经济活动的影响日益加强

4、T前最重要的竞争领域II,在优化国内外两个市场的资源配置中起着重要的作用。据专家测算，现代物流成本约占企业经营成本的30-50%，当一个有效的物流系统与企业主要商业系统集成之后，可使仓储量降低50%，准时交货率提高40%，营业收入增加10%以上1。在经济发达国家和一些经济水平较高的发展中国家，现代物流水平以成为影响企业竞争力的关键因素2。物流的现代化水平成为反映一个国家现代化程度和综合国力的重要标志，物流对经济有巨大的拉动作用，被喻为经济发展的动口速器II,物流的迅速发展将大大提升城市物流中心或经济中心的地位。近年来，油价不断的节节飙升，许多物流企业的运输费用超过了库成费用，同时拥有的城市交

5、通与及时的配送服务间的矛盾也愈演愈烈。优化物流配送线路，不仅给供需双方带来降低物流成本、享受优质服务的直接效益，还能缓解交通压力、减少运输污染和保护生态环境。所以，采用合适的车辆调度方案规划配送线路是配送业务中一项非常重要的工作。优化配送路线可以减少重复运输、倒流运输、迂回运输、单程运输和空车驾驶等，不仅提高了配送效率，提高了经济效益，还可以减少车辆在城市中的运行，有效缓解交通压力。对洪盛物流公司之物流配送车辆优化调度问题的应用研究是洪盛物流公司物流集约化发展、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。1.1.2 课题的意义洪盛物流公司主要从事物流配送的汽车货运工作，工作

6、条件复杂，货运点多、货物种类繁多、道路网复杂，而且运输服务地区内运输网点分布不均匀，因此利用现代数学方法及计算机建立一个网络系统快速求解线路优化方案。为实现运输成本的降低，必须对运输进行合理规划。运输的合理规划涉及到时间、财务、环境三方面的因素，首先从时间要考虑准时性、快速响应；财务上要考虑运输涉及的各种开支；环境上要尽可能减少不必要的行驶，避免交通拥挤。这些都可以改进运输方式、线路规划等交通管理来加以改善。其中运输方式属于硬技术的问题，是可以通过设施的完善来提高运输的效率，降低相应的成本。而运输路线规划主要利用各种完进的信息技术对车辆及其路线进行规划，实现对车辆合理有效的利用，从而节省大量的

7、时间和成本。本课题从洪盛物流公司的物流配送车辆优化调度问题出发，利用现代数学方法分析及计算机建立网络系统，运用混合蚁群算法解决洪盛物流公司车辆优化调度问题及其效果预测。利用现实问题，结合理论，应该说的研究具有很强的的实际意义。1.2 国内外研究现状物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出，他们描述了一个将汽油送往各加油站的实际问题，并提出了相应的数学规划模型及其求解算法。Bodin、Golden等人在他们的综述文章中对一般的车辆优化调度问题做了详尽的论述。随着研究的深入发展，如何使研究的理论模型更贴近现实中的运输调度问题开始成为研究焦点3。Laporte

8、和Nobert等人（1985年）主要研究了带容量和距离限制的车辆优化调度问题，Solomon和Desrosiers等人（1987年）考虑将时间约束加入到一般的车辆优化调度问题中，最早对带时间约束的车辆优化调度问题进行了研究。90年代以后车辆优化调度问题引起了运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。随着现代物流的不断发展，多车场车辆优化调度问题、随机车辆优化调度问题闭、装卸混合车辆优化调度问题等更加复杂的路径问题被不断的提出和研究3。目前国内外用于解决该问题的现代数学方法主要分为

9、以下几类:精确优化方法、启发式方法、模拟方法、交互式优化方法。以往广泛采用的是第一种方法，另外三种方法则代表了较近的研究思想。尤其是启发式方法，作为一种逐次逼近的算法，虽然不一定得到最优解，但可以高效地得到具有较高精度的解，而且也易于考虑各种各样的实际问题，因此，现己成为解决物流配送问题的重要方法。随着人工智能技术的引入和不断发展，模拟退火算法和遗传算法等新的方法以及人工神经网络和专家系统等新技术，为解决大规模、多目标车辆优化调度问题提供了新的辅助手段。目前，算法研究集中在对启发式规则和搜索方法的改进，以便提高搜索速度和质量。主要有遗传算法45、蚁群算法67、混合蚁群算法8910、等算法在车辆

10、路径优化问题中的应用。随着高性能计算机的迅速发展，国外应用计算机及现代数学方法调度车辆以优化运输管理效果的研究工作正在较大范围内展开。例如在国外一些国家将地理信息系统、全球定位系统、智能交通系统等技术应用于物流配送车辆优化调度问题中，更加有助于直观的、实时的反映配送状况，使得该系统更加智能化。国外车辆优化调度研究已广泛用于生产、生活的各个方面，如报纸投递及线路的优化、牛耐配送及送达线路的优化、电话预定货物的车辆载货和路线设计、垃圾车的线路优化及垃圾站选址优化、连锁商店的送货及线路优化等等。目前研究水平已有很大发展，其理论成果除在汽车领域外，在水运、空运、通讯、电力、工业管理、计算机应用等领域也

11、有一定的应用，还用于航空乘务员轮班安排、轮船公司送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题11。1.3 本文的主要内容本文给出了物流配送车辆优化调度常见问题，通过对洪盛物流公司物流配送车辆优化调度问题的调研，然后根据蚁群算法在车辆优化调度应用，运用混合蚁群算法求解洪盛物流公司车辆优化调度问题及其效果预测。最后，建立一个车辆优化调度计算机系统。其主要工作如下：首先，包括选题的背景、研究意义、发展状况和本文研究的内容等；其次，进行物流配送车辆优化调度概述，介绍一些常见的物流配送车辆优化调度问题，有一个初步的认识；再其次，对洪盛物流公司物流配送车辆优

12、化调度问题的调研，可优化的原则，问题和困难等；再次，蚁群算法概述、发展及其现状，基本蚁群算法在车辆优化调度中的应用；运用混合蚁群算法求解洪盛物流公司车辆优化调度问题，混合蚁群算法求解洪盛物流公司车辆优化调度问题，算法设计及步骤。最后，利用计算机建立车辆优化调度系统，主要是运用地理信息系统对车辆进行可视化管理；建立一个社会车辆资源网络等，处理紧急情况下车辆优化调度。结论与展望:总结本人所做的研究工作，所用到方法的优缺点，以及有待未来在物流配送车辆优化调度发展。第2章配送车辆优化调度理论综述2.1 物流配送车辆优化调度的概述随着社会主义市场经济的发展，作为戈三利润源泉的物流对经济活动的影响日益明显

13、越来越引起的人们的重视，成为当前重要的竞争领域II,未来的市场竞争，物流将起者举足轻重的作用。配送事故物流中一个重要的直接与消费者相连的环节。配送一般定义为，将货物从物流节点送达收货人的过程。配送是在集货、配货基础上，完全按用户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，配送的流程一般如下图2.1所示。图2.1物流配送流程电子商务的发展，新的物流配送模式的出现，存储已不是必然的环节。因此配送的主要包括以下几部分：1、 集货作业。从生产工厂进货、并集结的过程。2、 配货作业。配货即货物的分拣过程，根据各个用户的不同需求，在配送中心将所需的货物挑选出来的过程。3、 车载货物的配

14、装。由于配装作业本身的特点，配装工作所需车辆一般为汽车，由于配送货物的质量和体积的差异，在配装货物时要考虑车辆的载重和容积，为使车辆载重和容积充分利用，还要考虑一趟多送几户的问题。4、 配送路线的确定。配送路线合理与否对配送速度、成本、效益影响很大，特别是多用户配送路线的确定更为复杂。随着物流配送的集约化、一体化的发展，常将配送的各个环节综合起来，核心是配送车辆的集货、货物配装及发货过程，进行配送系统优化的主要工作是配送车辆优化调度，越来越多的采用地理信息系统技术的物流配送车辆调度优化系统，实现可视化的车辆调度，发展成为智能计算机配送调度。122.2车辆优化调度问题对物流配送的研究当中，以有效

15、的控制配送中发生的库存成本、运输成本和运输时间为内容的运输调度问题成为主要目标。大多数的物流配送运输调度问题可以归结为车辆优化调度问题，即根据不同要求目标函数（例如运距最短、配送时间最短、费用最少等），将配送运输过程归结为表述问题的数学模型，设计求解问题的算法，然后用计算机求得合理可行的优化方案。车辆优化调度问题主要内容是车辆分配和配送线路的生成。车辆优化调度问题一般可根据空间特性和时间特性分为车辆路径规划问题（VehicleRoutingProblem,VRP）和车辆调度问题（VehicleSchedulingProblem,VSP）。目前多数研究该领域的学者将车辆优化调度问题统称为VRP，

16、而具体的问题会加约束限制来命名，如将有时间要求的车辆调度问题称VRPTW（VehicleRoutingProblemWithTimeWindows），还有CVRP（CapacityVehicleRoutingProblem）、MDVRP（Multi-DepotVehicleRoutingProblem）、DVRP（DynamicVehicleRoutingproblem）等。车辆优化调度问题一般可描述为对一系列装货点和（或）卸货点，组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标如路程最

17、短、费用最少、时间尽量少、使用车辆数尽量少等）。2.3 车辆优化调度问题分类配送车辆优化调度问题可按照其构成要素划分为不同的种类13。1、 按任务特征分，有纯装问题或纯卸问题（车辆在所有任务点装货或卸货或送货问题）及装卸混合问题（每项任务有不同的装货点和卸货点，即集货、送货一体化问题）；2、 按车辆载货状况分，有满载问题（货运量不小于车辆容量，完成一项任务需要不只一辆车）、非满载问题（货运量小于车辆容量，多项任务用一辆车），以及满载和非满载混合问题；3、 按车场（或货场、配送中心等）数目分，有单车场问题和多车场问题；4、 按车辆类型数分，有单车型问题（执行任务的所有车辆容量相同）和多车型问题（

18、车辆的容量不全相同）；5、 按车辆对车场的所属关系分，有车辆开放问题（车辆可以不返回其发出车场）和车辆封闭问题（车辆必须返回其发出车场）;6、 按优化目标数来分，有单目标问题和多目标问题。实际中的车辆优化调度问题可能是以上分类中的一种或几种的综合，根据情况的不同，问题的模型构造及算法有很多差别。2.4 车辆优化调度问题构成要素物流配送车辆调度问题主要包括货物、车辆、物流中心、客户、运输网络、约束条件和目标函数等要素14。1、货物。货物是配送的对象。可将每个客户需求或供应)的货物看成一批货物。每批货物都包括品名、包装、重量、体积、要求送到(或取走)的时间和地点、能否分批配送等属性。货物的品名和包

19、装，是选用配送车辆的类型以及决定该批货物能否与其它货物装在同一车辆内的依据。例如，一些货物因性质特殊需要使用专用车辆装运;一些货物因性质特殊不能与其它货物装在同一车辆内;一些货物虽然性质特殊，但由于包装条件很好，故也能与其它货物装在同一车辆内。货物的重量和体积是进行车辆装载决策的依据。当某个客户需求(或供应)货物的重量或体积超过配送车辆的最大装载重量或容积时，则该客户将需要多台车辆进行配送。货物的送到(或取走)时间和地点是制定车辆的出行时间和配送路线的依据。允许货物分批配送，是指某个客户的需求(或供应)的货物可以用多辆车分批送到(或取走)，即使其需求或供应)量在一辆车的装载量以下。2、车辆。车

20、辆是货物的运载工具。其主要属性包括车辆的类型、装载量，一次配送的最大行驶距离、配送前的停放位置及完成任务后的停放位置等。车辆的类型有通用车辆和专用车辆之分，通用车辆适于装运大多数普通货物，专用车辆适于装运一些性质特殊的货物。车辆的装载量是指车辆的最大装载重量和最大装载容积，是进行车辆装载决策的依据。在某配送系统中，车辆的装载量可以相同，也可以不同。对每台车辆一次配送的行驶距离的要求可分为以下几种情况:(1) 无距离限制；(2) 有距离限制；(3) 有距离限制，但可以不遵守，只是不遵守时需另付加班费。车辆在配送前的停放位置可以在某个停车场、物流中心或客户所在地。车辆完成配送任务后，对其停放位置的

21、要求可分为以下几种情况:(1) 必须返回出发点；(2) 必须返回某停车场；(3) 可返回到任意停车场；（4） 可停放在任何停车场、物流中心或客户所在地。3、物流中心。也称为物流基地、物流据点，是指进行集货、分货、配货、配装、送货作业的配送中心、仓库、车站、港口等。在某配送系统中，物流中心的数量可以只有一个，也可以有一个以上;物流中心的位置可以是确定的，也可以是不确定的。对于某个物流中心，其供应的货物可能有一种，也可能有多种，其供应的货物数量可能能够满足全部客户的需求，也可能仅能满足部分客户的需求。4、客户。也称为用户，包括分仓库、零售商等。客户的属性包括需求（或供应）货物的数量、需求（或供应）

22、货物的时间、需求（或供应）货物的次数及需求（供应）货物的满足程度等。在某个配送系统中，某个客户的需求或供应）货物的数量可能大于车辆的最大装载量，也可能小于车辆的最大装载量;而该系统全部客户的货物需求（或供应）总量可能超过全部车辆的总装载量，也可能低于全部车辆的总装载量。某客户的需求（或供应）货物的时间，是指要求货物送到（或取走）的时间，对配送时间的要求可分为以下几种情况:（1） 无时间限制；（2）要求在指定的时间区间（也称为时间窗）内完成运输任务；（3）有时间限制，但可以不遵守，只是不遵守时要给予一定的惩罚。某客户的需求（或供应）货物的次数可能仅有一次，即只需一次配送服务;也可能为多次，即需要

23、多次配送服务。某客户对需求（或供应）货物的满足程度的要求可分为两种情况:（2） 要求全部满足；（3） 可以部分满足，但不满足时要受到惩罚。5、运输网络。运输网络是由顶点（指物流中心、客户、停车场）、无向边和有向弧组成的。边、弧的属性包括方向、权值和交通流量限制等。某运输网络中可能仅有无向边;也可能仅有有向弧;还可能既有无向边，又有有向弧。运输网络中边或弧的权值可以表示距离、时间或费用。边或弧的权值变化分为以下几种情况:（1） 固定，即不随时间和车辆的不同而变化；（2） 随时间不同而变化；（3）随车辆的不同而变化；（4）既随时间不同而变化，又随车辆不同而变化。对运输网络权值间的关系可以要求其满足

24、三角不等式，即两边之和大于第三边，也可以不加限制。对运输网络中顶点、边或弧的交通流量要求分为以下几种情况:(1)无流量限制；(2)边、弧限制，即每条边、弧上同时行驶的车辆数有限；(3)顶点限制，即每个顶点上同时装、卸货的车辆数有限；(4)边、弧、顶点都有限制。6、约束条件。物流配送车辆调度问题应满足的约束条件主要包括:(1)满足所有客户对货物品种、规格、数量的要求；(2)满足客户对货物发到时间范围的要求；(3)在允许通行的时间进行配送(如有时规定白天不能通行货车等)；(4)车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量，在物流中心现有运力范围内。7、目标函数。对物流配送车辆调度问题，

25、可以只选用一个目标，也可以选用多个目标。经常选用的目标函数主要有:(1)配送总里程最短。配送里程与配送车辆的耗油量、磨损程度以及司机疲劳程度等直接相关，它直接决定运输的成本，对配送业务的经济效益有很大影响。由于配送里程计算简便，它是确定配送路线时用得最多的指标。(2)综合费用最低。降低综合费用是实现配送业务经济效益的基本要求。在物流配送中，与取送货有关的费用包括:车辆维护和行驶费用、车队管理费用、货物装卸费用、有关人员工资费用等。(3)准时性最高。由于客户对交货时间有较严格的要求，为提高配送服务质量，有时需要将准时性最高作为确定配送路线的目标。(4)运力利用最合理。该目标要求使用较少的车辆完成

26、配送任务，并使车辆的满载率最高，以充分利用车辆的装载能力。(5)劳动消耗最低。即以司机人数最少、司机工作时间最短为目标。根据以上构成VRP的因素，加上现实中车辆优化调度问题是十分复杂，为方便建模和求解，需要对现实问题进行一些抽象和简化。现对本文研究的物流配送车辆优化调度问题做如下界定：1、从一个物流中心向多个客户送货或取货，物流中心和客户的位置是一定，物流中心供应的货物，能够满足所有客户的需求。2、各个客户需求的或供应的货物均可以相互混装，即可以装在同一个配送车辆内，每个客户的货物需求量或供应量不超过配送车辆的最大载重量，每个客户的送货或取货要求必须满足，且仅能由一台车辆完成，不允许分批配送或

27、取走。3、每台配送车辆的最大载重量一定，不允许超载；配送或取货时，设每台车辆都从物流中心出发，向一些客户提供配送或取货服务后，最终返回物流中心。4、对于客户要求货物送到或取走的时间，分别考虑以下两种情况：(1)无时间限制(2)要求在指定的时间窗内完成送货或取货任务，不允许提前或拖后，即硬时间窗；5、物流中心与客户之间以及客户相互之间的距离已知，配送车辆在物流中心、客户间的行使时间以知，不考虑运输车辆中、车辆流量的限制。因此，本文所研究的物流配送车辆优化调度问题均属于单物流中心、非满载的车辆优化调度。第3章洪盛物流公司业务分析3.1 洪盛物流公司简介洪盛物流公司是湘潭钢铁集团下属的现代化的第三方

28、物流公司，主要从事钢铁、汽车零件等一系列的货物配送。洪盛物流公司成立于2007年，将自己定位为整个湘潭市各种物流配送管理者和领导者，并逐步向外扩展。洪盛物流结构：一个配送中心，加上几个子公司（一些正在建设中）。自己拥有的车辆不多，主要是靠社会运输车辆，来进行货物的运输。3.2 洪盛物流公司的业务分析洪盛物流公司操作流程如下：湘潭钢铁集团多元化商品供应商VV货物配送中心客户客户图3.1在洪盛物流的业务中，洪盛物流的物流运输是对整个配送业务的管理。配送业务有:1、物流公司与客户的具体送货或提货地点之间的运输。包括原材料供应商的备货、交易入库；湘潭钢铁集团的销售运输业务2、单独的针对具体客户的门到门

29、的运输。主要指不用经过物流结点直接从客户到客户的运输，或者是其它的第三方物流客户的运输业务。由于每天都有大量的货物的运输，伴随着物流行业的发展，竞争的激烈，目前所有的运输资源都是由洪盛物流公司统一调度管理，由于湘潭钢铁集团运作和集中调度的需要，对洪盛物流公司运力的统一优化就成为必然。目前，洪盛物流可用到的车辆中从所有及调度管理管理管理上分为三种类型：1、 洪盛自购车辆，所有权属及调度权完全属于洪盛。2、 其它社会运输车辆。一旦签定协议，调度权也属于洪盛，只不过是雇佣，按单生效。3、 与其它物流公司合作（承运商的车辆），签定协议，按照洪盛的要求进行运输。3.2.1 运输路线洪盛运输模型中，直接两

30、点间的运输线路分主线路和备用线路，都是也确定好的。主线路是默认的运输线路，备用线路用于异常情况的应对处理。因此在进行车辆优化调度时不考虑中间上货的问题。本文主要优化计算的是默认路线。3.2.2 优化的基本原则车辆优化调度的基本原则是在保证及时性的最小成本原则，具体有：（ 1）供应客户的货物及时，客户需要的货物及时的到达是优化调度中必须优先考虑的因素。（ 2）成本最低原则。比如：运输中尽量避免回程空载，先前就要对往返货物配合好；全局优化，车辆调度不能仅仅局限在当前任务的两点，车辆可以在全国范围内运输，不必一定返回原来的地点。3.2.3 车辆优化调度问题和困难通过对洪盛物流公司物流配送车辆业务分析

31、它存在的问题和困难如下：（ 1）自己车辆比较少，大多数靠联系社会运输车辆来完成货物运输，而且缺乏有效的网络技术平台，不能很好的掌握社会运输车辆信息。（ 2）缺乏有效运输理论支持，分析洪盛的运输模型，其有特殊的要求，它稳定的顾客不多，流动性很大。这不同于我们通常所见的配送车辆优化计算模型，也有别于多点需求，多点供货的运筹优化模型。（ 3）财务投资，需要采用自力更生的法则进行优化方法设计和实现，需要经历实践的充分检验。（ 4）范围广，多个优化原则共同作用，必须满足货物配送的及时性与最小成本的原则。这就需要建立一个计算机网络系统，及时的了解货物运输、客户的情况；并且通过算法计算让行驶的总路线最小或

32、运输费用最小，以及运输车次最少。3.3小结本章首先介绍了洪盛物流公司的业务背景，然后对洪盛物流公司中的业务进行分析运输路线、可优化的原则，提出在物流配送车辆优化调度上存在的问题和困难，有待解决。第4章蚁群算法在车辆优化调度问题中的应用4.1 蚁群算法的概述自然界一直是人类创造力的丰富源泉，人类认识食物的能力来源于与自然界的相互作用。自然界中的许多自适应优化现象不断给人以启示，近年来，一些与经典的数学规划原理截然不同的、试图通过模拟自然生态系统机制以求解复杂优化问题的仿生优化算法相继出现（如遗传算法、蚁群算法、微粒群算法、人工免疫算法、人工鱼群算法、混合蛙跳算法等），大大丰富了现代优化技术，也为

33、那些传统最优化技术难以处理的组合优化问题提供了切实可行的解决方案15。蚁群算法是一种随机搜索算法，是基于对自然界蚂蚁的群体觅食行为的模拟而得出的一种仿生优化算法，它具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法相结合等优点。尽管蚁群算法的严格理论基础尚未奠定，国内外的相关研究还处于实验探索和初步应用阶段，但是目前人们对蚁群算法的研究己经由当初单一的TS嗷域渗透到了多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内的研究逐渐拓展到了连续域范围内的研究，而且在蚁群算法的硬件实现上也取得了很多宋破性的研究进展，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的

34、发展前景3。4.2 蚁群算法原理蚁群算法是意大利学者M.Dorigo等提出的一种仿生寻优算法，它通过模拟自然界蚁群从巢穴到食物源的最短路径的觅食过程来求解一些NP难题16。蚁群算法是一种通用型随机优化算法，对向题的求解没有苛刻的限制使用条件，可以在非常困难的条件下搜索到组合问题的最优解或较优解，在很多经典的组合优化领域上都有较好的应用，如旅行商问题（TSP）和非对称旅行商问（ATSP）、作业车间调度问题（JSP）7。蚁群算法是通过信息素的积累和更新来寻求最优解。蚂蚁有能力在没有任何提示下找到从巢穴到食物源的最短路径，并且能随环境的变化而变化，适应性地搜索新的路径，产生新的选择。其根本原因是妈蚁

35、在寻找食物源时，在其走过的路上释放一种特殊的分泌物信息素，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。当它们碰到一个没有走过的路口时，就随机地挑选一条路径前行与此同时释放出与路径长度有关的信息素。路径越长，释放的信息素浓度越低。当后来的蚂蚁再次碰到这个路口时，选择信息素较高路径的概率就会相对较大。而当一定路径上通过蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来的蚂蚁选择该路径的概率也越高.从而更增加了该路径的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。文献17阐述了蚂蚁的路径搜索原理，如图4.1所示：D图4.1有两条支路ACB和ADB,支路ACB

36、长；节点A和B各有两只蚂蚊，其中蚂蚁1,2由A向B行进，而3,4则由B向A行进。假设蚂蚁速度相同，当蚂蚁2和蚂蚁4经过支路ADB分别到达节点B和A,而蚂蚁1和3还在支路ACB的途中。显然，支路ADB留下的信息素的痕迹浓度要高于支路ACB上的信息素浓度；所以当再有蚂蚁到达点A和B时，它们选择支路ADB的概率就会更大，从而增加支路ADB上的信息素痕迹的浓度，形成正反馈，这样蚂蚁可以容易找到一条到食物源的最短路径。4.3 蚁群算法在车辆优化调度问题中的应用一般车辆优化调度（VRP）问题是指对于给定的n个客户集合（1,2,，n）,找到从配送中心出发，及时访问每个客户完成配送任务，且回到配送中心的最小花

37、费的环路。VRP问题的目标函数是：MinZ=二d（i,i+1）+d（n,0）i1式中dj（i,j=1,2,n）表示客户点i至客户点j完成配送所需的费用。4.3.1 算法设计设n是客户数，m是蚂蚁的数目，bi表示t时刻位于客户i的蚂蚁的数目，石表示t时刻在路径（i,j）上的信息素浓度，则m=Zbi（t）;r=jt）|i,ccjC是t时刻集i4合C中元素（客户）两两连接线上lij上残留信息素浓度的集合，蚁群算法是通过有向图g=（C,L,P）实现。初始状态，各条线路上信息素浓度相等，设M0)=const=0(或MAX),每只蚂蚁k(k=1,2,m)从配送中心出发，论文用禁忌表tab味来记录蚂蚁k当前

38、已经完成配送任务的客户，并随时作动态更新。在搜索过程中，蚂蚁根据各条线路上的信息素浓度及路径的启发信息来计算状态转移概率。P1(t)表示在t时刻蚂蚁k由客户i转向客户j的状态转移概率:(4.3.1)式中，allowedk=C-tabuk表示蚂蚁下一步允许访问的客户集；可表示由客户i转移到客户j的期望程度，可由某种启发式算法确定(通常取值为1/dij)；冉B分别表示蚂蚁信息素浓度及路径长度在蚂蚁选择概率上所起的作用。经过n个时刻，蚂蚁完成一次循环，所有蚂蚁的禁忌表都已填满，此时计算每只蚂蚁走过的路径长度，并找到最优路径保存，记录此路径并更新信息素。这种更新策略模仿了人类大脑记忆的特征，在新信息不

39、断存入大脑的同时，存储在大脑中的旧信息随时间的推移不断淡化，甚至忘记。t+n时刻在路径(i,j)上的信息素浓度可按如下规则进行更新：u(t+n)=(1-p)*/(/式t)Mt尸rj(t)k1式中，P称为消散系数，则1-P表示信息素残留因子，为了防止信息素的无限积累，的初始值范围设定为：pC0,1；Tj(t)表示本次循环中路径(i,j)上的信息素增量,初始时刻47(t)=0,Uk(t)表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息素。式中，Q是参数，Lk表示第k只蚂蚁在本次循环中路线上的费用。4.3.2算法分析蚁群算法是一种源于大自然中生物世界的仿生算法，是一种通用型随机优化方法。ACO算

40、法不仅能够智能搜索、全局优化，而且具有鲁棒性、正反馈、分布式计算、易与其它算法集成等特征，为求解复杂优化问题提供了有力的工具。分布式计算可以避免过早地收敛；正反馈可以强化问题的可行解18。(1)强鲁棒性:对蚁群算法模型稍加改进，就可以应用于其它问题；(2)分布式计算:蚁群算法是一种基于群体智能的启发式搜索算法，具有本质并行性，易于并行实现；(3)容易与其他方法集成:蚁群算法很容易与多种启发式算法集成，以改善算法的性能。但是，任何一种新算法都有一个不断完善不断发展的过程，蚁群算法也存在一些缺陷，如需要较长的搜索时间和容易陷入局部最优等问题。从蚁群算法的描述可以看出，算法在求解过程中，蚁群的转移是

41、由各条路径上留下的信息素的轨迹和客户间的距离信息来引导。蚁群的移动总是趋近于信息素浓度增大的方向。信息素浓度最大的路径常常与所需要的最优路径比较接近。然而，信息素浓度最大的路径并不总是最优路径。这是因为当N条路径上信息素浓度相差不大时，由于蚂蚁选择的随机性，它可能会选中一条离最优解相差甚远的路径，蚁群会在正反馈作用下移向这条路径，使其它路径上的信息素浓度得不到应有的加强，从而阻碍后续蚂蚁搜索更好的全局最优解。蚂蚁随机选路的策略，使得算法进化速度缓慢;正反馈机制旨在强化性能较好的解，却使算法容易出现停滞现象。这是造成蚁群算法缺陷的根本原因。在卡索府年I用I间建立一个平衡点是蚁群算法所要研究的关键

42、问题之一，也就是说既要使得算法的搜索空间尽可能大，以寻找那些可能存在最优解的解区间，又要充分利用蚂蚁群体当前所具有的有效信息，使算些可能具有较高适应值的个体所在的区间，从而以较大的法搜索的侧重点放在那概率收敛到全局最优解6。第5章运用混合蚁群算法求解洪盛物流车辆优化调度问题5.1 一般车辆优化调度问题描述物流配送车辆优化调度问题是配送车辆从一个或多个设施到多个地理上分散的客户点，优化设计一套车辆调度方案，同时要满足一系列的约束条件。现在所分析的是有容量限制的车辆优化调度问题（CVRP）。有容量限制的VRP问题一般可描述为：从同一物流中心用多台配送车辆向多个客户送货。每个客户的位置和货物需求量一

43、定，配送车辆的载重量一定，要求合理安排配送车辆的路线，使成本最小。5.2 混合蚁群算法目前，针对车辆优化调度问题的求解算法是相当丰富的，由于实际问题的规模庞大，使得精确算法的实施受到阻碍，现在的研究多数是集中在启发式算法上。在设计VRP蚁群算法时，通过吸收前人设计TSP的蚁群算法的经验基础上，充分考虑VRP的具体要求。并在此基础上，对算法的选择机制、更新机制以及协调机制进一步改进，引人自适应的转移策略和信息素更新策略，并融合爬山法、节约法等求解VRP的传统方法，充分发挥其易与其它方法结合的优点，以克服蚁群算法计算时间长、易出现停滞的缺陷。本章节采用改进的蚁群算法求解CVRPo5.2.1 算法设

44、计（1）转移规则借鉴Dorigo的Ant-Q算法思想19,采用确定性选择和随机选择相结合的转移策略,如下宵和巧的含义与TSP蚁群算法中的相同，分别表示信息素浓度和能见度（取边长倒数），pj=di0+d0j中是考虑了任务点与配送中心间的距离而引入的变量，称为节约值。四反映了将两点直接连接比将两点分别与配送中心连接所能获得的路径长度节约量，显然，肉越大，收益越大，而选择结点丫的概率也就越大。p是个随机数，服从（0,1）区间上的均匀分布。r0随算法的进化过程在0-1范围内动态调整。在初始阶段，蚂蚁选择的范围较大，因此ro也应该比较大.在中间阶段，若算法收敛速度较慢，则减小r。，而若较快，则适当地放大

45、ro,若算法陷入局部解，则加大ro,让蚂蚁更多地进行随机选择。（2）信息素更新规则信息素更新规则采用局部更新和全局更新相结合的策略。a扃部更新规则定义1吸引力.设经过结点i的蚂蚁数为R,经过有向边（i,j）的蚂蚁数为r,则称r/R为边（i,j）的蚂蚁吸引力。在进行信息素局部更新时，若每次施放的信息素量Q为常量，则（i,j）的蚂蚁吸引力越大，经过边（i,j）的蚂蚁相对其它的边来说数量越多，从而局部更新的次数就越多，久而久之，会导致边之间的信息素量差距过大，限制算法搜索的全局性。Q值的大小也会影响算法的搜索效率，Q值过大会使算法易收敛于局部极小值，过小又会影响算法的收敛速度。随着算法搜索状态的变化

46、Q值也应该不断调整，调整的原则是，边的吸引力越大，Q（t）越小，不妨设Q（t）=Q（1-r/R）。假设第k只蚂蚁在第nc次迭代周期中的第f次转移时经过边（i,j）,在此之前共有Rk只蚂蚁经过i点，其中有rk只蚂蚁选择了边（i,j）.则该蚂蚁在（i,j）上的信息素局部更新量（采用Ant-Qsystem型）为Qi(1-rk/Rk)蚂蚁k从i转移到jTijk=4o0否则4ewij=pl%dij+丁Wij任意i,jYjmu=vTk丁wj和gdj分别表示边（*j）上的原有信息素浓度以及更新后的信息素浓度。b.全局更新规则在所有蚂蚁均构造完路径后，对所有可行解以及岂今为止最优解的边进行全局信息素更新。采取的规则如下pnewold-pA*Tij=p2rij+LTij+1jpT任意i,ji*j其中，当（i,j）CAp时，J=Q2/D（Ap）,否则用p=0,当（i,j）CL*时，4*=Q3/D（L*）,否则下*=0,D（Ap）表示第p个可行解的路径长度，D（L*）表示迄今为止最优解的路径长度。（3）负反馈机制蚁群算法的选择机制就是使好的路径会以较大的概率选中，而正反馈机制的存在又必然会促使这些路径在以后的选择中更具竞争优势.当搜索陷人局部最优解时，按传统的方式，算法无法从局部极小值点跳出来。为此引人负反馈机制，包括：1）