车辆路径问题专题—VehicleRoutingProblem课件.ppt

1、车辆路径问题专题车辆路径问题专题 Vehicle Routing Problem 物物流配送流配送车辆优化调度，是物流糸统优化车辆优化调度，是物流糸统优化中关键的一环。对配送车辆进行优化调度，中关键的一环。对配送车辆进行优化调度，可以提高物流经济效益、实现物流科学化。可以提高物流经济效益、实现物流科学化。对物流配送车辆优化调度理论与方法进行系对物流配送车辆优化调度理论与方法进行系统研究是物流集约化发展、构建综合物流系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。运输系统和开展电子商务的基础。车辆路

2、径问题专题车辆路径问题专题主要内容主要内容一、车辆路径问题概述一、车辆路径问题概述 二、车辆路径问题数学模型二、车辆路径问题数学模型车辆路径问题专题车辆路径问题专题一、车辆路径问题概述一、车辆路径问题概述 The Vehicle Routing Problem(VRP)is a generic name given to a whole class of problems in which a set of routes for a fleet of vehicles based at one or several depots must be determined for a number

3、of geographically dispersed cities or customers.The objective of the VRP is to deliver a set of customers with known demands on minimum-cost vehicle routes originating and terminating at a depot.组合爆炸 一台汽车每天要给20-30个不同的自动售货机(AVM：automatic vending machine)补充饮料，这个时候，巡回路线要访问20台机器的时候，就有20！2432902008176640

4、000条巡回路线可供选择，若是访问30台，就有30！265252859812191058636308480000000条巡回路线可供选择，利用计算机，若是一秒钟可以计算100亿条路线的距离的话，20台AVM的计算需要花费7年的时间，30台AVM则需要花费8411兆年的时间，这种现象称为“组合爆炸”。Features Depots(number,location)Vehicles(capacity,costs,time to leave,driver rest period,type and number of vehicles,max time)Customers(demands,hard o

5、r soft time windows,pickup and delivery,accessibility restriction,split demand,priority)Route Information(maximum route time or distance,cost on the links)Objective Functions(also multiple objectives)Minimise the total travel distance Minimise the total travel time Minimise the number of vehiclesFig

6、ure 1 Typical input for a Vehicle Routing ProblemFigure 2 An output for the instance aboveFigure 3 An output for the instance aboveVehicle 1Vehicle 2Vehicle 3车辆路径问题的分类车辆路径问题的分类一、车辆路径问题概述一、车辆路径问题概述分类标准分类标准 类类 型型物流中心的数目物流中心的数目单车场问题、多车场问题单车场问题、多车场问题车辆载货状况车辆载货状况满载问题、非满载问题、满载和非满载混合问题满载问题、非满载问题、满载和非满载混合问题

7、配送任务特征配送任务特征纯送货问题或纯取货问题、取送混合问题纯送货问题或纯取货问题、取送混合问题货物取货物取(送送)时间的要求时间的要求 无时间窗问题、有时间窗问题无时间窗问题、有时间窗问题车辆类型数车辆类型数单车型问题、多车型问题单车型问题、多车型问题车辆对车场的所属关系车辆对车场的所属关系 车辆开放问题、车辆封闭问题车辆开放问题、车辆封闭问题优化目标数优化目标数单目标问题、多目标问题单目标问题、多目标问题 Capacitated VRP(CPRV)Multiple Depot VRP(MDVRP)Periodic VRP(PVRP)Split Delivery VRP(SDVRP)Stoc

8、hastic VRP(SVRP)VRP with Backhauls VRP with Pick-Up and Delivering VRP with Satellite Facilities VRP with Time Windows(VRPTW)Capacitated VRP(CPRV)CVRP is a VRP in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common dep

9、ot at minimum transit cost.That is,CVRP is like VRP with the additional constraint that every vehicles must have uniform capacity of a single commodity.We can find below a formal description for the CVRP:Objective:The objective is to minimize the vehicle fleet and the sum of travel time,and the tota

10、l demand of commodities for each route may not exceed the capacity of the vehicle which serves that route.Feasibility:A solution is feasible if the total quantity assigned to each route does not exceed the capacity of the vehicle which services the route.Multiple Depot VRP(MDVRP)A company may have s

11、everal depots from which it can serve its customers.If the customers are clustered around depots,then the distribution problem should be modeled as a set of independent VRPs.However,if the customers and the depots are intermingled then a Multi-Depot Vehicle Routing Problem should be solved.A MDVRP r

