Routing problem: Manual assignment better than solver for small testcases.

[rpb...@gmail.com]

Hi Team, 

Can someone please guide me  on an "apparently simple" routing problem that has a better manual solution where I'm able to assign all loads to available trucks, but the solver seems to be dropping some loads (despite additional trucks being available).

Problem: 

Material has to be dispatched from a warehouse to multiple destinations (nodes) using minimum trucks (and drop the fewest loads possible) given the following constraints: 

1. Two types of trucks: each with a maximum & minimum capacity it can carry. 
   1. I enabled this constraint setting max capacity of truck using AddDimensionWithVehicleCapacity constraint.
   2. If the cumul load of truck is > min_truck_capacity, the assignment cost is zero (0). 
   3. If cumul load of truck < min_truck_capacity, assignment cost = node drop penalty. I set it to a huge value so solver doesn't assign less than min_truck_capacity to a given truck.
2. Bigger (of the two) truck is preferable since the cost per unit load is lower for the truck.
   1. So, fixed_vehicle_cost_of_big_truck = 1 & fixed_vehicle_cost_of_small_truck = 2.
3. Route association: There are pre-defined routes. Nodes in different routes can't be associated to the same truck. 
   1. This constraint is set using a dimension 
4. Max nodes per truck: A truck can deliver to a maximum of "n" nodes. 
   1. This constraint is enabled through a capacity dimension.
5. Node drop penalty: An arbitrarily high value (set through disjunction) to ensure assigning a load to truck results in cheapest objective cost. 

Ran the solver using "PATH_CHEAPEST_ARC and GLS metaheuristic. 

With a small test case that can fit the target load in 5 trucks (2 big + 3 small) using manual assignment (same constraints), the solver ends up using 4 trucks (1 big + 3 small) and drops the remaining load. 

Can someone suggest any alternate options / enhancements to enable the solver converge to a better solution? Any obvious mistake I'm making in the constraints?  

thx, 
Ravi

[Mizux Seiha]

Hi,

I fear the 1.3 `If cumul load of truck < min_truck_capacity, assignment cost = node drop penalty.` will block the solver to try to use an other truck vs dropping remaining load.

questions:
1.  How many node do you need (i.e. avoid the dropping penalty) to compensate the "load of truck < min_truck_capacity" penalty ?
2. How did you model this constraint ? Did you use RoutingDimension::SetCumulVarSoftLowerBound() ?

[Ravi]

Hi Mizux,

Thanks for your response,

My objective cost = Fixed vehicle cost (based on truck type) + Node drop penalty. So ideally solver should prefer to add node to truck than to drop as my node drop penalty is way higher compared to fixed vehicle cost (Big truck = 1, Small truck = 2). 

1.  How many node do you need (i.e. avoid the dropping penalty) to compensate  for the "load of truck < min_truck_capacity" penalty ?

Answer: 

1. The way I have given the loads in the problem statement, I have enough nodes to form 5 trucks (and not drop any node) while meeting all constraints.

2.  Max. No. of nodes allowed (per truck) is 6, and they should cover all the min quantity to avoid node drop penalty. 

2. How did you model this constraint? Did you use RoutingDimension::SetCumulVarSoftLowerBound() ?

Answer:

I modeled it using "AddConstantDimensionWithSlack", fetched cumulative load of truck at end node & using conditions & methods such as "MakeIsLessCstVar", "MakeProd", "AddConstraint" & others and then used "SetCumulVarSoftUpperBound" on dimension at vehicle end index to have 0 in initial nodes & actual association penalty of truck in vehicle end node

I tried with SetCumulVarSoftLowerBound but most of the solution is not inline with our expectations & even tried "RemoveIndex" as well, but solutions are not being formed and so I opted the above approach

Just to add on to the initial question, I reduced my sample size and gave node demands such that they can fit into 5 trucks (2 big & 3 small), the solver didn't drop anything in the manual plan. My observation was: 

1. If I give exactly 2 big trucks & 3 small trucks as available to solver, solver formed solution same as manual but when I give 2 big trucks & 7 small trucks are available (i.e., more than sufficient), solver formed 1 big truck & 3 small trucks and dropped few node demands and objective cost of solution is way higher than previous solution

Let me know if there is any mistake in our approach

thx, 

Ravi

--
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/0jJpIvvNMS8/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/8ff18538-7bdc-41f9-88e4-de2d06a9565an%40googlegroups.com.

[koushik maringanti]

Hi,

Am also having similar issue, If I give more no. of vehicles to solver, solution differs (has more objective value) as to when we give exactly how many are required for it.

Awaiting suggestions

Thanks,

Koushik