物流配送路径英文文献.docx

1、A Memetic Algorithm for the Vehicle Routing Problem with Time WindowsJean Berger and Mohamed BarkaouiDefence Research and Development Canada一Valcartier, Decision Support System Section 2459 Pie-XI Blvd. North, Val-Belair, PQ, Canada, G3J 1X5 email: jean.bergerdrdc-rddc.gc.ca, barkaouioricom.caAbstra

2、ctSerial and parallel versions of a new memetic algorithm to address the Vehicle Routing Problem with Time Windows are presented. The underlying approach involves parallel co-evolution of two populations. The first population evolves individuals to minimize total traveled distance while the second f

3、ocuses on minimizing temporal constraint violation to generate a feasible solution. New genetic operators have been designed to incorporate key concepts emerging from recent promise techniques such as insertion heuristics, large neighborhood search and ant colony systems to further diversify and int

4、ensify the search. The parallel version of the method is based on a master-slave message-passing paradigm. The master controls the execution of the algorithm, synchronizes atomic genetic operations and handles parent selection while the slaves concurrently execute genetic operations. Results from a

5、computational experiment show that the serial version of the proposed technique matches or outperforms the best-known heuristic routing procedures, providing six new best-known solutions. In comparison, the method proved to be fast, cost-effective and highly competitive. Alternatively, simulation re

6、sults obtained for the parallel version show a significant improvement over the serial algorithm, matching or even improving solution quality. The parallel algorithm shows a speed-up of five in computing solution having near similar quality.1 .IntroductionVehicle routing problems are well known comb

7、inatorial considerable economic significance. The Vehicle Routing optimization Problem with problems with Time Windows(VRPTW) has received a lot of attention in the literature recently. This is mostly due to the wide applicability of time window constraints in real-world cases. In VRPTW, customers w

8、ith known demands are serviced by a homogeneous fleet of vehicles of limited capacity. Routes are ssumed to start and end at the central depot. Each customer provides a time interval during which a particular task must be completed such as loading/unloading the vehicle. It is worth noting that the t

9、ime window requirement does not prevent any vehicle from arriving before the allowed start of service at a customer location. The objective is to minimize the number of tours or routes, and then for the same number of tours, to minimize the total traveled distance, such that each customer is service

10、d within its time window and the total load on any vehicle associated with a given route does not exceed the vehicle capacity.A variety of algorithms including exact methods and efficient heuristics have already been proposed for VRPTW. For excellent surveys on exact, heuristic and metaheuristic met

11、hods, seeDesrosiers et al.1995, Cordeau et al.,2001 and Braysy and Gendreau, 2001a and 2001b respectively. In particular, evolutionary and genetic algorithms have been among the most suitable approaches to tackle the VRPTW, and are of particular interest to us. Genetic algorithms Holland, 1975;De Jo

12、ng, 1975 and Goldberg, 1989 are adaptive heuristic search methods that mimic evolution through natural selection. They work by combining selection, recombination and mutation operations. The selection pressure drives the population toward better solutions while recombination uses genes of selected p

13、arents to produce offspring that will form the next generation. Mutation is used to escape from local minima. Routing techniques based on genetic algorithms to solve VRPTW emerge from the work of Blanton and Wainwright,1993, Thangiah, 1995a and 1995b, Thangiah et al., 1995, Potvin and Bengio, 1996,

14、Berger et al., 1998, 1999, 2000 and Tan et2001.Alternate methods using evolutionary metaheuristics have been proposed by Homberger and G1999,Gehring and Homberger, 1999 and 2001，and Braysy et al., 2000. Other recent studies on vmetaheuristics for VRPTW can be found in Rochat and Taillard, 1995, Tail

15、lard etal.1997, Chiang and Russell, 1997, Cordeau et al., 2001(tabu searches), Gambardella et al.,1999 (ant colony optimization), and Liu and Shen, 1999. Proposed metaheuristics so far show significant variability in performance. They often requireconsiderable computational effort and therefore fail

