VRP: is there a good way to force a vehicle to visit some nodes/customers?

270ajay commented 6 years ago

Need help:

I have 2 Vehicles and 5 nodes/customers.

I want to add constraint to force vehicle_X to visit node_1, node_3 (in any sequence).

I have tried the following:

routing.solver().Add(
  routing.VehicleVar(routing.NodeToIndex(1)) == 
  routing.VehicleVar(routing.NodeToIndex(3)))

Which is not consistent. Gives infeasibility sometimes even after trying different First Solution Strategy.
AddSoftSameVehicleConstraint which is also not consistent in finding optimal solution. But it finds feasible solution violating the constraint even if I add a big penalty cost.
ApplyLocksToAllVehicles may be able do it but I don't want to lock sequence.

Thank you very much!

braktar commented 6 years ago

You have to make your constraint verified only if both of your node are active within the solution.

Using MakeConditionalExpression Or generating an intermediate boolean and putting it the following way :

constraintActive = routing.ActiveVar(routing.NodeToIndex(1)) * routing.ActiveVar(routing.NodeToIndex(3))
routing.solver().Add(
  constraintActive * routing.VehicleVar(routing.NodeToIndex(1)) == 
  constraintActive * routing.VehicleVar(routing.NodeToIndex(3)))

270ajay commented 6 years ago

Thank you for trying to help! @braktar

I can see that ActiveVar returns the active variable of the node corresponding to index. Could you please tell me what active variable of the node means?

I know there exists a solution for vehicle_X to visit node_1, node_3. However, using

routing.solver().Add(
  routing.VehicleVar(routing.NodeToIndex(1)) ==
  routing.VehicleVar(routing.NodeToIndex(3)))

gives me infeasible in some cases. You may see the last few comments here https://github.com/google/or-tools/issues/685#issue-320629750

Is there any other way to model it? Is there a way to force a specific vehicle, vehicle_1 to visit node_1, node_3?

braktar commented 6 years ago

routing.solver().Add(
  routing.VehicleVar(routing.NodeToIndex(1)) ==
  routing.VehicleVar(routing.NodeToIndex(3)))

This constraint induces that node_1 and node_3 must be within the same vehicle from the beginning of the resolution, which is not obvious for the solver until the constraints propagates. Both node have to be inserted at the same time within a vehicle. Which can enforced using "AddPickupAndDelivery". By default node are inserted sequentially. So if node_1 is inserted, node_3 is unassigned and the insertion can't be done.

270ajay commented 6 years ago

Thank you for your explanation @braktar

When I wanted same vehicle to visit nodes = [1,3,6], It worked for me and gave feasible solution when I used:

for i in range(0, len(nodes)-1):
   routing.solver().Add(routing.VehicleVar(routing.NodeToIndex(nodes[i])) == routing.VehicleVar(routing.NodeToIndex(nodes[i+1])))

However, when i added another node to nodes = [1,3,6,8] for which solution exists I get infeasible immediately (even when time_limit_ms = 30000). I have tried changing First Solution Strategy but only for some cases it worked.

Infeasible log:

WARNING: Logging before InitGoogleLogging() is written to STDERR
I0912 18:54:11.126096 13476 search.cc:244] Start search (memory used = 38.18 MB)
I0912 18:54:11.127593 13476 search.cc:244] Root node processed (time = 1 ms, constraints = 2124, memory used = 39.02 MB)
I0912 18:54:11.353176 13476 search.cc:244] Finished search tree (time = 226 ms, branches = 136, failures = 72, memory used = 39.99 MB)
I0912 18:54:11.353675 13476 search.cc:244] End search (time = 227 ms, branches = 136, failures = 72, memory used = 40.01 MB, speed = 599 branches/s)

I tried using AddPickupAndDelivery with nodes = [1,3,6] and I get the above infeasible log.

Is there a way to use SetValues or RemoveValues or another way to force a specific vehicle to visit a set of nodes/ for set of nodes to be visited by same vehicle?

Mizux commented 6 years ago

What about this method ?

// Adds a soft contraint to force a set of nodes to be on the same vehicle.
// If all nodes are not on the same vehicle, each extra vehicle used adds
// 'cost' to the cost function.
void AddSoftSameVehicleConstraint(
  const std::vector<NodeIndex>& nodes,
  int64 cost);

