车辆路径问题优化算法

《车辆路径问题优化算法》由会员分享，可在线阅读，更多相关《车辆路径问题优化算法（9页珍藏版）》请在金锄头文库上搜索。

1、车辆路径问题优化算法美国物流管理学会（Council of Logistics Management , CLM）对物流所作的定 义为： “为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息， 从其起运点至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制 过程。”而有关资料显示，物流配送过程 （包含仓储、分拣、运输等 ）的成本构成中，运输 成本占到 52% 之多。因此，如何在满足客户适当满意度的前提下，将配送的运 输成本合理地降低，成为一个紧迫而重要的研究课题，车辆路径问题正是基于这 一需求而产生的。2.1 车辆路径问题的定义 车辆路径问题可以描述为：给定一组有容量限制的

2、车辆的集合、一个物流中心（或 供货地）、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所 有的客户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、 行驶里程限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、 使用车辆数尽量少等）。 4 因此研究车辆的路径问题，就是要研究如何安排运输车辆的行驶路线， 使运输车 辆依照最短的行驶路径或最短的时间费用， 依次服务于每个客户后返回起点，总 的运输成本实现最小。车辆路径问题已被证明是 NP-Hard 问题，因此求解比较困难。然而，由于其在 现实生活中应用非常广泛，使得它无论在理论上还是在实践上都有极大的研究价 值。P

3、enousal Machado 等人5 指出车辆路径问题 （vehicle routing problem ，简称 VRP）是一个复杂的组合优化问题，是古老的旅行商问题和背包问题的综合。实 际上，车辆路径问题通常可被分解或转化成一个或几个已经研究过的基本问题， 再采用相应比较成熟的基本理论和方法，以得到最优解或满意解。这些与车辆路径问题相关的常用基本问题有； 旅行商问题、运输问题、背包问题、 最短路问题、最小费用最大流问题、中国邮路问题、指派问题等。旅行商问题可被描述为：一个推销员欲到 n 个城市推销商品，每 2 个城市之间的 距离是已知的。如何选择一条路径使推销员依次又不重复地走遍每个城市后

4、， 回 到起点且所走的路径最短。运输问题关心的是（确实的或是比喻的）以最低的总配送成本把供应中心（称为 出发地，sources）的任何产品运送到每一个接受中心（称为目的地， destinations ）。运输问题需要的数据仅仅是供应量、需求量和单位成本。 背包问题是指有一只固定容量的背包和若干体积、 重量不等的物品，背包的容量 不允许装下这所有的物品，那么如何选择适当的物品装入背包，使得背包的装载 量（所装物品的重量之和）最大。最短路径问题解决的是在一个网络中， 如何寻找两点之间的最短路径。这两点之 间通常没有直接的通路可达，但可经由若干中间结点相通。最小费用流问题主要解决如何以最小成本在一个

5、配送网络中运输货物。 最小费用 流问题又称为网络配送问题。最大流问题和最小费用流问题一样，也与网络中的流有关。但是它们的目标不同， 最大流问题不是使得流的成本最小化， 而是寻找一个流的方案，使得通过网络的 中国邮路问题是由我国管梅谷同志在 1962 年首先提出的，它可描述为：一个邮 递员负责某一个地区的信件投递。 每天要从邮局出发， 走遍该地区所有的街道再 返回邮局，问应该怎样安排送信路线可以使所走的路程最短。指派问题解决将 n 件工作安排给 m 个人完成的问题。已知不同人完成不同工作 的效率(或成本)不同，指派问题要求以最高的效率(或最小的人工成本)完成 工作的安排。2.2 车辆路径问题的分

6、类 车辆路径问题当不考虑时间要求， 仅根据空间位置安排路线时称为车辆路线安排 问题(Vehicle Routing Problem 简记VRP)；当考虑时间要求安排路线时称为车辆 调度问题(Vehicle Scheduling Problem 简记VSP);当同时考虑空间位置和时间要 求时称为路线和调度混合问题 6 。车辆调度冋题即有时间要求的车辆路径冋题(VSP)又被称为带时间窗的车辆路 径问题(Vehicle Routing Problem with Time Windows ,简记为 VRPTW)。VRPTW 是在VRP的基础上增加了客户要求访问的时间窗口，是一般车辆路径问题的扩 展。其

