Low complexity algorithms for optimal consumer push-pull partial covering in the plane

Shimon Abravaya and Michael Segal

European Journal of Operational Research, 2009, vol. 197, issue 2, 456-464

Abstract: This paper considers a model for locating a consumer within a bounded region in the plane with respect to a set of n existing pull-push suppliers. The objective is to maximize the difference of total profits and costs incurred due to the partial covering of the consumer by the suppliers pull and push influence areas. We develop efficient polynomial time algorithms for the resulting problems in the rectilinear and the Euclidean planes where the bounded region is either a rectangle or a constant size polygon, respectively. Based on these solutions, we develop algorithms for evaluating efficiently the objective function at any possible location of the consumer inside the bounded region. We also employ the algorithms for the Euclidean optimization problem and the rectilinear query computation to solve efficiently their corresponding dynamic versions, where an appearance of a new supplier or an absence of an existing one occurs. Being easy to implement due to the extensive use of simple data structures, such as the balanced and binary segment tree, and the employment of standard mechanisms, such as the sweep line, the Voronoi diagram and the circular ray shooting, our solutions potentially have wide usability.

Keywords: Pull-push; criteria; Semi-obnoxious; Partial; covering; Optimization; algorithms (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00510-9
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:197:y:2009:i:2:p:456-464

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().