Przegląd badań wybranych problemów optymalizacyjnych

Woch, M.

Artykuł - szczegóły

Tytuł artykułu

Przegląd badań wybranych problemów optymalizacyjnych

Autorzy

Woch M.

Identyfikatory

Warianty tytułu

Selected optimisation problems researches survey

Języki publikacji

Abstrakty

The article briefly presents Traveling Salesman Problem, Vehicle Routing Problem and Vehicle Routing Problem with Time Windows researches history. In this work researches and publications related to these problems are presented.

Artykuł omawia historię badań nad problemami komiwojażera, dostaw oraz dostaw z oknami czasowymi. W pracy prezentowane są badania i publikacje związane z tymi problemami optymalizacyjnymi. Artykuł ma charakter przeglądowy i jako taki nie omawia uzyskanych wyników przez poszczególnych badaczy.

Słowa kluczowe

VRP VRMTP simulated annealing local search tabu search genetic algorithm

VRP VRMTP wyżarzanie symulowane przeszukiwanie lokalne przeszukiwanie tabu algorytm genetyczny

Wydawca

Wydawnictwo Politechniki Śląskiej

Czasopismo

Studia Informatica

Rocznik

2007

Tom

Vol. 28, nr 4

Strony

81--93

Opis fizyczny

bibliogr. 72 poz.

Twórcy

autor

Woch M.

Instytut Informatyki Politechniki Śląskiej, Gliwice, ul.Akademicka 16, tel.: 032-2371817, marcin.woch@us.edu.pl

Bibliografia

