Do ORTools always find a solution if it exists?

[Constantine Filin]

greetings

I have a CVRPTW problem and observe the following ORTools behavior:

1. First i have 2 vehicles and 9 orders and 1 depot. I run an ORTools script and it shows me an optimal route - 5 orders on one vehicle and 4 orders on the other. Everything is fine at this point.
   
   
2. Then I run the _same_ ORTools script but this time submitting to it only 1 vehicle (vehicle #1) and the 5 orders that the previous run of ORTools showed me as possible on vehicle #1. At this point ORTools returns an error showing there is no solution. Hm...

From step #1 it follows that there is indeed a solution for 5 orders on vehicle #1 but why does the second run tell me that there isn't?

Do ORTools *always* find a solution if there is one?
Or they do it only with certain likelihood?

Thanks!!!

[Laurent Perron]

No. 

1) this can be very difficult (still NP-Hard)

2) first solution methods are heuristics and can fail

This is why we recommend creating an easier problem (more vehicles, time windows with soft penalties) and let the optimizer improve upon the first solution.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/f70d779b-e2eb-4177-808c-f68fa6f8b2aan%40googlegroups.com.

[Constantine Filin]

greetings

About "first solution methods are heuristics and can fail"

I am trying to work around the first solution method failing.

So I build a model and attempt to search for a solution using different first solution strategies.

Literally I have code like this

```

for fss in [PARALLEL_CHEAPEST_INSERTION,GLOBAL_CHEAPEST_ARC,...,]:

    search_parameters.first_solution_strategy = fss

    routingModel.SolveWithParameters(search_parameters)

```

 

The trouble is that as soon as i try to solve the model with a first solution strategy that does not work, all other first solution strategies fail as well.

They fail even if the solution can be found with a strategy if i try to use this strategy strategies before the failed strategy.

In other words, after building a model I have only 1 chance to try to find the solution with the right solution strategy.

Is there a way to reset a model and try with another first solution strategy after searching with the previous one failed?
Is there another way who to work around the first solution failing problem?

Thank you

[arnaban...@gmail.com]

It seems that you are just using the first among the first solution strategies. Rather than reassigning the first solution you need to reinitiate the entire problem like so:

Steps:

1. Create a solve function  which creates a solver model by taking first solution strategy and the raw data as arguments.

2. Run "solve function(PARALLEL_CHEAPEST_INSERTION, raw data)"

3. If no solution found, run "solve function(GLOBAL_CHEAPEST_ARC, raw data)"

4. Continue until the last solution is found or the first solution strategies are exhausted.

[Constantine Filin]

Thanks for taking a look at this

Yes, I created that function and i do re-initiate the entire problem for each new first solution strategy to try.

I try these strategies in this order

    first_solution_strategies = [
        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC,
        routing_enums_pb2.FirstSolutionStrategy.SAVINGS,
        # routing_enums_pb2.FirstSolutionStrategy.SWEEP,
        routing_enums_pb2.FirstSolutionStrategy.CHRISTOFIDES,
        routing_enums_pb2.FirstSolutionStrategy.PARALLEL_CHEAPEST_INSERTION,
        routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_INSERTION,
        routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC,
        routing_enums_pb2.FirstSolutionStrategy.LOCAL_CHEAPEST_ARC,
        routing_enums_pb2.FirstSolutionStrategy.FIRST_UNBOUND_MIN_VALUE,
        routing_enums_pb2.FirstSolutionStrategy.AUTOMATIC,
    ]

Sometimes it works.
Sometimes it doesn't work even though there is an obvious solution that i can find myself

I guess something needs to be done with the setup of the problem itself, will have to look into it

BTW, it there a way to use ORTools to limit the total time from pickup to dropoff of an order?
I.e. it does not matter when i pick an order up but it is important that it does not pass more than - say - 1 hour

between the moment of the pickup and the moment of the dropoff?

Thank you

You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/exaJ6gqRH2c/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/812c350c-1bde-426b-b70a-7225f9bc7459n%40googlegroups.com.

[arnaban...@gmail.com]

You can just initiate the first solution strategy by defining the initial route yourself using "ReadAssignmentFromRoutes" function if that's the case. Also, if you can mention the steps you are using to arrive at the first solution yourself then maybe that strategy can also be added in the or-tools.

Open a separate discussion with respect to your pickup and delivery problem so that the problem gets visibility. I have personally dealt with routing problem so I don't know if it applies to your use case or not. I would personally create a time dimension and modify the speeds of the vehicles in such a way that some of the vehicles can fulfil  the deliveries within your time limit. Also another way might be, if you can reset the time of pickup to 0 by unloading time_dimension during pickup (check out cvrp_reload example where demand is getting unloaded at the depots) then you can specify the maximum time a vehicle can travel for.

[Constantine Filin]

Thanks, I opened a separate discussion about limiting time from pickup to delivery.

As for "if you can mention the steps you are using to arrive at the first solution yourself", I just build the solution by hands using Google Maps.
This is why i know that a solution exists but ORTools does not return it to me.

It is likely that it bumps into some constraint. I am going to have to find out what it is.

Thanks again! 

[Laurent Perron]

These are exactly the time of constraints that break both the first solution heuristics and the local search. 

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/02dc490a-8b7a-4e22-a291-8609a754a202n%40googlegroups.com.

[Constantine Filin]

You keep talking about first solution.

Why is it so important?

Is it because ORTools work by first finding _any_ solution (aka "first solution") and then slowly moving away from it to optimize the other constraints?

The answer on this question will give me a good insight into ORTools.

thank you 

[Laurent Perron]

Because the routing library is using local search. local search needs a feasible solution to begin searching. feasible solutions are either given by the user, or searched for using first solution heuristics.

So until the solver gets/finds a first solution, it returns nullptr, that is no solution found.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/15aa6817-18dd-4db4-9720-6bd951187068n%40googlegroups.com.

--

--Laurent