A Single chinese postman problem with two objectives

Download

index.pdf

Date

2015

Author

Eroğlu, Ezgi

Metadata

Show full item record

Item Usage Stats

126
views

55
downloads

The Chinese Postman Problem (CPP) is an arc routing problem in which a single postman serves a number of streets starting from a post office. The postman has to visit the households on each street in his route, delivering and collecting letters and then returning to the post office. The single objective CPP minimizes the total cost of the travel. The multi-objective CPPs consider other attributes like total distance and total time, etc. In this thesis, we consider a multi-objective CPP where each street is represented by two weights, like cost and distance. We propose a branch and bound algorithm that generates all efficient points with respect to the total cost and total distance criteria. Our algorithm benefits from the optimal solutions of the linear programming relaxations in defining the branching scheme and providing lower and upper bounds. Our extensive computational results show that our algorithm generates the efficient solution set for large-sized problem instances in reasonable time.

Subject Keywords

Algorithms., Computer algorithms., Mathematical optimization., Branch and bound algorithms.

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

A Scalable evolutionary algorithm for solving the one-dimensional bin packing problem on GPU using CUDA Özcan, Şükrü Özer; Coşar, Ahmet; Sahillioğlu, Yusuf; Department of Computer Engineering (2015) One-dimensional Bin Packing Problem (1DBPP) is a challenging NP-Hard combinatorial industrial engineering problem which is used to pack finite number of items into minimum number of fixed size bins. Different versions of 1DBPP can be faced in real life. Although the problems that have small number of items up to 20 can be solved with brute-force algorithms, large problem instances of the 1DBPP cannot be solved exactly due to its intractable nature. Therefore, heuristic approaches such as Genetic, Particle S...
Modeling of freight transportation on Turkish highways Ünal, Leyla; Türel, Ali; Department of City and Regional Planning (2009) Transportation planners are often faced with the problem of estimating passenger and freight flows between regions. In the literature there are many models for passenger flows. However, models about freight flows are more limited. Modeling freight flow is also more complex than modeling passenger flow and there are many agents related with freight flows. In addition, data availability is a critical factor. In this research, freight flows between provinces in Türkiye are forecasted by demand analysis. Transp...
Local search heuristics for pollution-routing problem with multiple vehicle types and deadlines Saka, Onur Can; Gürel, Sinan; Van Woensel, Tom; Department of Industrial Engineering (2013) Vehicle Routing Problem (VRP) is one of the most widely studied problems in logistics literature. Up to now, many different types of exact solution methods and heuristics have been developed in order to deal with various variants of this computationally complex optimization problem. However, only a few researchers have included the concepts of speed control, fuel consumption and greenhouse gas (GHG) emissions in their studies. The first part of this study is dedicated to a special variant of VRP called the ...
Solution approaches for single-source capacitated multi facility weber problem Damgacıoğlu, Haluk; İyigün, Cem; Department of Industrial Engineering (2014) Single Source Capacitated Multi Facility Location Problem (SSCMFLP) is a continuous location-allocation problem such that determining the locations of p facilities in the plane and allocations of n demand points to only one facility by considering the capacity restriction of each facility so as to minimize total transportation cost to satisfy n demand points from p facilities. In addition to Mixed Integer Non-Linear Programming formulation of the problem in the literature, we give a new formulation for the ...
Assembly line balancing with station paralleling Ege, Yunus; Azizoğlu, Meral; Özdemirel, Nur Evin (2009-11-01) We consider the NP-hard problem of assembly line balancing with station paralleling. We assume an arbitrary number of parallel workstations can be assigned to each stage. Every task requires a specified tooling/equipment, and this tooling/equipment should be available in all parallel workstations of the stage to which the task is assigned. Our objective is to find an assignment of tasks to stages so as to minimize sum of station opening and tooling/equipment costs. We propose two branch and bound algorithms...

Citation Formats

E. Eroğlu, “A Single chinese postman problem with two objectives,” M.S. - Master of Science, Middle East Technical University, 2015.