1. Antes J., Derigs U.: A New Parallel Tour Construction Algorithm for the Vehicle Routing Problem with Time Windows. Working Paper, Department of Economics and Computer Science, University of Koln, Germany, 1995.
2. Bachem A., Hochstattler W., Malich M.: The Simulated Trading Heuristic for Solving Vehicle Routing Problems. Disc. App. Math. 65,1996, s. 47-72.
3. Backer De B., Furnon V., Kilby P., Prosser P., Shaw P.: Solving Vehicle Routing Problems Using Constraint Programming and Metaheuristics. J. of Heuristics 6, 2000, s. 501-5-523.
4. Baker E. K., Schaffer J. R.: Solution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints. Am. J. Math. Mgmt. Sci. 6, 1986, s. 261-300.
5. Barnes J. W., Carlton W. B.: A Tabu Search Approach to the Vehicle Routing Problem with Time Windows. Presented at the Fall 1995 INFORMS Conference, New Orleans, LA, 1995.
6. Berger, Salois J. M., Begin R.: A Hybrid Genetic Algorithm for the Yehicle Routing Problem with Time Windows. Presented at the AI 98 12th Canadian Conference on Artificial Intelligence, June 1998, Vancouver, Canada, 1998.
7. Blanton J. L., Wainwright R. L.: Multiple Vehicle Routing with Time and Capacity Constraints using Genetic Algorithms. to Proceedings of the Fifth International Conference on Genetic Algorithms, S. Forrest (eds.). Morgan Kaufmann Publishing, San Francisco, 1993, s. 452-^459.
8. Bramel J., Simchi-Levi D.: Probabilistic Analyses and Practical Algorithms for the Vehicle Routing Problem with Time Windows. Opns. Res. 44,1996, s. 501-509.
9. Brandao J.: Metaheuristic for the Yehicle Routing Problem with Time Windows, to Metaheuristics - Advances and Trends in Local Search Paradigms for Optimization. Kluwer Academic Publishers, Boston, 1999, s. 19-36.
10. Braysy O.: A Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows. Licentiate thesis. Department of Mathematics and Statistics, University of Yaasa, Finland, 1999.
11. Braysy O.: A New Algorithm for the Vehicle Routing Problem with Time Windows Based on The of a Genetic Algorithm and Route Construction Heuristics. Proceedings of the University of Yaasa, Research papers 227, Vaasa, Finland, 1999.
12. Braysy O., Berger J., Barkaoui M.: A New Hybrid Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows. Presented at the Route 2000-Workshop, Skodsborg, Denmark, August 2000.
13. Braysy O., Berger J., Barkaoui M.: A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows.
14. Braysy O., Gendreau M.: Metaheuristics for the Vehicle Routing Problemwith Time Windows. Oslo 2001.
15. Braysy O.: A Reactive Variable Neighborhood Search for the Vehicle Routing Problem with Time Windows. Oslo 2001.
16. Braysy O.: Five Local Search Algorithms for the Vehicle Routing Problem with Time Window. Vaasa2001.
17. Carlton W. B.: A Tabu Search Approach to the General Vehicle Routing Problem. Ph.D. Dissertation. Mechanical Engineering Department, University of Texas, Austin, U.S.A, 1995.
18. Caseau V., Laburthe F.: Heuristics for Large Constrained Vehicle Routing Problems. J. of Heuristics 5,1999, s. 281+303.
19. Cerny V.: A thermodynamical approach to traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applic., 1985,45, s. 41+45.
20. Chiang W. C., Russell R. A.: Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows. Annals Opns. Res. 63, 1996, s. 3+27.
21. Chiang W. C., Russell R. A.: A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows. INFORMS J. on Computing 9,1997, s. 417-430.
22. Clarke G., Wright J. W.: Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Opns. Res. 12,1964, s. 568+581.
23. Cordeau J.-F., Laporte G., Mercier A.: Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Publication CRT-2000-03. University of Montreal, Canada, 2000.
24. Cordone R., Wolfler-Calvo R.: A Heuristic for the Vehicle Routing Problem with Time Windows. Internal Report, Department of Electronics and Information, Polytechnic of Milan, Milan, Italy. To appear in J. of Heuristics, 1998.
25. Czech Z. J., Czamas P.: Parallel simulated annealing for the vehicle routing problem with time windows.
26. Czech, Z.J.: Parallel simulated annealing for the delivery problem. Proc. of the 9th EuromicroWorkshop on Parallel and Distributed Processing, Mantova, Italy, (February 7-9, 2001), s. 219-226.
27. Desrochers M.: Shortest path problems with resource constraints. Technical Report GERAD G-88-97, Ecole des Hautes Etudes Commerciales, Montreal 1988.
28. Desrochers M., Soumis F., A column generation approach to the urban transit crew shedding problem. Transport. Sci., 23,1989, s. 1+13.
29. Dorigo M., Gambardella L. M.: Ant colonies for the traveling salesman problem. TR/IRIDIA/1996-3, Belgium, 1996.
30. Dorigo M., Maniezzo V., Colomi A.: The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Mań, and Cybernetics-Part B, Vol.26, No.l, 1996, s. l-s-13.
31. Gambardella L. M., Taillard E., Agazzi G.: MACS-YRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows. New Ideas in Optimization, D. Corne, M. Dorigo and F. Glover (eds), McGraw-Hill, London 1999, s. 63-76.
32. Gehring H., Homberger J.: A Parallel Hybrid Evolutionary Metaheuristic for the Yehicle Routing Problem with Time Windows. In Proceedings of EUROGEN99 - Short Course on Evolutionary Algorithms in Engineering and Computer Science, Reports of the Department of Mathematical Information Technology, Series A. Collections, No. A 2/1999, K. Miettinen, M. Makela and J. Toivanen (eds.). University of Jyvaskyla, Jyvaskyla, 1999, s. 57-64.
33. Glover F.: Multilevel Tabu Search and Embedded Search Neighborhoods for the Traveling Salesman Problem. Working Paper. College of Business & Administration, UniversityofColorado, Boulder, 1991.
34. Glover F.: New Ejection Chain and Alternating Path Methods for Traveling Salesman Problems. In Computer Science and Operations Research: New Developments in Their hiterfaces, O. Balci, R. Sharda, and S. Zenios (eds.). Pergamon Press, Oxford 1992, s. 449-509.
35. Homberger J., Gehring H.: Two Evolutionary Meta-heuristics for the Vehicle Routing Problem with Time Windows. INFORMS J. on Computing 37,1999, s. 297-318.
36. Kilby P., Prosser P., Shaw P.: Guided Local Search for the Vehicle Routing Problem with Time Windows. In META-HEURISTICS Advances and Trends in Local Search Paradigms for Optimization, S. Voss, S. Martello, I. H. Osman and C. Roucairol (eds.). Kluwer Academic Publishers, Boston, 1999, s. 473-486.
37. Kirkpatrick S., Gellat C.D., Yecchi M.P.: Optimization by simulated annealing. 1983, Science, 220, s. 671-680.
38. Kontoravdis G. A., BARD J. F.: A GRASP for the Vehicle Routing Problem with Time Windows. J. on Computing 7, 1995, s. 10-23.
39. Liu F-H., Shen S-Y.: A Route-neighborhood-based Metaheuristic for Vehicle Routing Problem with Time Windows. Eur. J. Opnl Res. 118,1999, s. 485-504.
40. Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Teller A.H., Teller E.: Equation of state calculation by fast computing machines. Journal of Chem. Phys., 1953, 21, s. 1087-1091.
41. Mladenovic N., Hansen P.: Variable Neighborhood Search. Computers & Opns. Res. 24, 1997, s. 1097*1100.
42. Or L: Traveling Salesman-Type Combinatorial Problems and their Relation to the Logistics of Regional Blood Banking. Ph.D. Thesis. Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 1976.
43. Osman I. H.: Metastrategy Simulated Annealing and Tabu Search Algorithms for the Yehicle Routing Problems. Annals Opns. Res. 41,1993, s. 421*452.
44. Potvin J-Y., Rousseau J-M.: A Parallel Route Building Algorithm for the Yehicle Routing and Scheduling Problem with Time Windows. Eur. J. Opnl. Res. 66,1993, s. 331*340.
45. Potvin J-Y, Robillard C.:. Clustering for Vehicle Routing with a Competitive Neural Network. Neurocomputing 8,1995, s. 125*139.
46. Porvin J-Y., Rousseau J-M.: Ań Exchange Heuristic for Routing Problems with Time Windows. J. Opnl. Res. Society46, 1995, s. 1433*1446.
47. Potvin J-Y, Dube D., Robillard C.: A Hybrid Approach to Vehicle Routing Using Neural Networks and Genetic Algorithms. Applied Intelligence 6,1996, s. 241*252.
48. Potvin J-Y., Bengio S.: The Yehicle Routing Problem with Time Windows Part II: Genetic Search. J. on Computing 8,1996, s. 165*172.
49. Potvin J-Y., Kervahut T., Garcia B. L., Rousseau J-M.: The Yehicle Routing Problem with Time Windows Part I: Tabu Search. J. on Computing 8,1996, s. 157*164.
50. Potvin J.-Y., Ichoua S., Gendreau M.: Yehicle dispatching with time-dependent travel limes. European Journal of Operational Research 144,2003, s. 379*396.
51. Potvin J.-Y., Ying X., Benyahia L: Yehicle routing and scheduling with dynamic travel times. Computers and Operations Research 33,2006, s. 1129-1137.
52. Rochat Y., Taillard E.: Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. J. of Heuristics l, 1995, s. 147*167.
53. Rousseau L.-M., Gendreau M., Pesant G.: Using Constraint-Based Operators to Solve the Vehicle Routing Problem with Time Windows. Working Paper. Centre for Research on Transportation, Universiry of Montreal, Canada. To appear in J. of Heuristics, 2000.
54. Russell R.: Hybrid Heuristics for the Vehicle Routing Problem with Time Windows. Trans. Sci. 29,1995, s. 156*166.
55. Russell R.: An Effective Heuristic for the M-tour Traveling Salesman Problem with Some Side Conditions. Opns. Res. 25,1997, s. 517*524.
56. Savelsbergh M. W. P.: The Vehicle Routing Problem with Time Windows: Minimizing Route Duration.ORSA Journal on Computing 4,1992, s. 146*154.
57. Shaw P.: A New Local Search Algorithm Providing High Quality Solutions to Yehicle Routing Problems. Working Paper. Department of Computer Science, University of Strathclyde, Glasgow, Scotland, 1997.
58. Shaw P.: Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. In Principles and Practice of Constraint Programming - CP98, Lecture Notes in Computer Science, M. Maher and J.-F. Puget (eds.). Springer-Verlag, New York 1998,8.417+431.
59. Schulze J., Fanie T.: A Parallel Algorithm for the Vehicle Routing Problem with Time Window Constraints. Annals Opns. Res. 8,19996, s. 585-607.
60. Solomon M.: Algorithms for the Yehicle Routing and Scheduling Problem with Time Windows Constraints. Oper. Res. 35,1987, s. 254+265.
61. Solomon M., Desrosiers J.: Time windows constrained routing and scheduling problems. Transp. Sci., 22,1988, s. 1-13.
62. Taillard E., Badeau P., Gendreau M., Guertin F., Potvin J-Y.: A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows. Trans. Sci. 31,1997, s. 170-186.
63. Thangiah Sam R., Kendall N., Juell P.: GIDEON: A Genetic Algorithm System for Vehicle Routing Problems with Time Windows. Proceedings of the Seventh IEEE Conference on Artificial Intelligence Applications, Miami, Florida, 1991, s. 322-328.
64. Thangiah S., Osman L, Sun T.: Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with Time Windows. Working Paper UKC/IMS/OR94/4. Institute of Mathematics and Statistics, University of Kent, Canterbury 1994.
65. Thangiah S.: Vehicle Routing with Time Windows Using Genetic Algorithms. In Application Handbook of Genetic Algorithms: New Frontiers, Yolume II, L. Chambers (eds.). CRC Press, Boca Raton, 1995, s. 253-277.
66. Thangiah S. R., Osman I. H., Yinayagamoorthy R., Sun T.: Algorithms for the Vehicle Routing Problems with Time Deadlines. Am. J. Math. Mgmt. Sci. 13,1995, s. 323-355.
67. Thangiah Sam R.: A Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Practical Handbook of Genetic Algorithms, Volume III: Complex Structures, L. Chambers (Ed.), CRC Press, 1999,8.347-381.
68. Thompson P. M., Psaraftis H. N.: Cyclic Transfer Algorithms for Multivehicle Routing and Scheduling Problems. Opns. Res. 41,1993, s. 935-946.
69. Van Landeghem H. R. G.: A Bi-criteria Heuristic for the Yehicle Routing Problem with Time Windows. Eur. J. Opns. Res. 36,1988, s. 217-226.
70. Voudouris C.: Guided Local Search for Combinatorial Problems. Ph.D. thesis. Department of Computer Science, University of Essex, Colchester, UK, 1997.
71. Voudouris C., Tsang E.: Guided Local Search. Eur. J. Opns. Res. 113,1998, s. 80-119.
72. Woch M.: Rozwiązanie problemu dostaw z oknami czasowymi za pomocą symulowanego wyżarzania. ZN Pol. Śl. Studia Informatica Vol. 25, No. 2 (58), Gliwice 2004.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BSL5-0023-0034