车辆路线规划问题概述.docVIP

车辆路线规划问题（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难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法.简单启发式方法包括节省法或 HYPERLINK /wiki/%E6%8F%92%E5%85%A5%E6%B3%95 \o 插入法 插入法、路线内间节点交换法、贪婪法和局部有哪些信誉好的足球投注网站法等方法。节省法或插入法是在求解过程中使用节省成本最大的可行方式构造路线，直到无法节省为止。交换法则是依赖其他方法产生一个起始路线，然后以迭代的方式利用交换改善法减少路线距离，直到不能改善为止。1960年，Clarke和Wright首先提出一种启发式节省法来建立车队配送路线。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的VRP问题。 两阶段方法包括先分组后定路线和先定路线后分组两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序；后者则是先将所有的需求点建构成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。1990年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将 HYPERLINK /wiki/%E4%BA%BA%E5%B7%A5%E6%99%BA%E8%83%BD \o 人工智能 人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。 HYPER