SCIENCE@home

A Multi-Objective Minimum Matrix Search Algorithm Applied to Large-Scale Bi-Objective TSP

M. M. Smith,Yun-Shiow Chen

Published 2018 in International Conference on Computational Science & Intelligence and Applied Informatics

ABSTRACT

The well-known NP-hard traveling salesman problem (TSP) primarily considers distance as its single objective. However, applications modeled from real world systems repeatedly involve more than one objective giving rise to multi-objective optimization. Fusing ideas of dimension reduction, decomposition approaches, and genetic algorithms, this paper presents a multiobjective minimum matrix search algorithm (MOMMS) for the heuristic resolution of the bi-objective TSP (bTSP). The MOMMS uses dimension reduction to obtain a reduce matrix network that is used to obtain or to approximate the set of efficient solutions. The reduce matrix network aids in the decomposition of a multiobjective combinatorial optimization (MOCO) problem into a single objective combinatorial optimization problem. Moreover, using the reduce matrix network MOMMS introduces a population generator that creates an initial population composed of an approximation to the extreme supported efficient solutions. The MOMMS does not use any numerical parameter. Also, MOMMS uses family competitive metamorphosis and short-term memory selection to maintain population diversity in MOCO problems. The proposed algorithm showed respectable results in testing on well-known benchmark problems of the bTSP. Comparisons are performed with the results of state-of-the-art algorithms from the literature. Moreover, the MOMMS is tested on largescale instances of the bTSP. The computational study shows that the proposed algorithm is able to solve large-scale instances in reasonable time. Therefore, the MOMMS is a competitive tool for solving the bTSP.

PUBLICATION RECORD

  • Publication year

    2018

  • Venue

    International Conference on Computational Science & Intelligence and Applied Informatics

  • Publication date

    2018-07-01

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    DOI 10.1109/CSII.2018.00017
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-18 of 18 references · Page 1 of 1

CITED BY