第二章 物流配送车辆路径问题

《第二章 物流配送车辆路径问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章物流配送车辆路径问题2.1问题的描述及各组成部分特点2.2车辆路径问题的分类2.3车辆路径问题的研究现状和发展趋势*2.1问题的描述及各组成部分特点配送活动中的配送车辆行驶线路优化确定问题，是近二十多年来国际运筹学界的研究热点之一。运筹学界将此类问题统称之为车辆路径问题（VehicleRoutingProblem,VRP），或车辆调度问题（VehicleSchedulingProblem,VSP）。一般描述是：对一系列给定的客户点，确定配送车辆行驶路线，使其从配送中心出发，有序地对它们进行服务，并在满足一定的约束条件下（如车辆载重量、客户需求量、服务时间限制等），使

2、总运输成本达到最小（如使用车辆数最少、车辆行驶总距离最短等）。一般把最小化车辆使用数作为第一优化目标，而最小化车辆行驶距离作为第二优化目标。*车辆路径问题的特点1.道路网（roadnetwork）弧表示路段，点表示道路交叉点、配送中心和客户。弧的权cij表示其距离或行驶时间。*2.客户（customer）用图上的小圆点表示；需运送或收取的货物量（需求量）di(或di和pi)；要求提供服务的时间段，即时间窗（timewindow）在客户点所花费的服务时间si；能用于服务该客户的车辆集合。3.配送中心（车场）（distributioncenter，depot）用图上的小方点表

3、示；车辆行驶路线开始并终止于配送中心或某一个客户点；其特征由所配备的车辆种类和数量、以及所能处理的货物总量来描述。*4.车辆（vehicle）车辆是自备还是外租，完成任务后是否返回；车辆的装载能力;车辆使用费;可用于进行货物装卸的设备.5.驾驶员（driver）给驾驶员安排取送货任务时，必须符合工作时间方面的有关规定。6.路径编排中的限制条件车辆的当前负载不能超过车辆的装载量；客户只要求送货、取货、或取送货兼有；在客户所要求的时间窗和驾驶员的工作时间内提供服务；访问客户的顺序要求。*7.行驶距离和行驶时间必须知道客户点与客户点之间，配送中心与客户点之间的行驶距离和行驶时间

4、。8.目标（objectives）最小化总运输成本，其大小取决于所需要的车辆数（或线路数）、总行驶距离（时间）；最小化与客户的不完全服务等有关的惩罚值；均衡各线路上的行驶时间和车辆载重量。*2.2车辆路径问题的分类根据配送车辆完成配送任务后是否必须返回原出发点以及返回的形式，可将问题分为闭合式和开放式两大类。在不需严格区分的场合，统称VRP。*当车辆完成运输任务后必须返回原出发点时（即车辆的行驶路线是闭合式的），称之为闭合式车辆路径问题（ClosedVRP），通常简称为车辆路径问题（VRP）。*当不要求车辆完成任务后返回原出发点，或者是若要求返回原出发点，则沿原去程路线返

5、回时（即车辆的行驶路线是开放式的），称之为开放式车辆路径问题（OpenVRP，OVRP）。*根据所包含的约束条件，问题又可进一步分类。以闭合式VRP为例，可归纳如下：DCVRP路程长度VRPPD装载能力取送作业CVRPVRPPDTW时间窗VRPTW回程运输VRPBTWVRPB*2.2.1带装载能力的VRP（CapacitatedVRP，CVRP）问题的特点是VRP中的最基本型式。所有客户都属于要送货的或要取货的，其需求量预先知道，且不能被分割。车辆类型相同且都停放在一个配送中心。对车辆只有装载能力限制。问题的目标是最小化服务所有客户的总费用（即所需要的车辆数及其车辆行驶距

6、离或行驶时间）。问题的描述（可描述为如下的图论问题）*设G=(V,A)为一个完备图，其中V={0,…,n}为顶点集，A是弧集。顶点i=1,…,n表示客户，而顶点0表示配送中心。有时配送中心用顶点n+1来表示。每条弧对应着一个非负的费用cij，表示从点i到点j的行驶费用。在一些测试算例中，顶点与给定坐标的平面上的点相对应，且弧的费用cij被定义为对应于顶点i和j的两点间的欧氏距离。yjj(xj,yj)yii(xi,yi)xjxi*在配送中心备有相同类型的车辆，每辆的装载能力为C。每一条线路上的送货任务只由一辆车承担。每个客户i有一个已知的需要送往交付的非负需求量di，假设d

7、i<C。服务所有客户至少所需要的车辆数*CVRP是求一个具有最小总费用的由K条简单回路组成的集合（每个回路对应于一条配送车辆行驶线路），并满足(1)每个回路从配送中心出发并返回配送中心；(2)每个客户点只在一条回路上；(3)一条回路上各客户点的需求量之和不超过车辆装载能力C。总费用一般包括所使用的车辆数（即回路数）和车辆行驶费用两项。通常都认为，多用一辆车所带来的固定费用的增加，总是超过其因总行驶距离缩短所带来的节省，因此，一般把最小化车辆使用数作为第一优化目标，最小化行驶费用作为第二目标。*当备有的车辆类型不是同一种时