Matthias,

The "right" way to do this is to assemble the MIP (Mixed integer problem) equations and use a MIP solver. The paper used CPLEX which is one of the best MIP solvers. I would not have accessed it directly through an API as the authors did -- I use a program called GAMS which separates the optimization problem from the solver so you can try different solvers with little effort. However either approach is a real investment both in both cost and learning time (i.e. a single user license to CPLEX costs $9,600 and then you have to figure out how to use it!). Solving MIP problems in Mathematica is possible but the process is a bit difficult for larger problems. That is why I suggested you try to co-opt the FindShortesTour function and create your own algorithm. If I have a chance this week I might take a quick shot at it -- its an interesting challenge. Let me know if you make progress or post some sample code if you get stuck.

Regards

Neil

Hi Ted,

Yes, I had seen that. This is solving a different problem because each route is a tour. Ie. some kids would be picked up when the bus is on its way back from the school to the depot.

Or perhaps there is a way to transform the problem so it can be solved using the demonstration's code? I need to try making all costs from stops to depots infinite, and costs from school/destination to bus depots all equal to zero.

Matthias,

Are you planning to do many of these types of problems or is this a "one off"? The recommended approach is different depending. Normally I would use software specific for this type of problem but if you want to create your own algorithm I can make some suggestions (which may or may not be helpful!).

One way to do it is to do a rough approximation that should give a reasonable solution:

As a simplifying first step let's just use your stops and assume one depot as the first point and the final destination is your 5th point (you can easily add the correct points to the list later) and assume this is a route for only one bus:

Define a lookup function for the point in the distStops list:

getDist[pt_] := Position[stops, pt][[1, 1]]

find the shortest tour:

tour2 = FindShortestTour[stops, 1, 5, 
  DistanceFunction -> (distStops[[getDist[#1], getDist[#2]]] &)]

This will route your bus from Depot (first point) to School (5th point) using the non-Euclidean distances.

Now the problem becomes breaking up the routes and stops so they are near the depots. As a quick cut you can create subsets of the stops near each depot and assign them into routes. You can create a heuristic and iterate a bit to move stops from individual routes that are longer than the others to routes that are shorter than the others. It seems like doing this a few iterations should give a reasonable solution with routes that are roughly the same duration. (although probably not globally "optimal")

I hope this helps.

Regards,

Neil