0

Imagine we manage a chain of stores. We already have a number $M$ of branches of this chain in a certain region. The CEO has decided we need to expand and should open $N$ new stores in this same region.
The question is: Where should we place these new stores such that the locations are optimal?

So we have the set of current branch locations $\vec{z}_{1...M}$ and are looking for the new locations: $\vec{x}_{1...N}$
The goal is have consistent cover of the city, such that any random citizen has the least walking distance to any chain.
Bonus: Each existing branch has a weight based on the current number of visitors.

  • Is there a name for this type of optimisation problem?
  • With what sort of algorithm could this be solved?

An idea I had:

  1. Place the $M$ new points evenly and randomly distributed on the map, together with the existing points.
  2. Per iteration perform a push/pull on the new points, similar to how charged particles repel one another. Effectively calculate a force on each new point from other new points and the old points.
  3. Move each new point slightly based on the net force.
  4. Repeat 2. and 3. untill there is no change.

This should be fairly robust but the outcome is strongly dependent on the initial guess and susceptible to local minima. The outcome would be hardly optimal.

Roberto
  • 163
  • Note that I was caught between asking this here and on StackOverflow. I decided to ask it here since it is a general problem, independent on code implementation. – Roberto Dec 02 '19 at 15:30

1 Answers1

1

This is the multi-source Weber problem, a particular example of a facility location problem. You can find lots of information on solution methods by searching these terms.

RobPratt
  • 45,619