| View previous topic :: View next topic |
| Author |
Message |
finecur
Guest
|
 Posted: Fri Oct 17, 2008 4:45 pm Post subject: selection optimization algorithm |
 |
|
Hi everyone:
I hope you can help me with a selection optimization problem.
Suppose I am doing a road show. My team drive from San Francisco to
New York on I80. Suppose there are about 1000 towns along the road. I
make a stop at a town and give a show. And then back on the road to
another twon. Once I get New York, I will drive back to San Franciso
giving the show along the road. Once I get San Francisco, I will
drive
to New York again and so on.
I would like to use the following rules:
1. Once I gave a show at a town, I would like to select my next twon
at least 100 miles but at most 500 miles away.
2. Every time I drive from San Francisco to New York, I would like to
stop at different towns. The same when I drive back.
What algorithm I can use to make the selection?
Thank you very much. |
|
| |
|
 Back to top |
Mark Lawton
Guest
|
| Posted: Fri Oct 17, 2008 8:31 pm Post subject: Re: selection optimization algorithm |
|
|
On 17 Oct, 17:45, finecur <fine...@yahoo.com> wrote:
[quote]Hi everyone:
I hope you can help me with a selection optimization problem.
Suppose I am doing a road show. My team drive from San Francisco to
New York on I80. Suppose there are about 1000 towns along the road. I
make a stop at a town and give a show. And then back on the road to
another twon. Once I get New York, I will drive back to San Franciso
giving the show along the road. Once I get San Francisco, I will
drive
to New York again and so on.
I would like to use the following rules:
1. Once I gave a show at a town, I would like to select my next twon
at least 100 miles but at most 500 miles away.
2. Every time I drive from San Francisco to New York, I would like to
stop at different towns. The same when I drive back.
What algorithm I can use to make the selection?
Thank you very much.
[/quote]
I think that a lot depends on what weightings you give to the factors
that you are trying to optimise. Use of fuel? Minimise travelling
time? Maximise the probability of finding new customers (suggesting
longer runs)? I suspect that, in practice, your choices will be
decided by factors like the availability of venues.
However, at a quick glance, it does look a little like a variation of
the Josephus problem - see http://en.wikipedia.org/wiki/Josephus_problem
.. You are basically trying to go back and forth from Frisco to the Big
Apple, going around the same distance each day, and avoiding visiting
the same town twice for as long as possible. |
|
| |
|
| Back to top |
Mark Lawton
Guest
|
| Posted: Fri Oct 17, 2008 9:01 pm Post subject: Re: selection optimization algorithm |
|
|
On 17 Oct, 21:31, Mark Lawton <creamrisestothe...@gmail.com> wrote:
[quote]However, at a quick glance, it does look a little like a variation of
the Josephus problem - seehttp://en.wikipedia.org/wiki/Josephus_problem
[/quote]
A problem with this type of approach is that you are likely to find
yourself visiting a neighbouring town when you reach either end of the
line. For example, if you>re visiting every 7th town, and their are
1000 towns, you might find yourself jumping from town 996 to town 997
- the nearest neighbour.
Greedy algorithms are easy to write, and tend to do a "fair" (but
rarely "optimal") job on the Travelling Salesman Problem. You might,
for example, give a maximum score for moving 5 towns along the road,
and fewer points for either more or less. You would also award more
points for visiting towns whose neighbours you had not visited
recently (so you would need to record the date on which each town is
visited). I suspect that such a greedy algorithm might well do a good
job on this task.
You might try the Operational Research group as well - they are very
fond of optimisation problems there (though I can>t think of an OR
method off the top of my head that will help you with this problem). |
|
| |
|
| Back to top |
|