7、简单的描述如下： 用于服务的若干车辆从站点出发， 为处在不同地理位置、 具有不同货物需求和不同服务时间窗要求的所有顾客提供服务，然后返回站点， 其中为每个顾客仅提供一次服务。 其目标是在时间窗内为顾客提供服务时， 使车 辆的行驶时间和等待时间之和最短。根据时间约束的严格与否， 带时间窗的车辆路径问题被分为两类： 软时间窗车辆 路径问题和硬时间窗车辆路径问题。 软时间窗车辆路径问题要求配送车辆尽可能 在时间窗内到达访问，否则将给予一定的惩罚。该惩罚包括两部分：(1)车辆在要求的最早到达时间之前到达，必须在任务点处等待而损失的成本；(2)车辆在要求的最迟到达时间之后到达， 必须付给客户预先约定的罚

8、金。 而硬时间窗车辆 路径问题则要求必须在时间窗内到达访问，否则服务被拒绝。Koskosidis 等人( 1992) 7 指出，软时间窗模式比硬时间窗更具优势是因为： 第一、软时窗模式较传统硬时窗模式更为一般化， 且软时窗的求解演算法较具弹 性(因限制式较少)。而且若要提高准点服务频率，只需适当的提高惩罚成本即 可；第二、在现实世界中，时窗限制大多属于软时窗限制。配送服务商没有在约 定的时间内送达顾客端， 并非一定不可服务， 而是可以服务但必须付出双方约定 的惩罚成本。 有较高准点送达要求的顾客的惩罚成本大， 不准时但是在可以忍受 的时间内送达的顾客的惩罚成本相对小些； 第三、软时窗模式可以有

9、效的反应配 送商在车队营运成本、 规模和服务水准两者之间的关系； 第四、软时窗模式可以 发现硬时窗模式无法找到的可行解。 特别是在小规模车队服务多数顾客以及严苛 的时间限制条件状况下。 在上述的情形得到软时窗限制下的可行解后， 可再调整 时间窗让违反时间窗的情况得到改善。车辆路径问题还有确定性 (Deterministic) 模式和随机性 (Stochastic) 模式之分8 。 确定性模式假设：其一、客户的数目在配送开始前是已知且固定的；其二、客户 的需求量在配送开始前是已知且固定的； 其三、两点之间的旅行时间仅取决于这 两点之间的距离。 而随机性模式不要求以上一个或多个假设。 随机性模式又

10、称为 随机需求车辆路径问题。如果考虑装卸工人的调配问题， 则车辆路径问题就称为带装卸工调配的车辆路径 问题。带装卸工调配的车辆路径问题描述如下 9:设配送中心有n辆货车都要 向b个客户装卸货物。配送中心可以安排 位装卸工跟着车辆，也可以安排位装 卸工固定在客户 处。已知在客户 处需要的装卸工人数是 ，配送中心应该考虑 如何调配装卸工，使总的装卸工人数最少。除了以上分类， 车辆路径问题还可以按任务特征分为装货问题、 卸货问题及装卸 混合问题； 按任务性质分为对弧服务问题 （如中国邮递员问题） 和对点服务问题 （如旅行商问题）以及混合服务问题（如校车路线安排问题）；按车辆载货状况 分为满载问题和非

11、满载问题； 按车场数目分为单车场问题和多车场问题； 按车辆 类型数分为单车型问题和多车型问题； 按车辆对车场的所属关系分为车辆开放问 题（车辆可不返回车场）和车辆封闭问题（车辆必须返回车场）；按优化目标可 分为单目标问题和多目标问题，等等。针对上述不同的分类方法，车辆路径问题的模型构造及求解算法有很大差别。2.3 车辆路径问题的构成要素 物流配送车辆路径问题的构成因素主要包括货物、车辆、配送中心、客户、运输 网络、约束条件和目标函数等要素 10 。2.3.1 货物 货物是配送的对象。可将每个客户需求（或供应）的货物看成一批货物。每批货 物包括品名、包装、重量、体积、要求送到（或取走）的时间和地

