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

163
views

71
downloads

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

S. Karademir, “A genetic algorithm for the biobjective traveling salesman problem with profits,” M.S. - Master of Science, Middle East Technical University, 2008.