車輛路徑問題專題-VehicleRoutingProblem課件

1、車輛路徑問題專題 Vehicle Routing Problem第1頁，共46頁。 物流配送車輛優(yōu)化調(diào)度，是物流糸統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)。對配送車輛進(jìn)行優(yōu)化調(diào)度，可以提高物流經(jīng)濟(jì)效益、實現(xiàn)物流科學(xué)化。對物流配送車輛優(yōu)化調(diào)度理論與方法進(jìn)行系統(tǒng)研究是物流集約化發(fā)展、構(gòu)建綜合物流系統(tǒng)、建立現(xiàn)代調(diào)度指揮系統(tǒng)、發(fā)展智能交通運(yùn)輸系統(tǒng)和開展電子商務(wù)的基礎(chǔ)。車輛路徑問題專題第2頁，共46頁。主要內(nèi)容一、車輛路徑問題概述 二、車輛路徑問題數(shù)學(xué)模型車輛路徑問題專題第3頁，共46頁。一、車輛路徑問題概述The Vehicle Routing Problem (VRP) is a generic name given t

2、o 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 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 ori

3、ginating and terminating at a depot. 第4頁，共46頁。組合爆炸一臺汽車每天要給20-30個不同的自動售貨機(jī)(AVM：automatic vending machine)補(bǔ)充飲料，這個時候，巡回路線要訪問20臺機(jī)器的時候，就有20！2432902008176640000條巡回路線可供選擇，若是訪問30臺，就有30！265252859812191058636308480000000條巡回路線可供選擇，利用計算機(jī)，若是一秒鐘可以計算100億條路線的距離的話，20臺AVM的計算需要花費(fèi)7年的時間，30臺AVM則需要花費(fèi)8411兆年的時間，這種現(xiàn)象稱為“組合爆炸”。

4、第5頁，共46頁。FeaturesDepots(number, location)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 dis

5、tance, cost on the links)第6頁，共46頁。Objective Functions (also multiple objectives) Minimise the total travel distance Minimise the total travel time Minimise the number of vehicles第7頁，共46頁。Figure 1 Typical input for a Vehicle Routing Problem第8頁，共46頁。Figure 2 An output for the instance above第9頁，共46頁。Fi

6、gure 3 An output for the instance aboveVehicle 1Vehicle 2Vehicle 3第10頁，共46頁。車輛路徑問題的分類一、車輛路徑問題概述分類標(biāo)準(zhǔn) 類 型物流中心的數(shù)目單車場問題、多車場問題車輛載貨狀況滿載問題、非滿載問題、滿載和非滿載混合問題配送任務(wù)特征純送貨問題或純?nèi)∝泦栴}、取送混合問題貨物取(送)時間的要求無時間窗問題、有時間窗問題車輛類型數(shù)單車型問題、多車型問題車輛對車場的所屬關(guān)系車輛開放問題、車輛封閉問題優(yōu)化目標(biāo)數(shù)單目標(biāo)問題、多目標(biāo)問題第11頁，共46頁。Capacitated VRP (CPRV) Multiple Depot V

7、RP (MDVRP) Periodic VRP (PVRP) Split Delivery VRP (SDVRP) Stochastic VRP (SVRP) VRP with Backhauls VRP with Pick-Up and DeliveringVRP with Satellite Facilities VRP with Time Windows (VRPTW) 第12頁，共46頁。Capacitated VRP (CPRV) CVRP is a VRP in which a fixed fleet of delivery vehicles of uniform capacity

8、 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 below a formal description for the CVRP:Objective: The o

9、bjective 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 quantity assigned to each route does not exceed the capacity o

10、f the vehicle which services the route. 第13頁，共46頁。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 of independent VRPs. However, if the customers

11、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 assigned to that depot, and return to the same

12、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 travel time, and the total demand of commodities m

13、ust 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. 第14頁，共46頁。Periodic VRP (PVRP) In classical VRPs, typically the planning period is a single day. In the case of the Period Vehicle Routing

14、 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 solution is feasible if all constraints

