An evolutionary approach to generalized biobjective traveling salesperson problem

Date

2017-03-01

Author

Köksalan, Mustafa Murat
Ozturk, Diclehan Tezcaner

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

190
views

0
downloads

We consider the generalized biobjective traveling salesperson problem, where there are a number of nodes to be visited and each node pair is connected by a set of edges. The final route requires finding the order in which the nodes are visited (tours) and finding edges to follow between the consecutive nodes of the tour. We exploit the characteristics of the problem to develop an evolutionary algorithm for generating an approxiMation of nondominated points. For this, we approximate the efficient tours using approximate representations of the efficient edges between node pairs in the objective function space. We test the algorithm on several randomly-generated problem instances and our experiments show that the evolutionary algorithm approximates the nondominated set well.

Subject Keywords

Evolutionary computations, Multiobjective decision making, Combinatorial optimization, Multiobjective traveling salesperson problem

URI

https://hdl.handle.net/11511/56695

Journal

COMPUTERS & OPERATIONS RESEARCH

DOI

https://doi.org/10.1016/j.cor.2016.04.027

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

An interactive approach for biobjective integer programs under quasiconvex preference functions Ozturk, Diclehan Tezcaner; Köksalan, Mustafa Murat (2016-09-01) We develop an interactive algorithm for biobjective integer programs that finds the most preferred solution of a decision maker whose preferences are consistent with a quasiconvex preference function to be minimized. During the algorithm, preference information is elicited from the decision maker. Based on this preference information and the properties of the underlying quasiconvex preference function, the algorithm reduces the search region and converges to the most preferred solution progressively. Findin...
A methodology of swarm intelligence application in clustering based on neighborhood construction İnkaya, Tülin; Kayalıgil, Sinan; Özdemirel, Nur Evin; Department of Industrial Engineering (2011) In this dissertation, we consider the clustering problem in data sets with unknown number of clusters having arbitrary shapes, intracluster and intercluster density variations. We introduce a clustering methodology which is composed of three methods that ensures extraction of local density and connectivity properties, data set reduction, and clustering. The first method constructs a unique neighborhood for each data point using the connectivity and density relations among the points based upon the graph the...
An interactive preference based multiobjective evolutionary algorithm for the clustering problem Demirtaş, Kerem; Özdemirel, Nur Evin; Karasakal, Esra; Department of Industrial Engineering (2011) We propose an interactive preference-based evolutionary algorithm for the clustering problem. The problem is highly combinatorial and referred to as NP-Hard in the literature. The goal of the problem is putting similar items in the same cluster and dissimilar items into different clusters according to a certain similarity measure, while maintaining some internal objectives such as compactness, connectivity or spatial separation. However, using one of these objectives is often not sufficient to detect differ...
A Meta-Heuristic Paradigm for solving the Forward Kinematics of 6-6 General Parallel Manipulator Chandra, Rohitash; Frean, Marcus; Rolland, Luc (2009-12-18) The forward kinematics of the general Gough platform, namely the 6-6 parallel manipulator is solved using hybrid meta-heuristic techniques in which the simulated annealing algorithm replaces the mutation operator in a genetic algorithm. The results are compared with the standard simulated annealing and genetic algorithm. It shows that the standard simulated annealing algorithm outperforms standard genetic algorithm in terms of computation time and overall accuracy of the solution on this problem. However, t...
An interactive algorithm for multiobjective ranking for underlying linear and quasiconcave value functions TEZCANER ÖZTÜRK, DİCLEHAN; Köksalan, Mustafa Murat (Wiley, 2019-07-29) We develop interactive algorithms to find a strict total order for a set of discrete alternatives for two different value functions: linear and quasiconcave. The algorithms first construct a preference matrix and then find a strict total order. Based on the ordering, they select a meaningful pair of alternatives to present the decision maker (DM) for comparison. We employ methods to find all implied preferences of the DM, after he or she makes a preference. Considering all the preferences of the DM, the pre...

Citation Formats

M. M. Köksalan and D. T. Ozturk, “An evolutionary approach to generalized biobjective traveling salesperson problem,” COMPUTERS & OPERATIONS RESEARCH, pp. 304–313, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/56695.