Suboptimal routes when using multiple depot

[hopewise]

I have locations list of length 39, including 1 starting locations, 4 end locations.
In routes solution I got node at 38, 39, 40, 41, so there are 3 nodes out of location's list range, each one in a route.

What can be the reason for that?

[braktar]

Start and End nodes are duplicated for each routes. Be sure to manipulate the index and not the node, using nodeToIndex, in order to manipulate the correct object index.

or-tools/ortools/constraint_solver/routing.h

Line 951 in 9487eb8

int64 NodeToIndex(NodeIndex node) const;

[Mizux]

Also be sure to manipulate start and end node using routing.Start(vehicle_id) and routing.End(vehicle_id) respectively when adding constraint to them...

related to #708 issue

[hopewise]

@braktar Start nodes are the buses start locations at my case, End nodes are same for all buses, which is the school location actually.

Here is how I fill the locations list:

self._start_locations = []
self._end_locations = []
for x in buses_locations:
  # I add the school index each time for end_locations
  self._end_locations.append(0) 
  # as the bus location is  appended to locations, I add its index:
  start_index= len(self._locations)
  self._start_locations.append(start_index) 
  # the bus location ( start location is added to locations )
  self._locations.append(x)

@Mizux I do manipulate start and end node as:

def solution_output(self):
  routes = []
  for vehicle_nbr in range(num_routes):
    index = routing.Start(vehicle_nbr)
    route = [index] # should be the bus start location

    while not routing.IsEnd(index):
      index = assignment.Value(routing.NextVar(index))
      node_index = routing.IndexToNode(index)
      route.append(node_index)
    routing.End(vehicle_nbr)
    routes.append(route)
  return routes

Out of range seems to be solved, but the results are strange, I have developed a front end tool to experiment with the OR Tools library, by which I can determine the strategy on the fly, here is what I got:

yellow markers are the buses, notice the following:

1. each bus starts with a far away student rather than starting with the closer one.. even when I try different strategies..
2. the route colored with red is not starting from the bus!

Any advice?
Is there an example close to my case that you can point me to?

[hopewise]

Here is another strategy solution (path most constrained arc) only one route seems to be good (top left bus )

[Mizux]

You should take a look at https://github.com/google/or-tools/blob/master/examples/python/cvrp.py

As statute before index must be converted to a "node index" ie a location index so change your output routine to:

def solution_output(self):
    routes = []
    for vehicle_nbr in range(num_routes):
        index = routing.Start(vehicle_nbr)
        route = [routing.routing.IndexToNode(index)] # should be the bus start location

        while not routing.IsEnd(index):
            index = assignment.Value(routing.NextVar(index))
            node_index = routing.IndexToNode(index)
            route.append(node_index)
        route.append(routing.IndexToNode(routing.End(vehicle_nbr))) # to add the bus end location end aka start location
        routes.append(route)
    return routes

[hopewise]

Thanks for output routine, as I am newbie to OR-Tools library, here is the result after update it:

however, only top-right bus route seems to be reasonable, do you agree with me?

[Mizux]

well, without knowing which constraints you use it's difficult to say if result is reasonable or not.

Also OR-Tools use a two steps algo:

1. Using your model, the specified first strategy and all constraints the solver try to find a first correct solution (not necessary optimal only feasible i.e. not violating any constraint)
2. Then using a local search meta-heuristic, solver will try to refine this solution to find a better solution from it (e.g. interchange nodes etc)
   note you can activate log using:

search_parameters.log_search = True

note: if your model is strongly constrained your first solution will be near to optimal and local search (step 2) won't increase so much the solution (i.e. could be disable), on the other hand if your constraints are loose solver can find a first "dirty" solution very fast but not "so reasonable".

Also your image seems like route loop from yellow point as start and end node i.e. the red point in the center is not part of the other routes (only the orange one) (yellow -> {1, 2, 3} -> yellow) -> Did you use a vector of depots, ends nodes ?

[hopewise]

Well, I found that the order of which locations are stored into locations list does matter. ex: (A, B, C) will get different order result if revered as (C, B, A)

For example, having the same parameters at DataProblem with the same strategy, and the same constrains (just capacity constrain), I got two different results.

Result 1, (order of locations from start to origin)

Result 2, (order of locations from origin to start)

Do you mean that I have to run local solution on each route to determine the best order?

Also, can you please explain, strongly constrained and loose constraints?

[hopewise]

Even if I changed the order of start locations, the result is different:

Result 3

Result 4

How can I get results as expected (Result 1 and 3 above) regardless of locations order into locations list? and why locations order does matter?

[Mizux]

Did you use the routing.SetArcCostEvaluatorOfAllVehicles() ?
Basically first solution strategy base its distance calculation on it to create a first reasonable solution otherwise all node are equidistant to each others (i.e. all distance are zero) so solver just have to pick them randomly (e.g. in order) -> ugly first solution...

cf: https://github.com/google/or-tools/blob/master/examples/python/cvrp.py#L258
to test I use https://github.com/google/or-tools/tree/mizux/doc/doc i.e. I output svg image on console that I could pipe to inkscape to view the result using the vrp_svg.py program

[hopewise]

yes, I use it, as here:

routing.SetArcCostEvaluatorOfAllVehicles(distance_evaluator)
# Add Capacity constraint
demand_evaluator = CreateDemandEvaluator(data).demand_evaluator
add_capacity_constraints(routing, data, demand_evaluator)

yes, I am using a vector of depots (start points), ends nodes (the same end point), as here:

self._start_locations = []
self._end_locations = []
for x in buses_locations:
  # I add the school index each time for end_locations
  self._end_locations.append(0) 
  # as the bus location is  appended to locations, I add its index:
  start_index= len(self._locations)
  self._start_locations.append(start_index) 
  # the bus location ( start location is added to locations )
  self._locations.append(x)

