Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
A genetic algorithm for the biobjective traveling salesman problem with profits
Download
index.pdf
Date
2008
Author
Karademir, Serdar
Metadata
Show full item record
Item Usage Stats
214
views
98
downloads
Cite This
In Traveling Salesman Problem (TSP) with profits, a profit is associated with each city and the requirement to visit all cities is removed. The purpose is to simultaneously minimize cost (excluding as many cities as possible) and maximize profit (including as many cities as possible). Although the reduced single-objective case of the problem has been well-studied, the true biobjective problem has been studied only by a few researchers. In this paper we study the true biobjective problem using the Multiobjective Genetic Algorithm NSGA II and the Lin-Kernighan Heuristic. We propose several improvements for NSGA II in solving the problem. Based on these improvements, we provide computational results of the approximated Pareto-optimal front for a set of practically large size TSP instances. Finally, we provide a framework and its computational results for a post-optimality analysis to guide the decision maker, using the data mining software Clementine.
Subject Keywords
Industrial engineering.
URI
http://etd.lib.metu.edu.tr/upload/3/12609729/index.pdf
https://hdl.handle.net/11511/17705
Collections
Graduate School of Natural and Applied Sciences, Thesis
Suggestions
OpenMETU
Core
The biobjective traveling salesman problem with profit
Şimşek, Ömür; Karasakal, Esra; Department of Industrial Engineering (2007)
The traveling salesman problem (TSP) is defined as: given a finite number of cities along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities only once and returning to your starting city. Some variants of TSP are proposed to visit cities depending on the profit gained when the visit occurs. In literature, these kind of problems are named TSP with profit. In TSP with profit, there are two conflicting objectives, one to collect profit and the other to decrease ...
A variable neighborhood search procedure for the combined location with partial coverage and selective traveling salesman problem
Rahim, Fatih; Sepil, Canan; Department of Industrial Engineering (2010)
In this study, a metaheuristic procedure, particularly a variable neighborhood search procedure, is proposed to solve the combined location and selective traveling salesman problem in glass recycling. The collection of used glass is done by a collecting vehicle that visits a number of predefined collection centers, like restaurants and hospitals that are going to be referred to as compulsory points. Meanwhile, it is desired to locate a predetermined number of bottle banks to residential areas. The aim is to...
An integrated inventory control and vehicle routing problem
Solyalı, Oğuz; Süral, Haldun; Department of Industrial Engineering (2005)
In this study, we consider a logistics system, in which a single supplier delivers a product to multiple retailers over a finite time horizon. Supplier decides on the amount to order in each period and services retailers facing deterministic dynamic demand via a fleet of vehicles having limited capacity. Each retailer has specific minimum and maximum levels of inventory in an order-up-to level inventory policy setting. The problem is to simultaneously determine the quantity of product to order to the suppli...
A heuristic approach for profit oriented disassembly lot-sizing problem
Kaya, Melike; Bayındır, Zeynep Pelin; Çetinkaya, Ferda Can; Department of Industrial Engineering (2011)
In this thesis, we work on adisassembly lot-sizing problem for multiple products with parts commonality,i.e., general product structure. We assume that supply of discarded products is infinite. When a product (or a subassembly) is disassembled, all its immediate child items are obtained,i.e., complete disassembly case.Intermediate and leaf items obtained are demandedbyexternal suppliers or remanufacturers. The maximum possible salesfor each intermediate and leaf item are known.Sales of the intermediate and ...
The cardinality constrained multiple knapsack problem
Aslan, Murat; Azizoğlu, Meral; Department of Industrial Engineering (2008)
The classical multiple knapsack problem selects a set of items and assigns each to one of the knapsacks so as to maximize the total profit. The knapsacks have limited capacities. The cardinality constrained multiple knapsack problem assumes limits on the number of items that are to be put in each knapsack, as well. Despite many efforts on the classical multiple knapsack problem, the research on the cardinality constrained multiple knapsack problem is scarce. In this study we consider the cardinality constra...
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
S. Karademir, “A genetic algorithm for the biobjective traveling salesman problem with profits,” M.S. - Master of Science, Middle East Technical University, 2008.
