The biobjective traveling salesman problem with profit

Download

index.pdf

Date

2007

Author

Şimşek, Ömür

Metadata

Show full item record

Item Usage Stats

250
views

110
downloads

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 traveling cost. In literature, TSP with profit are addressed as single objective, either two objectives are combined linearly or one objective is constrained with a specified bound. In this study, a multiobjective approach is developed by combining ε-constrained method and heuristics from the literature in order to find the efficient frontier for the TSP with profit. The performance of approach is tested on the problems studied in the literature. Also an interactive software is developed based on the multiobjective approach.

Subject Keywords

Industrial Engineering

URI

http://etd.lib.metu.edu.tr/upload/12608890/index.pdf
https://hdl.handle.net/11511/17029

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A genetic algorithm for the biobjective traveling salesman problem with profits Karademir, Serdar; Süral, Haldun; Department of Industrial Engineering (2008) 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 Multiobjec...
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...
Multiobjective hub location problem Barutçuoğlu, Aras; Köksalan, Murat; Department of Industrial Engineering (2009) In this study, we propose a two-phase solution approach for approximating the efficient frontier of a bicriteria hub location problem. We develop an evolutionary algorithm to locate the hubs on the network as the first phase. In the second phase, we develop a bounding procedure based on dominance relations and using the determined bounds, we solve the allocation subproblem for each located hub set. The two-phase approach is tested on the Australian Post data set and it is observed that our approach approxim...
The planar hub location problem: a probabilistic clustering approach İyigün, Cem (Springer Science and Business Media LLC, 2013-12-01) Given the demand between each origin-destination pair on a network, the planar hub location problem is to locate the multiple hubs anywhere on the plane and to assign the traffic to them so as to minimize the total travelling cost. The trips between any two points can be nonstop (no hubs used) or started by visiting any of the hubs. The travel cost between hubs is discounted with a factor. It is assumed that each point can be served by multiple hubs.
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...

Citation Formats

Ö. Şimşek, “The biobjective traveling salesman problem with profit,” M.S. - Master of Science, Middle East Technical University, 2007.