Efficient optimal facility location determination method for convex position demand point
The present invention relates to an efficient optimal facility location determination method for convex demand position demand points implemented to arrange a plurality of facilities as close as possible to given demand locations when positions of the demand locations satisfy a convex position condition. According to the efficient optimal facility location determination method for convex position demand points of the present invention, when demand locations satisfy a convex position condition, it is possible to quickly calculate a method of efficiently arranging a plurality of facilities in a very short time. In addition, according to the present invention, even if positions of demand locations do not satisfy a convex position condition, it is possible to approximate arrangement of facilities, and to be applied to various fields such as a location selection of a warehouse or data clustering.
1 . A method for arranging facilities performed at a computing system having one or more processors and memory, the method comprising:
receiving, by the one or more processors, information regarding a plurality of facilities to be arranged, wherein arranging the plurality of facilities with no restrictions on positioning represents an NP-hard problem;
for each facility of the plurality of facilities, determining, by the one or more processors, whether the facility is arranged so that an optimal distance, which is a distance from a plurality of demand locations with a farthest distance to the facility, is less than or equal to a given distance, wherein the determination comprises:
performing a first type of determination in accordance with a determination that the plurality of facilities does not exceed a threshold number, wherein performing the first type of determination comprises determining whether there is a circle that covers points of a chain function; and
performing a second type of determination in accordance with a determination that the plurality of facilities does exceed the threshold number, the second type of determination being different than the first type of determination, wherein performing the second type of determination comprises applying a binary search;
for each facility of the plurality of facilities, calculating, by the one or more processors, an optimal facility location by applying a parametric search function so that a distance between the facility and the plurality of demand locations becomes the optimal distance; and
providing, by the one or more processors, arrangement information for the plurality of facilities, the arrangement information including respective optimal facility locations for the plurality of facilities.
2 . The method of claim 1 , wherein the plurality of demand locations satisfy a convex position condition in which the plurality of demand locations are positioned at vertices of a convex polygon.
3 . The method of claim 1 , wherein the determination is performed using a decision algorithm,
calculating the optimal facility location comprises using an optimization algorithm, and
the decision algorithm operates using dynamic programming.
4 . The method of claim 1 , wherein calculating the optimal facility location includes:
calculating a section including an optimal distance for calculating a section including the optimal distance; and
determining an optimal facility location for determining an optimal facility location within the section including the optimal distance.
5 . The method of claim 2 , wherein the determination is performed using a decision algorithm,
calculating the optimal facility location comprises using an optimization algorithm, and
the decision algorithm operates using dynamic programming.
6 . The method of claim 2 , wherein calculating the optimal facility location includes:
calculating a section including an optimal distance for calculating a section including the optimal distance; and
determining an optimal facility location for determining an optimal facility location within the section including the optimal distance.
7 . The method of claim 1 , wherein the threshold number corresponds to logarithmic growth, O(log n).
8 . The method of claim 1 , wherein the first type of determination comprises determining whether a circle may be identified that covers a first demand location of the plurality of demand locations and a second demand location of the plurality of demand locations.
9 . The method of claim 1 , wherein the first type of determination comprises determining whether respective intersections of respective circles centered on respective demand locations of the plurality of demand locations is an empty set.
10 . The method of claim 1 , wherein the determination comprises determining whether the plurality of demand locations may be covered with a set of circles corresponding to the plurality of facilities.
11 . The method of claim 10 , wherein each circle of the set of circles has a radius determined using dynamic programming.
12 . The method of claim 1 , wherein the plurality of facilities comprises a plurality of warehouses.
13 . The method of claim 1 , wherein the plurality of facilities comprises a plurality of data clusters.