Handling un-satisfiable setups

[amih77]

Hello,

Setup: VRPTW, 10 vehicles, 35 locations. I have a feasible solution

I'm currently facing a situation where all heuristics, meta or first_solution manage to assign only 34, but when I'm forcing the solver to my known solution it finds it under all heuristics.

I want to ask if there's a method to deal with these cases, or a work around.

I got the full assignment from a solution to the same dataset plus an extra location, up to small variations in the time windows - ones that are not changing the satisfiability of the instance, obviously but rather the ability of the solver to find an assignment for all 35 locations.

[Mizux]

Did you enable the Guided Local Search ? did you set a time limit ?

[amih77]

@Mizux No guided local search, I have a time limit. Is there an example for me to see?

[Mizux]

Look at VRP with time limit samples here: https://github.com/google/or-tools/tree/stable/ortools/constraint_solver/samples
IIRC this sample is provided in C++, Python, Java and C#

e.g.

or-tools/ortools/constraint_solver/samples/vrp_with_time_limit.py

Lines 95 to 104 in 45770b8

	# Setting first solution heuristic.
	# [START parameters]
	search_parameters = pywrapcp.DefaultRoutingSearchParameters()
	search_parameters.first_solution_strategy = (
	routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
	search_parameters.local_search_metaheuristic = (
	routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
	search_parameters.log_search = True
	search_parameters.time_limit.FromSeconds(10)
	# [END parameters]

[amih77]

Thanks @Mizux, before your reply, I found an assignment with TABU_SEARCH - not explicitly mentioning any first solution strategy. Now, I ran over all pairs of heuristics and TABU_SEARCH and LOCAL_GUIDED_SEARCH and find nothing....