下载  >  课程资源  >  讲义  > a shortest path approach to the multiple-vehicle routing problem

a shortest path approach to the multiple-vehicle routing problem 评分

a shortest path approach to the multiple-vehicle routing problem with split pick-ups
Brought on by competition, the pressure to reduce cost is ever-present in the trucking industry. Often cost reduction resulls froIn improving operational processes, such as leet rouling. In this paper we consider a process-related problem of broad and significant interest to the trucking industry 1. Determine the number of trucks needed to transport parts(modules, components, material) from a set of suppliers to a single assembly plant, and 2. for each truck, determine what suppliers it should visit and how many parts it should pick up at each supplier, in order to minimize total transportation cost. We allow more than one truck to visit each supplier; 1. e, we allow split pick-ups. We call this problem the multiple vehicle routing problem with split pick-ups(mVRPSP) Dror and Trudeau(1989)have shown that the advantages of permitting split pick-ups can be significant, although allowing split pick-ups adds to problem complexity. The problem has traditionally been modeled and solved as a Mixed Integer Program Due to the problem complexity, it is necessary to resort to heuristic or approximate solution techniques when solving the majority of instances of the mVRPSP; we discuss the literature on such techniques helow. The novelty of the approach presented in this paper is bi-fold We prescnt an altcrnativc modcl for the mVRPSP, formulating it as a deterministic Dynamic Program (P). Although the most natural such formnlation for mVRPSP entails a Dynamic Program with an uncountably-infinite state space, we show that it is possible to modify the formulation to obtain a DP with a finite state space Based on the above formulation, we present a new, exact, algorithm for solving mVRPSP We prove that the solution procedure presented in this paper is guaranteed to produce an optimal solution to mVRPSP upon termination. In addition, we present some encouraging, albeit preliminary, computational experiment Dror and Trudeau(1990) identify certain properties of an optimal solution of m VRPSP, and propose a heuristic algorithm. Other heuristic algorithms for the m vRPSP are presented in Frizzell and Griffin(1995), and Sierksma and Tijssen(1998) Dror et. al. (1994) strengthen the Mixed Integer Programming formulation of the mvRPSP by estab lishing several families of valid inequalities. They outline a two-part branch and bound procedure, which makes use of these valid inequalities both to perform branching and to obtain tighter lower bounds on the value of the optimal solution to be used in the branch and bound algorithms. Although a full implementation of the proposed algorithm would constitute a complete branch and bound procedure, and hence will eventu- ally Terminate with an optimal solulion, the authors chose lo implement only the first parl uf the algorithn (essentially, solving the relaxed problem at the root of the branch and bound tree), since their primary goal was lo investigale the strength of the derived valid inequalities. They report gaps from 0%wo 9%between the upper and lower bounds on the optimal objective value, where the gap of o%o was obtained in one problem instance having 10 suppliers. As Far as we knuw, the complele, and hence optimal, algorithIn has nul been implemented. Hence, feasible solutions of the m vRPSP cannot be inferred from the obtained output Belenguer et. al.(2000)study the facial structure of the mVRPSP polyhedron, and also identify several classes of valid inequalities. Based on a heuristic procedure for the identification of violated constraints, they present a culling-plane algorithn which identifies a lower bound on the optimal objective value. They consider instances with up to 48 suppliers and report gaps between 0% and 12%o. Once again, a feasible solution of the mVRPSP cannot in general be obtained from the output of this algorithm In this paper, we model the mvRPSP as a dynamic program(DP). The state of this dP is the vector of supplies a=(a1,., aM), where M is the number of suppliers and the non-negative real number a represents the number of truckloads of parts needed to be transported from supplier i to the assembly plant For example, if a=(1.4, 0.5), then there are two suppliers, supplier 1 has 1. 4 truckloads for pick-up, and supplier 2 has 0. 5 truckloads for pick-up. The resulting state space is the non-negative orthant of Given a supply vector C, an action for this DP is a set of suppliers to be visited and the number of truckloads of parts to be picked up from these suppliers by a single(capacitated)truck. We represent such an action by a non-negative vector u =(,., wm)such that u s a and >M ≤1. The set of all such actions represents the action space The main contribution of this paper is to show that this dp is equivalent to a finite action dP that has a finite state space for any given initial condition. We use 4, a best-first search algorithm for determining a minimum cost path through a network, to solve this equivalent DP. We compare this solution approach to two mixed integer programs(MIP)and show that our solution approach often requires less than 1 %o of the computational time required by the two MIPs. We demonstrate that our solution approach can solve instances of the mvrPSP that are too large for the two mip solution approaches and that our solution approach can be useful in solving instances of the mvRPSP having a realistic number of suppliers This paper is outlined as follows. In Section 1, we provide a statement of the mVRPSP. In Section 2,we present two MIP formulations for the mVRPSP. Section 3 presents several important properties of optimal solutions of the mVRPSP In Section 4, we present a DP formulation of the mVRPSP whose state and action spaces are uncountably infinite. We then construct a finite action DP, having a finite state space for any given initial conditions, that is equivalent to the original DP. A is applied to the finite action DP. In Section 6,we report the resulls of a numerical study comparing the two MIPs and the DP based apprOach. This comparison indicates that the DP based solution approach is able to solve larger problems than the MIPs and is able to solve the sarne sized problems far fasler than the MIPs In Section 7, conclusions are given 1 Preliminaries and the m vRPSP problem statement We denote the ith unit vector in Rn by ei and a vector of all ones by e. For a given vector v, v stands for its transpose. The nonnegative orthant in R is denoted by R+ Let M be the number of suppliers. We will assume that the suppliers are indexed with integers 1 through M, and the assembly plant, or the depot, is indexed by o Let Ci 220, i=1,., 1, be the supply amount at supplier i, as expressed as the number of truckloads Let a=(al,.,aM)ER denote the vector of supply amounts, or the supply vector. Every route originates at the depot(e.g, the assembly plant, in our application context), extends to one or several suppliers, and finally returns to the depot. Each truck collects parts from the suppliers on the route and makes a delivery at the depot. Each route can be represented by a vector ?c[0, 1], where ri=1 if and only if the truck following this route visits the ith supplier. Such a specification of a route does not describe the order in which the suppliers are visited by the truck. We will, however, assume that the suppliers are visited in the order leading to the minimal cost of the route specified by the vector r throughout this paper (i. e, the travelling salesman tour, perhaps, with some side constraints). The total cost of executing route ? is then the sum of travel costs between the consecutive suppliers on the route(according to the minimal cost routing), and is denoted by c(r). A route r is called a dedicated trip to supplier i if r= ei. There may be a restriction in selecting a route in practice such as"a truck is allowed to visit at most nine suppliers suppliers l and 5 may not be on the same route since they are too far apart "and so on. The collection of all feasible routes is denoted by R= p (1) In this paper we consider instances of the mVRPSP in which the incurred costs are determined only by the cost of travel. This would be the case, for example, if the measure of performance to be minir mize ed is the total mileage travelled by the truck fleet, or the total travel time of the trucks. Hence, the cost is independent of load size. The cost of travelling from location i to location is denoted by ci≥0,i,j=0,……,M,i≠ and assumed to satisfy the triangle inequality. Hence, r< r' implies c(r< c(r'y We assume that the collection of feasible routes I satisfies the following conditions. ·∑k1:ke.e…, every supplier is covered by at least one feasible route) ifr∈R, then T∈Rvr∈{0,1 such that r≤r(ie, if a collection of suppliers is allowed to be visited by one truck, any subset of this collection can also be visited by one truck). As a truck traverses route r, it picks up certain loads at each supplier it visits. We denote the vector of the loads picked up by this truck by u"c R. Any feasible vector w must satisfy the following two inequalities eur 1(i.., the capacity of the truck, assumed to be 1 for all trucks in the fleet, cannot be .U:<r(i.e, parts can be picked up only from the suppliers that are visited by the truck). In view of the this restriction the first constraint can also be stated as rTu<1 We can now formally state the mVRPSP: Given a set of suppliers ( 1,.,M, a supply vector aE R+, and a set of feasible routes R=r,.,h with route costs e("),i=1,., K, find a collection of routes R* (r..,f E I and corresponding feasible truck loads W*(uTI,., u P)that allow for all supplies to be delivered to the depot at minimal cost 2 MIP formulations of the mVRPSP a In this section we present two mixed integer programming(MIP)formulations of the m VRPSP.The first formulation arises from a generalization of a well-known formulation of a mulLiple vehicle routin problem(with no split pick-ups allowed). References and similar formulations are presented in Lawler et al.( 1985). Let U be an upper bound on the number of trucks needed to move all the parts(for example, one might take U=>sal, where [al is the smallest integer n such that a n). For k= 1,...,U and i,j=0,.. M, let us define the variables as follows 1, if truck hi travels to supplier directly from supplier i 泛下k 0. otherwise, if supplier i is visited by truck hi, 0, otherwise, tliT d picked up at supplier i by vehicle k Lik dummy continuous variables for subtour elimination constraints Then m VRPSP can then be formulated as an mip LLLL ∑∑∑ t∑=∑ Vi, vh (2b) d (M+1)·m≤M,Vi(≠0),j(≠0),k 2k≤a19ik,y,vk, 丁 wik Vi ∑法≤1,k (2f) WWWe(.cIn.com k≥0,v2.v The objective function(2a) expresses the total travel cost. as a sum of costs of travelling between consecu tive suppliers. Constraints (2b)are fow conservation constraints and serve as definitions of variables y,k- Constraints (2c)are subtour elimination constraints defined for the route of every truck. Constraints (2d) ensure that pickups are made only from suppliers visited, while constraints (2e) guarantee that all supplies are picked up. Finally, constraints(2f)ensure that the total load of each truck does not exceed the truck capacity The above formulation is rather generic, in particular, it does not include possible constraints on the routes, If any such constraints are present in a problem instance, they would need to be added to the mip model. The alternative MIP formulation below assumes knowledge and makes explicit use of the collection of feasible routes=frI, ...,mk)of(1)and their costs c(r),TER Let be an upper bound on the number of trucks needed. For=l,..., and k:= k. define the variables as follows if truck j takcs route h 0. otherwise WjER+: load vector for truck i Then the mVrPSP can be formulated via the following MIP min clr k=1 s, t (3b) k=1 ≤∑rr, h=1 doc (3d) ≤1,V 豆丁 {0,1},vk,Yj (3f) ≥0,V (3g) The objective function (a) expresses the total travel cost as the sum of costs of all routes taken by the trucks. Constraints(3b) ensure that each truck is assigned a feasible route(since the empty? route r=0 is considered to be feasible, the use of this route will make up for possible over-estimation of the number of trucks necessary Constraints (3c)ensure that pickups are made only from suppliers visited, while constraint(3d) guarantees that all supplies are picked up. Finally, constraints(e)ensure that total loads of each truck do not exceed the truck capacit Formulating the mVRPSP in the form(3)requires a pre-processing step, in which the minimal costs c(r of all routes r E R are computed. Since, in practice, the feasible routes usually visit only a few locations, the computational overhead incurred by including this pre-processing step is not expected to be excessive 3 Properties of optimal collections of routes In this section we explore some properties of optial collections of routes. For a given set of supplier and travel costs cii 20, let z: R4 -R+ denote the function mapping each supply vector a E R+ to the cost of the optimal routing, z(a). Proposition 1 follows from the assumption that the costs cij satisfy the Triangular inequality Proposition 1 The function 2: R+R+ has the following properties .x(0)=0a=0. i.ja≥a,henz(a)≥(a’).( tonicity) i(a+a1)≤z(a)+2(a),va2a’∈Rl.( Triangular inequality be an optimal collection of routes with respect to the costs cii for a given supply vector a E R+. Here, rER, i=l,., F, and the routes are allowed to be repeated. In addition, let W"- T be a corresponding optimal collection of(vectors of)loads to he picked up hy cach route in R I emmas 2 and 4 present slight modifications of results of Dror and Trudcau(1990)for the possibly restricted collection of feasible routes R. We say that two routes and 72, have a split supplier i in common if r=ri=l Lemma 2 There exists an optimal collection R with no two routes having ore than one split supply location in commoN Proof: Let R" be an optimal collection of routes. Suppose P* contains routes r and r2 that both visit two suppliers, i and ], i#. j, and letup, wi, wi, and w; be the corresponding loads. Suppose without loss of generality that wf-minw?, u, wr, w;. Consider the alternative feasible routing decision and the corresponding loads m-0 I. Now r can skip supplier i since a;=0 and omitting a stop on a route results in a feasible route according to our assumptions on R. The ncw loads arc fcasiblc, and the now routing has onc fcwcr split supplier, and is no morc expensive than the original routing duc to thc triangular inequality. Continuing inductively, wc can construct an optimal collection of routes with at most onc split supplier betwcen any two routes 7 Definition 3 Suppose jor a collection of h routes there exist k distinct Locutions i1, .. ik such that route 1 includes locations i1 and i2, route 2 includes locations i2 and is, etc. Finally, route k includes locations ik and i. Such collection of locations is called a hi-split cycle. The following lemma generalizes lemma 2. Lemma 4( Dror and Trudeau) There exists an optimal collection of routes in which there are no k-split cycles( for any k≥2) Suppose that R=(r,., r")is an optimal collection of routes and that the routes are executed one at a time. Each route visits one or more suppliers, picking up all or part of the supply remaining at each location at the time of the visit. We will say that the routeempties"the supplier when there is no supply remaining at this location after the route is executed. For the route r/(i. e, the j th route in the ordering)let T.=i: ( r:=l, and supplier i is not eMptied by r H We will now show that the routes in the optimal collection can be ordered in such a way that every route leaves at most one supplier non-empty, i. e, I<1,3-1,.,F. Theorem 5 Suppose I contains no k-split cycles for any k > 2. Then the routes in It can be ordered in such a way that[ I2 <1, j-1,., F, where I is defined by (4) Proof: Let S 2=(i:(r2)i= 1, wr< ai).(This definition is slightly different from I'.Indeed s consists of indices of suppliers whose total supplies exceed the amounts allocated to the route r3. 73 consists of the indices of the suppliers not emptied by route at the time the route is executed, i.e. the total supply might have been reduced by a previous pickup by the time r' is executed. As a result, in particular, F CS".)Suppose that S?> 2 for all j= 1,..., F. Then, taking into account Lemma 2, every route T'E R intersects at least two other routes, i.e., there must he a k-split cycle for some k> 2, contradicting our assumption. Hence, there exists a route rE R$<1 Let w be the load vector corresponding to r. Execute this route first(by construction, it"empties"all nodcs it visits but onc)and update thc remaining supply amounts and collection of routes: a =a R=R\r. It is straightforward to show that R* is the optimal collection of F-1 routes for a with no split cycles, and hence the proof can he continued by induction Corollary6 Suppose0<a:≤1,2=1,, i and∑1al=∑1[an1=M. Then the optimal collection of routes consists of dedicated trips to every Location, at the total cost (a)=2iailail(coi+Cin) It follows from Corollary 6 that if a E 4+, then the optimal collection of routes consists of dedicated trips to every location, at the total cost z(a)=2i-1ai(coi Cio)

...展开详情
所需积分/C币:10 上传时间:2015-03-24 资源大小:4.98MB
举报 举报 收藏 收藏
分享 分享
a shortest path approach to the multiple-vehicle routing problem

a shortest path approach to the multiple-vehicle routing problem with split pick-ups

立即下载
The Shortest Path Problem

最短路问题The Shortest Path ProblemThe Shortest Path ProblemThe Shortest Path ProblemThe Shortest Path ProblemThe Shortest Path Problem

立即下载
matlab k shortest path

matlab k shortest path code 供相关研究的学生使用

立即下载
A Constrained Shortest Path Scheme for Virtual Network Service Management

本文来自 俄罗斯和美国两位大牛 研究出的 在虚拟网络环境下,一种最短选路的算法

立即下载
shortest path faster algorithm

sqrt((x2-x0)^2+(y2-y0)^2)-sqrt((x1-x0)^2+(y1-y0)^2)=t

立即下载
一个Shortest path程序

一个用VS开发的最短路径程序,可作为学习这方面的案例,希望对这方面的学习有所帮助。

立即下载
k shortest Path C++

基于D算法实现K shortest Path,封装得比较好。也很方便修改类的实现。

立即下载
shortest path案例小程序

一个用VS开发的最短路径程序,可作为学习这方面的案例,希望对这方面的学习有所帮助。

立即下载
petri net and shortest path

介绍了用Petri Net 的相关理论来求解最短路径问题

立即下载
K shortest path - Yens

MATLAB_kShortestPath_Yen_s_algorithm undirected

立即下载
查找关键路径(shortest path)

查找关键路径(shortest path)

立即下载
Priority-Based Genetic Algorithm for Shortest Path Routing Problem in OSPF

Priority-Based Genetic Algorithm for Shortest Path Routing Problem in OSPF 主要介绍了遗传算法求解最短路径问题中的基于优先级的编码。这种编码方式可以很有效地解决图的最短路径等问题。

立即下载
Prim算法求顶点间shortest path最短距离 C++图实现

Prim算法求顶点间最短距离,算法学习中经典的shortest path类问题,用图实现,初学者可参考

立即下载
OSPF(Open Shortest Path First开放式最短路径优先)

OSPF(Open Shortest Path First开放式最短路径优先)路由协议是一种典型的链路状态(Link-state)的路由协议,一般用于同一个路由域内。在这里,路由域是指一个自治系统(Autonomous System),即AS,它是指一组通过统一的路由政策或路由协议互相交换路由信息的网络。在这个AS中,所有的OSPF路由器都维护一个相同的描述这个AS结构的数据库,该数据库中存放的是路由域中相应链路的状态信息,OSPF路由器正是通过这个数据库计算出其OSPF路由表的

立即下载
k最短路径 k shortest path problem matlab 代码 Yen's algorithm

两个Yen的k最短路径算法(matlab),一个Eppstein的k最短路径算法(C#)。

立即下载
Shortest_Path

用c++编写的最短路径问题,主要用dijkstra和floyd算法

立即下载
Dijkstra-Shortest-Path

关于最短路径得malab程序算法.求单元点到各原点的最短距离

立即下载
Fast exact shortest-path distance queries on large networks

为了在大图中找到两点之间的最短路径,我们先通过宽度优先搜索为每个点建立距离标签索引。关键是在宽度优先搜索是进行剪枝。

立即下载