Thủ Tục Dựa Trên Tìm Kiếm Tabu Để Giải Quyết Bài Toán Ba Lô 0-1 Nhiều Mục Tiêu: Trường Hợp Hai Mục Tiêu

Journal of Heuristics - Tập 6 - Trang 361-383 - 2000
Xavier Gandibleux1, Arnaud Freville1
1LAMIH-ROAD, UMR CNRS 8530, University of Valenciennes, Valenciennes Cedex, France

Tóm tắt

Trong bài báo này, chúng tôi xem xét việc giải quyết các bài toán ba lô 0-1 với nhiều mục tiêu tuyến tính. Chúng tôi trình bày một phương pháp tìm kiếm tabu nhằm tạo ra một xấp xỉ tốt cho tập hợp hiệu quả. Sơ đồ heuristic được bao gồm trong một khung không gian quyết định giảm thiểu. Trường hợp có hai mục tiêu được phát triển trong bài báo này. Các nguyên tắc TS được xem xét trong bối cảnh đa mục tiêu được thảo luận. Theo một cách tiếp cận triển vọng, một số biến thể của thuật toán được điều tra. Các thí nghiệm số được báo cáo và so sánh với các giải pháp hiệu quả chính xác có sẵn. Những giải thích trực quan cho hành vi thực nghiệm quan sát được của quy trình và các câu hỏi mở được thảo luận.

Từ khóa

#Bài toán ba lô 0-1 #tối ưu hóa đa mục tiêu #tìm kiếm tabu #phương pháp heuristic #hiệu quả.

Tài liệu tham khảo

Ben Abdelaziz, F., S. Krichen, and J. Chaouachi. (1999). “An Hybrid Metaheuristic for the MultiObjective Knapsack Problem. ” In St. Voss, S. Martello, I. Osman, and C. Roucairol (eds.), Meta-Heuristics-Advances and Trends in Local Search Paradigms for Optimization. Kluwer, pp. 205–212.

Brandimarte, P. and M. Calderini. (1995). “A Hierarchical Bicriterion Approach to Integrated Process Plan Selection and Job Shop scheduling. ” Int. J. Prod. Res. 33(1), 161–181.

Czyzak, P. and A. Jaszkiewicz. (1998). “Pareto Simulated Annealing-A Metaheuristic Technique for Multiple Objective Combinatorial Optimization. ” Journal of Multicriteria Decision Analysis 7, 34–47.

Dahl, G., K. Jornsten, and A. Lokketangen. (1995). “A Tabu Search Approach to the Channel Minimization Problem. ” ICOTA'95, 9p.

Fréville, A. and G. Plateau. (1993). “Sac-à-dos multidimensionnel en variables 0–1: encadrement de la somme des variables à l'optimum. ” RAIRO 27(2), 169–187.

Fréville, A. and G. Plateau. (1994). “An Efficient Preprocessing Procedure for the Multidimensional 0–1 Knapsack Problem. ” Discrete Applied Mathematics, 189–212.

Gandibleux, X., N. Mezdaoui, and A. Fréville. (1997a). “A Multi-Objective Tabu Search Procedure to Solve Combinatorial Optimization Problems. ” In R. Caballero, F. Ruiz, and R. Steuer (eds.), Advances in Multiple Objective and Goal Programming. Lecture Notes 455 in Economics and Mathematical Systems, Springer, pp. 291–300.

Gandibleux, X., N. Mezdaoui, and E.L.B. Ulungu. (1997b). “Simulated Annealing Versus Tabu Search Multi-Objective Approaches to the MultiObjective KnapSack Problem. ” 13th International Conference on Multiple Criteria Decision-Making, Jan. 6–10, 1997, Cape Town, South Africa.

Geoffrion, A.M. (1974). “Lagrangean Relaxation for Integer Programming. ” Mathematical Programming Study 2, 82–114.

Glover, Fr. (1965). “A Multiphase Dual Algorithm for the Zero-One Integer Programming Problem. ” Operations Research 13(6), 879–919.

Habenicht, W. (1982). “Quad Trees. A Data Structure for Discrete Vector Optimization Problems. ” In P. Hansen (ed.), Springer-Verlag, pp. 136–145. Lecture Notes “Essays and surveys on MCDM”.

Hansen, M.P. (1997). “Tabu Search for MultiObjective Optimization: MOTS. ” 13th International Conference on Multiple Criteria Decision-Making, Jan. 6–10, 1997, Cape Town, South Africa.

Hertz, A., B. Jaumard, C.C. Ribeiro, and W.P. Formosinho. (1994). “A MultiCriteria Tabu Search Aproach to Cell Formation Problems in Group Technology with Multiple Objectives. ” Recherche Opérationnelle-Operations Research 28(3), 303–328.

Malakooti, B., J. Wang, and E.C. Tandler. (1990). “A Sensor-Based Accelerated Approach for Multi-Attribute Machinability and Tool Life Evaluation. ” International Journal of Production Research 28, 2373.

Martello, S. and P. Toth. (1990). Knapsack Problems: Algorithms and Computer Implementations. New York: Wiley.

Martello, S., D. Pisinger, and P. Toth. (1997). “New Trends in Exact Algorithms for the 0–1 Knapsack Problem. ” EURO/INFORMS-97, Barcelona, Spain, pp. 151–160.

Mezdaoui, N., X. Gandibleux, and A. Fréville. (1997). “Decision Space Exploration Techniques in the MultiObjective Tabu Search Procedure Applied on the 0–1 MOKP. ” EURO XV-INFORMS XXXIV, July 14–17, 1997, Barcelona, Spain.

Osman, I. and G. Laporte. (1996). “Metaheuristics: A Bibliography. ” Annals of Operations Research 63, 513–623.

Reeves, C. (1995). Modern Heuristic Techniques for Combinatorial Problems. London: McGrawHill.

Roy, B. and D. Bouyssou. (1993). Aide multicritère à la décision: méthode et cas. Gestion, Economica.

Savelsberg, M.W.P. (1994). “Preprocessing and Probing Techniques for Mixed Integer Programming Problems. ” ORSA Journal on Computing 6(4), 445–454.

Schaffer, J.D. (1985). “Multiple Objective Optimization using Vector Evaluated Genetic Algorithms. ” In Proc. of 1st Int. Conf. on G.A. and Their Applications, 1985, pp. 93–100.

Serafini, P. (1992). “Simulated Annealing for Multi Objective Optimization Problems. ” 10th Int. Conf. on MCDM Proc., Vol. 1, July 19–24, 1992, Taipei, Taiwan, pp. 87–96.

Steuer, R. (1986). Multiple Criteria Optimization: Theory, Computation and Application. New York: Wiley.

Sun, M. and R. Steuer. (1995). “Quad-Trees and Linear Lists for Identifying Non Dominated Criterion Vectors. ” Informs, Journal on Computing 8(4), Fall 1996.

Teghem, J and E.L. Ulungu. (1997). “Bicriteria Assigment Problem. ” MAMDM Int. Conf, May 14–16, 1997, Mons, Belgium, pp. 144–147.

Ulungu, E.L.B. and J. Teghem. (1994). “Multi-Objective Combinatorial Optimization Problems: A Survey. ” Journal of Multi-Criteria Decision Analysis 3, 83–104.

Ulungu, E.L. and J. Teghem. (1995). “The Two Phases Method: An Efficient Procedure to Solve Bi-Objective Combinatorial Optimization Problems. ” Foundations of Computing and Decision Sciences 20(2), 149–165, 1995.

Ulungu, E.L.B., J. Teghem, and Ph. Fortemps. (1995). “Heuristics for Multi-objective Combinatorial Optimization Problems by Simulated Annealing. ” In J. Gu, G.C.Q. Wei, and Sh. Wang (eds.), MCDM: Theory and Applications SCI-TECH Information Services, pp. 228–238.

Vanderpooten, D. (1990). “Multiobjective Programming: Basic Concepts and Approaches. ” In R. Slowinski and J. Teghem (eds.), Stochastic versus Fuzzy Approaches to Multiobjective Mathematical Programming under Uncertainty Kluwer, pp. 7–22.

Van Wassenhove, L. and L. Gelders. (1980). “Solving a Bicriterion Scheduling Problem. ” European Journal of Operational Research 4, 42–48.

WWW Site, LAMIH-ROAD, UVHC, numerical instances for MultiObjective MetaHeuristics. http://www.univ-valenciennes.fr/ROAD/MCDM.html, Université de Valenciennes.

Yu, G. (1990). “Algorithms for Optimizing Piecewise Linear Functions and for Degree Constrained Minimum Spanning Tree Problems. ” PhD, 09–11–01, Wharton School, University of Pennsylvania.