12、equires the assignment of customers to depots.A fleet of vehicles is based at each depot.Each vehicle originate from one depot,service the customers assigned to that depot,and return to the same depot.The objective of the problem is to service all customers while minimizing the number of vehicles an

13、d travel distance.We can find below a formal description for the MDVRP:Objective:The objective is to minimize the vehicle fleet and the sum of travel time,and the total demand of commodities must be served from several depots.Feasibility:A solution is feasible if each route satisfies the standard VR

14、P constraints and begins and ends at the same depot.Periodic VRP(PVRP)In classical VRPs,typically the planning period is a single day.In the case of the Period Vehicle Routing Problem(PVRP),the classical VRP is generalized by extending the planning period to M days.We define the problem as follows:O

15、bjective:The objective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers.Feasibility:A solution is feasible if all constraints of VRP are satisfied.Furthermore a vehicle may not return to the depot in the same day it departs.Over the M-day period,each custome

16、r must be visited at least once.Split Delivery VRP(SDVRP)SDVRP is a relaxation of the VRP wherein it is allowed that the same customer can be served by different vehicles if it reduces overall costs.This relaxation is very important if the sizes of the customer orders are as big as the capacity of a

17、 vehicle.It is concluded that it is more difficult to obtain the optimal solution in the SDVRP that in the VRP.Objective:The objective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers.Feasibility:A solution is feasible if all constraints of VRP are satisfied

18、 except that a customer may be supplied by more than one vehicle.Formulation:Minimize the sum of the cost of all routes.An easy way to transform a VRP into a SDVRP consists on allowing split deliveries by splitting each customer order into a number of smaller indivisible orders.Stochastic VRP(SVRP)S

19、tochastic VRP(SVRP)are VRPs where one or several components of the problem are random.Three different kinds of SVRP are the next examples:Each customer vi is present with probability pi and absent with probability 1-pi.:The demand di of each customer is a random variable.:Service times si and travel

20、 times tij are random variables.In SVRP,two stages are made for getting a solution.A first solution is determined before knowing the realizations of the random variables.In a second stage,a recourse or corrective action can be taken when the values of the random variables are known.Objective:The obj

21、ective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers with random values on each execution for the customers to be served,their demands and/or the service and travel times.Feasibility:When some data are random,it is no longer possible to require that all c

22、onstraints be satisfied for all realizations of the random variables.So the decision maker may either require the satisfaction of some constraints with a given probability,or the incorporation into the model of corrective actions to be taken when a constraint is violated.VRP with Pickup and Deliveri

23、es The Vehicle Routing Problem with Pickup and Deliveries(VRPPD)is a VRP in which the possibility that customers return some commodities is contemplated.So in VRPPD its needed to take into account that the goods that customers return to the deliver vehicle must fit into it.This restriction make the

24、planning problem more difficult and can lead to bad utilization of the vehicles capacities,increased travel distances or a need for more vehicles.Hence,it is usually to consider restricted situations where all delivery demands start from the depot and all pick-up demands shall be brought back to the

25、 depot,so there are no interchanges of goods between the customers.Another alternative is relaxing the restriction that all customers have to be visited exactly once.Another usual simplification is to consider that every vehicle must deliver all the commodities before picking up any goods(VRPB).Obje

26、ctive:The objective is to minimize the vehicle fleet and the sum of travel time,with the restriction that the vehicle must have enough capacity for transporting the commodities to be delivered and those ones picked-up at customers for returning them to the depot.Feasibility:A solution is feasible if

27、 the the total quantity assigned to each route does not exceed the capacity of the vehicle which services the route and the vehicle has enough capacity for picking-up the commodities at customers.VRP with Backhauls The Vehicle Routing Problem with Backhauls(VRPB)is a VRP in which customers can deman

28、d or return some commodities.So in VRPPD its needed to take into account that the goods that customers return to the deliver vehicle must fit into it.The critical assumption in that all deliveries must be made on each route before any pickups can be made.This arises from the fact that the vehicles a

29、re rear-loaded,and rearrangement of the loads on the tracks at the delivery points is not deemed economical or feasible.The quantities to be delivered and picked-up are fixed and known in advance.VRPB is similar to VRPPD with the restriction that in the case of VRPB all deliveries for each route mus

