StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is a classic example of a problem that deserves an <a href="http://en.wikipedia.org/wiki/Category:Optimization_algorithms" rel="nofollow noreferrer">optimized solution</a> rather than trying to solve for "The OPTIMUM". It's similar in some ways to the "<a href="http://en.wikipedia.org/wiki/Traveling_salesman_problem" rel="nofollow noreferrer">Travelling Salesman Problem</a>", but you also need to segment the locations during the optimization.</p> <p>I've used three different optimization algorithms to good effect on problems like this:</p> <ol> <li><a href="http://en.wikipedia.org/wiki/Simulated_annealing" rel="nofollow noreferrer">Simulated Annealing</a></li> <li><a href="http://en.wikipedia.org/wiki/Great_Deluge_algorithm" rel="nofollow noreferrer">Great Deluge Algorithm</a></li> <li><a href="http://en.wikipedia.org/wiki/Genetic_algorithm" rel="nofollow noreferrer">Genetic Algoritms</a></li> </ol> <p>Using an optimization algorithm, I think you've described the following "goals":</p> <ol> <li>The geographic area for each paper boy should be minimized.</li> <li>The number of subscribers served by each should be approximately equal.</li> <li>The distance travelled by each should be about equal.</li> <li>(And one you didn't state, but might matter) The route should end where it began.</li> </ol> <p>Hope this gets you started!</p> <p><strong>* Edit *</strong></p> <p>If you don't care about the routes themselves, that eliminates goals 3 and 4 above, and perhaps allows the problem to be more tailored to your bonus requirements.</p> <p>If you take demographic information into account (such as population density, subscription adoption rate and subscription cancellation rate) you could probably use the optimization techniques above to eliminate the need to rerun the algorithm at all as subscribers adopted or dropped your service. Once the clusters were optimized, they would stay in balance because the rates of each for an individual cluster matched the rates for the other clusters.</p> <p>The only time you'd have to rerun the algorithm was when and external factor (such as a recession/depression) caused changes in the behavior of a demographic group.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload