多回路运输车辆路径问题模型及求解,物流配送车辆优化调度，是物流糸统优化中关键的一环。对配送车辆进行优化调度，可以提高物流经济效益、实现物流科学化。对物流配送车辆优化调度理论与方法进行系统研究是物流集约化发展、构建综合物流系统、建立现代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。,车辆路径问题专题,主要内容,一、车辆路径问题概述 二、车辆路径问题数学模型,车辆路径问题专题,一、车辆路径问题概述,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 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！2432902008176640000条巡回路线可供选择，若是访问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 or 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 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,Vehicle 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 which 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 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 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 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 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 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 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. 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: 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. 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 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 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 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)