15、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. 第15頁，共46頁。Split Delivery VRP (SDVRP) SDVRP is a relaxation of the VRP wherein it is allowed that the same customer can be served by

16、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.Objective: The objective is to minimize

17、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 routes. An easy way to transform

18、a VRP into a SDVRP consists on allowing split deliveries by splitting each customer order into a number of smaller indivisible orders.第16頁，共46頁。Stochastic VRP (SVRP)Stochastic VRP (SVRP) are VRPs where one or several components of the problem are random. Three different kinds of SVRP are the next ex

19、amples: 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 stages are made for get

20、ting 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.第17頁，共46頁。Objective: The objective is to minimize the vehicle fleet and the sum o

21、f 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 realizations of t

22、he 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.第18頁，共46頁。VRP with Pickup and DeliveriesThe Vehicle Routing Problem with Pi

23、ckup 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 difficult an

24、d 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 intercha

25、nges 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). 第19頁，共46頁。Objective: The objecti

26、ve 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

27、 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.第20頁，共46頁。VRP with Backhauls The Vehicle Routing Problem with Backhauls (VRPB) is a VRP in which customers can demand

28、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

29、are 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

30、 must be completed before any pickups are made.第21頁，共46頁。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 picku

31、ps are made and the vehicle capacity is not violated by either the linehaul or backhaul points assigned to the route. 第22頁，共46頁。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, definin

32、g an interval av,bv wherein the 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 custo

33、mers in their required hours. 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 add

34、itional waiting time on the route. 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. 第23頁，共46頁。一、車輛路徑問題概述系統(tǒng)名稱

35、開 發(fā) 者 核 心 算 法 VRPX IBM(美國) 最短路算法啟發(fā)式算法 VSS 富士通(日本)節(jié)約法HPCAD 美孚(美國) 掃描法第24頁，共46頁。相關(guān)網(wǎng)站1. 西班牙 University of Mlaga： http:/neo.lcc.uma.es/radiaeb/WebVRP/index.html2. 挪威 SINTEF： http:/www.top.sintef.no/3. 瑞士IDSIA：http:/www.idsia.ch/4. 美國Univiversity of Lehigh： / 5. 德國University of Heidelberg： http:/www.iwr.

36、uniheidelberg.de/groups/comopt/software/TSPLIB95/index.html第25頁，共46頁。旅行商問題(Travelling Saleman Problem）TSP 某貨郎由一城市出發(fā)，擬去已確定的n個城市推銷產(chǎn)品，最后回到出發(fā)城市。設(shè)任意兩城市間的距離都是已知的，要求找出一條每個城市都只到一次的旅行線路，使其總旅程最短。二、車輛路徑問題數(shù)學(xué)模型第26頁，共46頁。建模: TSP又稱為貨郎擔(dān)問題。給這些城市編號。出發(fā)城市為0，擬訪問城市分別為1,2,n問題就轉(zhuǎn)化為： 求一個 的排序 使得 最小。其中， 為城市 到 的距離。第27頁，共46頁。TSP

37、的數(shù)學(xué)規(guī)劃形式：表示進(jìn)入且僅進(jìn)入城市 j 一次;表示離開且僅離開城市i一次;(保證線路連通性) 其中， 表示若該旅行商在訪問城i后接著訪問城 j ，則令 ，否則令 。第28頁，共46頁。Problem:Whats difference between TSP and VRP?第29頁，共46頁。Capacitated VRP (CPRV) (非滿載/有向圖）G=(V,A)，連通有向圖，V=v0,v1vn，A=(vi,vj)；v0代表配送中心，Vc=v1vn，客戶點(diǎn)vi的需求為qi (0)；cij 0代表客戶點(diǎn)vi，vj之間的費(fèi)用；M輛同車型的車輛，車載容量Q(qi)第30頁，共46頁。第31頁

38、，共46頁。第32頁，共46頁。Example：0123Suppose M = 1第33頁，共46頁。Example：0123Suppose M = 2第34頁，共46頁。Example：0123Suppose M = 2456第1輛車服務(wù)？第2輛車服務(wù)？第35頁，共46頁。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 called the scheduling h