Florios, Kostas and Mavrotas, George (2014): Generation of the exact Pareto set in multiobjective traveling salesman and set covering problems. Published in: Applied Mathematics and Computation , Vol. 237, (15 June 2014): pp. 119.

PDF
MPRA_paper_105074.pdf Download (1MB)  Preview 
Abstract
The calculation of the exact set in MultiObjective Combinatorial Optimization (MOCO) problems is one of the most computationally demanding tasks as most of the problems are NPhard. In the present work we use AUGMECON2 a MultiObjective Mathematical Programming (MOMP) method which is capable of generating the exact Pareto set in MultiObjective Integer Programming (MOIP) problems for producing all the Pareto optimal solutions in two popular MOCO problems: The MultiObjective Traveling Salesman Problem (MOTSP) and the MultiObjective Set Covering problem (MOSCP). The computational experiment is confined to twoobjective problems that are found in the literature. The performance of the algorithm is slightly better to what is already found from previous works and it goes one step further generating the exact Pareto set to till now unsolved problems. The results are provided in a dedicated site and can be useful for benchmarking with other MOMP methods or even MultiObjective MetaHeuristics (MOMH) that can check the performance of their approximate solution against the exact solution in MOTSP and MOSCP problems.
Item Type:  MPRA Paper 

Original Title:  Generation of the exact Pareto set in multiobjective traveling salesman and set covering problems 
Language:  English 
Keywords:  multiobjective, traveling salesman problem, set covering problem, εconstraint, exact Pareto set 
Subjects:  C  Mathematical and Quantitative Methods > C6  Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C61  Optimization Techniques ; Programming Models ; Dynamic Analysis C  Mathematical and Quantitative Methods > C6  Mathematical Methods ; Programming Models ; Mathematical and Simulation Modeling > C63  Computational Techniques ; Simulation Modeling 
Item ID:  105074 
Depositing User:  Kostas Florios 
Date Deposited:  01 Jan 2021 12:59 
Last Modified:  01 Jan 2021 12:59 
References:  R.E. Steuer, Multiple Criteria Optimization. Theory, Computation and Application, Krieger, Malabar FL, 1986. C.L. Hwang, A. Masud, Multiple Objective Decision Making. Methods and Applications: A state of the art survey, Lecture Notes in Economics and Mathematical Systems, 164, SpringerVerlag, Berlin, 1979. M. Ehrgott, X. Gandibleux, A survey and annotated bibliography of multiobjective combinatorial optimization, OR Spectrum 22 (2000) 425460. C.A. Coello Coello, D.A. Van Veldhuizen, G.A. Lamont, Evolutionary Algorithms for Solving MultiObjective Problems, Kluwer Academic Publishers, Boston MA, 2002. G. Mavrotas, K. Florios, An improved version of the augmented εconstraint method (AUGMECON2) for finding the exact pareto set in multiobjective integer programming problems, Applied Mathematics and Computation 219 (2013) 96529669. T. Lust, J. Teghem, The multiobjective traveling salesman problem: A survey and a new approach, Studies in Computational Intelligence 272 (2010) 119141. R. Fischer, K. Richter, Solving a multiobjective traveling salesman problem by dynamic programming, Mathematische Operationsforschung und Statistik  Series Optimization 13 (1982) 247252. P.C. Borges, M.P. Hansen, A basis for future successes in multiobjective combinatorial optimization, Technical Report, Institute of Mathematical Modelling, Technical University of Denmark, 1998. M.P. Hansen, Use of substitute scalarizing functions to guide a local search based method: The case of moTSP, Journal of Heuristics 6 (2000) 419431. A. Jaszkiewicz, Genetic local search for multiobjective combinatorial optimization, European Journal of Operational Research 137 (2002) 5071. L. Paquete, T. Stützle, A twophase local search for the biobjective traveling salesman problem, Lecture Notes in Computer Science 2632 (2003) 479493. L. Paquete, T. Stützle, Design and analysis of stochastic local search for the multiobjective traveling salesman problem, Computers & Operations Research 36 (2009) 26192631. T. Lust, J. Teghem, Twophase Pareto local search for the biobjective traveling salesman problem, Journal of Heuristics 16 (2010) 475510. T. Lust, A. Jaszkiewicz, Speedup techniques for solving largescale biobjective TSP, Computers & Operations Research 37 (2010) 521533. A. Jaszkiewicz, P. Zielniewicz, Pareto memetic algorithm with path relinking for biobjective traveling salesperson problem, European Journal of Operational Research 193 (2009) 885890. W. Peng, Q. Zhang, H. Li, Comparison between MOEA/D and NSGAII on the multiobjective travelling salesman problem, Studies in Computational Intelligence 171 (2009) 309324. F. Samanlioglu, W.G. Ferrell Jr, M.E. Kurz, A memetic randomkey genetic algorithm for a symmetric multiobjective traveling salesman problem, Computers & Industrial Engineering 55 (2008) 439449. C. GarcíaMartínez, O. Cordón, F. Herrera, A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bicriteria TSP, European Journal of Operational Research 180 (2007) 116148. J. Cheng, G. Zhang, Z. Li, Y. Li, Multiobjective ant colony optimization based on decomposition for biobjective traveling salesman problems, Soft Computing 16 (2012) 597614. M. LópezIbáñez, T. Stüzle, An analysis of algorithmic components for multiobjective ant colony optimization: A case study on the biobjective TSP, in: P. Collet et al. (Eds.), EA 2009, LNCS 5975, SpringerVerlag, Berlin Heidelberg, 2009, pp. 134145. A. Liefooghe, J. Humeau, S. Mesmoudi, L. Jourdan, EG. Talbi, On dominancebased multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems, Journal of Heuristics 18 (2012) 317352. L. Paquete, Stochastic local search algorithms for multiobjective combinatorial optimization: Methods and analysis. Dissertations in Artificial Intelligence, Vol. 295, AKA Verlag/ IOS Press, 2006. T. Lust, New metaheuristics for solving MOCO problems: application to the knapsack problem, the traveling salesman problem and IMRT optimization, PhD Thesis, Université de Mons, Mons, Belgium, 2009. O. Özpeynirci, M. Köksalan, Pyramidal tours and multiple objectives, Journal of Global Optimization 48 (2007) 569583. O. Özpeynirci, M. Köksalan, Multiobjective traveling salesperson problem on Halin graphs, European Journal of Operational Research 196 (2009) 155161. M. Stanojević, M. Vujošević, B. Stanojević, Computation results of finding all efficient points in multiobjective combinatorial optimization, International Journal of Computers, Communications & Control 3 (2008) 374383. J.F. Bérubé, M. Gendreau, JY. Potvin, An exact εconstraint method for biobjective combinatorial optimization problems: Application to the traveling salesman problem with profits, European Journal of Operational Research 194 (2009) 3950. N. Jozefowiez, F. Glover, M. Laguna, Multiobjective metaheuristics for the traveling salesman problem with profits, Journal of Mathematical Modelling and Algorithms 7 (2008) 177195. B. Manthey, L. Shankar Ram, Approximation algorithms for multicriteria traveling salesman problems, Algorithmica 53 (2009) 6988. G. Laporte, The traveling salesman problem: An overview of exact and approximate algorithms, European Journal of Operational Research 59 (1992) 231247. C.H. Papadimitriou, The euclidean traveling salesman problem is NPcomplete, Theoretical Computer Science 4 (1977) 237244. D. Applegate, R. Bixby, V. Chvátal, W. Cook, On the solution of travelling salesman problems, Documenta Mathematica 3 (1998) 645656. A. Volgenant, Symmetric traveling salesman problems, European Journal of Operational Research 49 (1990) 153154. Source Code available at ftp://www.mathematik.unikl.de/pub/Math/ORSEP/VOLGENAN.ZIP. G.R. Jahanshahloo, F. Hosseinzadeh, N. Shoja, G. Tohidi, A method for generating all efficient solutions of 01 multiobjective linear programming problem, Applied Mathematics and Computation 169 (2005) 874886. G. Mavrotas, D. Diakoulaki, Multicriteria branch & bound: A vector maximization algorithm for Mixed 01 Multiple Objective Linear Programming, Applied Mathematics and Computation 171 (2005) 5371. A. Chinchuluun, P.M. Pardalos, A survey of recent developments in multiobjective optimization, Annals of Operations Research 154 (2007) 2950. K. KhaliliDamghani, M. Tavana, S. SadiNezhad, An integrated multiobjective framework for solving multiperiod project selection problems, Applied Mathematics and Computation 219 (2012) 31223138. T. Lust, J. Teghem, D. Tuyttens, Very largescale neighborhood search for solving multiobjective combinatorial optimization problems, in: R.H.C. Takahashi et al. (Eds.), EMO 2011, LNCS 6576, SpringerVerlag, Berlin Heidelberg, 2011, pp. 254268. A. Jaszkiewicz, A comparative study of multipleobjective metaheuristics on the biobjective set covering problem and the Pareto memetic algorithm, Annals of Operations Research 131 (2004) 135158. C. Prins, C. Prodhon, R.W. Calvo, Twophase method and Lagrangian relaxation to solve the biobjective set covering problem, Annals of Operations Research 147 (2006) 2341. G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, 1999. G. Mavrotas, Effective implementation of the εconstraint method in multiobjective mathematical programming problems, Applied Mathematics and Computation 213 (2009) 455465. K.M. Miettinen, Nonlinear Multiobjective Optimization, Kluwer Academic Publishers, Boston, 1998. M.R. Bussieck, Introduction to GAMS BranchandCut Facility, Technical report, GAMS Development Corp., 2003. http://www.gams.com/docs/bch.htm GAMS Corp., Traveling Salesman problem with BCH, http://www.gams.com/modlib/libhtml/bchtsp.htm. M.R. Bussieck, Column generation in GAMS – Extending the GAMS BranchandCutandHeuristic (BCH) facility, 83rd Working Group Meeting Real World Optimization, Workshop “Mathematical Optimization in Transportation – Airline, Public, Transport, Railway” GOR, Bad Honnef, Germany, 2009. Available online at: http://www.gams.com/presentations/bussieck_cg.pdf G. Reinelt, TSPLIB – A traveling salesman problem library, ORSA Journal on Computing 3 (1991) 376384. G. Reinelt, TSPLIB95, URL: http://www.iwr.uniheidelberg.de/groups/comopt/software/TSPLIB95/. A. Brooke, D. Kendrick, A. Meeraus, R. Raman, GAMS. A user’s guide, GAMS development corporation, Washington, 1998. https://sites.google.com/site/thibautlust/research/multiobjectivetsp (last accessed on July 24th 2013). http://eden.dei.uc.pt/~paquete/tsp (last accessed on July 22nd 2013). http://xgandibleux.free.fr/MOCOlib/MOSCP.html (last accessed on July 29th 2013). M. Laumanns, L. Thiele, E. Zitzler, An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilonconstraint method, European Journal of Operational Research 169 (2006) 932942. K. Deb, MultiObjective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Chichester, 2001. V. Khare, X. Yao, K. Deb, Performance scaling of multiobjective evolutionary algorithms, in: C.M. Fonseca et al. (Eds.), EMO 2003, LNCS 2632, SpringerVerlag, Berlin Heidelberg, 2003, pp.376390. M. Visée, J. Teghem, M. Pirlot, E.L. Ulungu, Twophases method and branch and bound procedures to solve the biobjective knapsack problem, Journal of Global Optimization 12 (1998) 139155. A. Przybylski, X. Gandibleux, M. Ehrgott, Two phase algorithms for the biobjective assignment problem, European Journal of Operational Research 185 (2008) 509533. A. Przybylski, X. Gandibleux, M. Ehrgott, A two phase method for multiobjective integer programming and its application to the assignment problem with three objectives, Discrete Optimization 7 (2010) 149165. W.H. Press, S.A. Teukolsky, W.T. Vetterling, B.P. Flannery, Numerical Recipes in Pascal. The art of Scientific Computing, Cambridge University Press, 1989. K. Helsgaun, An effective implementation of the LinKernighan traveling salesman heuristic, European Journal of Operational Research 126 (2000) 106130. C.E. Miller, A.W. Tucker, R.A. Zemlin, Integer programming formulations of traveling salesman problems, Journal of the Association for Computing Machinery 7 (1960) 326329. M. Ozlen, B.A. Burton, C.A.G. MacRae, Multiobjective integer programming: An improved recursive algorithm, Journal of Optimization Theory and Applications 2013, inPress (DOI 10.1007/s109570130364y). O. Özpeynirci, M. Köksalan, An exact algorithm for finding extreme supported nondominated points of multiobjective mixed integer programs, Management Science 56 (2010) 23022315. D. Applegate, R. Bixby, V. Chvátal, W. Cook, Concorde TSP solver http://www.tsp.gatech.edu/concorde.html J. Lemesre, C. Dhaenens, E.G. Talbi, Parallel partitioning method (PPM): A new exact method to solve biobjective problems, Computers & Operations Research 34 (2007) 24502462. K. Dächert, J. Gorski, K. Klamroth, An augmented weighted Tchebycheff method with adaptively chosen parameters for discrete bicriteria optimization problems, Computers & Operations Research 39 (2012) 29292943. 
URI:  https://mpra.ub.unimuenchen.de/id/eprint/105074 