VRP constraint to limit each vehicle can load demands within the same order

[aliboun]

Dear all,
I have such routing constraint problem that looks somehow weird to model on or-tools (Capacity const. VRP)

Data model has locations(x,y coordinates), demands(qty of orders at each location), number of vehicles and the vehicle capacity.

Each location address to products located in the warehouse to get picked. Customer orders can have multiple products and you have list of orders belongs to group of different customers.

Rather than capacity and distance dimension there is one specific constraint that each vehicle should pick products belongs to same order during it's route. If the vehicle capacity not exceeded then continues to collect another order. At the end of route each vehicle must have products for whole orders.

Glad to have your feedbacks how to apply those constraints on VRP solution.

Sample Data:

List<Order> orders = new List<Order>()
                {
                    new Order{OrderNo="1", Product="A1", Qty=10, Location= new int[] {12,23}},
                    new Order{OrderNo="1", Product="A2", Qty=15, Location= new int[] {10,14}},
                    new Order{OrderNo="1", Product="A3", Qty=30, Location= new int[] {25,27}},
                    new Order{OrderNo="2", Product="A1", Qty=20, Location= new int[] {33,41}},
                    new Order{OrderNo="2", Product="A4", Qty=25, Location= new int[] {67,78}},
                };

[Mizux]

few questions:

• If a vehicle can't load all products of an order, should you split it among the fleet or drop the order ?

• you can add same vehicle constraint for product belonging to the same order
  see: https://gist.github.com/Mizux/9e37c370a459bd472a6ac13c304f0b54

• to drop N nodes or 0 you can use the third parameter of AddDisjunction() aka max_cardinality
  

  or-tools/ortools/constraint_solver/routing.h

  Lines 599 to 617 in b77bd3a

  	/// Adds a disjunction constraint on the indices: exactly 'max_cardinality' of
  	/// the indices are active. Start and end indices of any vehicle cannot be
  	/// part of a disjunction.
  	///
  	/// If a penalty is given, at most 'max_cardinality' of the indices can be
  	/// active, and if less are active, 'penalty' is payed per inactive index.
  	/// This is equivalent to adding the constraint:
  	/// p + Sum(i)active[i] == max_cardinality
  	/// where p is an integer variable, and the following cost to the cost
  	/// function:
  	/// p * penalty.
  	/// 'penalty' must be positive to make the disjunction optional; a negative
  	/// penalty will force 'max_cardinality' indices of the disjunction to be
  	/// performed, and therefore p == 0.
  	/// Note: passing a vector with a single index will model an optional index
  	/// with a penalty cost if it is not visited.
  	DisjunctionIndex AddDisjunction(const std::vector<int64>& indices,
  	int64 penalty = kNoPenalty,
  	int64 max_cardinality = 1);

[aliboun]

Hi Mizux,
Appreciated to have your prompt reply. Regarding first question, order list does not contain ugly orders such as over-capacity pickup in a single route is not applicable in our use case. If a vehicle does not fill up its capacity during its route, then continues to pick-up new orders.

I will try to implement your "same vehicle" constraint. As far as I understand, I should flag the every product that would be carried in same vehicle. I am not sure this will cover the case that if the capacity of vehicle not full-filled then go and pick some more orders.

Will back to you soon.
Regards;

[dennisylyung]

Hi @Mizux ,

To clarify, if I have more than 2 locations per constraints (e.g. 10 locations to be on the same route), should I add inequality constraints that evaluate only when all locations are added, like:

active_all = routing.ActiveVar(loc_1) * routing.ActiveVar(loc_2) * ... * routing.ActiveVar(loc_10)

or add inequality constraints for when each of the 10-C-2 combinations are active?
The later makes more sense to me if the first solution is searched greedily, but there seems to be a lot of constraints

[Mizux]

you can "incentive" solver to fully load your vehicle using

or-tools/ortools/constraint_solver/routing.h

Lines 2516 to 2526 in b77bd3a

	/// Sets a soft lower bound to the cumul variable of a given variable index.
	/// If the value of the cumul variable is less than the bound, a cost
	/// proportional to the difference between this value and the bound is added
	/// to the cost function of the model:
	/// cumulVar > lower_bound -> cost = 0
	/// cumulVar <= lower_bound -> cost = coefficient * (lower_bound -
	/// cumulVar).
	/// This is also handy to model earliness costs when the dimension represents
	/// time.
	void SetCumulVarSoftLowerBound(int64 index, int64 lower_bound,
	int64 coefficient);

[aliboun]

@Mizux,
Tried to implement the same vehicle logic as attached. First case, it was ok and worked as expected. But the second case, it just dropped P5 even if the vehicle has enough capacity. Without disjunction function, there was no solution produced for both cases.

If we clarify this drop issue, then I can move to incentive solver part as you mention earlier. It would be great if you guide me how to apply "SetCumulVarSoftLowerBound" method - especially the parameters needed for lowerbound and the coefficient.

Thanks.

VrpCapacity.txt

CASE(1): P1 & P2 at same vehicle

Total cost: 668
Locations :{X=0,Y=0};{X=33,Y=78};{X=10,Y=137};{X=4,Y=28};{X=33,Y=78};{X=86,Y=37}
Demands :0;10;15;30;20;25
Number of Vehicle :2
Vehicle Capacities :50;50

Route for Vehicle 0:
0 Load(0) -> 2 Load(15) -> 1 Load(25) -> 5 Load(50) -> 0
Distance of the route: 446m
Route for Vehicle 1:
0 Load(0) -> 3 Load(30) -> 4 Load(50) -> 0
Distance of the route: 222m
Total distance of all routes: 668m
Total load of all routes: 100m

CASE(2): P4 & P5 at same vehicle

Total cost: 1404
Locations :{X=0,Y=0};{X=33,Y=78};{X=10,Y=137};{X=4,Y=28};{X=33,Y=78};{X=86,Y=37}
Demands :0;10;15;30;20;25
Number of Vehicle :2
Vehicle Capacities :50;50

Dropped orders: 5
Route for Vehicle 0:
0 Load(0) -> 4 Load(20) -> 1 Load(30) -> 2 Load(45) -> 0
Distance of the route: 340m
Route for Vehicle 1:
0 Load(0) -> 3 Load(30) -> 0
Distance of the route: 64m
Total distance of all routes: 404m
Total load of all routes: 75m

[aliboun]

@Mizux One more question; how should I set to solver if we group more than two product in the same vehicle?