搜索
车辆路径问题优化算法美国物流管理学会(CouncilofLogisticsManagement，CLM)对物流所作的定义为：“为符合顾客的需要，对原料、制造过程中的存货与制成品以及相关信息，从其起运点至最终消费点之间，做出的追求效率与成本效果的计划、执行与控制过程。”而有关资料显示，物流配送过程(包含仓储、分拣、运输等)的成本构成中，运输成本占到52%之多。因此，如何在满足客户适当满意度的前提下，将配送的运输成本合理地降低，成为一个紧迫而重要的研究课题，车辆路径问题正是基于这一需求而产生的。2.1车辆路径问题的定义车辆路径问题可以描述为：给定一组有容量限制的车辆的集合、一个物流中心（或供货地）、若干有供货需求的客户，组织适当的行车路线，使车辆有序地通过所有的客户，在满足一定的约束条件（如需求量、服务时间限制、车辆容量限制、行驶里程限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。[4]因此研究车辆的路径问题，就是要研究如何安排运输车辆的行驶路线，使运输车辆依照最短的行驶路径或最短的时间费用，依次服务于每个客户后返回起点，总的运输成本实现最小。车辆路径问题已被证明是NP-Hard问题，因此求解比较困难。然而，由于其在现实生活中应用非常广泛，使得它无论在理论上还是在实践上都有极大的研究价值。PenousalMachado等人[5]指出车辆路径问题(vehicleroutingproblem，简称VRP)是一个复杂的组合优化问题，是古老的旅行商问题和背包问题的综合。实际上，车辆路径问题通常可被分解或转化成一个或几个已经研究过的基本问题，再采用相应比较成熟的基本理论和方法，以得到最优解或满意解。这些与车辆路径问题相关的常用基本问题有；旅行商问题、运输问题、背包问题、最短路问题、最小费用最大流问题、中国邮路问题、指派问题等。旅行商问题可被描述为：一个推销员欲到n个城市推销商品，每2个城市之间的距离是已知的。如何选择一条路径使推销员依次又不重复地走遍每个城市后，回到起点且所走的路径最短。运输问题关心的是（确实的或是比喻的）以最低的总配送成本把供应中心（称为出发地，sources）的任何产品运送到每一个接受中心（称为目的地，destinations）。运输问题需要的数据仅仅是供应量、需求量和单位成本。背包问题是指有一只固定容量的背包和若干体积、重量不等的物品，背包的容量不允许装下这所有的物品，那么如何选择适当的物品装入背包，使得背包的装载量（所装物品的重量之和）最大。最短路径问题解决的是在一个网络中，如何寻找两点之间的最短路径。这两点之间通常没有直接的通路可达，但可经由若干中间结点相通。最小费用流问题主要解决如何以最小成本在一个配送网络中运输货物。最小费用流问题又称为网络配送问题。最大流问题和最小费用流问题一样，也与网络中的流有关。但是它们的目标不同，最大流问题不是使得流的成本最小化，而是寻找一个流的方案，使得通过网络的流量最大。中国邮路问题是由我国管梅谷同志在1962年首先提出的，它可描述为：一个邮递员负责某一个地区的信件投递。每天要从邮局出发，走遍该地区所有的街道再返回邮局，问应该怎样安排送信路线可以使所走的路程最短。指派问题解决将n件工作安排给m个人完成的问题。已知不同人完成不同工作的效率（或成本）不同，指派问题要求以最高的效率（或最小的人工成本）完成工作的安排。2.2车辆路径问题的分类车辆路径问题当不考虑时间要求，仅根据空间位置安排路线时称为车辆路线安排问题(VehicleRoutingProblem简记VRP)；当考虑时间要求安排路线时称为车辆调度问题(VehicleSchedulingProblem简记VSP)；当同时考虑空间位置和时间要求时称为路线和调度混合问题[6]。车辆调度问题即有时间要求的车辆路径问题（VSP）又被称为带时间窗的车辆路径问题（VehicleRoutingProblemwithTimeWindows，简记为VRPTW)。VRPTW是在VRP的基础上增加了客户要求访问的时间窗口，是一般车辆路径问题的扩展。其简单的描述如下：用于服务的若干车辆从站点出发，为处在不同地理位置、具有不同货物需求和不同服务时间窗要求的所有顾客提供服务，然后返回站点，其中为每个顾客仅提供一次服务。其目标是在时间窗内为顾客提供服务时，使车辆的行驶时间和等待时间之和最短。根据时间约束的严格与否，带时间窗的车辆路径问题被分为两类：软时间窗车辆路径问题和硬时间窗车辆路径问题。软时间窗车辆路径问题要求配送车辆尽可能在时间窗内到达访问，否则将给予一定的惩罚。该惩罚包括两部分：(1)车辆在要求的最早到达时间之前到达，必须在任务点处等待而损失的成本；(2)车辆在要求的最迟到达时间之后到达，必须付给客户预先约定的罚金。而硬时间窗车辆路径问题则要求必须在时间窗内到达访问，否则服务被拒绝。Koskosidis等人（1992）[7]指出，软时间窗模式比硬时间窗更具优势是因为：第一、软时窗模式较传统硬时窗模式更为一般化，且软时窗的求解演算法较具弹性（因限制式较少）。而且若要提高准点服务频率，只需适当的提高惩罚成本即可；第二、在现实世界中，时窗限制大多属于软时窗限制。配送服务商没有在约定的时间内送达顾客端，并非一定不可服务，而是可以服务但必须付出双方约定的惩罚成本。有较高准点送达要求的顾客的惩罚成本大，不准时但是在可以忍受的时间内送达的顾客的惩罚成本相对小些；第三、软时窗模式可以有效的反应配送商在车队营运成本、规模和服务水准两者之间的关系；第四、软时窗模式可以发现硬时窗模式无法找到的可行解。特别是在小规模车队服务多数顾客以及严苛的时间限制条件状况下。在上述的情形得到软时窗限制下的可行解后，可再调整时间窗让违反时间窗的情况得到改善。车辆路径问题还有确定性(Deterministic)模式和随机性(Stochastic)模式之分[8]。确定性模式假设：其一、客户的数目在配送开始前是已知且固定的；其二、客户的需求量在配送开始前是已知且固定的；其三、两点之间的旅行时间仅取决于这两点之间的距离。而随机性模式不要求以上一个或多个假设。随机性模式又称为随机需求车辆路径问题。如果考虑装卸工人的调配问题，则车辆路径问题就称为带装卸工调配的车辆路径问题。带装卸工调配的车辆路径问题描述如下[9]：设配送中心有n辆货车都要向b个客户装卸货物。配送中心可以安排位装卸工跟着车辆，也可以安排位装卸工固定在客户处。已知在客户处需要的装卸工人数是，配送中心应该考虑如何调配装卸工，使总的装卸工人数最少。除了以上分类，车辆路径问题还可以按任务特征分为装货问题、卸货问题及装卸混合问题；按任务性质分为对弧服务问题（如中国邮递员问题）和对点服务问题（如旅行商问题）以及混合服务问题（如校车路线安排问题）；按车辆载货状况分为满载问题和非满载问题；按车场数目分为单车场问题和多车场问题；按车辆类型数分为单车型问题和多车型问题；按车辆对车场的所属关系分为车辆开放问题（车辆可不返回车场）和车辆封闭问题（车辆必须返回车场）；按优化目标可分为单目标问题和多目标问题，等等。针对上述不同的分类方法，车辆路径问题的模型构造及求解算法有很大差别。2.3车辆路径问题的构成要素物流配送车辆路径问题的构成因素主要包括货物、车辆、配送中心、客户、运输网络、约束条件和目标函数等要素[10]。2.3.1货物货物是配送的对象。可将每个客户需求（或供应）的货物看成一批货物。每批货物包括品名、包装、重量、体积、要求送到（或取走）的时间和地点、能否分批配送等属性。货物的品名和包装，是选用配送车辆的类型以及决定该批货物能否与其他货物装在同一车辆内的依据。例如，一些货物因性质特殊需要使用专用车辆装运；而一些货物虽然性质特殊，但由于包装条件很好，故也能与其它货物装在同一车辆内。另外，货物的重量和体积也是进行车辆装载决策的重要依据。当某个客户的需求量（供应量）的货物的重量或体积超过车辆的最大装载量或体积时，则对该客户需要采用多台车辆进行配送。2.3.2车辆车辆是货物的运载工具，其主要包括:车辆的类型、装载量、一次配送的最大行驶距离、配送前以及完成任务后车辆的停放位置等。其一、车辆的类型有通用车辆和专用车辆之分，通用车辆适于运载大多数普通货物，专用车辆适于载运一些性质特殊的货物。其二、车辆的装载量是指车辆的最大装载重量和最大装载容积，是进行车辆装载决策的依据。在某个配送系统中，车辆的装载量可以相同也可以不同。其三、对每台车辆一次配送的行驶距离的要求可以分为以下几种情况:第一、无距离限制;第二、有距离限制;第三、有距离限制，但可以不遵守。其四、车辆在配送前可以是停放在某个停车场、配送中心或者是客户所在地。完成任务后，其停放位置一般可以分为以下几种情形:一是必须返回出发点;二是必须某个停车场或配送中心;三是可返回任意停车场;四是可停放在任何地点。2.3.3配送中心配送中心是从事货物配备(集货、加工、拣选、配货)和组织对客户的送货，以提高水平实现销售或供应的现代流通设施。在某个配送系统中，配送中心的个数可以是一个也可以是多个，这涉及到配送网络问题，如在某些配送网点多而且配送范围广的情形下，往往采用多级配送中心进行配送，通过一级配送中心配送到下一级配送中心再配送，在多个二级配送中心下，究竟由哪个配送中心配送，这涉及到配送的优化问题。其配送示意图见图2-1:图2-1分级配送示意图2.3.4客户也称为用户，包括各盆景展览馆、陈列中心、公司、家庭用户等。单个客户一次所需的盆景数量可能大于盆景配送车某车辆的最大装载量，也可能小于该车辆的最大装载量。而该系统全部客户的货物需求（或供应）总量可能超过全部车辆的总装载量。在以上情形下，当货物一次性需求（或供应）总量超过运输能力时，需要多次（多辆）分批配送；当货物一次性需求（或供应）量小于某车辆的最大装载量时，在可能的情况下，应进行货物配载。客户的需求（或供应）盆景的时间，是指要求盆景送达（或取走）的时间，对配送时间的要求可分为以下几种情况:第一、无时间限制；第二、要求在指定的时间区间（也称为时间窗）内完成运输任务；第三、有时间限制，但可以不遵守，只是不遵守时要给予一定的惩罚。2.3.5运输网络运输网络是由顶点（指配送中心、客户、停车场等）、无向边和有向弧组成的，边、弧的属性包括方向、权值和交通流量限制等。运输网络中边或弧的权值可以表示距离、时间或费用。边或弧的权值变化可分为以下几种情况:一是固定，即不随时间和车辆的不同而变化；二是随时间而变化；三是随车辆不同而变化；四是既随时间不同而变化，又随车辆不同而变化。对运输网络权值间的关系可以要求其满足三角不等式，即两边之和大于第三边。也可以不加限制。运输网络见示意图2-2.图2-2运输网络示意图对运输网络中顶点、边或弧的交通流量要求分为以下几种:其一、交通流量随时间不同而变化;其二、边、弧限制，即每条边、弧上同时行驶的车辆数有限制;其三、顶点限制，即每个顶点上同时装、卸的车辆数有限；其四、边、弧、顶点都有限制。2.3.6约束条件通常说来，物流配送车辆路径问题应满足的约束条件主要包括：第一，满足所有客户对货物品种、规格、数量的要求；第二，满足客户对货物发到的时间范围的要求；第三，在允许通行时间进行配送（如有时规定白天不能通行货车等）；第四，车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量；第五，在配送中心现有的运力范围内。2.3.7目标函数对物流配送车辆路径问题，可以只选用一个目标，也可以是多个目标。经常选用的目标函数主要有:第一，配送总里程最短。配送里程与配送车辆的耗油量、磨损程度以及司机疲劳程度等直接相关，它直接决定运输的成本，对配送业务的经济效益有很大影响。由于配送里程计算简便，它是确定配送路线时用得最多的指标。第二，配送车辆的吨位公里数最少。该目标将配送距离与车辆的载重量结合起来考虑，即以所有配送车辆的吨位数（最大载重吨）与其行驶距离的乘积的总和最少为目标。第三，综合费用最低。降低综合费用是实现配送业务经济效益的基本要求。在