Algebraic properties of location problems with one circular barrier. (Q1420408): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:18, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Algebraic properties of location problems with one circular barrier. |
scientific article |
Statements
Algebraic properties of location problems with one circular barrier. (English)
0 references
2 February 2004
0 references
A single location problem in the plane is considered where the location of the new facility as well as transportation is subject to a circular barrier. This means that the new location cannot be placed inside the circle and the paths between existing locations and the (unknown) new location must not travers the circle. As a consequence, the problem of minimizing the sum of the barrier distances is a non-convex optimization problem. The author shows that this problem is separable into a polynomial number of convex optimization problems. This is achieved by a tesselation of the plane into so-called cells of algebraic invariance (CAI), the latter depending on the existing facilities and the location and size of the circular barrier. It is shown that only a polynomial number of CAIs is needed, thus yielding a polynomial solution algorithm (including the solution of a convex optimization problem as black box in each iteration). The paper also includes a faster heuristic for the barrier problem.
0 references
Location
0 references
Barriers to travel
0 references