16、 to convincingly provide a single robust and successful technique. Recently, a new memetic or parallel hybrid genetic algorithm (PHGA) forthe VRPTW has been successfully developed Bergen Barkaoui and Braysy, 2002. Algorithms is a population-based approach for heuristic search in optimization problem

17、sMoscato, 1989. They have shown that they are orders of magnitude faster than traditional genetic algorithms for some problem domains. Basically, they combine local search heuristics with mutation and crossover operators. For this reason, some researchers have viewed them as hybrid genetic algorithm

18、s or genetic local search. Our approach is based on a new concept that combines constrained parallel co-evolution of two populations and partial temporal constraint relaxation to improve solution quality. The firs population evolves individuals to minimize the total traveled distance while the secon

19、d focuses on minimizing temporal constraint violation in trying to generate a feasible solution. Imposing a constant number of tours for each solution of a given population, temporal constraint relaxation allows escaping local minima while progressively moving toward a better solution. Populations i

20、nteract with one another whenever a new feasible solution emerges, reducing by one the number of tours imposed on future solutions. New genetic operators have been designed to maximize the number of customers served within their time intervals first, and then temporal constraint relaxation is used t

21、o insert remaining unvisited customers. Key principles and variants emerging from recent promising techniques are also captured to further diversify and intensify the search. As a result, even though the algorithm is more robust, efficient, stable and highly competitive, prohibitive computational co

22、st of key genetic operators and overall run-time still remain a sensitive issue to be satisfactorily addressed. The main contribution of this paper is to further improve the PHGA technique by developing an efficient parallel implementation based upon a master-slave message-passing paradigm(networked

23、 parallel computing) in order to significantly reduce run-time. The master processing element controls the execution of the algorithm, synchronizes atomic genetic operations and handles the parent selection process while the slave processing elements concurrently executereproduction and mutation ope

24、rators. Current and new genetic operators have been designed and revisited to reduce processor starvation over each generation. The paper is outlined as follows. Section 2 introduces the basic concepts of the proposed parallel hybrid genetic algorithm. The basic principles and features of the algori

25、thm are first described. Details on the parallel implementation of the algorithm are then given. Section 3 presents the results of a computational experiment to assess the value of the proposed approach and reports a comparative performance analysis to alternate methods. Finally, a summary is presen

26、ted in Section 4.2. Parallel Hybrid Genetic Algorithm2.1 General DescriptionThe proposed algorithm relies upon constrained parallel co-evolution and partial constraintrelaxation. Two populations Pop, and Pope, primarily formed of non-feasible solution individuals, are evolving concurrently, each wit

27、h their own objective functions. Pop, contains at least one feasible solution and is used to minimize total traveled distance while Pope focuses on minimizing constraint violation. Constrained to a fixed number of tours over the some population, solution individuals differ by exactly one route acros

28、s both populations. Parallel evolution is interrupted whenever a new best feasible solution is obtained. Populations are then reinitialized and co-evolution resumed, while decreasing the number of routes associated with solution individuals by one. The number of tours imposed on solution individuals

29、 in Pop, and Pope are R,; and R,;。一1，respectively. R,; refers to the number of routes found in the best feasible solution obtained so far. As a new feasible solution emerges from Pope, population Pop, is replaced by Pope, R,; is updated and, Pope is reinitialized with the revised number of tours (R.

30、。一1)，using the RSS_ M mutation operator. In addition, a post-processing procedure (RC_ M) aimed at reordering customers, is applied to further improve the new best solution. Theevolutionary process is repeated until a predefined stopping condition is met. The proposed approach uses a steady-state ge

31、netic algorithm that involves overlapping populations. At first, new individuals are generated and added to the current population Popp. The process continues until the overlapping population outnumbers the initial population by up. Then, the up worst individuals are eliminated to maintain populatio

32、n size using the following individual evaluation: The proposed evaluation expression indicates that better individuals generally (but notnecessarily) include fewer routes, and smaller total traveled distance, while satisfying temporalconstraints. The general algorithm is as follows:InitializationRep

