Two-phase algorithm for multi-warehouse and multi-task basedlogisticsdeliveryAbstract:To a scaled logistic company,assigning is an important part of logistic, and furtherdevelopment will make the optimized assigning of multi-warehouse and multi-task possible. Thispaper provided a two-phase multi-warehouse and multi-task based algorithm which has two phases. Inthe first phase, it combines sweep algorithm, saving algorithm and virtual task point to present amethod. And in the second phase it provides an algorithm for the arrangement of goods loading whichis based on the constraints of time-window and attributes of goods and vehicle. It uses the computingresults of the first phase to form more detailed delivery scheme based on the constraints oftime-window and attributes of vehicle and goods.Key words: logistics delivery; time—window; multi-—warehouse and multi-—taskDocumentcode:AIntroductionTo a large-scale logistics enterprise, the number of daily task reaches hundred and sometimeseven thousand. In most cases, an enterprise itself has many warehouses who are distributed indifferent places.In Fig.1,the model of this problem is introduced.How to collect the warehouse andall delivery task synthetically, how to carry on overall arrangement and send vehicles to accomplishthe delivering task respectively, and how to accomplish the task of providing and delivering atordinary times are the problems to be solved.Task pointaWarehouseFig.1 The model of multi-warehouse and multi-taskThe problem here, first of all, is a Vehicle-Routing-Problem. The most elementary version of the
Two-phase algorithm for multi-warehouse and multi-task based logistics delivery Abstract: To a scaled logistic company, assigning is an important part of logistic, and further development will make the optimized assigning of multi-warehouse and multi-task possible. This paper provided a two-phase multi-warehouse and multi-task based algorithm which has two phases. In the first phase, it combines sweep algorithm, saving algorithm and virtual task point to present a method. And in the second phase it provides an algorithm for the arrangement of goods loading which is based on the constraints of time-window and attributes of goods and vehicle. It uses the computing results of the first phase to form more detailed delivery scheme based on the constraints of time-window and attributes of vehicle and goods. Key words: logistics delivery；time—window；multi—warehouse and multi—task Document code: A Introduction To a large-scale logistics enterprise, the number of daily task reaches hundred and sometimes even thousand．In most cases, an enterprise itself has many warehouses who are distributed in different places．In Fig．1,the model of this problem is introduced．How to collect the warehouse and all delivery task synthetically, how to carry on overall arrangement and send vehicles to accomplish the delivering task respectively, and how to accomplish the task of providing and delivering at ordinary times are the problems to be solved． The problem here, first of all, is a Vehicle-Routing-Problem．The most elementary version of the
vehicle routing problem is the capacitated vehicle routing problem (CVRP).The CVRP is described asfollows: n customers must be served from a unique depot. Each customer asks for a quantity q ofgoods(i=1,2,. ,n) and a vehicle of capacity Q is available to deliver goods. Because the vehiclecapacity is limited, the vehicle has to periodically return to the depot for reloading.In the CVR, it isnot possible to split customer delivery.Therefore, a CVRP solution is a collection of tours where eachcustomer is visited only once and the total tour demand is at most Q. From a graph theoretical point ofview the CVRP may be stated as follows: Let G =(C,L) be a complete graph with node set C =(co, cl,c2,*,cn ) and arc set L=(ci,ci):ci,cjEC, itj. In this graph model,fo is the depot and the other nodesare the customers to be served. Each node is associated with a fixed quantity of goods to be delivered(a quantity qO= O is associated to the depot Co). To each arc (ci,cj)is associated with a value trepresenting the travel time between ci and cj. The goal is to find a set of tours of minimum totaltravel time. Each tour starts from and terminates at the depot co, each node ci(i= 1,2,.*- ,n) must bevisited exactly once, and the quantity of goods to be delivered on a route should never exceed thevehicle capacity Q. An important extension of the CVRP is the vehicle routing problem with timewindows (VRPTW ). The additional constraints are that the service beginning time at each node ci(i-1,2,.*-,n) must be greater than or equal to b ,the beginning of the time window . and the arrival timeat each node c must be lower than or equal to e ,the end of the time window. In case the arrival time isless than bij the vehicle has to wait till the beginning of the time window before starting servicing thecustomer.1Two-PhaseAlgorithm1.14AlgorithmforMultipleWarehousesinFirstPhase1.1.1 The symbol and concept introductiond'-Thedistance betweentaskpointiandwarehouse tdi-The distance between task point i andtask point js (i,j)-The saving value of task point i andtask point jC-The cost to go from task point i to taskpoint jInside point- The task point not linking with warehouse directly on the delivery routine1.1.2Algorithm for multiple warehousesIn a lot of existing algorithms, there is always a prerequisite: the quantity of goods is enough to meet
vehicle routing problem is the capacitated vehicle routing problem (CVRP).The CVRP is described as follows: n customers must be served from a unique depot. Each customer asks for a quantity q of goods(i=1,2,⋯ ,n) and a vehicle of capacity Q is available to deliver goods．Because the vehicle capacity is limited, the vehicle has to periodically return to the depot for reloading． In the CVRP, it is not possible to split customer delivery．Therefore, a CVRP solution is a collection of tours where each customer is visited only once and the total tour demand is at most Q．From a graph theoretical point of view the CVRP may be stated as follows: Let G =(C,L) be a complete graph with node set C =(c0, c1, c2,⋯ ,cn ) and arc set L=(ci,cj):ci,cj∈C, i≠j．In this graph model,f0 is the depot and the other nodes are the customers to be served．Each node is associated with a fixed quantity of goods to be delivered (a quantity q0= 0 is associated to the depot Co)．To each arc (ci,cj)is associated with a value t representing the travel time between ci and cj．The goal is to find a set of tours of minimum total travel time． Each tour starts from and terminates at the depot c0, each node ci(i= 1,2,⋯ ,n) must be visited exactly once, and the quantity of goods to be delivered on a route should never exceed the vehicle capacity Q．An important extension of the CVRP is the vehicle routing problem with time windows (VRPTW )．The additional constraints are that the service beginning time at each node ci(i= 1,2,⋯ ,n) must be greater than or equal to b ,the beginning of the time window ．and the arrival time at each node c must be lower than or equal to e ,the end of the time window．In case the arrival time is less than bij the vehicle has to wait till the beginning of the time window before starting servicing the customer． 1 Two-Phase Algorithm 1.1 Algorithm for Multiple Warehouses in First Phase 1.1.1 The symbol and concept introduction Inside point- The task point not linking with warehouse directly on the delivery routine. 1.1.2 Algorithm for multiple warehouses In a lot of existing algorithms, there is always a prerequisite: the quantity of goods is enough to meet
the needs of task requirement. But in reality, such a thing will often happen: the shortage of goodsquantity in warehouse makes it unable to meet goods quantity ordered to deliver in a day, while it isimpossible to make the supplement. Taking this unexpected situation into account, in order to make itclose to the actual conditions as much as possible, it needs to consider the goods quantity ofwarehouse as a factor in the process of assignment Let f denote the value whether the delivery to taskpoint i can be fulflled by warehouse t:The delivery can be totallyr1fulfilled by warehouse tf=1The delivery can not betotallyfulfilled by warehouse tThe steps of this algorithm are as follows:Step1Seta propervalue forE(0<<1),toeach warehouse t, set S,-@.Step 2 To each task point i and each ware-house t:A, Calculate f.,B.CalculateD,.D,=f'xdi.Step 3Initialize the assignmentTo each task point i: Calculate r(i)=D'/D's,where, t,-The warehouse who is nearest to pointi,t2-The warehouse who is second nearest topoint i. Comparer(i)with ,if r(i)<e,assigntask point i to warehouse ti, add i to S, of ti, ifr(i) ≥ E, the point is a critical point.Step 4 Assignment of critical point:(1)If r(i)≠1, use Clarke-Wright algorithmto make the assignment.First of all, assign the nearest warehouse tofulfill each task point as the initial solution. Thenthe initial cost is: C-,2 min (d.) (h is thenumber of critical point).Calculate the saving value:S,=a+a,-d,Meanwhile,2min (d')-d'if pointihasn'tbeengivena-a definite assignment(d,otherwiseIn Fig.2,it shows how the process goes. In initial assignment, points i and J are assigned to thenearest warehouse respectively.Then try to add them to the routine of warehouse t, if the saving
the needs of task requirement．But in reality, such a thing will often happen: the shortage of goods quantity in warehouse makes it unable to meet goods quantity ordered to deliver in a day, while it is impossible to make the supplement．Taking this unexpected situation into account, in order to make it close to the actual conditions as much as possible, it needs to consider the goods quantity of warehouse as a factor in the process of assignment Let f denote the value whether the delivery to task point i can be fulfilled by warehouse t: The steps of this algorithm are as follows: In Fig.2,it shows how the process goes．In initial assignment, points i and J are assigned to the nearest warehouse respectively． Then try to add them to the routine of warehouse t, if the saving
value is a positive value, the initial assignment should be changedWarehouseFig.2Adding point i and j to the routine of warehouse tList these S, in an order from great to small,get the largest one, then assign the according pointi and j to warehouse t; calculate the value Si, forother remaining critical points.(2)If r(i)-1,critical points should be assigned as follows)If point J and point k have been assigned definitely to warehouse t already, try to insert point Iinto the middle of J and k. Calculate the additional expense produced:djk(i)=dji+dik-djk (to each warehouse t)Get the warehouse t of min djk (i),then assign to the warehouse. Refresh Sf of warehouse t.Step 5 Assignment of difficult point:In this situation, the assignment for a task point must be fulfilled by several warehouses joinly(Fig. 3). The algorithm is as follows:A,Initial assignment:To each"difficultpoint" i, assign it to the warehouse t which has themin(d:)value;B. Convert warehouse to virtual task point;C, Deliver goods to virtual task point;D.Assignment endsirtuVirtuWarchouseWarehouWarehouseFig.3 Delivering to virtual task point1.2AlgorithmforTimeWindowVehicleProblemin SecondPhase1.2.1The symbol and concept introduction
value is a positive value, the initial assignment should be changed． (2)If r(i)=1,critical points should be assigned as follows: If point J and point k have been assigned definitely to warehouse t already, try to insert point I into the middle of J and k．Calculate the additional expense produced: djk(i)=dji+dik-djk (to each warehouse t) Get the warehouse t of min djk (i),then assign to the warehouse．Refresh Sf of warehouse t． Step 5 Assignment of difficult point: In this situation, the assignment for a task point must be fulfilled by several warehouses joinly (Fig．3)．The algorithm is as follows: 1.2 Algorithm for Time Window Vehicle Problem in Second Phase 1.2.1 The symbol and concept introduction
TiThe time to finish task iETiThe earliest time permitted to start task iLTi-The latest time permitted to start task iSiThe time when a vehicle reaches I,ETi<Si<LTiTijThe time cost by a vehicle to go from point i to point jCijThe expense for a vehicle to go from point i to point js(i.j)The saving value to link point i and pointjs(i.j) = C+ C, -C,EEjai-Thepostponement(ortheadvancing)of time to reach point j after linking point i andpoint j,EE, =S, +T +t,-S,A, -The biggest advancing arrival time to jwhen a vehicle need not wait at other pointsbehind jA,-The biggest postponement of arrival timepermitted to j without violating the constraint oftimewindowPea-The set of aggregate attributes of vehi-cleiPeon - The set of containing attribute ofvehicle iPex-The set of excluding attribute of goods kVeh; -The set of vehicles on the routine r ofwarehouse tR-The set of routines of warehouse t1.2.2Algorithm for time windorw vehicle routineproblem under restriction of attributesThe steps are as follows:Step 1 Initialize the routine set of the ware-house.R=@.Step 2 Calculate all s(i.j), set M=(s(i,j)]s(i.j)>0)
Ti—The time to finish task i ETi—The earliest time permitted to start task i LTi—The latest time permitted to start task i Si—The time when a vehicle reaches I,ETi≤Si≤LTi Ti j—The time cost by a vehicle to go from point i to point j Cij—The expense for a vehicle to go from point i to point j s(i,j)—The saving value to link point i and point j