-1
$\begingroup$

Context:

I was working on some VRP solvers and realized that tractability deproved when I added Fixed Cost for each vehicle (in an attempt to reduce number of vehicles used).

Questions:

1- Due to the traingle inequality, it is always shorter(or equal to) to remove an intermediate node. Adding more vehicles would mean more visits to the central depot/start. Thus, using additional vehicles to fulfill a set of nodes would always result in a longer tour. If this were true,that would imply that mTSPs will naturally try to minimize number of vehicles used? If so, it feels like mTSP would always result in the same solution as TSP which does not seem to make sense.

2- What about in the case if there are capacity limits to the vehicle? I have been trying to generate examples to disprove this but have not been able to.

Is my reasoning flawed? An example or simple logical proof would be greatly appreciated

Improve this question
$\endgroup$
4
  • $\begingroup$ An example where your reasoning is off is an instance with 3 nodes in a straight line, with the depot being the middle node. You can use 1 or 2 vehicles and the solution cost would be the same. $\endgroup$
    – Joris Kinable
    Jun 28 at 15:35
  • $\begingroup$ Sorry, if it wasnt very clear in the title. I meant that it would never be lower cost to have additional vehicles $\endgroup$
    – Abilash
    Jun 28 at 16:23
  • $\begingroup$ There are instances among the “P” instances in the cvrp library (with Euclidean distances, so the triangle inequality is satisfied) where an optimal solution does not minimise the number of vehicles used. This is due to the capacity constraints. Constructing such an example can be done by placing an isolated node with high demand on “one side of the depot” and the remaining customers on the “other side”. This should be done such that it is better to send one extra vehicle to single-serve the isolated customer than to include it in one of the other routes $\endgroup$
    – Sune
    Jun 28 at 17:19
  • $\begingroup$ I have been trying to generate such instances (albeit simple ones) and none of them seem to be this case. Could you please give an example? $\endgroup$
    – Abilash
    Jun 29 at 19:01

1 Answer 1

Reset to default
1
$\begingroup$

I found one such instance(from the "P" datasets) and i distilled it to just the customers who will result in this 'phenomenon'.

NAME : P-n22-k8
COMMENT : (Augerat et al, No of trucks: 8, Optimal value: 603)
TYPE : CVRP
DIMENSION : 9
EDGE_WEIGHT_TYPE : EUC_2D
VEHICLES : 3
CAPACITY : 3000

NODE_COORD_SECTION
D1 145 215
C13 156 217
C15 146 208
C16 164 208
C17 141 206
C18 147 193
C19 164 193
C21 155 185
C22 139 182
-1

DEMAND_SECTION
D1 0
C13 1300
C15 300
C16 900
C17 2100
C18 1000
C19 900
C21 1800
C22 700
-1

DEPOT_SECTION
 D1
 -1
EOF

If you run this with 3 vs 4 vehicles, you will see a savings of 13. The total demand of this instance is 90 and with only 3 vehicles you have to make sure each route has total demand of 30. This together with C17, who has high demand, has to be paired with someone with demand = 9 which results in a 'sub-optimal' solution which can be avoided with more vehicles.

Generating such instances is not as trivial as i had anticipated. Thanks to Sune for the idea to look at the "P" datasets.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.