Abstract | ||
---|---|---|
We consider a spatial interaction model for locating a set of new facilities that compete for customer demand with each other, as well as with some pre-existing facilities to capture the “market expansion” and the “market cannibalization” effects. Customer demand is assumed to be a concave non-decreasing function of the total utility derived by each customer from the service offered by the facilities. The problem is formulated as a non-linear Knapsack problem, for which we develop a novel solution approach based on constructing an efficient piecewise linear approximation scheme for the objective function. This allows us to develop exact and α-optimal solution approaches capable of dealing with relatively large-scale instances of the model. We also develop a fast Heuristic Algorithm for which a tight worst-case error bound is established. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1016/j.ejor.2005.10.075 | European Journal of Operational Research |
Keywords | Field | DocType |
Location,Integer programming,Competitive facility location models,Non-linear Knapsack problem,Alpha-optimal solutions,Greedy heuristics,Worst-case bounds | Linear approximation,Mathematical optimization,Cannibalization,Heuristic (computer science),Concave function,Greedy algorithm,Facility location problem,Integer programming,Knapsack problem,Mathematics | Journal |
Volume | Issue | ISSN |
181 | 2 | 0377-2217 |
Citations | PageRank | References |
27 | 2.02 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Robert Aboolian | 1 | 122 | 9.15 |
O. Berman | 2 | 1604 | 231.36 |
Dmitry Krass | 3 | 483 | 82.08 |