Re: VRP solution for Eilon 30 nodes problem

Hello Menny,

Menny wrote:
Does anyone know the Eilon 30 nodes problem? (can be found at
http://neo.lcc.uma.es/radi-aeb/WebVRP/).

I am not familiar with those problem instances, but

It seems that my GA program had found a better solution than that
provided. Does anyknow know where i can find the latest best-so-far
solution for it? According to WebVRP the best solution is 534 long,
while mine is 521.

according to the website and e. g. this article:
http://www.cs.princeton.edu/~rwerneck/docs/FLPRUW04.pdf

they solve the problem with branch-and-cut which is, as far as i know, an exact approach. Look at http://www.branchandcut.org for more information. There you can find the problem instances and the optimal solution, if it is known.

The optimal solution for the Eilon 30 instance is (according to branchandcut.org):

Route #1: 26 28 27 29 25 24 6 21
Route #2: 22 3 4 1 5 2 20
Route #3: 19 15 16 13 7 17 9 14 8 12 11 10 23 18
Cost 534

I don't know how familiar you are with the VRP in general, but the VRP can be seen as multiobjective optimization problem.

The main optimization goal may be different in different problem instances:
* minimization of waiting time,
* minimization of travel time/distance or
* minimization of vehicles used.

Most of the time the primary optimization goal is the minimization of the number of vehicles needed to serve the customers, the second goal is the minimization of the total travel distance, for example.

So if your solution needs more than three vehicles, your solution is not as good as the best known, which should be the optimal solution. If your solution only needs three vehicles you should recalculate the total distance of your solution with a pocket calculator and verify that all constraints are satisfied (just to be sure there are no errors in your implementation) and then post your routes here (your solution concept and computation times, would be interesting too).

Michael
.