30、t be completed before any pickups are made.Objective:The objective is to find such a set of routes that minimizes the total distance traveled.Feasibility:A feasible solution of the problem consists of a set of routes where all deliveries for each route are completed before any pickups are made and t

31、he vehicle capacity is not violated by either the linehaul or backhaul points assigned to the route.VRP with Time Windows(VRPTW)The VRPTW is the same problem that VRP with the additional restriction that in VRPTW a time window is associated with each customer v,defining an interval av,bv wherein the

32、 customer has to be supplied.The interval av,bv at the depot is called the scheduling horizon.Here is a formal description of the problem:Objective:The objective is to minimize the vehicle fleet and the sum of travel time and waiting time needed to supply all customers in their required hours.Feasib

33、ility:The VRPTW is,regarding to VRP,characterized by the following additional restrictions:A solution becomes infeasible if a customer is supplied after the upper bound of its time window.A vehicle arriving before the lower limit of the time window causes additional waiting time on the route.Each ro

34、ute must start and end within the time window associated with the depot.In the case of soft time widows,a later service does not affect the feasibility of the solution,but is penalized by adding a value to the objective function.一、车辆路径问题概述一、车辆路径问题概述系统名称 开 发 者 核 心 算 法 VRPX IBM(美国)最短路算法启发式算法 VSS 富士通(日

35、本)节约法HPCAD 美孚(美国)扫描法相关网站 1.西班牙 University of Mlaga：http:/neo.lcc.uma.es/radiaeb/WebVRP/index.html 2.挪威 SINTEF：http:/www.top.sintef.no/3.瑞士IDSIA：http:/www.idsia.ch/4.美国Univiversity of Lehigh：http:/branchandcut.org/5.德国University of Heidelberg：http:/www.iwr.uniheidelberg.de/groups/comopt/software/TSPL

36、IB95/index.html旅行商问题旅行商问题(Travelling Saleman Problem）TSP 某货郎由一城市出发，拟去已确定的n个城市推销产品，最后回到出发城市。设任意两城市间的距离都是已知的，要求找出一条每个城市都只到一次的旅行线路，使其总旅程最短。二、车辆路径问题数学模型二、车辆路径问题数学模型建模建模:TSP又称为货郎担问题。给这些城市编号。出发城市为0，拟访问城市分别为1,2,n问题就转化为：1 2,n12ni,i,i10()nkkkd i,i1ki1()kkd i,iki 求一个 的排序 使得 最小。其中，为城市 到 的距离。TSP的数学规划形式：的数学规划形式：

37、minijijijd x00(,)11.|1(,|2)0 1nijinijjiji j Sijxxs txSi jSSxor表示进入且仅进入城市表示进入且仅进入城市 j 一次一次;表示离开且仅离开城市表示离开且仅离开城市i一次一次;(保证线路连通性保证线路连通性)其中，其中，表示若该旅行商在访问城表示若该旅行商在访问城i后后接着访问城接着访问城 j，则令，则令 ，否则令，否则令 。(0)ijxi,jn1 ijx0 ijx Problem:Whats difference between TSP and VRP?Capacitated VRP(CPRV)(非满载/有向图）G=(V,A)，连通有向

38、图，V=v0,v1vn，A=(vi,vj)；v0代表配送中心，Vc=v1vn，客户点vi的需求为qi(0)；cij 0代表客户点vi，vj之间的费用；M辆同车型的车辆，车载容量Q(qi)1,)=(,1.)0 kiji jkxi jV kM如果边(由车辆 服务否则1(,1.)0 ikicvkyi V kM如果客户点 由车辆 服务否则(,)11min .1()(,1.)(,1.)Mkijiji jAkMkijcij V kkkijjci Vkkijicijj VcxstxiVvxyjV kMxyiV kMv vk 客户点 在某辆车的服务线路上如果客户点,在车辆 的服务线路上，1001,1()|1

39、,|2 cMkicikMkiki Vkiji j SkyiVvxMvMxSSVS 那么将由车辆 服务每个客户点 仅被服务一次从配送中心 出发的线路有条 (1.)0,1(,1.)0,1(,1.)ckiii Vkijkicq yQkMxi jA kMyiV kM 车载容量限制Example：012311()Mkijcj V kxiV Suppose M=1Example：1121x2201x2301x0123Suppose M=22031x1011x kkijij Vxy111y 221y Example：1121x1201x2301x0123Suppose M=22031x1011x111y 1

40、21y,|1 kiji j SxS456第1辆车服务？第2辆车服务？VRP with Time Windows(VRPTW)The VRPTW is the same problem that VRP with the additional restriction that in VRPTW a time window is associated with each customer vi,defining an interval ai,bi wherein the customer has to be supplied.The interval E,L at the depot is cal

41、led the scheduling horizon.Model Description VRPTW is defined on the network G=(V,A),where node n+1 is added in V.All feasible vehicle routes correspond to paths in G that start from node v0 and end also at node v0.A time window is also associated with nodes 0 and n+1,i.e.,a0,b0=an+1,bn+1=E,L,where

42、E and L represent the earliest possible departure from the depot and the latest possible arrival at the depot,respectively.Zero demands and service times are defined for v0.That is,q0=s0=0.tij表示车辆由vi驶到vj的时间 客户点vi的需求为qi(0)客户点vi的开始服务时间需在一定的时间范围ai,bi si表示车辆对客户点vi的时间硬时间窗问题 每个客户点vi的开始服务时间必须落在时间窗ai,bi中；1,

43、)=(,1.)0:kijkiii jkxi jV kMwvk如果边(由车辆 服务否则客户点 被车辆 开始服务时间1(,1.)0 ikivkyiV kM如果客户点 由车辆 服务否则(,)11min .1()(,1.)(,1.)Mkijiji jAkMkijcij V kkkijjci Vkkijicijj VcxstxiVvxyjV kMxyiV kMv vkk 客户点 在某辆车的服务线路上如果客户点,在车辆 的服务线路上，那么将由车辆 服务101,11 1()v vccMkicikMkiki VMki nki VyiVvxMMxMM 00每个客户点 仅被服务一次从配送中心 出发的线路有条回到配

44、送中心 出发的线路有条 ,|1 ,|2 (1.)()0 ckijci j Skiii Vkkkijiiijjkkkiijiiijj VjxSSVSq yQkMxwstwaxwbx 车载容量限制 服务顺序限制(1.)(1.01)0,1(,1.)0,1(,1.)cVkikijkikM iVEwLkM inxi jA kMyiV kM ,时间窗限制 ,，MDVRP(Multiple Depot VRP)从多个车场(配送中心)用多辆车向多个客户送货，组织适当的行车路线，使车辆有序地通过它们；每个配送中心的位置一定，每个客户的位置和需求量一定，每台车辆的载重量一定，其一次配送的最大行驶距离一定，配送中心

45、供应的货物，能够满足所有客户的需求，要求合理安排车辆配送路线，使目标函数得到优化(如路程最短、费用最小、时间尽量少、使用车辆尽量少等)，从而加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本。并满足以下条件：每条配送路径上客户的需求量之和不超过车载容量；每条配送路径的长度不超过车辆一次配送的最大行驶距离；每个客户的需求必须满足，且只能由一辆车送货。Problem StatementThe Multiple Depot Vehicle Routing Problem(MDVRP):DCustomers D DMDVRP(Multiple Depot VRP)(

46、非满载/有向图）G=(V,A)，连通有向图，,Vc=v1vN，Vd=vN+1,vN+M，A=(vi,vj)，Vd代表配送中心集合，Vc代表客户点集合；客户点vi的需求为qi(0)；cij 0代表客户点vi,vj之间的费用；配送中心vi 有Km辆车 同车型的车辆，车载容量Q(qi)cdVVV1 0 mijmkijvkvvx配送中心 的车辆 从客户 到客户否则 MNiMNjMmKkmkijijmxc1111min11111.1 1,2,1,2,1 1,2,mNNmkmkmjjmmjjKN M N Mmkijjm NkmkijkstxxmNNNMkKxiNx 从某配送中心出发的车辆必须回到该配送中心111,111 1,2,|1 ,|2,1,2,mKN MN Mim Nmkijcdmi j SNN MmkiijijjNxSSVSmV kKgxQ 每个客户点仅被某配送中心派出的车辆服务一次11 1,2,1,2,1,2,mmKNmkmjmjkmNNNMkKxKmNNNM车载容量限制配送中心车辆数目限制11 0 1,2,1,2,N MN Mmkmkjmmjmj Nj NxxmNNNMkK配送中心间没有车辆来往