WWW.DISSERTATION.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Dissertations, online materials
 
<< HOME
CONTACTS



Pages:     | 1 ||

«A Parallel Hybrid Evolutionary Metaheuristic for the Period Vehicle Routing Problem Dalessandro Soares Vianna, Luiz S. Ochi and L cia M. A. Drummond ...»

-- [ Page 2 ] --

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.

Cost 9000

–  –  –

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.

Time(s) Speedup

–  –  –

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

–  –  –

References

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.

e

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

Pages:     | 1 ||


Similar works:

«UNIT-1 CANADIAN POETRY Structure 1.0 Objectives 1.1 Introduction 1.2 Pre-Confederation Period 1.2.1 The First Stirrings of the Poetic Culture 1.3 Confederation Period 1.3.1 Emergence of a National Literature 1.4 Modernist Period: 1.4.1 First Phase 1.4.2 Second Phase 1.4.3 Third Phase 1.5 Postmodernist /Contemporary Period 1.6 Let Us Sum Up 1.7 Review Questions 1.8 Bibliography 1.0 Objectives · To introduce the students to an understanding of the phases of Canadian poetic culture; · To...»

«From Black to White Hat Hacker Education in IT Security Trends and Questions Charif Bilal MSc. Information Security (Year 1) Luleå University of Technology, Sweden Abstract Education, training and awareness have been connected to information security recently. Although some companies started to implement awareness programs, user education is still a questionable fact. Electronic media such as TV, video and computer games can be of high influence on children. Criminals are most of the time...»

«DRUID Working Paper No. 06-22 How does Knowledge Transfer from Foreign Subsidiaries affect Parent Companies’ Innovative Capacity? By Lucia Piscitello and Larissa Rabbiosi www.druid.dk How does Knowledge Transfer from Foreign Subsidiaries affect Parent Companies’ Innovative Capacity? Lucia Piscitello Piazza L. da Vinci, 32 20133 Milano Italy Tel. +39 02 2399 2740 Fax +39 02 2399 2710 E-mail: lucia.piscitello@polimi.it Larissa Rabbiosi Piazza L. da Vinci, 32 20133 Milano Italy Tel. +39 02...»

«1 THE NEED FOR A THEISTIC SPIRITUAL STRATEGY We are not human beings having a spiritual experience; We are spiritual beings having a human experience. —Teilhard deChardin The end of the 20th century and dawn of the new millennium was characterized by a resurgence of interest in spiritual issues and faith within the American population. Leading mainstream news magazines and newspapers such as Time, Newsweek, and U.S. News and World Report featured cover stories on these issues (e.g., Kalb,...»

«Archive: eNewsletter December 2011                  UC Berkeley Department of Music   A Letter from the Chair  Featured Stories  A Music Student recently had the opportunity to accompany Chancellor Birgeneau to Shanghai . 4  Visiting Postdocs bring unique research interests and popular classes to the Music Department. . 4  Graduating student starts a musical theatre tradition ...»

«UNIVERSITY OF LAS PALMAS DE GRAN CANARIA DEPARTAMENT OF PHYSICAL EDUCACTION Doctoral Program: Motor Praxiology, Physical Education and Sport Training DOCTORAL THESIS BASKETBALL FROM THE PERSPECTIVE OF NON-LINEAR COMPLEX SYSTEMS YVES DE SAÁ GUERRA LAS PALMAS DE GRAN CANARIA, 2013 BASKETBALL FROM THE PERSPECTIVE OF NON-LINEAR COMPLEX SYSTEMS DOCTORAL THESIS By YVES DE SAÁ GUERRA, B.S. SCIENCES OF PHYSICAL ACTIVITY AND SPORT \ UNIVERSITY OF LAS PALMAS DE GRAN CANARIA, GRAN CANARIA, SPAIN 2013...»





 
<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.