Message Boards Message Boards

Solve bus routing problem with a single destination and multiple depots?

GROUPS:

I'm trying to optimize the transportation of a fleet of buses that: (1) start from several depots, (2) pick up students from several stops, and (3) drop off all students at a single destination (the school). Travel times are not symmetric: the time to go from Point A to Point B is not the same as from Point B to Point A. The goal is to minimize the number of buses and finding their routes while satisfying the constraint that no student should travel for longer than k = 1.5 times the duration of the direct route from her bus stop to school.

To simplify the problem, let's assume that buses have infinite capacity, ie. each bus can accommodate all students at all stops on its route.

I am aware that this is a well studied, hard, problem e.g., a recent presentation in:

https://www.acsu.buffalo.edu/~qinghe/thesis/2017-01%20Caceres%20PhD%20School%20Bus%20Routing.pdf

I have tried without much luck to trick FindShortestTour using a cost matrix with "phantom", duplicated destinations, infinite distances, etc.

Any thoughts? Toy data below.

nstops = 50;
nbus = 10;
ndepots = 4;

destination = {0, 0};
depots = Table[
   ReIm[(1 + RandomReal[.1*{-1, 1}])*
     Exp[I*2*(j*Pi/ndepots + RandomReal[.1*{-1, 1}])]], {j, 0, 
    ndepots - 1}];
stops = RandomReal[{-1, 1}, {nstops, 2}];

ListPlot[stops, 
 Epilog -> {PointSize[Large], Red, Point[destination], Black, 
   Point[depots]}, PlotRange -> {{-1.5, 1.5}, {-1.5, 1.5}}, 
 AspectRatio -> 1]

distStops = 
  Table[If[i == j, 0, 
    EuclideanDistance[stops[[i]], stops[[j]]]*RandomReal[{0.9, 1.2}]], {i, 
    nstops}, {j, nstops}];

distDepotsStops = 
  Table[EuclideanDistance[depots[[i]], stops[[j]]]*RandomReal[{0.9, 1.2}], {i,
     ndepots}, {j, nstops}];

distStopsDestination = 
  Table[EuclideanDistance[stops[[i]], destination]*RandomReal[{0.9, 1.2}], {i,
     nstops}];

Distances from stops to depots and from depots to destination are infinite.

POSTED BY: Matthias Odisio
Answer
1 month ago

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

POSTED BY: Neil Singer
Answer
1 month ago

Thanks Neil.

It's definitely a "one-off' thing --- nothing commercial at stake here.

I played a bit with heuristics akin to what you mention. My progress was so slow I felt the method might not converge. Perhaps I should go back to this mixed, user-guided, approach, and manually tweaks routes until I find a set that works.

Alternatively, there's implementing a published algorithm. Unfortunately papers that seem relevant (e.g. references 3 to 10 in the linked dissertation above) are behind a paywall...

POSTED BY: Matthias Odisio
Answer
1 month ago

There is a related Wolfram Demonstration at
http://demonstrations.wolfram.com/TheVehicleRoutingProblem/ If you download the author notebook, you can see how it's implemented.

POSTED BY: Ted Ersek
Answer
1 month ago

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.

POSTED BY: Matthias Odisio
Answer
1 month ago

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

POSTED BY: Neil Singer
Answer
1 month ago

This is useful information, Neil.

I ended up with this simple, non-optimal, algorithm: 1. Cluster all stops according to their nearest depot 2. Within each cluster, start a route taking the furthest stop and greedily adding the nearest stops until the route does not satisfy the requirements any more.

travelTimes[route_List] := 
  Reverse@Accumulate@Reverse[Append[
      distStops[[#[[1]], #[[2]]]] & /@ Partition[route, 2, 1], 
      distStopsDestination[[Last@route]]]];

routeOKQ[route_List] := With[{\[Alpha] = 1.5}, 
   And @@ MapThread[#1 < \[Alpha]*#2 &, {travelTimes@route, distStopsDestination[[route]]}]];

findRoutes[indices_List] := Module[
   {pool, route, routes, i0, r, c},
   pool = indices;
   routes = {};
   While[Length@pool > 0,
       route = {pool[[First@Ordering[distStopsDestination[[pool]], -1]]]};
        pool = DeleteCases[pool, Alternatives @@ route];
        While[Length@pool > 0,
             c = pool[[First@Ordering[distStops[[route[[-1]], pool]], 1]]];
             r = Append[route, c];
             If[routeOKQ@r,
                  route = r;
                  pool = DeleteCases[pool, Alternatives @@ route]
                  ,
                  Break[]
              ]
         ];
        AppendTo[routes, route];
        pool = DeleteCases[pool, Alternatives @@ route];
    ];
   routes
   ];

Example:

nstops = 50;
ndepots = 4;

destination = {0, 0};
depots = Table[ReIm[(1 + RandomReal[.1*{-1, 1}])*Exp[I*2*(j*Pi/ndepots + RandomReal[.1*{-1, 1}])]], 
                {j, 0, ndepots - 1}];
stops = RandomReal[{-1, 1}, {nstops, 2}];

distStops = Table[If[i == j, 0, EuclideanDistance[stops[[i]], stops[[j]]]*RandomReal[{0.9, 1.2}]],
 {i, nstops}, {j, nstops}];

distDepotsStops = Table[EuclideanDistance[depots[[i]], stops[[j]]]*RandomReal[{0.9, 1.2}], {i, ndepots}, {j, nstops}];

distStopsDestination = Table[EuclideanDistance[stops[[i]], destination]*RandomReal[{0.9, 1.2}], {i, nstops}];

nf = Nearest[Range@ndepots, DistanceFunction -> (distDepotsStops[[#2, #1]] &)];
c = Flatten@nf[Range@nstops, 1];
allroutes = Flatten[Table[findRoutes[Flatten@Position[c, k]], {k, ndepots}], 1];

ListPlot[stops, Prolog -> {
   Table[{Hue[i/Length@allroutes], 
     Line[Append[stops[[allroutes[[i]]]], destination]]}, {i, 
     Length@allroutes}],
   PointSize[Large], Red, Point[destination], Black, Point[depots]
   }, PlotRange -> {{-1.5, 1.5}, {-1.5, 1.5}}, AspectRatio -> 1]
Attachment

Attachments:
POSTED BY: Matthias Odisio
Answer
1 month ago

Group Abstract Group Abstract