33、eat p=1 Repeat evolve population Pope一new generation For j=1二n, do Select two parents from Pope Generate a new solution S using recombination and mutation operators associated with Pope Add S to Pope end for Remove the n, worst individuals from Pope using the evaluation function (1). P=P刊 Until (all

34、 populations Pope have been considered) if (Pops includes a new best feasible solution) then eliminate all Pop, individuals Set Pop=Pops Modify Pops solutions by applying RSS_ M reduces number of routes by one. End if Apply RC_ M on the best solution customer reorderingDntil (convergence criteria or

35、 max number of generations)Feasible solutions for initial populations are first generated using a sequential insertion heuristicin which customers are inserted in random order at randomly chosen insertion positions withinroutes. The initialization procedure then proceeds as follows:For p=1二2 do revi

36、sit Pop, and Pops For j=1二n, do Generate a new solution S using the EE一 M mutator (defined in Section 2.3.2) Add S in Pope End for Remove the n, worst individuals from Pope using Evczl;End forDetermine Rm;, the minimum number of tours associated with a feasible solution in Pop, or Pops.Replicate (if

37、 needed) best feasible solution (Rm; routes) in Pop,.Replace Pop, individuals with Rm;-route solutions using the procedure RI(Rm;).Replace Pops members with Rm;-1 route solutions using the procedure RI(Rm;-1).RI(r) is a re-initialization procedure creating an r-route solution. It first generates r o

38、ne-customerroutes formed from randomly selected customers. Then, it uses the insertion procedure proposedby Liu and Shen Liu and Shen, 1999 to insert as many customers as possible without violatingtime window constraints. Accordingly, customer route-neighborhoods are repeatedly examined2.3 Genetic O

39、peratorsThe proposed genetic operators mostly rely on two basic principles. First, for a given number oftours, an attempt is made to construct feasible solutions with as many customer visits as possible.Second, the remaining customers are inserted into existing routes through temporal constraintrela

40、xation. Constraint violation is used to restrict the total number of routes to a constant value.The proposed genetic operators incorporate some key features of the best heuristic routing techniques such as Solomons insertions heuristic Il Solomon, 1987 large neighborhood searchShaw, 1998 and the rou

41、te neighborhood-based two一stage metaheuristic (RNETS) Liu andShen, 1999. Details on the recombination and mutation operators used are given in the nextsections.2.3.1 RecombinationThe insertion-based IB_ X (k) recombination operator creates an offspring by combining, one at a time, k routes of parent

42、 solution P, with a subset of customers, formed by nearest-neighborroutesr2in parent solution P2. The routes (ri) are selected either randomly, with a probability proportional to the relative number of customers or based on the average distance separating consecutive customers on the routes. A remov

43、al procedure is first carried out to remove from r, some key customers believed to be most suitably relocated within some alternate routes. More precisely, the stochastic customer removal procedure removes either randomly some customers, customers rather distant from their successors, or customers w

44、ith waiting times. Then, a modified insertion heuristic of Solomon, 1987 is applied to build a feasible route considering the modified partial route r, as the initial solution and unrouted customers in routesr2 for insertion. The I1 standard insertion heuristic of Solomon, 1987 is coupled to a rando

45、m customer selection procedure, to choose the next candidate customer to be routed. Once the construction of the child route is completed, and reinsertion is no longer possible, a new route construction cycle is initiated. The overall process is repeated for the k routes selected from P. Finally, if

46、 necessary, the child inherits the remaining diminished routes of P.If unrouted customers still remain, additional routes are built using a nearest-neighbor procedure of Solomon, 1987. The whole process is then iterated once more to generate a second child by interchanging the roles of P and P2. Fur

47、ther details of the operator may be found in Berger and Barkaoui, 2000. In order to keep the number of routes of a child solution identical to its parents, a post-processing procedure is applied. If the solution has a larger number of routes thanexpected, the RSS_ M (Section 2.3.2) procedure is used repeatedly to reduce the number of routes. Conversely, for solutions having a smaller number of routes, new feasible routes are constructed repeatedly by breaking the most populated route in two until the targeted number of routes is obtained.