Heuristics for a continuous multi-facility location problem with demand regions

Download

index.pdf

Date

2013

Author

Dinler, Derya

Metadata

Show full item record

Item Usage Stats

211
views

277
downloads

We consider a continuous multi-facility location problem where the demanding entities are regions in the plane instead of points. Each region may consist of a finite or an infinite number of points. The service point of a station can be anywhere in the region that is assigned to it. We do not allow fractional assignments, that is, each region is assigned to exactly one facility. The problem we consider can be stated as follows: given m demand regions in the plane, find the locations of q facilities and allocate regions to the facilities so as to minimize the sum of squares of the maximum Euclidean distances of the demand regions to the facility locations they are assigned to. We assume that the regions are closed polygons as any region can be approximated within any desired accuracy with a polygon. We first propose mathematical programming formulations of single and multiple facility location problems. The single facility location problem is formulated as a second order cone program (SOCP) which can be solved in polynomial time. The multiple facility location problem is formulated as a mixed integer SOCP. This formulation is weak and does not even solve medium-size problems. We therefore propose heuristics to solve larger instances of the problem. We develop three heuristics that work when the regions are polygons. When the demand regions are rectangles with sides parallel to coordinate axes, a special heuristic is developed. We compare our heuristics in terms of both solution quality and computational time.

Subject Keywords

Business logistics, Heuristic algorithms, Operations research

URI

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

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

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.
Generalization of restricted planar location problems : unified meta-heuristics for single facility case Farham, Mohammad Saleh; Süral, Haldun; İyigün, Cem; Department of Industrial Engineering (2013) A planar single facility location problem, also known as the Fermat–Weber problem, is to ﬁnd a facility location such that the total weighted distance to a set of given demand points is minimized. A variation to this problem is obtained if there is a restriction coming from congested regions. In this study, congested regions are considered as arbitrary shaped polygonal areas on the plane where location of a facility is forbidden and traveling is charged with an additional ﬁxed cost. The traveling ﬁxed cost ...
A Multi-level continuous minimax location problem with regional demand Faridyahyaei, Amin; Tural, Mustafa Kemal; Department of Industrial Engineering (2017) The minimax facility location problem seeks for the optimal locations of the facilities in the plane so that the maximum Euclidean distance between the demanding entities (given points in the plane) and their corresponding nearest facilities is minimized. In the solutions, remote entities (irrespective of their weights) tend to pull the facilities toward themselves which may result in larger distances for the other entities. In this thesis, we consider a multi-level minimax location problem which allows som...
Generalization of the restricted planar location problems: Unified metaheuristic algorithms Farham, Mohammad Saleh; Süral, Haldun; İyigün, Cem (Elsevier BV, 2018-11-01) In the restricted planar location problems, facilities cannot be located inside certain areas on the plane. We define congested regions as polygonal areas on the plane inside which locating a facility is infeasible but through which traveling is possible at an additional fixed cost. The location problem with congested regions on the Euclidean plane is shown to be a generalization of the two most studied problems in the literature, i.e. the restricted planar facility location problems with forbidden regions ...
A Heuristic for Obtaining and Initial Solution for the Transportation Problem Kirca, Ömer; Şatır, Ahmet (JSTOR, 1990-9) A heuristic for obtaining an initial solution for the transportation problem is presented. Comparison of findings obtained by the new heuristic and Vogel's approximation method (VAM) are tabulated for 480 examples. Superior performance of the new heuristic over VAM is discussed in terms of total costs obtained, number of iterations required to reach the final solution, and CPU time required to solve the problems. Experimental design aspects are also presented.

Citation Formats

D. Dinler, “Heuristics for a continuous multi-facility location problem with demand regions,” M.S. - Master of Science, Middle East Technical University, 2013.