Premature solution - VRP ortools

[bhavya padmanabhan]

Hi, 

I am using Google ORtools to solve a vehicle routing problem. However, I am getting premature solution when the order of the input changes. Specifically, I have two vehicle types electric and diesel, and the service time of the two vehicle types are different. This is achieved by assigning factors for each vehicle types for instance, veh_factors = [1, 10] and veh_types = ['EV', 'DV'] meaning DV's service time is 10 times higher than EV.  the goal is to let the model choose the vehicle types while finding the optimal route. 

I am testing this with a toy problem with 3 requests and 5 vehicles. Suppose if there are 3 DVs and 2 EVs, and vehicle ids are 0, 1, 2 for DVs and 3, 4 for EVs and the order of vehicle factor input is veh_factors = [1, 100] (for veh_types = ['DV', 'EV']) I am getting a better solution. One vehicle is serving all requests. However, when I change the order such that veh_factors = [100, 1] and veh_types = ['DV', 'EV'], I am getting a premature solution;  each vehicle is serving only one request.  

The search parameters I have used are:

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    #to get an initial solution

    search_parameters.first_solution_strategy = (

        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    #to find a better solution

    search_parameters.local_search_metaheuristic = (

    routing_enums_pb2.LocalSearchMetaheuristic.AUTOMATIC)

    search_parameters.time_limit.seconds = 90

I have attached the code here and can provide more details if that helps. I would greatly appreciate any assistance. 

Thank you, 

Bhavya 

[bhavya padmanabhan]

In addition, I have tried other built in  metaheuristics other than 'AUTOMATIC' like  GUIDED_LOCAL_SEARCH, SIMULATED_ANNEALING, and TABU_SEARCH, however, I got the same result. 

Thank you, 

Bhavya 

[J. E. Marca]

Hi,

A quick observation.  Inside of your vehicle loop, where you create
the transit callback per vehicle and also set the cost evaluator of
each vehicle, you define the same time dimension multiple times with
different transit callbacks.

I think that is wrong.

I would suggest that you should make another callback that does not
include the per-vehicle factor weight, and use that for a clean,
vanilla time dimension.

Then create just one time dimension...take the "AddDimension" call
outside of the `for vehicle_id ...` loop.

I don't really understand why you are doing what you are doing with
the costs and all that, and I don't have the time to do a thorough
debugging of your code.  So I can't really address your original
question much.  But maybe defining too many "time" dimensions is the
root cause of your bug?

Hope that helps,

James

[bhavya padmanabhan]

Hi, 

Thank you very much for your help and I will definitely try that. 

Best, 

Bhavya 

--
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 visit https://groups.google.com/d/msgid/or-tools-discuss/0e2b8e37-ac74-4038-a92d-a454719f2c73n%40googlegroups.com.