| Author |
Message |
    
Rastro
Citizen
Username: Rastro
Post Number: 3457
Registered: 5-2004
| | Posted on Friday, June 30, 2006 - 4:07 pm: | 
|
I'm helping a camp optimize their bus routing. They have a fixed number of buses, and a fixed number of pickups and drop offs. They need to minimize the number of buses they use, while maintaining a route time of less than an hour per bus.
Essentially, it's a modified traveling salesman problem (TSP).
Has anyone seen or heard of software that can do this? I've seen TSP software for a single route, but none that incorporates multiple routes.
Free is good, but they spend about $10k per bus for the summer, so saving one bus route could be very worthwhile. Any ideas? |
Hillsider
Supporter
Username: Hillsider
Post Number: 77
Registered: 3-2004
| | Posted on Friday, June 30, 2006 - 6:10 pm: |
|
I have never used any of these but I did a wuick Google and:
http://www.google.com/search?hl=en&lr=&q=travelling+salesman+software
Maybe one of them will work for you...
If you are really into it, you should bring out your paper and pencil and solve it by hand... It is a minimizing function with just 2 constraints right? Have not done that since my undergrad days... but depending on your geekiness, it could be a good July 4th weekend excecise  |
Rastro
Citizen
Username: Rastro
Post Number: 3458
Registered: 5-2004
| | Posted on Saturday, July 1, 2006 - 4:09 pm: |
|
It's actually quite a bit more complex. I used to do these with up to about 10 stops, but we're talking about 400 kids (with 400 stops), with a variable number of buses (though a max of 16).
This would probably take a couple of weeks for me to do by hand :-)
I used to use a software program to do linear programming for this stuf. I can't even remember the methodology to do it anymore.
I did find a few programs on google, but I'm hesitant to spend a few hundred to a few thousand bucks without tesdting. I guess I'll have to call and get demos. I was hoping someone in this vast community of ours might have used one somehow.
Thanks for the info and tips, though. I might see what I can remember and try to set up the equations. |
TarPit Coder
Citizen
Username: Tarpitcoder
Post Number: 90
Registered: 12-2004
| | Posted on Monday, July 24, 2006 - 7:13 pm: |
|
Hey Rastro, I just saw this post - Here's a simple Prolog solution. It runs in swi-prolog which is free. You can even use swi-prolog via Cygwin on Windows.
http://www.computational-logic.org/~pascal/progs/tsp.pl
The link below runs on LPA-Win Prolog. It uses a genetic algorithm.
http://perso.orange.fr/colin.barker/lpa/tsp_ga.htm
--Tarp
|
Rastro
Citizen
Username: Rastro
Post Number: 3633
Registered: 5-2004
| | Posted on Tuesday, July 25, 2006 - 10:34 am: |
|
Thanks, TPC. I'll take a look. I've been doing it by hand for a while, but it's a mess trying to deal with streets (one way, traffic, lights, etc.). I'm fine when I do things using coordinates, but roads are making me crazy.
What I really need is some kind of mashup with Google Maps.
Hmm... there's an idea! |
|
Closed: New threads not accepted on this page