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

Posted 3 years ago
7590 Views
|
6 Replies
|
6 Total Likes
|
 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.pdfI 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.
6 Replies
Sort By:
Posted 3 years 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 3 years 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 3 years ago
 There is a related Wolfram Demonstration athttp://demonstrations.wolfram.com/TheVehicleRoutingProblem/ If you download the author notebook, you can see how it's implemented.
Posted 3 years 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.
 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]  Attachments: