Abstract
Solving the Tchebycheff program means optimizing a particular scalarizing function. When dealing with combinatorial problems, however, it is due to computational intractability often necessary to apply heuristics and settle for approximations to the optimal solution. The experiments in this paper suggest that for the multiobjective traveling salesman problem (moTSP) instances considered, heuristic optimization of the Tchebycheff program gives better results when using a substitute scalarizing function instead of the Tchebycheff based one to guide the local search path. Two families of substitute scalarizing functions are considered.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ben Abdelaziz, F., J. Chaouchi, and S. Krichen. (1997). “A Hybrid Heuristic for Multiobjective Knapsack Problems. ” Technical Report, Institut Supérieur de Gestion, Tunisie, submitted for publication.
Czyzak, P. and A. Jaszkiewicz. (1998). “Pareto Simulated Annealing-A Metaheuristic Technique for Multiple Objective Combinatorial Optimization. ” Journal of Multi-Criteria Decision Analysis 7, 34–47.
Fonseca, C.M. and P.J. Fleming. (1995). “An Overview of Evolutionary Algorithms in Multiobjective Optimization. ” Evolutionary Computation 3, 1–16.
Gandibleux, X., N. Mezdaoui, and A. Fréville. (1997). “A Tabu Search Procedure to Solve Multiobjective Combinatorial Optimization Problems. ” In R. Caballero and R. Steuer (eds.), Proceedings Volume of MOPGP’ 96. Springer-Verlag. LNEMS 455, 291–300.
Gardiner, L.R. and R.E. Steuer. (1994). “Unified Interactive Multiple Objective Programming. ” European Journal of Operational Research 74, 391–406.
Glover, F. (1989). “Tabu Search-Part I.” ORSA Journal on Computing 1(3), 190–206.
Glover, F. (1990). “Tabu Search-Part II.” ORSA Journal on Computing 2(1), 4–32.
Hansen, M.P. (1997). “Tabu Search for Multiobjective Optimization: MOTS. ” Paper Presented at the 13th International Conference on Multiple Criteria Decision Making, University of Cape Town, Jan. 6–10, 1997.
Knox, J. (1994). “Tabu Search Perfomance on the Symmetrical Traveling Salesman Problem. ” Computers and Operations Research 21(8), 867–876.
Reinelt, G. (1995). TSPLIB, available at URL http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html.
Serafini, P. (1987). “Some Considerations about Computational Complexity for Multiobjective Combinatorial Problems. ” Lecture Notes in Economics and Mathematical Systems 294, 222–232.
Serafini, P. (1992). “Simulated Annealing for Multi Objective Optimization Problems. ” In Proceedings of the Xth International Conference on MCDM, Tapei, July 19–24, 1992, pp. 87–96.
Steuer, R.E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons.
Ulungu, E.L. and J. Tegham. (1994). “Multi-Objective Combinatorial Optimization Problems: A Survey. ” Journal of Multiple-Criteria Decision Analysis 3, 83–104.
Ulungu, E.L., J. Tegham, and P. Fortemps. (1995). “Heuristics for Multiobjective Combinatorial Optimization Problems by Simulated Annealing. ” In J. Gu, G. Chen, Q. Wei, and S. Wang (eds.), MCDM: Theory and Application. Beijing: Sciences-Techniques, pp. 229–238.
Wierzbicki, A.P. (1986). “On the Completeness and Constructiveness of Parametric Characterizations to Vector Optimization Problems. ” OR Spektrum 8, 73–87.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Hansen, M.P. Use of Substitute Scalarizing Functions to Guide a Local Search Based Heuristic: The Case of moTSP. Journal of Heuristics 6, 419–431 (2000). https://doi.org/10.1023/A:1009690717521
Issue Date:
DOI: https://doi.org/10.1023/A:1009690717521