车辆路线规划问题概述

车辆路线规划问题（VRP）的主要内容车辆路线优化问题一般可根据空间特性和时间特性分为车辆路线规划问题和车辆调度问题。当不考虑时间要求，仅根据空间位置安排车辆的线路时称为车辆线路或车辆路线规划问题（VRP）。当考虑时间要求安排运输线路时称为车辆调度问题（VSP）。物流配送车辆路线优化问题(VRP)最早是由Dautzig和Ramser于1959年首次提出的，该问题一般定义为:对一系列给定的顾客(取货点或送货点),确定适当的配送车辆行驶路线,使其从配送中心出发，有序地通过它们,最后返回配送中心[14]。并在满足一定的约束条件下(如车辆容量限制、顾客需求量、交发货时间等),达到一定的目标(如路程最短、费用最少等)。由于配送中心每次配送活动一般都面对多个非固定用户,并且这些用户坐落地点各不相同,所以对于它们的配送时间和配送数量也都不尽相同。如果配送中心不进行运输路线的合理规划,往往会出现不合理运输现象,不仅造成运输成本上升,而且导致配送服务水平难以提高,因此经常对配送路线进行规划是大多数配送中心的一项重要工作[12]。3.2.1车辆路线规划问题（VRP）的主要构成构成车辆路线问题的主要因素包括:货物、车辆、物流中心、客户、运输网络、约束条件和目标等。（1）货物。货物是车辆运输的对象，也是构成需求的主要因素。可将每个客户需求(供应)的货物看成一批货物。每批货物都包括品名、包装、重量、体积、要求送到(或取走)的时间和地点、能否分批配送等属性。货物的品名和包装，是选用配送车辆的类型以及决定该批货物能否与其它货物装在同一车辆上的依据。(2）车辆。车辆是货物的运载工具。其主要属性包括：车辆的类型、装载量、一次配送的最大行驶距离、配送前的停放位置及完成任务后的停放位置等。(3）配送中心。配送中心也称为物流基地、物流据点，主要是指进行集货、分货、配货、配装、送货等物流作业的中心、仓库、车站、港口等。在具体的VRP中，配送中心的数量可以是一个或一个以上；配送中心的位置可以是确定的，也可以是不确定的；对于某个物流中心，其供应的货物可能有一种，也可能有多种；供应的货物数量可能能够满足全部客户的需求，也可能仅能满足部分客户的需求。（4）客户即用户。客户的属性包括需求（或供应）货物的数量、需求（或供应）的时间、需求（或供应）货物的次数及对服务的要求等。在VRP中，客户是最主要的因素，客户的性质决定着VRP的规划，客户的需求是VRP中约束条件的主要来源和重点考虑对象。（5）运输网络。运输网络是由顶点（指物流中心、客户、停车场）、无向边和有向弧组成的。边、弧的属性包括方向、权值和交通流量限制等。（6）约束条件。物流VRP应满足的约束条件主要包括：①满足所有客户对货物品种、规格、数量的要求；②满足客户对货物发到时间范围的要求；③在允许通行的时间进行配送(如有时规定白天不能通行货车等)；④车辆在运输过程中的实际载货量不得超过车辆的最大允许装载量，或货物的体积总和不能超过车辆的容积。⑤在物流中心现有运力范围内。（7）最终目标。对物流配送车辆调度问题，可以只选用一个目标，也可以选用多个目标。经常选用的目标主要有:运输总里程最短、综合费用最低、准时性最高、运力利用最合理、消耗最低等。由于VRP难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法.简单启发式方法包括节省法或\o"插入法"插入法、路线内间节点交换法、贪婪法和局部搜索法等方法。节省法或插入法是在求解过程中使用节省成本最大的可行方式构造路线，直到无法节省为止。交换法则是依赖其他方法产生一个起始路线，然后以迭代的方式利用交换改善法减少路线距离，直到不能改善为止。1960年，Clarke和Wright首先提出一种启发式节省法来建立车队配送路线。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的VRP问题。两阶段方法包括先分组后定路线和先定路线后分组两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序；后者则是先将所有的需求点建构成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。1990年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将\o"人工智能"人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。\o"禁忌搜索法"禁忌搜索法（TS）基本上是属于一种人工智能型（AI）的局部搜寻方法，Willard首先将此算法用来求解VRP，随后亦有许多位学者也发表了求解VRP的TS算法。\o"西南交通大学"西南交通大学的袁庆达[等设计了考虑时间窗口和不同车辆类型的禁忌算法，这种算法主要采用GENIUS方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，美国科学家对VRP的模拟退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组。\o"遗传算法"遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法（GA）编码解决VRPTW问题。现在多数学者采用\o"混合策略"混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Bent提出了用\o"遗传算法"遗传算法进行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。Bent和VanHentenryck则首先用\o"模拟退火算法"模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法将运输费用降到最低。总结几种人工智能方法可以看出，TS算法所得到的解最接近最优解，但其运算时间也最长，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能较好的逼近最优解，同时使运算时间大大缩短，所以GA算法能兼顾运算时间和效率两方面，是具有较好的发展前途的方法；SA算法求解速度非常快，也能提供一定程度上的优化方案在求解较小规模问题上具有较好效果。3.2.2车辆路线规划问题（VRP）的主要类型VRP是一大类问题的基本模型，根据附加条件和任务要求的不同，可以构成不同类型的VRP。为更好地了解VRP，现对其分类作详细阐述。（1）按物流中心的数目分，有单物流中心问题（配送系统中仅有一个物流中车辆调度问题)的一般定义为：对一系列装货点和(或)卸货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件下(如货物需求量、发送量、交货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定目标，如路程最短、费用最少、时间尽量少、使用车辆数尽量少等。VRP的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。结合本文研究内容，VRP可具体描述如下：设有一个配送中心仓库，共有K辆货车，车辆容量为Q，有N个网点需要服务，每个网点有其需求量C，车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被服务，顾客需求由一次配送完成，不能违反车辆容量的限制，目的是所有车辆行驶的总距离最小[16]。（2）按客户对货物取(送)时间的要求程度分，可以分为硬时间窗问题（客户要求货物必须在规定的时间窗内送到或取走，不能提前也不能拖后）、软时间窗问题（客户要求将货物尽量在规定的时间窗内送到或取走，但也可以提前或拖后，只不过在提前或拖后时可能会给客户带来一些损失，这时要通过增加补偿费用等方式对配送企业实施一定的惩罚）和混合型时间窗（在系统中有些顾客属于硬时间窗，有些属于软时间窗；对同一顾客，又可能软、硬时间窗混合使用）。（3）按车辆载货状况分，有满载问题(由于客户需求或供应的货物数量大于或等于车辆的载重量，故完成一项配送任务需要一辆或更多的配送车辆，配送车辆需要满载运行)、非满载问题(由于客户需求或供应的货物数量小于车辆载重量，多项配送任务可共用一辆配送车辆，车辆在配送过程中经常处于不满载状态)以及满载和非满载混合问题(由于一部分客户需求或供应的货物数量大于或等于车辆的载重量，而另一部分客户需求或供应的货物数量小于车辆的载重量，造成一些配送车辆需要满载运行，而另一些车辆则经常处于不满载状态)。（4）按配送任务特征分，有纯送货问题(仅考虑从物流中心向客户送货，也称为纯卸问题)或纯取货问题(仅考虑把各客户供应的货物取到物流中心，也称为纯装问题)及取送混合问题(既考虑将客户需求的货物从物流中心送到各个客户，同时考虑将客户供应的货物从客户取回到物流中心，也称为装卸混合问题或集货和送货一体化问题)。为了便于叙述，本文将纯送货或纯取货的物流配送车辆路径问题称为单向物流配送车辆路径问题，而将取送混合的物流配送车辆路径问题称为双向物流配送车辆路径问题。（5）按车辆类型分，有单车型问题(所有配送车辆的载重量相同)和多车型问题(配送车辆的载重量不完全相同)。（6）按车辆对车场的所属关系分，有车辆开放问题(即车辆完成配送任务后可以不返回其发出车场)和车辆封闭问题(车辆完成配送任务后必须返回其车场)。（7）按优化目标数分，有单目标问题(仅考虑一个配送目标)和多目标问题(同时考虑多个配送目标)。（8）按客户和路网的特点分，有静态问题(客户位置、客户数目、客户需求、天气路况等因素是事先确定的)和动态问题(客户数目、客户位置、客户需求、天气路况等因素不是事先确定的，而是随机变化的)。目前研究的车辆路线规划的模型主要有两类，一类为网络图模型，另一类为数学模型。网络图模型的优点是直观性强，容易理解；缺点是对参数的容纳能力有