（系统工程专业论文）基于GIS的物流配送路径优化算法研究.pdf

第一章绪论 第一章绪论 物流作为“第三利润源泉”，对现代经济活动的作用同益明显， 也越来越引起人们的重视。在经济全球化和信息化的大环境下，现 代物流业己从为社会提供传统的运输仓储服务向产品包装、分拣、 配送、流通加工等增值服务扩展。 配送是物流系统中一个直接与消费者相连的重要环节，包括货 物从物流结点送达收货人的全过程，是指在集货、配货基础上，按 客户对货物种类、品种搭配、数量、时间等要求所进行的运送，是 “配”和“送”的有机结合。 对配送系统进行优化研究的最终目标是降低配送总成本，从而 获取“第三利润”。其中，配送路径选优是物流配送系统决策的重 要内容，其主要指在满足客户需求条件下进行车辆调度和配送路线 的优化，办即本文将重点研究的物流配送系统路径优化问题。配送 车辆路线是否合理对配送的速度、成本、效益有着直接的影响，在 配送决策中显得至关重要【l 】。 1 1 论文研究背景和意义 随着现代物流业的快速发展，物流信息量迅速增加，物流配送 也呈现出很多新的特点，主要表现在：城市道路网复杂，配送货运 点多、分布不均匀，货物种类繁多，符合电子商务特点的配送高时 效性，客户对配送需求的时间约束要求等等。新的形势对配送系统 也有新的要求，如何在保持高度准时、快速配送要求下降低成本是 物流配送面临的新挑战。相比之下，传统的配送系统有以下问题： 物流系统管理信息化程度较低，缺乏可视性；对海量数据分 析、处理及决策支持能力较差；决策时所依赖的配送模型过于 理想化，较少考虑实际因素的变化，实用性较差。主要体现在： ( 1 ) 难以满足客户的服务高要求。电子商务的特征是交易量巨 北京交通人学硕十学位论文 大和交易速度极快，而传统物流配送的特点是人工调度、反应时间 长。信息流与物流效率的矛盾会导致整个电子商务客户服务的低 效，服务质量自然大打折扣。 ( 2 ) 物流成本高。传统的物流配送大多是由人工调度的，在交 易量较小的情况下，可以合理地安排配送，降低成本。一旦交易量 增加、交易速度加快，配送调度就会超出人工的能力范围，会导致 大量的不合理调度的出现，配送运输出现迂回，物流成本升高。 ( 3 ) 增加城市交通的负担。物流配送调度的不合理，会使物流 配送路线迂回，导致在途车辆增加，使本己拥挤的城市交通更加拥 挤。在我国，物流配送的落后己经成为电子商务蓬勃发展的瓶颈之 一，要进一步发展电子商务，必须实现物流配送的现代化。其主要 包括配送网络的合理布局、运输车辆的智能调度、运输线路优化选 择等一系列问题，这些问题的解决需要海量的计算并且配送问题 有时限的要求，仅靠人的经验难以完全满足要求。因此，迫切需要 计算机支持的配送决策支持系统来辅助决策。 另一方面，地理信息系统( g e o g r a p h i ci n f o 硼a t i o n s y s t e f n ，g i s ) 作为计算机科学、地理学、测量学、地图学等多门学 科综合的交叉学科，近年来发展非常迅速，应用范围也不断扩大。 g i s 技术的快速发展和广泛应用给物流配送技术提供了新的思路。 g i s 除了具有信息系统的各种特点外，还能够进行相关的空间数据 可视化操作，并在此基础上进行更为复杂的空间分析，这对于物流 配送路径的优化和可视化具有重要意义。由于传统物流系统规划局 限于单一的数据处理和表现，缺乏直观性和可视化，而g i s 能够帮 助人们将电子表格和数据库中无法看到的数据之间的模式和发展 趋势以图形的形式清晰直观地表现出来，实现数据可视化，并进行 地理空问信息的相关分析，实现地理空间分析与配送模型的集成， 从而满足配送决策优化的需求。因此，从某种意义上讲，g i s 是一 种决策支持系统，g i s 技术的应用可以给物流配送系统提供较优的 决策方案。 现代物流配送信息量的急剧膨胀和配送环境的复杂化造成了 第一章绪论 配送方案的决策复杂化。引入g i s 技术可以在使配送系统决策在三 个方面得到改善：可视化、效率和可靠性。 第一，传统物流配送系统仅限于单纯的数据处理和表现，引入 g i s 可以提高决策的直观性和可视化程度。 第二，现代物流具有信息量极大的特点，对于一般的信息系统 来讲，对大量与配送相关的空间数据进行高效操作和分析比较困 难，可以利用g i s 强大的空间数据处理能力提高配送决策的效率。 第三，现代物流的复杂性使得仅依赖传统的运筹学方法无法得 出满意的方案，借助g i s 的空间分析功能，可提高决策的可靠性。 因此，利用g i s 技术，结合物流配送优化方法，对物流配送方 案中的车辆路径选择进行优化是本论文研究的目的所在。具体表现 在三个方面：一是寻求提高物流配送决策可视化的途径：二是要寻 求由于海量信息引起空间数据处理能力不足问题的解决方法，提高 决策的效率：三是寻求g i s 与配送模型相更好的结合方法，提高决策 的可靠性。 本论文根据配送信息具有较强的空间地域性的特点，探讨将 g i s 技术应用于物流配送路径优化中的技术和方法，以提高物流配 送管理可视化程度、配送决策的科学性和决策效率，因而本论文研 究具有重要的理论意义和实际意义。 1 2 物流配送概述 配送：在经济合理区域范围内，根据客户要求，对物品进行拣 选、加工、包装、分割、组配等作业，并按时送达指定地点的物流 活动。物流配送系统包括货物集中，库存管理，车辆调度，配送运 输等多个环节，配送的一般流程如图卜1 所示：【2 】 北京交通火学硕士学位论文 幽卜1 配送流程图 配送中心：指以组织配送性销售或供应，执行实物配送为主要 职能的流通性节点。配送中心是从供应者手中接收大量的货物，进 行包装、分类、保管、流通加工和信息处理等作业然后，按照众多 需要者的订货要求备齐货物，以令人满意的服务水平进行配送的设 施。一般来看，配送中心是在仓库的基础上形成和发展起来的，因 而，配送中心与仓库在许多方面有相似之处，但是配送中心具有更 加广泛的功能。它包括货物的接收、分拣、整理、保管、装卸和发 运等功能，并且配送中心也是物流信息的集聚和发散中心，物流信 息全面、系统流动性强。 物流配送也就是在产品用户集中的区域，按用户的订货要求和 时间计划，在物流中心配货，并将配好的货物采用汽车巡回运送方 式送交收货人的为多用户服务的运输。配送不是单纯的运输或是送 货，而是运输与其它活动的组合，除了各种运输活动外，还要从事 大量的集货、分货、配货、配装等工作，是配与送的结合。 物流配送类型：按物流配送的主体来划分为大型生产厂商主导 型物流配送，大型连锁企业自主型物流配送，专业物流企业丌展的 社会化物流配送，以交通运输业为主体的货运转运型物流配送。 物流配送的形式：按物流配送经营的形式主要可分为直送和分 送。直送是指生产厂商或供应商根据客户订货要求，直接将商品从 仓库( 配送中心) 运送到零售商场或需求客户的整车量、高频度地运 送方式。直送的最大特点是客户的需求量大，每一次订货需求往往 北京交通人学硕士学位论文 第三章物流配送路径优化问题的数学描述：首先给出了t s p 问 题的数学描述，然后给出一般v r p 问题的数学描述，最后对起终点 固定的v r p 问题进行数学描述。 第四章基于遗传算法的物流配送路径优化模型求解方法：在 前述理论基础上，探讨基于基于遗传算法的物流配送路径优化模型 求解方法，首先对遗传算法应用与物流配送路径问题进行分析，然 后提出了基于遗传算法的物流配送路径优化模型求解步骤与实现。 第五章基于蚁群算法的物流配送路径优化模型求解方法：在 | j i 述理论基础上，探讨基于基于蚁群算法的物流配送路径优化模型 求解方法，首先对蚁群算法应用与物流配送路径问题进行分析，然 后提出了基于蚁群算法的物流配送路径优化模型求解步骤与实现。 第六章基于禁忌搜索算法的物流配送路径优化模型求解方 法：在前述理论基础上，探讨基于基于禁忌搜索算法的物流配送路 径优化模型求解方法，首先对禁忌搜索算法应用与物流配送路径问 题进行分析，然后提出了基于禁忌搜索算法的物流配送路径优化模 型求解步骤与实现。 第七章基于g i s 的物流配送路径优化问题的实现与分析：首 先给出了以上三种算法的g i s 系统实现，然后对三种算法进行比较 分析。 第八章总结与展望：对本文主要研究成果进行了总结，提出 了相关建议。 第二章物流配送路径优化问题研究综述 第二章物流配送路径优化问题研究综述 2 1 物流配送车辆调度问题概述 2 1 1 物流配送车辆调度问题的描述 物流配送车辆调度问题可以描述为：在一个存在供求关系的系 统中，有若干台车辆、若干个物流中心和客户，要求合理安排车辆 的行车路线和出行时间，从而在给定的约束条件下，把客户需求的 货物从物流中心送到客户，把客户供应的货物从客户取到物流中 心，并使目标函数取得优化。 2 1 2 物流配送车辆调度问题的构成要素4 1 物流配送车辆调度问题主要包括货物、车辆、物流中心、客户、 运输网络、约束条件和目标函数等要素。 ( 1 ) 货物。货物是配送的对象。可将每个客户需求( 或供应) 的 货物看成一批货物。每批货物都包括品名、包装、重量、体积、要 求送到( 或取走) 的时间和地点、能否分批配送等属性。 货物的品名和包装，是选用配送车辆的类型以及决定该批货物 能否与其它货物装在同一车辆内的依据。例如，一些货物因性质特 殊需要使用专用车辆装运：一些货物因性质特殊不能与其它货物装 在同一车辆内：一些货物虽然性质特殊，但由于包装条件很好，故 也能与其它货物装在同一车辆内。 货物的重量和体积是进行车辆装载决策的依据。当某个客户需 求( 或供应) 货物的重量或体积超过配送车辆的最大装载重量或容 积时，则该客户将需要多台车辆进行配送。 货物的送到( 或取走) 时间和地点是制定车辆的出行时间和配 送路线的依据。允许货物分批配送，是指某个客户的需求( 或供应) 北京交通大学硕士学位论文 的货物可以用多辆车分批送到( 或取走) ，即使其需求( 或供应) 量在 一辆车的装载量以下。 ( 2 ) 车辆。车辆是货物的运载工具。其主要属性包括：车辆的类 型、装载量、一次配送的最大行驶距离、配送前的停放位置及完成 任务后的停放位置等。 车辆的类型有通用车辆和专用车辆之分，通用车辆适于装运大 多数普通货物，专用车辆适于装运一些性质特殊的货物。 车辆的装载量是指车辆的最大装载重量和最大装载容积，是进 行车辆装载决策的依据。在某配送系统中，车辆的装载量可以相同， 也可以不同。对每台车辆一次配送的行驶距离的要求可分为以下几 种情况：无距离限制：有距离限制：有距离限制，但可以不遵 守，只是不遵守时需另付加班费。 车辆在配送前的停放位置可以在某个停车场、物流中心或客户 所在地。车辆完成配送任务后，对其停放位置的要求可分为以下几 种情况：必须返回出发点：必须返回某停车场：可返回到任意 停车场：可停放在任何停车场、物流中心或客户所在地。 ( 3 ) 物流中心。也称为物流基地、物流据点，是指进行集货、 分货、配货、配装、送货作业的配送中心、仓库、车站、港口等。 在某配送系统中，物流中心的数量可以只有一个，也可以有一 个以上：物流中心的位嚣可以是确定的，也可以是不确定的口对于 某个物流中心，其供应的货物可能有一种，也可能有多种：其供应 的货物数量可能能够满足全部客户的需求，也可能仅能满足部分客 户的需求。 ( 4 ) 客户。也称为用户，包括分仓库、 圆搿葫嚼；瑚增穗糯谭堪 x 北京交通大学硕士学位论文 标，也可以选用多个目标。经常选用的目标函数主要有： 配送总里程最短。配送里程与配送车辆的耗油量、磨损程度以及 司机疲劳程度等直接相关，它直接决定运输的成本，对配送业务的 经济效益有很大影响。由于配送里程计算简便，它是确定配送路线 时用得最多的指标。 配送车辆的吨位公里数最少。该目标将配送距离与车辆的载重量 结合起来考虑，即以所有配送车辆的吨位数( 最大载重吨) 与其行驶 距离的乘积的总和最少为目标。 综合费用最低。降低综合费用是实现配送业务经济效益的基本要 求。在物流配送中，与取送货有关的费用包括：车辆维护和行驶费 用、车队管理费用、货物装卸费用、有关人员工资费用等。 准时性最高。出于客户对交货时间有较严格的要求，为提高配送 服务质量，有时需要将准时性最高作为确定配送路线的目标 运力利用最合理。该目标要求使用的较少的车辆完成配送任务， 并使车辆的满载率最高，以充分利用车辆的装载能力。 劳动消耗最低。即以司机人数最少、司机工作时间最短为目标。 2 1 3 物流配送车辆调度问题的分类 物流配送车辆调度问题可按照其构成要素划分为不同的种类 川 ( 1 ) 按物流中心的数目分，有单物流中心问题( 配送系统中仅有 一个物流中心) 和多物流中心问题( 配送系统中存在多个物流中 心) 。 ( 2 ) 按车辆载货状况分，有满载问题( 由于客户需求或供应的货 物数量大于或等于车辆的载重量，故完成一项配送任务需要一辆及 其以上的配送车辆，配送车辆需要满载运行) 、非满载问题( 由于客 户需求或供应的货物数量小于车辆载重量，多项配送任务可共用一 辆配送车辆，车 参 基旨型删卿爱扛瓣年磊载混合问题( 由于一部分客户需求或 第二章物流配送路径优化问题研究综述 于车辆的载重量，而另一部分客户需求或供应的货物数量小于车辆 的载重量，造成一些配送车辆需要满载运行，而另一些车辆则经常 处于不满载状念) 。 ( 3 ) 按配送任务特征分，有纯送货问题( 仅考虑从物流中心向客 户送货，也称为纯卸问题) 或纯取货问题( 仅考虑把各客户供应的货 物耿到物流中心，也称为纯装问题) 及取送混合问题( 既考虑将客户 需求的货物从物流中心送到各个客户，同时考虑将客户供应的货物 从客户取到物流中心，也称为装卸混合问题或集货和送货一体化问 题) 。 ( 4 ) 按客户对货物取( 送) 时间的要求分，有无时限问题( 客户对 货物的取走或送到的时间无具体要求) 和有时限问题( 客户要求将 需求的货物在规定的时间窗内送到，将供应的货物在规定的时间窗 内取走，也称为有时间窗问题) 。有时限问题又可以分为硬时间窗 问题( 客户要求货物必须在规定的时间窗内送到或取走，不能提前 也不能拖后) 和软时间窗问题( 客户要求将货物尽量在规定的时间 窗内送到或取走，但也可以提前或拖后，只不过在提前或拖后时， 要对配送企业实施一定的惩罚) 。 ( 5 ) 按车辆类型数分，有单车型问题( 所有配送车辆的载重量相 同) 和多车型问题( 配送车辆的载重量不完全相同) 。 ( 6 ) 按车辆对车场的所属关系分，有车辆开放问题( 即车辆完成 配送任务后可以不返回其发出车场) 和车辆封闭问题( 车辆完成配 送任务后必须返回其发出车场) 。 ( 7 ) 按优化目标数分，有单目标问题( 仅考虑一个配送目标) 和 多目标问题( 同时考虑多个配送目标) 。 2 2 物流配送车辆调度问题的现有求解方法综述 国外对物流配送车辆调度问题作了大量而深入的研究。早在 1 9 8 3 年b o d i n g 0 1 d e n 等人在他们的综述文章中就列举了7 0 0 余篇有 关文献。在c h r i s t o f i d e s ( 1 9 8 5 ) ，g o l d e n 和a s s a d ( 1 9 8 8 ) 编辑的论 北京交通人学硕士学位论文 文集中，以及a l t i n k e m e 和g a v i s h ( 1 9 9 1 ) ，l a p o r t e ( 1 9 9 2 ) ，s a l h i ( 1 9 9 3 ) 等的综述文章中都对该领域的研究成果进行了详尽的阐述。 近年来，有很多国外学者利用多种算法对物流配送车辆调度问题进 行了求解。该研究领域的代表人物主要有b o d i n ， c h r i s t o f i d e s ，g o l d e n ， a s s a d ，b a l l ，l a p o r t e ，r i n n o o yk a n ， i 。e n s t r a ，d e s r o s i e r s 矛口d e s r o c h e r s 等h 1 。 国内也有一些对物流配送车辆调度问题的研究。李大卫”“等以 t s p 的最近距离启发式算法为基础，通过设置评价函数来处理时间 窗约束，求解了简单的v s p 问题。张震针“1 对单车场满载问题，提 出了考虑运输行程约束的优化方法。蔡延光“1 等应用并行禁忌搜 索算法和模拟退火算法对满载问题进行了求解。刘浩1 等用模拟退 火算法求解了两车型随机需求的v r p 。张涛“”。等用禁忌搜索算法和 遗传算法的混合策略求解了v r p 。王莉。用启发式算法求解了有时 限的v r p 。袁健“等用神经网络法求解了v r p 。姜大立、李大卫1 1 。 分别用遗传算法求解了无时限和有时限的物流配送车辆调度问题。 近年来，郭耀煌、李军、谢秉磊“”、”。等对物流配送车辆调度问题 进行了较为深入的研究，提出了多种求解算法。周双贵。“1 对物流 配送车辆调度问题的模型和求解方法也进行了较为深入的研究。 物流配送车辆调度问题提出后，不少专家学者对其计算复杂性 进行了研究，这是确定其求解算法研究方向的基础。l e n s t r a 和 r i n n o o yk a n 。“”在文献中，对v r p 的计算复杂性进行了综述和分 析：d a n t z i g 和f u i k e r s o n ( 1 9 5 4 ) 证明了有确定开始时间的物流配 送车辆调度问题的复杂性为0 ( n 。) ；s a v e l s b e r g h ( 1 9 8 5 ) 和 s o l o m o n ( 1 9 8 6 ) 提出有时限的物流配送车辆调度问题比一般的物 流配送车辆调度问题更复杂；s a v e l s b e r 曲( 1 9 8 5 ) 提出有时限的物 流配送车辆调度问题不仅问题本身是n p 难题，甚至在车队大小固定 时，找一个可行解也是n p 难题；l e n s t r a 和r i n n o o p yk a n 还证明了 几乎所有类型的物流配送车辆调度问题均为n p 难题。 第二章物流配送路径优化问题研究综述 物流配送车辆调度问题作为一个n p 难题，随着客户数量的增 加，可选的配送路径方案数量将以指数速度急剧增长，即出现组合 爆炸现象。据计算，对于一个有2 0 个顶点的t s p ( t r a v e l i n g s a l e s m a np r o b l e m ，即旅行商问题) ，其可能的路径总数为 2 01 ( 2 牢2 0 ) 。6 0 8 1 0 ”，即使用每秒一亿次的计算机按穷举搜索法 求解，也需要计算3 5 0 年“。物流配送车辆调度问题作为一个约束 性多路旅行商问题，与t s p 相比，不仅约束条件更为复杂，而且存 在多条配送路径，因此，其计算量会比t s p 大得多。一般地，只有 在客户数量较少、运输网络较简单时，才能求得物流配送车辆调度 问题的精确最优解。求解物流配送车辆调度问题的方法很多，究其 实质，可以分为精确算法和启发式算法两大类。精确算法是指可求 出其最优解的算法，主要有：分枝定界法、割平面法、网络流算法、 动态规划法等。由于精确算法的计算量一般随问题规模的增大呈指 数增长，在实际中其应用范围很有限。为此，专家们把精力主要用 在构造高质量的启发式算法上。 下面对物流配送车辆调度问题的一些常用求解方法进行简单 评述。 由于v r p 与t s p 存在内在的本质联系，因此有相当数量的t s p 的 启发式算法在考虑到v r p 的特点和约束后，可以用于v r p ，诸如，邻 近点算法、插入算法、行程改进算法等。但是，大多数的v r p 的人 工智能算法并不等同于t s p 的启发式算法，常见的有特色的人工智 能算法有以下几种。 1 ) s w e e p 算法。该算法是由w r e n g i l l e t t 等人提出的。即先 计算出所要访问的点的极坐标，并按角度大小排序。然后在满足可 行性条件的前提下，按角度大小归并到不同的子路径中。最后再根 据t s p 的优化算法对所得到的子路径进行优化。 2 ) c h r i s o f i d e s m i n g o z z i t o t h l 两阶段算法它主要面向 c v r p 和d v r p 。该算法的求解过程分为两个阶段：第一阶段按最小路 径的原则形成初始解，然后用k o p t 算法对所得的各子路径分别进 第二章物流配送路径优化问题研究综述 用于辅助规划，即是把g i s 系统与其他领域系统相结合，以充分利 用其空间数据处理分析功能完成其他系统的决策分析。 g i s 应用于物流分析，也是利用g i s 强大的地理数据功能来完善 物流分析技术，国外公司已经开发出利用g i s 为物流分析提供专门 分析的工具软件。完整的g i s 物流分析软件集成了车辆路线模型、 最短路径模型、网络物流模型、分配集合模型和设施定位模型等。 一方面，可用于物流配送车辆优化调度、解决行程路线安排，以使 物流费用最优；另一方面，可用于城市物流网络设施( 如配送中心) 的选址规划，在产地、销地、仓库、运输线路组成的物流网络中， 确定仓库的最佳数量、位置、规模；在地图上划分最合理的销售市 场范围或服务范围等问题。 1 )车辆路线模型：用于解决一个起始点、多个终点的货 物运输中如何降低物流作业费用，并保证服务质量的 问题，包括决定使用多少辆车，每辆车的路线等。 2 )网络物流模型：用于解决寻求最有效的分配货物路径 问题，也就是物流网点布局问题。 3 )分配集合模型：可以根据各个要素的相似点把同一层 上的所有或部分要素分为几个组，用以解决确定服务 范围和销售市场范围等问题。 4 )设施定位模型：用于确定一个或多个设施的位置。在 物流系统中，仓库和运输线共同组成了物流网络，仓 库处于网络的节点上，节点决定着线路，如何根据供 求的实际需要并结合经济效益等原则，在既定区域内 设立多少个仓库，每个仓库的位置，每个仓库的规模， 以及仓库之间的物流关系等问题，运用此模型均能很 容易地得到解决。 g i s 还可用于设备的配置和管理方面，如各种物流设备的数量 匹 x 北京交通火学硕士学位论文 第三章物流配送路径优化问题的数学描述 3 1t s p 问题的数学描述 旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简称t s p ) 是著 名的组合优化问题，自1 9 3 2 年由k m e n g e r 提出后，引起了许多专 家学者的兴趣，产生了各种各样的求解方法，但对于大规模的t s p ， 无一能行之有效的产生全局最优解。 一般t s p 问题可以描述起来十分简单，即一个旅行商通过全部 1 个城市一次且仅一次的最短旅行线路。该问题可以用图g = ( v ，a ) 表示，其中v 为要访问的城市集合，彳= ( f ，川f ，矿，且f _ ， 是连 接其中任意两个城市弧的集合；c 。表示城市i 和城市j 间的距离。 为了说明问题方便，设城市o 为旅行商出发和返回的城市，定义： i1 ，若弧f ，在旅行回路上 。f 一1 0 ，否则 则其数学模型可表示为 ，一i ，一1 m i n z = 勺勤 ( 2 一1 ) ，：o = 0 ，一l s t 勤= 1 ，= o k ，f 一1 ( 2 2 ) f = 0 ，一1 勘= l ，f = o ，1 ，一1 ( 2 3 ) 其中式( 2 1 ) 表示路径最短的目标函数，式( 2 2 ) ，( 2 3 ) 约束 每个节点被访问且仅被访问一次。 t s p 的每个可行解都是1 个城市的一个全排列，解的个数是 第三章物流配送路径优化问题的数学描述 ( 卜1 ) ! ，解的规模随着城市数的增加指数增长，出现组合爆炸现 象。 因此，t s p 问题是典型的n p 难题，研究它的重要意义在于所有 的n p 类问题都等价于t s p 。t s p 已成为组合优化中的一个标准问题， 人们每提出一种新的寻优方法，总是力图用t s p 来检验。另外各种 车辆路径优化问题都是t s p 的变形。 3 2v r p 问题的数学描述 车辆路径问题( v e h i c l er o u t i n gp m b l e m ，v r p ) 由d a n t z i g 于 1 9 5 9 年提出，属于典型的复杂组合优化问题，该问题可以看做是 两类经典的组合优化问题的结合一旅行商问题( t s p ) 和装箱问题 ( b i np a c k i n gp r o b l e m ，b p p ) 。 由于v r p 问题是t s p 问题的变形，因此v r p 问题也是n 王，难 问题，当问题规模增大时也会出现组合爆炸现象，很难求其精确解。 一般v r p 问题可描述为：用于送货的若干辆相同型号的车从 配送中心出发，到不同地理位置的客户那里去送货，然后返回配送 中心，要求每辆车只能出发一次，任何一个客户有且只能有一辆车 访问，并且所配送的货物不能超过车辆的载重量，求一种配送方案 使得配送总成本最少。 一般v r p 问题在数学上可描述为【”】： 令g = ( v ，e ) 为一无向图，其中y = f v ，l f _ 0 ，1 ，2 ，一l 表示顶 点集，e = ( v ，v 川v ，v ，矿，f ) 为边集。此无向图有n 个顶点， 其中顶点v ，v ：v 。表示客户，形成客户集合c ，有ccy ，表 示配送中心。 每条边( v ，) 都具有属性值c 。其中c 。表示从点i 到点j 的 运输成本，并且c l j _ c 0 du ，其中c 。表示单位距离费用，这里不妨 取值l ，d 表示v v 。两点之间的距离。客户i 的需求量为d 。 配送中心有m 辆相同型号的车辆，记为车辆集 第三章物流配送路径优化问题的数学描述 3 3 起终点固定的v r p 问题的数学描述 本文研究的是一类特殊的v r p 问题，它不同于传统的t s p 与v r p 的地方在于，传统的v r p 问题强调是车辆从起点出发最后再回到起 点而形成闭合的线路的最优路径，比较适合于有配送中心的车辆优 化调度问题。 本文的v r p 问题可以描述为，有一辆车从起点出发经过途中所 有的节点到达终点的最短路径，在传统t s p 问题中各个节点的地位 是等同的，但在起终点固定的v r p 问题中存在两类不同的节点：一 类为起点、终点，另一类为途中的各个节点，因此在算法实现时应 予这两类不同的点以不同的考虑，而不能像t s p 中那样对各节点采 用同样的处理。 起终点固定的v r p 问题是城市交通中常遇到的一类问题，如单 位班车的线路选择问题、货运公司从车场出发到各个地点进行装货 最后将收集的货物送到指定地点如码头、车站等。有统计数字表明， 这类运输问题在城市交通中所占的比例越来越大，因此研究起终点 固定的v r p 问题对解决这类 送过程中都采用g i s 技术，并且获得了巨大的成功【35 1 。 国内目前己有一些学者做过gis在交通道路规划中研究硝岗： 毽。葡浦凇簿建法憾旧性竖赫笼奠鼙艮戢淫雨惦际。博t i 邵蓬的集金氇时篓至等譬蛙蠢砖塑鱼釜蠹雾矽踅荤透露y ，且f 是连接 其中任意两个节点的弧的集合，c 表示节点i 和节点j间的距离， 一辆车从起点出发要求访问其余所有节点到达终点，求总路 程最短的一条路径。定义：i 1，车辆从f点行驶到，点 北京交通入学硕+ 学位论文 m i n z = c f 嘞 扛0j = 0 h 一】 s t = l ，- ，= o ，1 ，n l - 0 h 一1 z 口= 1 ，f = o ，l ，n 一1 ：o x 叽卜l = 0 z ，= o ，= 0 ，1 n 一1 ( 2 1 3 ) ( 2 一1 4 ) ( 2 1 5 ) ( 2 1 6 ) ( 2 1 7 ) 其中式( 2 一1 3 ) 表示路径最短的目标函数，式( 2 1 4 ) ，( 2 1 5 ) 约 束每个节点被访问且仅被访问一次，式( 2 16 ) 约束车辆不能从起点 直接到达终点，式( 2 1 7 ) 约束车辆到达终点后不能再继续行进，因 此所有这些约束条件共同保证了车辆只能从起点出发，终点结束经 过其余中间节点一次且仅一次。 可见起终点固定的v r p 问题与传统的t s p 问题是不同的，在传 统的t s p 问题中，求的是从出发点经过所有节点一次且仅一次回到 出发点的一条闭合线路的最短路径，t s p 中各节点的地位是等同 的，因为如果找到了从某一点出发经过所有其他节点回到出发点的 最短路径，那么在这条闭合路径上任何一点为出发点经过所有其它 节点返回出发点的最短路径都应该是同一条路径，例如一条有十个 节点的网络，节点编号为o ，l ，2 ，3 ，4 ，5 ，6 ，7 ，8 ，9 假如旅 行商从o 点出发找到了一条最短路径为f 0 ，3 ，7 ，8 ，2 ，l ，9 ，5 ，4 ，6 ，o 那么若他从2 点出发必有最短路径为 2 ，1 ，9 ，5 ，4 ，6 ，o ，3 ，7 ，8 ) ，和 ( 如果网络为对称网络) 2 ，8 ，7 ，3 ，o ，6 ，4 ，5 ，9 ，l ，2 ) 。观察发现这 些路径的长度都是相同的，因此是同一条路径。 而在起终点固定的v r p 问题中存在两类不同的点，一类为起点、 终点，另一类为要求途径的各个节点。假设车辆从起点出发到达终 点的最短路径为 o ，3 ，6 ，2 ，4 ，5 ，7 ，8 ，1 ，9 ，如果网络为对称网络则 只有 9 ，1 ，8 ，7 ，5 ，4 ，2 ，6 ，3 ，o 为与最短路径等同的路径，即车辆从 第三章物流配送路径优化问题的数学描述 终点出发经过途中所有节点返回起点的最短路径，因此可以认为在 起终点固定的v r p 问题中起点和终点的地位是等同的。因此在设计 起终点固定的v r p 问题算法时不能完全按照求解t s p 时的方法设计 算法，要对不同类型的节点以不同的考虑。 第四章基于遗传算法的v r p 问题求解方法 4 1 2 遗传算法的国内研究现状 现在g a 的典型应用领域有：函数优化、t s p 、v r p 、模式识别、 v l s i 电路布置设计问题、煤气管道布局问题、生产系统中的实时 控制问题、图着色问题、人工神经网络优化问题以及车问作业调度 问题等。 关伟等借鉴g a 对t s p 问题的研究，针对问题特性利用g a 求解 了起终点固定的货物配送问题，简称s t t s p 问题【4 9 】；肖美华等将 g a 与模拟退火算法结合来求解布局问题【5 0 】；刘铁男等通过在g a 中 引入局部搜索技术提出了一种新型混合算法，并应用马尔克夫链理 论证明了其收敛性刚；姜大立等利用g a 求解了一般v r p 问题，并 对染色体进行了可行化影射【52 】；h 雷等提出了一种改进型遗传算 法，利用此算法求解了一般v r p 问题，并与简单遗传算法进行了比 较【5 3 】；陈廷等将g a 应用于飞行管理问题的求解中，得到了最优的 飞行管理方案 5 4 】；丁建立等将遗传算法与蚂蚁算法进行融合来求 解t s p 问题，先利用g a 生成初始信息素，然后利用蚂蚁算法求解 最短路径【”】，杨晓华等提出了蚁群加速遗传算法，应用它来解决 水环境优化问题p “。 4 2 遗传算法的基本原理 4 2 1 遗传算法的基本思想 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是一种有效地解决最优化 问题的方法。它最先是由j o h nh o l l a n d 于1 9 7 5 年提出来的，是模拟 达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。其思想 源于生物遗传学和适者生存的自然规律，是具有“生存+ 检测”的 迭代过程的搜索算法。g a 以一种群体中的所有个体为对象，并利用 随机化技术指导一个被编码的参数空间进行高度搜索。其中，选择、 第四章基于遗传算法的冲问题求解方法 的个体，选择实现了达尔文的适者生存原则。根据群体中每个个体 的适应值，从中选择具有最好的个体作为父代重新繁殖下一代群 体。 交叉：杂交或交叉是两个染色体之间随机交换信息的一种机制。 以事先给定的杂交概率p c 在选择出的个体中任意选择两个个体进 行杂交运算或重组运算，产生两个新的个体，重复此过程直到所有 要求杂交的个体杂交完毕。交叉操作是g a 中最主要的遗传操作。通 过交叉操作可以得到新一代个体，新个体结合了其父辈个体的特 性。交叉体现了信息交换的思想。 变异：变异首先在群体中随机选择一个个体，对于选中的个体以 一定的概率随机的改变串结构数据中某个串的值。同生物界一样， g a 中发生变异的概率很低，通常取值在0 0 0 卜o 0 1 之间。变异为新 个体的产生提供了机会。根据需要可以以事先给定的变异概率p 。 在最好的个体中选择若干个体，并按一定的策略对选中的个体进行 变异运算。变异运算增加了g a 找到最优解的能力。 检验停机条件，若满足收敛条件或固定迭代次数则停机：若不满 足条件则转重新进行进化过程。每一次进化过程就产生新一代的 群体。群体内个体所表示的解通过进化最终达到最优解。 实际上，g a 中有遗传( 交叉和变异) 和进化( 选择) 两类运算。 北京交通火学硕士学位论文 ( 1 ) 拒绝策略 拒绝策略抛弃进化过程中产生的不可行的染色体，这是g a 中普 遍的做法。当可行的搜索空间是凸的且为整个搜索空间的适当的一 部分时，这种做法是有效的，然而这样的条件也是比较苛刻的。例 如对许多约束优化条件初始种群可能是由非可行染色体构成的，这 就需要对他们进行修补。对于某些系统，允许跨过不可性染色体使 用修复往往更能达到最优解。 ( 2 ) 修复策略 修复染色体是对不可行染色体采用修复程序使之变为可行的。 对于许多组合优化问题，构造修复程序比较容易。己经证明，对于 一个有多个不连通可行集的约束优化问题，修复策略在速度和计算 性能上都远胜于其他策略。但是该方法的缺点是它对问题本身的依 赖性，对于每个具体问题必须涉及专门的修复程序，而对于某些问 题，修复过程本身比原问题的求解更复杂。 ( 3 ) 改进遗传子策略 解决可行性问题的一个合理办法是涉及针对问题的表达式，以 及专门的遗传算子来维持染色体的可行性。许多领域的实际工作者 采用专门的问题表达方式和遗传算子构成了非常成功的g a ，这是一 个非常普遍的趋势。但是该方法遗传搜索受到了可行域的限制。 ( 4 ) 惩罚策略 上面的三种策略的共同优点是不会产生不可行解，缺点是无法 考虑可行域外的点。对于约束严格问题，不可解在种群中占的比例 很大，这样将搜索限制在可行域内就很难找到可行届。惩罚策略就 是在遗传搜索中考虑不可行解的技术。构造带有惩罚项的适值函数 一般有两种，一种是采用加法形式： v a l ( x ) = f ( x ) + p ( x ) 其中，x 代表染色体，f ( x ) 是问题的目标函数；p ( x ) 是惩罚项。 对于极大化问题， 第四章基于遗传算法的v r p 问题求解方法 f p ( x ) = o 若x 可行 l p ( x ) o 其他 对于极小化问题，则取： i p ( z ) = o ，若x 可行 l p ( x ) o ，其他 另一种是乘法形式： v a l ( x ) = f ( x ) 木p ( x ) 此时，对于极大化问题，则取 i p ( x ) = 1 ，若z 可行 【o s p ( 工) - - l ，其他 4 2 3 遗传算法的特点 遗传算法是以决策变量的编码作为运算对象。在优化过程中借 鉴生物学中染色体和基因等概念，模拟自然界中生物的遗传和 进化等机理，应用遗传操作，求解无数值概念或很难有数值概念 的优化问题； 遗传算法直接以目标函数作为搜索信息。它仅使用由目标函数 变换来的适应度函数值就可确定进一步搜索的方向和范围，而 不需要目标函数的导数值等信息： 遗传算法同时在多点进行信息搜索，具有天生的并行性，由多个 个体组成一个初始群体开始搜索，对群体进行选择、交叉、变异 等运算，产生出新一代的群体，继续搜索； 遗传算法使用概率搜索技术。它属于一种自适应概率搜索技术， 其选择、交叉、变异等运算都是以一定的概率进行的，增加了其 搜索过程的灵活性。实践和理论证明了在一定条件下遗传算法 第四章基于遗传算法的v r p 问题求解方法 s t e p 2 ：设景b s e l e c t e d o = t r u e ，置第一点编号a r r y 0 = 0 ， 剩余待编节点数l e f t = n 一2 s t e p 3 ：设置待编点号j = 1 s t e p 4 ：判断1 e f t 是否为0 ，如果是则转s t e p 8 。否则产生一 个1 到l e f t 的随机数r a n d o m 。 s t e p 5 ：从被选标志数组b s e l e c t e d 中找到第r a n d o m 个 b s e l e c t e d k = f a l s e s t e p 6 ：置a r r y j = k s t e p 7 ：准备编下一个点，置j 1 e f t 一1 转s t e p 4 s t e p 8 ：置最后一点a r r y n 一1 = n 一1 重复执行以上步骤m 次，就可以得到群体规模为m 的随机染色 体编码。 初始群体形成框图如图4 1 北京交通火学硕士学位论文 s t e p 4 ：将f a t h e r 中r 1 至r 2 之间的染色体片断作为c h 订d 2 继o 点之后起始片断。 s t e d 5 ：顺序将m o t h e r 中没有在c h i l d 2 中出现的点编号插入 到c h i l d 2 中形成子代染色体二。 例如： f a t h e r ：0l1 453 l26 m o t h e r ：03254 l16 其中实线所画区域为匹配区域，仅交叉操作后得到的子代为 c h i l d l ：o2 54 【 l36 c h i l d 2 ：o4 53 216 另外交叉算子是受交叉概率p c 限制的，在进行交叉之前需要先 产生一个在0 到1 之间的随机小数p ，只有p m 爿。能对双亲染色体 进行交叉操作，为了保证大多数双亲都能进行交叉操作来产生新个 体保证遗传操作的不断进行m 一般取得较大，目前常用的参数范 围为p c = 0 5 1 o 。 变异算子 变异算子也是遗传算法中常用的算子之一，但较交叉算子要次 要一些，引入交叉算子的目的是要保持群体的多样性，体现了自然 选择中的基因突变。变异操作可以减少遗传算法快速收敛于局部最 优解的概率。对于起终点固定的v r p 问题由于起点o 和终点n 一1 在染色体中的位置要保持不变，因此在设计变异算子时要考虑到此 问题，防止变异后产生无效解的情况发生。设0 1 d 为变异操作之前 的染色体，n e w 为变异之后的染色体，则变异操作的步骤可以描述 为： s t e p l ：产生随机数1 r l n 一2 ，l r 2 n 一2 且r 1 r 2 s t e p 2 ：交换o l d 中位置为r l 和r 2 所对应的节点编号 第四章基于遗传算法的v i 心问题求解方法 s t e p 3 ：将o l d 赋给n e w 得到新染色体n e 例如某个体0 1 d 编码为01 546 237 ，其变异过程如下 变异前：ol546237 变异后0 1 当7 变异后得到个体n e w 编码为o134625 7 适应度计算 本算法中取适应度函数f = 1 0 0 0 o 木f f d ，其中f f = 瑟，1 c 为染色体长度这里f 不单纯是d 的倒数，而是其倒数的倍数，这样f 的值就不致于过小，影响我们观察实验结果，d 是由译码得出的路 径长度。 4 3 3 算法步骤 本文设计的求解起终点固定的v r p 问题的遗传算法执行步骤如下： s e t p l ：根据节点坐标计算路径长度矩阵 s t e p 2 ：根据群体规模构造初始群体 s t e p 3 ：通过适应度函数计算个体的适应度 s t e p 4 ：采用轮盘赌方法选择两个待交叉的双亲染色体 s t e p 5 ：采用交叉算子对选择的双亲染色体进行交叉操作产生 两个子代染色体 s t e p 6 ：采用变异算子对两个子代染色体进行变异操作 s t e p 7 ：判断生成的子代染色体的数量是否达到群体规模，如 果未达到群体规模，则转s t e p 4 ，否则转s t e p 8 s t e p 8 ：采用最优保存策略用生成的子群体更新父群体 s t e p 9 ：判断是否达到迭代次数，如果未达到，则转s t e p 3 ，否 第五章基于蚁群算法的v r p 问题求解方法 第五章基于蚁群算法的v r p 求解方法 5 1 蚁群算法的国内外研究现状【3 8 】【5 9 】 5 1 1 蚁群算法的国外研究现状 蚁群算法( a n tc o l o n ys y s t e m ) 是一种源于自然界中生物世界 的新的仿生类随机型搜索算法，它吸收了昆虫王国中蚂蚁的行为特 性，通过其内在的搜索机制，在一系列困难的组合优化问题求解中 取得了成效。最早是由意大利学者d o r i g o 、m a l l i e z z o 、c o n o r i n i 等 人于1 9 9 1 年提出的，称之为蚁群算法，并应用该算法求解t s p 问 题、分配问题、j o b s h o p 调度问题，取得了较好的结果。受其影响， 蚁群算法模型逐渐引起了其它研究者的注意，将蚁群算法的思想应 用到各自研究领域，取得了大量的研究成果。 d o r i g o 等人提出基本蚁群算法后不久，又提出一种更一般的 蚁群算法，并称之为a n t qs y s t e m 。在该算法中，个体的移动规 则不只是根据转移概率进行转移，还包括对以前找到的最优路径的 利用。s t u t z l e 提出m m a s ( m a ) 【m i na n ts y s t 锄) ，其基本思想是仅 让每一代中的最好个体所走路径上的信息量作调整，以加快收敛速 度，这样便容易出现停滞现象，为了避免这一点，用k 分支因子作 为衡量群体多样性的一个指标，当k 分支因子低于某一数值时，便 对各