src: https://github.com/google/or-tools/blob/master/ortools/constraint_solver/routing.h#L591

270ajay commented 6 years ago

// Adds a soft contraint to force a set of nodes to be on the same vehicle.
// If all nodes are not on the same vehicle, each extra vehicle used adds
// 'cost' to the cost function.
void AddSoftSameVehicleConstraint(
  const std::vector<NodeIndex>& nodes,
  int64 cost);

src: https://github.com/google/or-tools/blob/master/ortools/constraint_solver/routing.h#L591

@Mizux AddSoftSameVehicleConstraint method gives feasible solution however, it does not give optimal solution and it may be due to First Solution Strategy when with dealing too many additional constraints?

I run solver with 231 locations and 50 vehicles and other constraints.
I store the solution in a list of list. For example: Solution = [[1,3,6], [8,9,11]] where [1,3,6] are locations served by same vehicle.
You can see the First Solution Strategy came up with solution of ObjectiveValue = 256000 in log below.
Best Solution found in time_limit_ms = 30000 is ObjectiveValue = 253968
Below is the log when I solve this problem.

WARNING: Logging before InitGoogleLogging() is written to STDERR
I0912 20:34:27.726068  7260 search.cc:244] Start search (memory used = 38.36 MB)
I0912 20:34:27.727564  7260 search.cc:244] Root node processed (time = 1 ms, constraints = 2117, memory used = 39.10 MB)
I0912 20:34:27.951648  7260 search.cc:244] Solution #0 (256000, time = 225 ms, branches = 84, failures = 0, depth = 33, memory used = 40.17 MB, limit = 0%)
I0912 20:34:27.966619  7260 search.cc:244] Solution #1 (255988, objective maximum = 256000, time = 240 ms, branches = 137, failures = 2, depth = 33, neighbors = 27, filtered neighbors = 1, accepted neighbors = 1, memory used = 40.37 MB, limit = 0%)

I rerun solver with same problem with the following additional constraints

    violationCost = 1000000
    for i in range(len(Solution)):
        routing.AddSoftSameVehicleConstraint(Solution[i], violationCost)

The First Solution Strategy now comes with a solution whose ObjectiveValue = 66256000
Local search cannot find good solution in 30 sec.
Best solution found in time_limit_ms = 30000 is ObjectiveValue = 41254589
Below is the log when AddSoftSameVehicleConstraint is used.

WARNING: Logging before InitGoogleLogging() is written to STDERR
I0912 20:49:16.242600 10612 search.cc:244] Start search (memory used = 46.36 MB)
I0912 20:49:16.281639 10612 search.cc:244] Root node processed (time = 39 ms, constraints = 10467, memory used = 51.04 MB)
I0912 20:49:16.684394 10612 search.cc:244] Solution #0 (66256000, time = 442 ms, branches = 84, failures = 0, depth = 33, memory used = 52.00 MB, limit = 1%)
I0912 20:49:16.712340 10612 search.cc:244] Solution #1 (66255988, objective maximum = 66256000, time = 469 ms, branches = 137, failures = 4, depth = 33, neighbors = 27, filtered neighbors = 3, accepted neighbors = 1, memory used = 52.21 MB, limit = 1%)

270ajay commented 6 years ago

I have found a workaround for this...

Using AddSoftSameVehicleConstraint along with setting initialRoutes for search is giving good feasible results BUT NOT THE BEST.

sameVehicleNodes = [[1,3,6], [8,9,11]]
initialRoutes = [[1,3,6], [8,9,11], [2,4,5,7], [10]]  # needs to be feasible.

violationCost = 1000000
for i in range(len(sameVehicleNodes)):
     routing.AddSoftSameVehicleConstraint(sameVehicleNodes [i], violationCost)

initialAssignment = routing.ReadAssignmentFromRoutes(initialRoutes, True)

searchParameters = pywrapcp.RoutingModel.DefaultSearchParameters()
searchParameters.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
searchParameters.time_limit_ms = 30000
searchParameters.log_search = True

