数学建模供应链网络物流配送与车辆路径问题

供应链网络物流配送与车辆路径问题配送是指对局域范围内的客户进行多客户、多品种、按时联合送货活动。配送活动是指根据一定区域范围内各个客户所需要的各个品种要求，对配送中心的库存物品进行拣选、加工、包装、分割、组配、分装上车，并按一定路线循环依次送达各个用户的物流活动。物流配送是供应链网络中一个重要的直接与消费者相连的环节，是货物从物流节点送达收货人的过程。配送是在集货、配货基础上，按货物种类、品种搭配、数量、时间等要求所进行的运送，是“配”和“送”的有机结合。配送的实质是现代送货，是以低成本、优质服务为宗旨，是一种先进的物流形式。供应链网络的物流配送过程主要包括：从生产工厂进货并集结的集货作业；根据各个用户的不同需求，在配送中心将所需要的货物挑选出来的配货作业；考虑配送货物的质量和体积，充分利用车辆的载重和容积的车载货物的配装及路线的确定。随着供应链管理系统的集约化、一体化的发展，常将配送的各环节综合起来，核心部分为配送车辆的集货、货物装配及送货过程。进行配送系统优化，主要是配送车辆优化调度，包括集货线路优化、货物配装及送货线路优化，以及集货、货物配装和送货一体化优化。物流配送车辆优化调度，是供应链系统优化中关键的一环，也是电子商务活动不可缺少的内容。对配送车辆进行优化调度，可以提高供应链管理的经济效益、实现供应链管理科学化。配送车辆优化调度实际上也就是车辆路径问题（VehicleRoutingProblem，简称VRP），是Dantzig和Ramse]80[于1959年提出来的，该问题被提出来之后，很快就引起了运筹学、应用数学、组合数学、图论、网络分析、物流学、管理学、以及计算机科学等学科专家和运输计划制订者的极大重视，成为了运筹学和组合优化领域的前沿和研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。车辆路径问题是径旅行商问题（TravelSalesmanProblem，简称TSP）衍生而出的多路TSP问题，即为K-TSP。VRP的一般定义为]81[：对一系列送货点和（或取货点），组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件下（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等），达到一定的目标（如路程最短、费用最少、使用车辆数最少等）。见图1。●●●●●●●●●●●图1车辆路径问题示意图物流配送车辆路径问题可以归纳为一般网络模型：设G＝(V,E,A)是一个连通的混合网络，V是顶点集（表示物流中心、客户、停车场等），E、A分别为无向的边集和有向的弧集，E中的边和A中的弧均被赋权（可以表示配送的距离、时间或费用），V1、E1、A1分别为V、E、A的子集，求满足约束条件（包括客户的货物需求或供应数量约束、需求或供应时间约束、配送车辆一次配送的最大行驶距离约束、车辆的最大载重量约束等），并包含V1、、E1、A1的一些巡回路线，使目标函数取得优化，目标函数可以取配送总里程最短、配送车辆总吨位公里数最少、配送总费用最低、配送时间最少、使用的配送车辆数最少、配送车辆的满载率最高等。一、车辆路径问题的分类1.车辆路径问题的目标函数和约束条件(1)目标函数对配送车辆路径的问题，可以选用一个目标，也可以选用多个目标。经常选用的目标函数有：·配送总里程最短配送里程与配送车辆的耗油量、磨损程度以及司机疲劳程度直接相关，它直接决定运输成本，对配送业务的经济效益有很大影响。·配送车辆的吨位公里数最小该目标将配送距离与车辆的载重量结合起来考虑，即以所有配送车辆的吨位数（最大载重量）与行驶距离乘积的总和最少为目标。·综合费用最低降低综合费用是实现配送业务经济效益的基本要求。在配送中，与取送货物有关的费用包括：车辆维护和行驶费用、车队管理费用、货物装卸费用、相关工作人员工资费用等。·准时性最高由于客户对交货时间有较严格的要求，为提高配送服务质量，有时需要将准时性最高的作为确定配送路线的目标。·运力利用最合理该目标要求使用较少的车辆完成配送任务，并使车辆的满载率最高，以充分利用车辆的装载能力。·劳动消耗最低即以司机人数最少，司机工作时间最短为目标。(2)约束条件配送车辆路径问题应满足的约束条件主要包括：·满足所有客户对货物品种、规格、数量的要求；·满足客户对货物发到时间范围的要求；·在允许通行的时间进行配送（如有时规定白天不能通行货车等）；·车辆在配送过程中的实际载重量不得超过车辆的最大允许载重量；·在配送中心现有运力范围内。2.车辆路径问题的分类现实中的物流配送车辆路径问题是一个非常复杂的问题，根据车辆路径问题的构成要素将车辆路径问题分为以下几类]111[：(1)按配送中心的数目分·单配送中心问题，即只有一个配送中心；·多配送中心问题，既有两个或两个以上的配送中心。(2)按车辆载货状况分·满载问题，即客户需求或供应的货物大于或等于车辆的载重量，完成一项配送任务需要一辆或一辆以上的配送车辆，且配送车辆需要满载运行；·非满载问题，即客户需求或供应的货物小于车辆的载重量，多项配送任务可以用一辆配送车辆，且配送车辆常处于非满载状态；·混载问题，即满载和非满载混合问题。(3)按配送任务分·纯送货问题，即纯卸货问题，只考虑由配送中心向客户送货；·纯取货问题，即纯装货问题，只考虑将客户供应的货物取到配送中心；·取送混合问题，即装卸混合问题或集货和送货一体化问题。(4)按客户对货物取（送）时间的要求分·无时限问题，即客户对货物的取（送）的时间无具体要求；·有时限问题，又称有时间窗问题，即客户要求在规定的时间内完成交易。同时有时间窗问题又分为硬时间窗问题和软时间窗问题，硬时间窗问题即对客户的交易必须在规定的时间内完成；软时间窗问题即对客户的交易尽量在规定的时间内完成，否则对配送企业给予一定的惩罚。(5)按车辆类型分·单车型问题，即所有配送车辆的载重量、最大行驶里程及其他性能均相同；·多车型问题，即配送车辆的载重量、最大行驶里程及其他性能不相同。(6)按车辆对车场的所属关系分·开放式车辆路径问题，即车辆完成任务后可以不返回其出发的车场；·封闭式车辆路径问题，即车辆完成任务后必须返回其出发的车场。(7)按优化目标分·单目标问题，即仅考虑一个配送目标；·多目标问题，即同时考虑多个配送目标。二、车辆路径问题的数学模型1.单车场车辆路径问题设配送中心编号为0，客户编号为N,,2,1，配送中心0有K辆配送车辆，每辆的载重量为Q，需要向N个客户送货，客户i的需求量为iq),,2,1(N，客户i到j的距离为ijc),,2,1,(Nji，配送中心到各客户的距离为ojc,2,1(j，)N，另外，令01kiy否则完成的任务由车辆客户ki(1)01xijk否则行驶到客户从客户车辆jik(2)则车辆路径问题的数学模型为：NiNjKkijkijxc111minZ＝(3)s.tQyqkiNii1(},,2,1{Kk)(4)11Kkkiy(Ni,,2,1)(5)kjNiijkyx1(kNj;,,2,1)(6)kiNjijkyx1(kNi;,,2,1)(7)hkSiSjijkyx(kShVS,,0\)(8)1,0ijkx(kNji;,,2,1,)(9)1,0kiy(kNi;,,2,1)(10)式（1）、（2）表示变量约束；式（3）表示目标函数为车辆行驶的最短距离和；式(4)表示分配给每一辆车的客户需求量之和不大于车辆的最大装载量；式(5)表示每个客户只能由一辆车配送；式（6）、（7）表示两个变量之间的约束关系；式（8）表示为保证车辆k的行驶路线的连通性，避免出现与配送中心分离的路线，它可以用支路消去约束代替，即SxSiSjijkkNSNS;12,,,2,1多车场车辆路径问题（Multiply－DepotVehicleRoutingProblem，简称MDVRP）是基本车辆路径问题（VehicleRoutingProblem,简称VRP）的推广，指的是有多个车场同时对多个客户送货，各客户有一定的货物需求，每个车场都可提供货物，并且由车队负责执行运输任务，要求对各客户的车辆和行驶路线进行适当的安排，在保证满足各客户需求的前提下，使总的运输成本最低。多车场车辆路径问题比单车场车辆路径问题更具有一般性，更接近于现实生活，具有更广泛的应用背景。随着现代商业的发展，许多大型的企业均建立了多配送中心。因此，研究多车场车辆路径问题对促进现代商业的发展有重要的意义。多车场车辆路径问题可描述为：有M个车场，各自拥有容量为Q的车),,2,1(MmKm辆，负责对N个客户进行货物分送工作；客户i的货物需求量为iq，Qqi，客户i和客户j之间的运输成本为),,2,1,(Njidij，每个客户可以由任意一个车场的车辆服务，但只能由一辆车服务一次，每辆车完成任务后必须返回原车场，要求一合适的车辆调度方案，使各车场的车辆能满足所有客户的要求，并使车辆的总运输成本最低。设客户的编码为N,,2,1，车场编码为MNNN,,2,1，定义变量01mkijx否则行驶到客户从客户的车辆车场jikm(11)则多车场车辆路径问题的数学模型为：mkijMNiMNjMmKkijxdZm1111min(12)s.tmNjKkmkijKxm11MNNNmi,,2,1,(13)111NjmkjiNjmkijxxMNNNmi,,2,1,mKk,,2,1(14)1111MNjMmKkmkijmxNi,,2,1(15)1111MNiMmKkmkijmxNj,,2,1(16)QxqmkijNiMNji11MNNNm,,2,1mKk,,2,1(17)011MNNjmkijMNNjmkjixxMNNNmi,,2,1mKk,,2,1(18){0,1}mkijx(19)模型中，式(12)表示目标函数，即最短路径长度；式(13)表示各车场派出的车辆数目不能超过该车场所拥有的车辆数；式(14)确保车辆都是从各自的车场出发，并返回原车场；式(15)、(16)保证每个用户只能被一辆车服务一次；式（17）定义了车辆容量约束；（18）式表示车辆不能从车场直接到车场。