《系统工程》课程教学资源（英文文献）Two-phase algorithm for multi-warehouse and multi-task based logistics delivery

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,ETi0)

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

Step 3 List s(i.j) in an order from great tosmall.Step 4If M=@,algorithm stops, other-wise, to the first s(i,j) in M,generate a routine:r=....i.j...,gotoStep5.Step 5 To each goods listed by task point i:If Veh; is empty or no vehicle in Veh; can loadthis goods, select an empty vehicle, add it intoVehr,then load goods to this vehicle,go to Step8; otherwise, go to step 6.Step 6 Check Pex of the this goods:If it is incompatible with the existing goods onthis vehicle, choose another suitable vehicle(searching in Veh:)oran empty vehicle (if there isno suitable vehicle), add it to Veh,,go to Step 8;Otherwise,goto Step7.Step7 Check Phand Peon of the vehicle:Calculate all of the goods on this vehicle.Ifthe constraint can not be satisfied after adding thisgoods to the vehicle, choose another empty vehi-

cle, add it to Veh, go on to check another goods;otherwise, go to Step 8.Step 8 Check whether the point i and point jsatisfy one of the following conditions:(1) None of i and jare on an existing routine.(2)One of them is on an existing routine andit is not an inside point.(3) Both of point i and point j are on differentexisting routines while none of them are insidepoint. If one of these conditions can be satisfied,go to Step 9; otherwise, go to Step 12.Step 9Check whether conflicts occur afterlinking point i and point j.To each goods listed by task point j: If no ve-hicle in Veh can load this goods,choose an emptyvehicle, add it to Veh,, add this goods to the se-lected vehicle, and go to Step 12;otherwise,choose a suitable vehicle. go to Step 10.Step 10 Check Px of the vehicle.If it is incompatible with the existing goods onthis vehicle, choose another suitable vehicle or anempty vehicle (if there is no suitable vehicle), addit toVehi,go toStep12;otherwise,go to Step11.Step 11 Check Pag and Peon of the vehicle.If the constraint can not be satisfied afteradding this goods to the vehicle, choose anotherempty vehicle, add it to Vehi, go on to check an-other goods of task point j.Go to next step.Step 12 Calculate EF,:(1) If EF,=0,go to Step 13.(2)IfEF,0,calculate △,if[EF,I≤A,go to Step 13, otherwise, go to Step 14.Step 13Link pointi to point j;go to Step14.Step14SetM=M-s(i,j),gotoStep4.2Analysis and DiscussionLet's discuss some key points of the two-phase algorithm:

2 Analysis and Discussion Let’s discuss some key points of the two-phase algorithm:

(1)The threshold value of.:After some tests. it is found that the value between 0.7 and 0.9 is proper; but the tasks will of tenvary ,it is difficult to say which value of &will produce best solution.(2)CalculatethedistancebetweentwopointsThe method in this paper is: create a database table, put information of the shortest path from onepoint to another point into it; because warehouses are definite, and the task points will be graduallydefinite with the going on of daily business; so before calculating the distance, search it in the table, ifit cannotbegot, usethedistance of straight lineto substitute it, thenadd thesetwo points into a set inwhich the distance between a pair of points is waiting to be calculated. When the system is idle, anagent will calculate them according to the algorithm of shortest path in a network routine model, thenrecordthedistanceandpath intothedatabasetablewhichcanbeusedatnexttime3ConclusionThis paper presents a two-phase algorithm for it. In the first phase, the objective is to convert themulti-warehouseproblemintoasingle-ware-houseproblem;andinthesecondphase,theobjectiveisto calculate furthermore to arrange routines from single warehouse to multiple task points under theconstraints of time window and the attributes of vehicle and goods.This two-phase algorithm has avery high value in reality. It is used in a logistics system of a project, and it is also useful to otherresearchers ofthisfield

(1)The threshold value of: After some tests．it is found that the value between 0.7 and 0.9 is proper; but the tasks will of ten vary ,it is difficult to say which value of ξwill produce best solution． (2) Calculate the distance between two points The method in this paper is: create a database table, put information of the shortest path from one point to another point into it；because warehouses are definite, and the task points will be gradually definite with the going on of daily business；so before calculating the distance, search it in the table, if it cannot be got, use the distance of straight line to substitute it, then add these two points into a set in which the distance between a pair of points is waiting to be calculated．When the system is idle, an agent will calculate them according to the algorithm of shortest path in a network routine model, then record the distance and path into the database table which can be used at next time. 3 Conclusion This paper presents a two-phase algorithm for it．In the first phase, the objective is to convert the multi-warehouse problem into a single-ware-house problem；and in the second phase, the objective is to calculate furthermore to arrange routines from single warehouse to multiple task points under the constraints of time window and the attributes of vehicle and goods．This two-phase algorithm has a very high value in reality．It is used in a logistics system of a project, and it is also useful to other researchers of this field．