12、点、能否分批 配送等属性。货物的品名和包装， 是选用配送车辆的类型以及决定该批货物能否 与其他货物装在同一车辆内的依据。 例如，一些货物因性质特殊需要使用专用车 辆装运；而一些货物虽然性质特殊， 但由于包装条件很好， 故也能与其它货物装 在同一车辆内。 另外， 货物的重量和体积也是进行车辆装载决策的重要依据。 当 某个客户的需求量 （供应量） 的货物的重量或体积超过车辆的最大装载量或体积 时，则对该客户需要采用多台车辆进行配送。2.3.2 车辆 车辆是货物的运载工具，其主要包括 : 车辆的类型、装载量、一次配送的最大行 驶距离、配送前以及完成任务后车辆的停放位置等。 其一、车辆的类型有通用车辆

13、和专用车辆之分， 通用车辆适于运载大多数普通货 物，专用车辆适于载运一些性质特殊的货物。 其二、车辆的装载量是指车辆的最大装载重量和最大装载容积， 是进行车辆装载 决策的依据。在某个配送系统中，车辆的装载量可以相同也可以不同。 其三、对每台车辆一次配送的行驶距离的要求可以分为以下几种情况 : 第一、无 距离限制 ; 第二、有距离限制 ; 第三、有距离限制，但可以不遵守。 其四、车辆在配送前可以是停放在某个停车场、 配送中心或者是客户所在地。 完 成任务后，其停放位置一般可以分为以下几种情形 : 一是必须返回出发点 ; 二是 必须某个停车场或配送中心 ; 三是可返回任意停车场 ; 四是可停放在任

14、何地点。2.3.3 配送中心 配送中心是从事货物配备 （集货、加工、拣选、配货 ） 和组织对客户的送货，以提 高水平实现销售或供应的现代流通设施。 在某个配送系统中， 配送中心的个数可 以是一个也可以是多个， 这涉及到配送网络问题， 如在某些配送网点多而且配送 范围广的情形下， 往往采用多级配送中心进行配送， 通过一级配送中心配送到下 一级配送中心再配送， 在多个二级配送中心下， 究竟由哪个配送中心配送， 这涉 及到配送的优化问题。其配送示意图见图 2-1:图 2-1 分级配送示意图2.3.4 客户 也称为用户，包括各盆景展览馆、陈列中心、公司、家庭用户等。单个客户一次 所需的盆景数量可能大于

15、盆景配送车某车辆的最大装载量， 也可能小于该车辆的 最大装载量。 而该系统全部客户的货物需求 （或供应）总量可能超过全部车辆的 总装载量。在以上情形下，当货物一次性需求（或供应）总量超过运输能力时， 需要多次（多辆）分批配送；当货物一次性需求（或供应）量小于某车辆的最大 装载量时，在可能的情况下，应进行货物配载。客户的需求（或供应）盆景的时间，是指要求盆景送达（或取走）的时间，对配 送时间的要求可分为以下几种情况 : 第一、无时间限制；第二、要求在指定的时 间区间（也称为时间窗）内完成运输任务；第三、有时间限制，但可以不遵守， 只是不遵守时要给予一定的惩罚。2.3.5 运输网络 运输网络是由顶

16、点（指配送中心、客户、停车场等）、无向边和有向弧组成 的，边、弧的属性包括方向、权值和交通流量限制等。运输网络中边或弧的权值 可以表示距离、 时间或费用。边或弧的权值变化可分为以下几种情况 : 一是固定， 即不随时间和车辆的不同而变化；二是随时间而变化；三是随车辆不同而变化； 四是既随时间不同而变化，又随车辆不同而变化。对运输网络权值间的关系可以要求其满足三角不等式，即两边之和大于第三边。 也可以不加限制。运输网络见示意图 2-2.图 2-2 运输网络示意图 对运输网络中顶点、边或弧的交通流量要求分为以下几种 : 其一、交通流量随时 间不同而变化 ; 其二、边、弧限制，即每条边、 弧上同时行驶的车辆数有限制 ; 其 三、顶点限制，即每个顶点上同时装、卸的车辆数有限；其四、边、弧、顶点都 有限制。2.3.6 约束条件 通常说来， 物流配送车辆路径问题应满足的约束条件主要包括： 第一，满足所有 客户对货物品种、规格、数量的要求；