assignment = routing.SolveFromAssignmentWithParameters(initialAssignment, searchParameters)

NOT THE BEST because when using initialRoutes:

the solver mostly terminates before searchParameters.time_limit_ms = 30000. Why is that? If the solver ran till 30sec, it could get a better solution (i know a better solution exists).
log is NOT printed even when searchParameters.log_search = True. Why?
Any method that can accept partial routes as initialRoutes for search?

Other questions:

Is there a way to use use_depth_first_search to get initial solution and then start local search?

mateuscardosogs commented 6 years ago

hello guys, I have a problem a little bit alike, could you help me?

I have the CVRPTW algorithm in python.

I would like to know how to add constraints to force node_1, node_7, and node_3, for example, to be on the same route (in any sequence), before starting the solver, and when running the algorithm it adds more nodes to those routes if they obey the capacity constraints and time window.

Example:

I have N initial groups before running the solver: [[1,7,3], [2,9], [8, 4, 5, 12, 6, 15]]

After running the solver (until you complete the capacity constraints and time window): [1, 11, 7, 14, 3], [19, 2, 17, 9], [8, 4, 5, 12, 6, 15]]

Note: All code must be in python

Thank you very much in advance to all who can help. I'm grateful!

Mizux commented 6 years ago

@mateusc42 Does partial route (like above example) doesn't solve your issue ?

mateuscardosogs commented 6 years ago

@Mizux In case for my idea I just needed the initialRoutes. My question was whether it was the best solution. I also thought about doing this division by vehicle using tags, but I did not find any examples in python. Would you know some example tag restrictions using python?

mateuscardosogs commented 6 years ago

Hi @Mizux, I got to test the method of @270ajay, but it did not work for me, because the way I want to do after optimizing the routes the values that are in the groups could not separate and I realized that maybe this is not the best solution, so I thought of a new possibility. I would like to know how to define categories in the destination and in the vehicles, so the destinations could only be visited by those vehicles with specific category.

Example:

location 1 - category: type1 location 2 - category: type2 location 3 - category: type3

vehicle 1 - category: type1, type3 vehicle 2 - category: type2

Would anyone have an example of this model using python?

Thanks in advance.

Georgepop commented 5 years ago

for location_idx,x in enumerate(location_i.loc[:,'car']):
routing.VehicleVar(location_idx).SetValues(list2d)

this is how you should do it ! list2d- is set of points a given vehicle can visit

weslleylc commented 5 years ago

Would anyone have an example of how to fix partial routes? I want to give an initial solution that can not be modified (nodes removed), but can have new nodes added.

lperron commented 5 years ago

You can restrict the vehicle var of that visit. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le lun. 20 mai 2019 à 18:52, Weslley Lioba Caldas notifications@github.com a écrit :

Would anyone have an example of how to fix partial routes? I want to give an initial solution that can not be modified (nodes removed), but can have new nodes added.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/847?email_source=notifications&email_token=ACUPL3J5F7KFGVC7Y6E2AADPWLJMDA5CNFSM4FUUJJ32YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODVZN44I#issuecomment-494067313, or mute the thread https://github.com/notifications/unsubscribe-auth/ACUPL3JFKT5T7WLDQPFDPB3PWLJMDANCNFSM4FUUJJ3Q .

Georgepop commented 5 years ago

sorry for location_idx,x in enumerate(location_i.loc[:,'car']): routing.VehicleVar(location_idx).SetValues(list2d)

location_idx - point list2d-a set of vehicles can visit

in case of weslleylc: vehicle_id=1 for location_idx in nodes: routing.VehicleVar(location_idx).SetValues(vehicle_id)

tvwenger commented 5 years ago

NOT THE BEST because when using initialRoutes:

* the solver mostly **terminates before** `searchParameters.time_limit_ms = 30000`. Why is that? If the solver ran till 30sec, it could get a better solution (i know a better solution exists).

* log is **NOT printed** even when `searchParameters.log_search = True`.  Why?

* Any method that can accept partial routes as `initialRoutes` for search?

I know I'm late to the party here, but I just spent a few hours flailing around with this same problem. Google led me to this discussion.

Noting Paul Trow's final comment:

Geoff,

