A maximal covering location model in the presence of partial coverage

Date

2004-08-01

Author

Karasakal, O
Karasakal, Esra

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

81
views

0
downloads

The maximal covering location problem (MCLP) addresses the issue of locating a predefined number of facilities in order to maximize the number of demand points that can be covered. In a classical sense, a demand point is assumed to be covered completely if located within the critical distance of the facility and not covered at all outside of the critical distance. Since the optimal solution to a MCLP is likely sensitive to the choice of the critical distance, determining a critical distance value when the coverage does not change in a crisp way from "fully covered" to "not covered" at a specific distance may lead to erroneous results. We allow the coverage to change from "covered" to "not-covered" within a distance range instead of a single critical distance and call this intermediate coverage level partial coverage, In this paper, we formulate the MCLP in the presence of partial coverage, develop a solution procedure based on Lagrangean relaxation and show the effect of the approach on the optimal solution by comparing it with the classical approach.

Subject Keywords

Lagrangean relaxation, Partial coverage, Maximal covering problem, Location

URI

https://hdl.handle.net/11511/46610

Journal

COMPUTERS & OPERATIONS RESEARCH

DOI

https://doi.org/10.1016/s0305-0548(03)00105-9

Collections

Department of Industrial Engineering, Article

Suggestions

OpenMETU
Core

A genetic algorithm for the uncapacitated single allocation planar hub location problem Damgacioglu, Haluk; DİNLER, DERYA; Özdemirel, Nur Evin; İyigün, Cem (2015-10-01) Given a set of n interacting points in a network, the hub location problem determines location of the hubs (transfer points) and assigns spokes (origin and destination points) to hubs so as to minimize the total transportation cost. In this study, we deal with the uncapacitated single allocation planar hub location problem (PHLP). In this problem, all flow between pairs of spokes goes through hubs, capacities of hubs are infinite, they can be located anywhere on the plane and are fully connected, and each s...
A multi-objective genetic algorithm for a bi-objective facility location problem with partial coverage Karasakal, Esra (2016-04-01) In this study, we present a bi-objective facility location model that considers both partial coverage and service to uncovered demands. Due to limited number of facilities to be opened, some of the demand nodes may not be within full or partial coverage distance of a facility. However, a demand node that is not within the coverage distance of a facility should get service from the nearest facility within the shortest possible time. In this model, it is assumed that demand nodes within the predefined distanc...
A generalized Weiszfeld method for the multi-facility location problem İyigün, Cem (2010-05-01) An iterative method is proposed for the K facilities location problem. The problem is relaxed using probabilistic assignments, depending on the distances to the facilities. The probabilities, that decompose the problem into K single-facility location problems, are updated at each iteration together with the facility locations. The proposed method is a natural generalization of the Weiszfeld method to several facilities.
A column generation approach for the location-routing problem with time windows Farham, Mohammad Saleh; Süral, Haldun; İyigün, Cem (2018-02-01) The location-routing problem with time windows consists of opening a subset of depots, assigning customers to depots, and determining routes within allowable times such that the sum of depot opening, vehicle usage, and traveling costs is minimized. Customers have to be visited only once during their time windows and depot capacities and load limits of vehicles cannot be violated. In order to find the exact solution to the problem, we propose a branch-and-price algorithm based on set-partitioning approach. T...
A minisum location problem with regional demand considering farthest Euclidean distances DİNLER, DERYA; Tural, Mustafa Kemal (2016-06-01) We consider a continuous multi-facility location-allocation problem that aims to minimize the sum of weighted farthest Euclidean distances between (closed convex) polygonal and/or circular demand regions, and facilities they are assigned to. We show that the single facility version of the problem has a straightforward second-order cone programming formulation and can therefore be efficiently solved to optimality. To solve large size instances, we adapt a multi-dimensional direct search descent algorithm to ...

Citation Formats

O. Karasakal and E. Karasakal, “A maximal covering location model in the presence of partial coverage,” COMPUTERS & OPERATIONS RESEARCH, pp. 1515–1526, 2004, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/46610.