algorithm/logic to balance the load and determine the route of busses

Question

hi there!

i want to create a software for planning routes of busses (and their optimal loading) for disabled-kids-transportation.

these busses have following specifications:

• m seats (maximum 7 - as there is a driver and an assistance)
• o "seats" for wheel-chairs (maximum 4)
• fixed amount of maximum load (in austria: 9 or 20 persons; 9 for eg. ford transit; 20 for eg. mercedes benz sprinter)

specifications for routes:

• the journey to the institutes must be shorter than 2 hours for a kid (not for the bus)
• for optimization: it may be optimal to mix institutes

example

the optimal route 1 would be:

• 6, 1, 7, group (2, 3, 4, 5), insitute A (exit for 1, 2, 3, 4, 5, 6), 8, 9, insitute B (exit for 7, 8, 9) or
• 1, 7, 6, group (2, 3, 4, 5), insitute A (exit for 1, 2, 3, 4, 5, 6), 8, 9, insitute B (exit for 7, 8, 9) or
• 7, 1, 6, group (2, 3, 4, 5), insitute A (exit for 1, 2, 3, 4, 5, 6), 8, 9, insitute B (exit for 7, 8, 9) or
• ...

depending on the specific road (aka the road distance for the triangle 1-6-3 and 7-1-6)

this is simple example. when it comes down to transport wheel-chairs it's more complex.

edit:
NOTE: there are more than 2 instutes, as there are more than 9 kids. this was just for giving an example. in real world there would be 600 kids and 20 institutes...

what data do i need?
my guesses were: coordinates, distances between points (not air-line distance, rather the road distance), type of "seat-usage" (seat or wheel-chair), somehow road specifications (may be obsolete due to distance)

can anyone please come up with some idea, algorithm, logic, feedback, (free! as disabled-kid-transportation is no enterprise business) software i may use to gain data (eg. coordinates, distances, ...).

oh, and i must say. i'm no studied software-engineer, so it's somehow hard to go through scentific literature, but i'm willed to get my hands dirty!

thanks in advance!

Answer 1

Well, this is actually what I do for a living. Basically, we solve this using MiP with column-generation and using a path-model. Seeing that the problem is quite small, I would think you can using the simpler edge-flow-model with a reasonable result. That will save you doing the column-generation, which is quite some work. I'd suggest starting out by calculating the flow on a given set off routes before thinking about generating the routes themselves --- in fact, I would simply do that "by hand" using the routing calculator and dual costs as a guide.

Specifically, you need to create a graph where each pickout and delivering point is a node, and each bus route is a set of connected notes. Connect as appropriate, this is really easier to draw than write :) Then, make a LP system that models the flow, constraining the flow to the bus' compacity, and either requiring that all passengers are delivered or pay a heavy toll for not doing so.

Once that is in place, create boolean variables for each route and multiply this with the capacity: this will enable you to turn bus routes on and off.

Ask for details as needed, the above is just a rough outline.

EDIT:

Ok, reading the responses, I think I have to say that to solve this problem in the way I suggest, you at least need to have some knowledge about linear programming and graph theory. And yes, this is a problem that is very hard... so hard that I consider it unsolvable except for very small systems using the current computer technology. Seeing that this actually is a very small. I think it would be possible, and you are very welcome to contact our company for help ([email protected]). However, professional assistance in optimization is not exactly cheap.

However, all is not lost! There are simpler ways, though the result will not be so good. When you cannot model, simulate! Write a simulation that given the bus routes, passengers etc shows how the passengers move along the bus routes. Make a score, where each bus you use cost something, each kilometer cost something, and each passenger not transported costs a lot. Then look at the result, change the routes and work toward the best (cheapest) solution you can come up with. It is probably not a bad solution.

Again, creating a program that will generate a solution for the above problem from scratch is not a suitable enterprise for someone not versed in LP+MiP+graph theory. But perhaps less can do it?

I will be on vacation for the next week or so.