I've had a problem for several years, I can't get to solve : it seems similar to Travelling Salesman Person (I guess), except
- I need to visit a specific number of times
the "distance criterion" is obviously a little different, or there's a trivial solution where you visit consecutively N times the same city. Actually, cities have a "weight" that may be positive or negative and the cumulative sum shall remain as neutral as possible (near zéro)
I calculate this distance with([weigth(i-1)/2+weigth(i)/2])² (proposition)
I don't particularly NEED to come back to starting point (but I think it could)
Let's say I need to visit 5*A(20), 4*B(-25), the trivial solution is ABABABABA, like :
____________________________________
|city | weight |cumulative|distance|
|_________________________|________|
| A | 20 | 20 | 100 =((0+20)/2)²
| B | -25 | -5 | 56.25 =((20-5)/2)²
| A | 20 | 15 | 25 |...
| B | -25 | -10 | 6.25|
| A | 20 | 10 | 0 |
| B | -25 | -15 | 6.25|
| A | 20 | 5 | 25 |
| B | -25 | -20 | 56.25|
| A | 20 | 20 | 100 |
|_________________________|________|
total ->value to minimize| 375 |
|________|
But that is a trivial configuration, where the occurrences of >0 and <0 weights are "easy" to sequence.
Now, I try to find a nice sequence with let's say 6*A(26331), 6*B(38848), 3*C(-50976), 12*D(-10825) and 2*E(-43298), that's a little less obvious.
I had the idea to use genetic algorithm, but I don't handle the theory very well, and I only found examples with each city visited once.
Please if you have an idea, I'm listening. And if my question isn't clear enough, just tell me I'll try to improve.
Cheers !