Minimize the number of vehicles

[TeodoraB21]

Hello!

I want to minimize the number of vehicles used. Does anyone know what constrain should I use?

I try to solve the c1_8_1 example from here https://www.sintef.no/projectweb/top/vrptw/homberger-benchmark/800-customers/ and the best solution uses 80 vehicles and the total distance is 25030.36. But my algorithm returns a solution with 96 vehicles and a total distance of 35012.73

[lperron]

are you using GLS ?

[orwant]

In case it's unclear, Laurent is asking whether you're using the GUIDED_LOCAL_SEARCH routing option https://developers.google.com/optimization/routing/routing_options#local_search_options .

Jon

On Thu, Jun 13, 2019 at 2:38 PM Laurent Perron notifications@github.com wrote:

are you using GLS ?

— 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/1356?email_source=notifications&email_token=ACFCEW277RJGWILEL4FNTVDP2KHZBA5CNFSM4HXYP6V2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXUVAUQ#issuecomment-501829714, or mute the thread https://github.com/notifications/unsubscribe-auth/ACFCEW3EWXHMFSIW5AZFO7TP2KHZBANCNFSM4HXYP6VQ .

[TeodoraB21]

Yes, I am using GUIDED_LOCAL_SEARCH and I set the time-limit even to 500 seconds, and the solution is the same.

The distance between 2 stops I calculated it with the distance between 2 points formula: real32 result = std::sqrt(std::pow(from[0] - to[0], 2) + std::pow(from[1] - to[1], 2));

[niangjunchen]

My approach is to add a fixed cost to each vehicle use:

routing.SetFixedCostOfVehicle(penalty, vehicle_idx)

and set the penalty parameter to be some large number, not sure if this is the best possible approach though.

[TeodoraB21]

Ok, I will try it. Thank you!

[TeodoraB21]

It worked! Is there a setting to minimize the total distance? Or what first solution strategy and local search options should I use?

[niangjunchen]

You can use SetArcCostEvaluatorOfAllVehicles(transit_callback_index) to minimize total distance. From my experience, parallel_cheapest_insertion seems better in most cases, but not always though.

[TeodoraB21]

I used SetArcCostEvaluatorOfAllVehicles(int distanceCallback) and the solution doesn't have the shortest distance.

[niangjunchen]

I used SetArcCostEvaluatorOfAllVehicles(int distanceCallback) and the solution doesn't have the shortest distance.

Well, the vehicle routing problem is NP-hard, which means there is no efficient algorithm that can guarantee to find the optimal solution. The ortools routing library implemented a lot of heuristic and local search algorithms, but it does not always find the optimal solution.

[GuyBenhaim]

Hello, If your "penalty" in routing.SetFixedCostOfVehicle(penalty, vehicle_idx) is lower than the penalty of dropping any single Node, do you see the solver totally skips this vehicle?

[niangjunchen]

If the cost of dropping a single node is higher than the cost of using a vehicle, ideally the solver would try to use more vehicles to meet all the demands rather than dropping some nodes to reduce the number of vehicles used.

[TeodoraB21]

I forgot to set the service times, and that's why my solution was so different than the one from benchmark.

[GuyBenhaim]

Yes, but seems that if vehicle FixedCost is higher than the cost of dropping any single node, but is much lower than the combined cost of dropping say 10 nodes - the solver still does not use the vehicle and drops all 10 nodes. Have you observed that?

[GuyBenhaim]

?

[lperron]

Please do not use closed issues. Open a discussion instead.