You were correct in the first place - you do have to call CloseModelWithParameters(search_parameters) first, before calling ReadAssignmentFromRoutes in order to use the search parameters. (Except for some reason this doesn't apply to the search limits, such as time_limit_ms - that's what was confusing me. Incidentally, the parameter name is time_limit_ms - not set_time_limit_ms. That parameter can be passed by ReadAssignmentfFromRoutes, even without doing CloseModelWithParameters(search_parameters).

ReadAssignmentFromRoutes() does call CloseModel, which does not preserve the parameters. But if you do the CloseModelWithParameters first, the subsequent CloseModel() has no effect.

Sorry for the confusion.

Best,

Paul

The problem you were seeing, @270ajay is that ReadAssignmentFromRoutes closes the model and discards any search parameters you might set later. Here is the proper way to do it such that the search parameters are maintained:

"""
Set search parameters, then close the model
"""
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.local_search_metaheuristic = \
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
search_parameters.time_limit.seconds = 10
search_parameters.log_search = True
routing.CloseModelWithParameters(search_parameters)
"""
Set initial assignment, then solve
"""
initial_assignment = routing.ReadAssignmentFromRoutes(initial_route, True)
assignment = routing.SolveFromAssignmentWithParameters(initial_assignment, search_parameters)

I don't know who is in charge of the documentation, @lperron @Mizux, but I think this should be addressed on the VRP page. Unless you're using the default search parameters, this is quite an undocumented headache!

270ajay commented 5 years ago

Thank you very much @tvwenger, @Georgepop!

SiddharthaPaul commented 4 years ago

@270ajay @Mizux @tvwenger I am working on a similar problem where I want to lock the initial route sequence up to [[1,3], [8,9]] and solve a new VRP with the existing nodes [6, 11] and a few new nodes [[2,4,5,7], [10]]. So how do I find an initial feasible solution like [[1,3,6,10], [8,9, 11,2], [4,5,7]]? Please note I am solving in python. Help will be highly appreciated.

Georgepop commented 4 years ago

@SiddharthaPaul, I think would be like this :

vehicle_id=[1] for location_idx in [1,3]: routing.VehicleVar(location_idx).SetValues(vehicle_id)

vehicle_id=[2] for location_idx in [8,9]: routing.VehicleVar(location_idx).SetValues(vehicle_id)

SiddharthaPaul commented 4 years ago

@Georgepop Thanks a lot! Will try this out. How we can improve the initial solution? I have tried the approach suggested by @tvwenger with "routing.CloseModelWithParameters(search_parameters)". But not working and returning the following error: ->next_node_index = routing.IndexToNode(assignment.Value(routing.NextVar(index))) AttributeError: 'NoneType' object has no attribute 'Value'

pandeyhs commented 3 years ago

I'm trying to constrain the optimizer to put the following list on the same vehicle. [[1,2],[3,4,5],[8,9]] For example - Node 1&2 should be on the same vehicle, Node 3,4&5 should be on the same vehicle, and Node 8&9 should be on the same vehicle.

I have already tried the SoftSameVehicleCosntraint, however, it gets overridden when the solution is applied on bigger sets. Is there any other scalable way of constraining a group of nodes to the same vehicle?

Any help would be appreciated at this point! Thank you!

pandeyhs commented 3 years ago

I just was able to add the same vehicle constraint by modifying the distance matrix. First I blew up the values in the distance matrix by adding a large constant to all the distances. I changed the distance value between Node 1 & Node 2 to 0, the same was done to the rest of the grouped locations [[1,2],[3,4,5],[8,9]], for each group the distance value for each pair was changed to 0. This ensures that all the nodes in the same group are always assigned to the same vehicle, since the distance between them is 0, they are treated as the same location.

I'm not using the SoftSameVehicleConstaint anymore, that was not helpful at all.

The above solution worked for me, hopefully, it works for others as well.

Mizux commented 3 years ago

so basically you are forcing the arc 1->2, 3->4->5, 8->9. Did you try to use some constraint like here: https://gist.github.com/Mizux/9e37c370a459bd472a6ac13c304f0b54

google / or-tools

VRP: is there a good way to force a vehicle to visit some nodes/customers? #847