<p>I'm currently writing a few varieties of nearest neighbour style solvers for the following:</p>

<ul>
<li>TSP (Travelling Salesmen Problem) </li>
<li>VRP  (Vehicle Routing Problem) </li>
<li>VRPTW (Vehicle Routing Problem with Time Windows).</li>
</ul>

<p>What I'm trying to do is to tweak my 'Cost' calculations used in determining the closest neighbour. I don't really have any documents on these, (and my understanding of mathematical notation isn't that great) so I'm hoping someone might be able to help. </p>

<p><strong>I've currently got:</strong></p>

<p>TSP Cost = Distance between Node1 &amp; Node2.<br>
VRP Cost = Distance between Node1 &amp; Node2.    </p>

<p>VRPTW Cost = {<br>
var x = Node2.StartOfTimeWindow - CurrentTime<br>
var y = Time between Node1 &amp; Node2;<br>
var z = Math.Max(x,y);<br>
cost = z * (Node2.EndTime - CurrentTime); }</p>

<p><strong>I'd like to introduce:</strong></p>

<p>VRP : Taking the Node2.Quantity into account, based upon the Quantity left in the current Vehicle.  </p>

<p>VRPTW: Include VRP quantity check and additionally take into account a set of skills. For example if a Node requires 'Plumbing &amp; Electrical', then it should have a lower cost to visit than a Node requiring no skills (e.g. visit a node with more difficult criteria first).</p>

<p>I'm not quite sure how to introduce these though. For the quantity check for example, should I simply do (cost - Node2.Quantity/Vehicle.Quantity). or would it be better to multiply (cost * Vehicle.Quantity/Node2.Quantity)? Or is there a better way to achieve this?</p>

<p>Any help is much appreciated.</p>

CC BY-SA 2.5
2011-03-17T11:25:50.833Z
Wouldn't it work better to plan the tour ahead a few steps to make sure you get to nodes with more difficult skill sets. If you just visit the nodes with difficult skill sets first, I'd guess you'll end up doing a significant amount of backtracking.
Peter Shor 
CC BY-SA 2.5
2011-03-17T12:20:51.337Z
You're right about the backtracking. I think really then the weighting of skills etc. to the cost needs have less impact than the distance, but still enough to allow a little out of the way. For now I'm not too interested in going ahead a few steps (I've got other algorithms that work after the Nearest Neighbour to optimize this, but these also need to have similar cost calculations). That's mainly why I've asked this question, as I'm not sure how to combine these relative costs in a sensible way, without some completely outweighing the others...
Ian
CC BY-SA 2.5
2011-03-17T12:57:50.663Z
I think we need more information before we can give you any reasonable answers. One question I have is: why should the quantity left in the vehicle matter (unless it's too little to handle a given node)? Does it really make sense to have a vehicle make longer trips to deliver to customers who just want one of whatever (which is what you'll get if you adjust your cost to include a term for Quantity), instead of making shorter trips, getting rid of all its contents, and then sending in another vehicle to deal with the remaining customers?
Peter Shor 
CC BY-SA 2.5
2011-03-17T14:18:48.100Z
If I have a mix of vehicles with varying quantity (say 100->500) that isn't evenly distributed, and I have a Node that requires (490), then I'd prefer a longer overall distance and that Node to be visited, than for a short distance where none of the vehicles with enough capacity visit the node. If there's other information that's useful, please let me know.
Ian
CC BY-SA 2.5
2011-03-17T15:27:24.793Z
In that case, you really care that the nodes with large demand are visited by vehicles with large quantity, whereas you don't really care whether a node with demand 95 is visited by a vehicle with quantity 100 or 500 (unless your vehicles with quantity 500 are already overworked). I don't think either of your cost functions makes this work properly.
Peter Shor 
CC BY-SA 2.5
2011-03-17T16:03:39.460Z
No, quite possibly not.. What I'm after is some advice on how I should introduce this factor into the cost. I'm not really a mathematician and don't know how to do so correctly :/
Ian
CC BY-SA 2.5
2011-03-17T16:24:46.957Z
Probably what you want is a cost function which gives a big incentive for large capacity vehicles to visit large demand nodes. One thing you could do is try a bunch of cost functions that do this, and figure out which one works best experimentally. I'm don't know whether there's an answer that doesn't depend on the specifics of the problem ... maybe somebody else will have some input.
Peter Shor 
<ds.algorithms>
Combining Cost Calculations (TSP, VRP style problems)
Ian
# Combining Cost Calculations (TSP, VRP style problems)

(Asked by: username_0 on 2011-03-16)

I'm currently writing a few varieties of nearest neighbour style solvers for the following:

* TSP (Travelling Salesmen Problem)
* VRP (Vehicle Routing Problem)
* VRPTW (Vehicle Routing Problem with Time Windows).

What I'm trying to do is to tweak my 'Cost' calculations used in determining the closest neighbour. I don't really have any documents on these, (and my understanding of mathematical notation isn't that great) so I'm hoping someone might be able to help.

**I've currently got:**

TSP Cost = Distance between Node1 & Node2.  
VRP Cost = Distance between Node1 & Node2.

VRPTW Cost = {  
var x = Node2.StartOfTimeWindow - CurrentTime  
var y = Time between Node1 & Node2;  
var z = Math.Max(x,y);  
cost = z \* (Node2.EndTime - CurrentTime); }

**I'd like to introduce:**

VRP : Taking the Node2.Quantity into account, based upon the Quantity left in the current Vehicle.

VRPTW: Include VRP quantity check and additionally take into account a set of skills. For example if a Node requires 'Plumbing & Electrical', then it should have a lower cost to visit than a Node requiring no skills (e.g. visit a node with more difficult criteria first).

I'm not quite sure how to introduce these though. For the quantity check for example, should I simply do (cost - Node2.Quantity/Vehicle.Quantity). or would it be better to multiply (cost \* Vehicle.Quantity/Node2.Quantity)? Or is there a better way to achieve this?

Any help is much appreciated.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Wouldn't it work better to plan the tour ahead a few steps to make sure you get to nodes with more difficult skill sets. If you just visit the nodes with difficult skill sets first, I'd guess you'll end up doing a significant amount of backtracking.  
> **username_0**: You're right about the backtracking. I think really then the weighting of skills etc. to the cost needs have less impact than the distance, but still enough to allow a little out of the way. For now I'm not too interested in going ahead a few steps (I've got other algorithms that work after the Nearest Neighbour to optimize this, but these also need to have similar cost calculations). That's mainly why I've asked this question, as I'm not sure how to combine these relative costs in a sensible way, without some completely outweighing the others...  
> **username_1**: I think we need more information before we can give you any reasonable answers. One question I have is: why should the quantity left in the vehicle matter (unless it's too little to handle a given node)? Does it really make sense to have a vehicle make longer trips to deliver to customers who just want one of whatever (which is what you'll get if you adjust your cost to include a term for Quantity), instead of making shorter trips, getting rid of all its contents, and then sending in another vehicle to deal with the remaining customers?  
> **username_0**: If I have a mix of vehicles with varying quantity (say 100->500) that isn't evenly distributed, and I have a Node that requires (490), then I'd prefer a longer overall distance and that Node to be visited, than for a short distance where none of the vehicles with enough capacity visit the node. If there's other information that's useful, please let me know.  
> **username_1**: In that case, you really care that the nodes with large demand are visited by vehicles with large quantity, whereas you don't really care whether a node with demand 95 is visited by a vehicle with quantity 100 or 500 (unless your vehicles with quantity 500 are already overworked). I don't think either of your cost functions makes this work properly.  
> **username_0**: No, quite possibly not.. What I'm after is some advice on how I should introduce this factor into the cost. I'm not really a mathematician and don't know how to do so correctly :/  
> **username_1**: Probably what you want is a cost function which gives a big incentive for large capacity vehicles to visit large demand nodes. One thing you could do is try a bunch of cost functions that do this, and figure out which one works best experimentally. I'm don't know whether there's an answer that doesn't depend on the specifics of the problem ... maybe somebody else will have some input.  

---

## 0 answers

