«A Parallel Hybrid Evolutionary Metaheuristic for the Period Vehicle Routing Problem Dalessandro Soares Vianna, Luiz S. Ochi and L cia M. A. Drummond ...»
After y migrations y is an entry parameter, mi becomes capable of nishing its execution and consequently it activates qi, which keeps an array of n elements representing the state of the system. Each position i of the array of state may assume values true or false, indicating that the process mi is capable of nishing or not. When qi is activated, it updates the positon i in the array of state with true and initiates a broadcast so that the other arrays represent the current state of the system. This strategy of termination is based on a simpli cation of the algorithm for detection of stable conjunctive predicates presented in 6. A task mi will continue its execution, even when capable of nishing, until all processors are able to nish. This prevents a processor from being idle while other processors remain executing and still allows the improvement of the optimal solution while the application does not nish. When all elements of the array of state are true, termination is detected by qi and mi is informed to nish its execution. A task mi informs to qi the optimal solution so far whenever its champion chromosome is improved.
The strategy described above allows that the process, which is responsible for the PAR-HEM execution does not remain occupied with the communication required by migration of individuals, and termination of the PAR-HEM, simplifying its design and implementation.
As showed in 11, their algorihtm HGA presents the best results in terms of quality of solution among the existing heuristics in literature. Thus, we compared PAR-HEM with an adapted version of HGA, which is called here as Hybrid Evolutionary Metaheuristic HEM.
6000 5000 4000 3000 2000 1000
Figure 1 and Table 4 show a comparison in terms of average costs between the algorithms HEM and PAR-HEM. Each problem of the Table 3 was executed 3 times. Data corresponding to problem 01 were not avalibale. Figure 1 and Table 4 show that PAR-HEM achieved the best results for 11 problems while HEM achieved the best results in 7 problems. Problem 15 presented identical results. Figure 2 and Table 5 show the average time in seconds required by the algorithms HEM and PAR-HEM. Figure 3 shows the speedup obtained by PARHEM. Sometimes the speedup exceeds the number of processors. In these cases the PAR-HEM converges faster than HEM. This may happen because the populations generated are di erent.
We also compared PAR-HEM with the heuristics CGL and CGW. Table 6 presents a comparison among PAR-HEM and these heuristics in terms of cost.
5 Concluding Remarks Our results presented in Tables and Figures above, show signi cant advantages for PAR-HEM, not only with respect to the running time but also with respect to the search quality.
The partial results exhibited by PAR-HEM qualify it as a promissing way to obtain good aproximate solutions of PVRP since the solutions shown in this paper were obtained by initial tests, without an accurate de nition of the best parameters for PAR-HEM. On the other hand, the results presented by sequential heuristics were obtained by exhaustive tests with several parameters.
10000 4 8000 3 6000 2 4000 1 2000 0 0 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
1. Back, T., Fogel, D.B., Michalewicz, Z.: Handbook of Evolutionary Computation, University Oxford Press, NY, 1996.
2. Christo des, N., Beasley, J.E.: The Period Routing Problem, Networks 14 1984 237 - 256.
3. Clarke, G., Wright, J.: Scheduling of Vehicles From a Central Depot to a Number of Delivery Points. Operations Research 12-4 1964 568-581.
4. Cordeau, J.F., Gendreau, M., Laporte, G.: A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems. Technical Report 95-75, Center for Research on Transportation, Montr al 1995.
5. Dueck, G.: New Optimization Heuristics: The Great Deluge Algorithm and the Record-to-Record Travel, Scienti c Center Technical Report, IBM Germany, Heidelberg Scienti c Center 1990.
6. Drummond, L.M.A., Barbosa, V.C.: Distributed Breakpoint Detection in Messagepassing programs, J. of Parallel and Distributed Computing 39 1996 153-167.
7. Golden, B.L., Chao, I.M., Wasil, E.: An Improved Heuristic for the Period Vehicle Routing Problem. Networks 1995, 25-44.
8. Ochi, L.S., Figueiredo, R.M.V., Drummond, L.M.A.: Design and Implementation of a Parallel Genetic Algorithm for the Travelling Purchaser Problem, ACM symposium on Applied Computing 1997 257-263.
9. Ochi, L.S., Vianna, D.S., Drummond, L.M.A.: A Parallel Genetic Algorithm for the Vehicle Routing Problem with Heterogeneous Fleet, Proc. of the BioSP3, Lecture Notes in Computer Science, Springer-Verlag 1388 1998 187-195.
10. Ribeiro, J.L.: An Object-oriented Programming Environment for Parallel Genetic Algorithms, Ph.D. Thesis, Dep. of Comp. Science, Univ. College London 1995.
11. Rocha, M.L., Ochi, L.S., Glover, F.: A Hybrid Genetic Algorithm for the Periodic Vehicle Routing Problem 1998 - To be published.
12. Snir, M., Otto, S.W., Huss-Lederman, S., Walker, D.W., Dongarra, J.: MPI: The Complete Reference, The MIT Press 1996.
This article was processed using the L TEX macro package with LLNCS style a