9

Given a CVRP where the number of trucks is not constrained, is there an upper bound on the number of trucks used in an optimal solution in terms of number of customers, some distances, capacities, and demands?

At the most general level I would like to say something about the case of heterogeneous vehicles, heterogeneous demand, and even the possibility of splitting demands across vehicles.

But, the case of homogeneous vehicles, homogeneous demand of say 1, and no splitting of demand is also of interest for this.

Bo Jones
  • 91
  • 4
  • 1
    I do not fully understand the question: If fleet size is a decision variable its upper bound will depend on whether or not the modeler is bounding the maximum fleet size? Alternatively, if it is unbounded it will depend on the relative cost of a vehicle vs. the potential distance savings? In some sense a trivial upper bound is the number of customers because in the extreme each customer gets one vehicle? – CMichael Sep 22 '19 at 08:34
  • 2
    Well, if there is no upper bound on route length, the fewer vehicles the better (minimising total travel distance), so the optimal number of vehicles should come from the multiple-knapsack relaxation. This should be true also in case of fixed costs per each used vehicle. – Alberto Santini Sep 22 '19 at 09:17
  • Alberto Sanitini, thank you. I was not familiar with the knapsack relaxation. I will look into using that. – Bo Jones Sep 23 '19 at 00:40
  • CMichael, I see the confusion. I was hoping for some kind of characterization of the dependence in the latter case. Essentially could I introduce an implicit constraint when the modeler is not bounding the size without changing the problem? Ideally with a bound significantly lower than the number of customers. – Bo Jones Sep 23 '19 at 00:53

2 Answers2

6

This article https://arxiv.org/abs/1905.05557 might help you. The authors "present an analytical upper bound on the number of required vehicles for vehicle routing problems with split deliveries and any number of capacitated depots." and "discuss the validity of the bound for a wide variety of routing problems with or without split deliveries."

Evike
  • 182
  • 7
  • Thank you. This is exactly the kind of result I was looking for. However they are relying on a constraint (admittedly not an unreasonable one) that does some balancing of the loads across the trucks. That's the only reason I am holding out for other answers, but I suppose I will close this soon. – Bo Jones Sep 25 '19 at 08:24
3

The "knapsack relaxation" or the bin packing problem will give you the minimum number of vehicles needed for a feasible solution. However, if you restrict the number of vehicles to this minimum value, you may change your optimal solution (it is unlikely but possible).

To prove that an optimal solution does not use more than a certain number of vehicles, you need a lower bound. You may use for example the linear relaxation optimum value of some MIP formulation.

Ruslan Sadykov
  • 1,504
  • 8
  • 8
  • I see. So the assumption mentioned above of optimal used is just minimum needed is not quite right. For the second part I guess I am not seeing how the value corresponding to number of vehicles used in a solution to a linear relaxation may not be smaller than the number used for optimality. – Bo Jones Sep 25 '19 at 08:31
  • Concerning the lower bound. You add to your MIP the constraint "# of vehicles >= X+1" and then solve the linear relaxation (or any relaxation of the MIP). If the obtained value is greater than the best solution you have so far, then you know that an optimal solution does not use more than X vehicles, i.e. constraint "# of vehicles <= X" is valid for your problem. Otherwise, you increase X by 1 and repeat. – Ruslan Sadykov Sep 26 '19 at 09:43