a shortest path approach to the multiplevehicle routing problem 评分

a shortest path approach to the multiplevehicle routing problem with split pickups
Brought on by competition, the pressure to reduce cost is everpresent in the trucking industry. Often cost reduction resulls froIn improving operational processes, such as leet rouling. In this paper we consider a processrelated 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 pickups. We call this problem the multiple vehicle routing problem with split pickups(mVRPSP) Dror and Trudeau(1989)have shown that the advantages of permitting split pickups can be significant, although allowing split pickups 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 bifold 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 uncountablyinfinite 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 twopart 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 cullingplane 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 nonnegative 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 pickup, and supplier 2 has 0. 5 truckloads for pickup. The resulting state space is the nonnegative 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 nonnegative 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 bestfirst 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 wellknown formulation of a mulLiple vehicle routin problem(with no split pickups 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 overestimation 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 preprocessing 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 preprocessing 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 wfminw?, u, wr, w;. Consider the alternative feasible routing decision and the corresponding loads m0 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 hisplit cycle. The following lemma generalizes lemma 2. Lemma 4( Dror and Trudeau) There exists an optimal collection of routes in which there are no ksplit 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 nonempty, i. e, I<1,31,.,F. Theorem 5 Suppose I contains no ksplit cycles for any k > 2. Then the routes in It can be ordered in such a way that[ I2 <1, j1,., 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 ksplit 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 F1 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)=2i1ai(coi Cio)所需积分/C币：10 上传时间：20150324 资源大小：4.98MB

a shortest path approach to the multiplevehicle routing problem
a shortest path approach to the multiplevehicle routing problem with split pickups
立即下载

A Constrained Shortest Path Scheme for Virtual Network Service Management
本文来自 俄罗斯和美国两位大牛 研究出的 在虚拟网络环境下，一种最短选路的算法
立即下载