as here

it seems that I am not doing local search?

[Mizux]

EDIT: Local search is enable by default (only the guided search is not)
cf https://developers.google.com/optimization/routing/routing_options#local-search-options
example here: https://developers.google.com/optimization/routing/tsp#changing-the-search-strategy
note: you can enable log using:

search_parameters.log_search = True

Concerning first solution strategy doc here: https://developers.google.com/optimization/routing/routing_options#first-solution-strategy-options
Did you try PARALLEL_CHEAPEST_INSERTION, LOCAL_CHEAPEST_ARC or PATH_CHEAPEST_ARC ?

In result 3/4 point 1 is the cheapest arc to insert (compare to the farther checkpoint 3) so I would say even during the first strategy pass solver should choose it as good candidate.
note: I never play with multiple depot/ends

[hopewise]

Thanks for the links, I have added local search, but I could not see any effect.

# used_strategy is dynamic to make testing easy
search_parameters.first_solution_strategy = (
        getattr(routing_enums_pb2.FirstSolutionStrategy, used_strategy)
    )

# used_local_search_strategy is dynamic to make testing easy
    search_parameters.local_search_metaheuristic = (
        getattr(routing_enums_pb2.LocalSearchMetaheuristic, used_local_search_strategy)
    )

I have recorded this video so that you can have a look here: https://youtu.be/0HvW0Epubic

In the video you will see two tabs for the same settings, the locations order is the only difference, I used all the possibilities, but I had the expected solution only when the locations were already sorted (from start to end )

[Mizux]

Thanks for the video, I'll try to do some tests also...
Keep this issue open as reminder

[hopewise]

@Mizux Hi! did you try some tests on cases with multiple starting locations?

[Mizux]

Hi, in a related issue #727 (comment) and on my branch mizux/java. I figure out that few examples (and me too) sometime missmatch "node index" and "index".

Are you sure to use the correct index when reading the solution etc ?
You should try to display/compare i and model.NodetoIndex(i) for all locations except start and end.
and use IndexToNode() when reading the solution.
cf https://github.com/google/or-tools/blob/master/examples/python/cvrptw.py#L325

[hopewise]

if we consider reading the solution as phase 2 at which we use IndexToNode(), what would be phase 1 which I shall use model.NodetoIndex(i) ?

I tried NodeToIndex for non end and start of route when reading the solution as:

for vehicle_nbr in range(num_routes):
    index = routing.Start(vehicle_nbr)
    route = [routing.IndexToNode(index)]

    while not routing.IsEnd(index):
        index = assignment.Value(routing.NextVar(index))
        node_index = routing.NodeToIndex(index)
        route.append(node_index)
    route.append(
            routing.IndexToNode(routing.End(vehicle_nbr)))
    routes.append(route)
return routes

but I got strange results for routes solution:

<class 'list'>: [7, 1, 0, -1, 7, 0]
<class 'list'>: [8, 4, 3, 2, 0, 0]

where can I find documentation about IndexToNode and NodeToIndex ? and about definition of node and index with respect to the algorithm? as I read internal solver at #727 (comment) could not find documentation about even here https://developers.google.com/optimization/ ..

[Mizux]

I agree with your phase 1 and phase 2 usage.

I thing you have a miss take in your code. in the while loop second line Value(NextVar()) return an index type.

index = assignment.Value(routing.NextVar(index))
node_index = routing.NodeToIndex(index)

should be

index = assignment.Value(routing.NextVar(index))
node_index = routing.IndexToNode(index)

also your loop seems to have an error I mean you verify while not routing.IsEnd(index) but use NextVar(index) just after...
I would rewrite it like this:

routes = []
for vehicle_nbr in range(num_routes):
    index = routing.Start(vehicle_nbr)
    route = []
    while not routing.IsEnd(index):
        node_index= routing.IndexToNode(index)
        route.append(node_index)
        index = assignment.Value(routing.NextVar(index))      
    route.append(routing.IndexToNode(index))
    routes.append(route)
return routes

Personally I use this loop to display store result...
src: https://github.com/google/or-tools/blob/master/examples/python/cvrp.py#L221

Unfortunately there is not doc on NodeIndex vs Index and half of our examples are broken, I'm currently trying to fix all examples when possible.

ProTips: use ```python when writing code block to have syntax coloration (I try to fixed few of your comments but if you can do it yourself ;))
src: https://help.github.com/articles/creating-and-highlighting-code-blocks/#syntax-highlighting

[hopewise]

Dear Mizux, I've fixed the loop now as you've mentioned, unfortunately, I am still getting un-reasonable solution for a trivial case, I've recorded another video which can see here

Two start locations, the algorithm decides to pick the far start location instead of the close one:

Ah .. what could be wrong?
By the way, thanks for the ProTips about ```python didn't know about it..

[ilaif]

@hopewise any change you are willing to share the source code of the front end tool you developed? I would find it very useful :)
Thanks in advance.

[hopewise]

@ilaif I will try to ask that company I was working with.. as I don't have that source code.. basically what I did is a frontend for testing the algorithm..

and as for the issue I was having above, it was related to calculating distances in the matrix.. it wasn't calculated correctly..

[donpaul120]

Thanks for output routine, as I am newbie to OR-Tools library, here is the result after update it:

however, only top-right bus route seems to be reasonable, do you agree with me?

Please what UI tool is this, I'm very new to OR-Tools and i really need to get up to speed

[hopewise]

That was a react project I wrote while learning about or-tools as well, unfortunately, I don't have access to that react project now.. I love visualization, it makes learning and reasoning much easier..