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

1、车辆路径问题专题 Vehicle Routing Problem,物流配送车辆优化调度，是物流糸统优化中关键的一环。对配送车辆进行优化调度，可以提高物流经济效益、实现物流科学化。对物流配送车辆优化调度理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。,车辆路径问题专题,主要内容,一、车辆路径问题概述 二、车辆路径问题数学模型,车辆路径问题专题,一、车辆路径问题概述,The Vehicle Routing Problem (VRP) is a generic name given to a whole class of pr

2、oblems in which a set of routes for a fleet of vehicles based at one or several depots must be determined for a number 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 terminat

3、ing at a depot.,组合爆炸,一台汽车每天要给20-30个不同的自动售货机(AVM：automatic vending machine)补充饮料，这个时候，巡回路线要访问20台机器的时候，就有20！2432902008176640000条巡回路线可供选择，若是访问30台，就有30！265252859812191058636308480000000条巡回路线可供选择，利用计算机，若是一秒钟可以计算100亿条路线的距离的话，20台AVM的计算需要花费7年的时间，30台AVM则需要花费8411兆年的时间，这种现象称为“组合爆炸”。,Features,Depots(number, loca

4、tion) Vehicles(capacity, costs, time to leave, driver rest period, type and number of vehicles, max time) Customers(demands, hard or soft time windows, pickup and delivery, accessibility restriction, split demand, priority) Route Information(maximum route time or distance, cost on the links),Objecti

5、ve Functions (also multiple objectives) Minimise the total travel distance Minimise the total travel time Minimise the number of vehicles,Figure 1 Typical input for a Vehicle Routing Problem,Figure 2 An output for the instance above,Figure 3 An output for the instance above,Vehicle 1,Vehicle 2,Vehic

6、le 3,车辆路径问题的分类,一、车辆路径问题概述,Capacitated VRP (CPRV) Multiple Depot VRP (MDVRP) Periodic VRP (PVRP) Split Delivery VRP (SDVRP) Stochastic 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 whic

7、h a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot 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

8、below a formal description for the CVRP: Objective: The objective is to minimize the vehicle fleet and the sum of travel time, and the total 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 quant

9、ity assigned to each route does not exceed the capacity of the vehicle which services the route.,Multiple Depot VRP (MDVRP),A company may have several 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

10、of independent VRPs. However, if the customers and the depots are intermingled then a Multi-Depot Vehicle Routing Problem should be solved. A MDVRP requires the assignment of customers to depots. A fleet of vehicles is based at each depot. Each vehicle originate from one depot, service the customers

11、 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 and 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

12、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 VRP constraints and begins and ends at the same depot.,Periodic VRP (PVRP),In classical VRPs, typically the planning period is a single day. I

13、n 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: Objective: The objective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers. Feasibility: A

14、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 customer must be visited at least once.,Split Delivery VRP (SDVRP),SDVRP is a relaxation of the VRP wherein it is allowed that the s

15、ame 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 vehicle. It is concluded that it is more difficult to obtain the optimal solution in the SDVRP that in the VRP. Objectiv

16、e: 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 except that a customer may be supplied by more than one vehicle. Formulation: Minimize the sum of the cost of all r

17、outes. 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),Stochastic VRP (SVRP) are VRPs where one or several components of the problem are random. Three different kinds

18、 of SVRP are the next examples: Stochastic customers: Each customer vi is present with probability pi and absent with probability 1- pi. Stochastic demands: The demand di of each customer is a random variable. Stochastic times: Service times si and travel times tij are random variables. In SVRP, two

19、 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 objective is to minimize the vehicle flee

20、t 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 constraints be satisfied for all re

21、alizations 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 Deliveries,The Vehicle Routing Problem

22、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 planning problem more diffi

23、cult 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 depot, so there are no

24、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).,Objective: The objective

25、 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 the the total q

26、uantity 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 demand or return s

27、ome 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 are rear-lo

28、aded, 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 must be co

29、mpleted 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 the

30、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 th

31、e 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.

32、Feasibility: 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 ro

33、ute. Each route 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.,一、车辆路径问题概述,相关网站,1. 西班牙 University of Mlaga： http:/neo.l

34、cc.uma.es/radiaeb/WebVRP/index.html 2. 挪威 SINTEF： http:/www.top.sintef.no/ 3. 瑞士IDSIA：http:/www.idsia.ch/ 4. 美国Univiversity of Lehigh： / 5. 德国University of Heidelberg： http:/www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/index.html,旅行商问题(Travelling Saleman Problem）,TS

35、P,某货郎由一城市出发，拟去已确定的n个城市推销产品，最后回到出发城市。设任意两城市间的距离都是已知的，要求找出一条每个城市都只到一次的旅行线路，使其总旅程最短。,二、车辆路径问题数学模型,建模:,TSP又称为货郎担问题。给这些城市编号。出发城市为0，拟访问城市分别为1,2,n问题就转化为：,求一个 的排序 使得 最小。,其中， 为城市 到 的距离。,TSP的数学规划形式：,表示进入且仅进入城市 j 一次;,表示离开且仅离开城市i一次;,(保证线路连通性),其中， 表示若该旅行商在访问城i后接着访问城 j ，则令 ，否则令 。,Problem: Whats difference between

36、 TSP and VRP?,Capacitated VRP (CPRV) (非满载/有向图）,G=(V,A)，连通有向图，V=v0,v1vn，A=(vi,vj)； v0代表配送中心，Vc=v1vn，客户点vi的需求为qi (0)； cij 0代表客户点vi，vj之间的费用； M辆同车型的车辆，车载容量Q(qi),Example：,0,1,2,3,Suppose M = 1,Example：,0,1,2,3,Suppose M = 2,Example：,0,1,2,3,Suppose M = 2,4,5,6,第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 th