itinero
CalculateTspTW - Round trip route - Not optimal tsp optimization
Hi, We use the CalculateTspTW algorithm but we get a results that is not optimal in some cases - it return round trip route. For example: We defined locations array with 9 coordinates, some of the points located in one city and others in other city (20 kilometers southern). We have defined that all points will have the same 24-hour time windows: [min=0,max=86400] As I mentioned the result is non optimal route - back and forth - The route passes through several points in the first city and then performs all the points in the second city and then returns to the first city to perform the other points. You can see images below. The optimal route should pass through all the points in the first city and then perform the points in the second city. Especially when the time window is 24 hours.
Here the code: `Coordinate[] locations = new Coordinate[] { new Coordinate((float)31.803462982177734,(float)34.64567184448242), new Coordinate((float)31.798843383789062,(float)34.6540412902832), new Coordinate((float)31.794118881225586,(float)31.794118881225586), new Coordinate((float)31.78878402709961,(float)34.65801239013672), new Coordinate((float)31.787199020385742,(float)34.662925720214844), new Coordinate((float)31.651636123657227,(float)34.55881118774414), new Coordinate((float)31.652114868164062,(float)34.55542755126953), new Coordinate((float)31.776153564453125,(float)34.632301330566406), new Coordinate((float)31.7714900970459,(float)34.63166046142578) };
var windows = new TimeWindow[]
{
new TimeWindow() { Max = 86400, Min = 0 },
new TimeWindow() { Max = 86400, Min = 0 },
new TimeWindow() { Max = 86400, Min = 0 },
new TimeWindow() { Max = 86400, Min = 0 },
new TimeWindow() { Max = 86400, Min = 0 },
new TimeWindow() { Max = 86400, Min = 0 },
new TimeWindow() { Max = 86400, Min = 0 },
new TimeWindow() { Max = 86400, Min = 0 },
new TimeWindow() { Max = 86400, Min = 0 }
};
route = router.CalculateTSPTW(Itinero.Osm.Vehicles.Vehicle.Car.Fastest(), locations, windows, 0);`
How we can avoid from the result of a round trip? I will appreciate for any help.
Round trip route:
Round trip route-ZOOM:
Optimal route:
Regards Ronen
If I understand correctly you want the end of the route to be 'open', it can end anywhere?
I read a bit better now sorry, can you try with the regular TSP calculation without timewindows? What result do you get then.
Also, the round-trip is most likely only sub-optimal when the route is 'open', is that what you had in mind? It's perfectly possible, and it could be optimal, to do the two other points in a route that's closed in between the others.
Hi,
Thank you for the quick reply!
The CalculateTsp return correct route – without 'back and forth' route and it really do optimization for TSP.
Regarding your question – Yes, i want the end of the route to be 'open', and it can end anywhere (at any stop). But the CalculateTspTW must refer to the time window and to the TSP calculation, especially when the time window is long enough. In such a situation that the time window is long enough to complete all the stops, I would expect it to return the same result as the TSP calculation. It makes no sense travel to the second city and return again to the first city!
I tried the CalculateTspTW with more time windows, and in all the cases, the result is not good - back and forth.
Here is the code for my other tests:
//Incity in 4 hour and intercity in 8 hour
var windows1 = new TimeWindow[]
{
new TimeWindow() { Max = 14400, Min = 0 },
new TimeWindow() { Max = 14400, Min = 0 },
new TimeWindow() { Max = 14400, Min = 0 },
new TimeWindow() { Max = 14400, Min = 0 },
new TimeWindow() { Max = 14400, Min = 0 },
new TimeWindow() { Max = 28800, Min = 0 }, //second city -
8 hr
new TimeWindow() { Max = 28800, Min = 0 }, //second city -
8 hr
new TimeWindow() { Max = 14400, Min = 0 },
new TimeWindow() { Max = 14400, Min = 0 }
};
//Incity in 2 hour and intercity in 8 hour
var windows2 = new TimeWindow[]
{
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 28800, Min = 0 }, //second city
new TimeWindow() { Max = 28800, Min = 0 }, //second city
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 7200, Min = 0 }
};
//Incity in 2 hour and intercity in 8 hour, but with diffrend
max time defintions
var windows3 = new TimeWindow[]
{
new TimeWindow() { Max = 1, Min = 0 },
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 6600, Min = 0 },
new TimeWindow() { Max = 6600, Min = 0 },
new TimeWindow() { Max = 6000, Min = 0 },
new TimeWindow() { Max = 27600, Min = 0 },
new TimeWindow() { Max = 27000, Min = 0 },
new TimeWindow() { Max = 4800, Min = 0 },
new TimeWindow() { Max = 4800, Min = 0 }
};
var windows4 = new TimeWindow[]
{
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 6600, Min = 0 },
new TimeWindow() { Max = 6600, Min = 0 },
new TimeWindow() { Max = 6000, Min = 0 },
new TimeWindow() { Max = 27600, Min = 4000}, //second city
new TimeWindow() { Max = 27000, Min = 4000}, //second city
new TimeWindow() { Max = 4800, Min = 0 },
new TimeWindow() { Max = 4800, Min = 0 }
};
The only case that the CalculateTspTW returned a correct result (route without 'back and forth') was when I defined the time window so, the 2 stops (in the second city) will perform after the other stops.
Here the code:
var windows5 = new TimeWindow[]
{
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 7200, Min = 0 },
new TimeWindow() { Max = 6600, Min = 0 },
new TimeWindow() { Max = 6600, Min = 0 },
new TimeWindow() { Max = 6000, Min = 0 },
new TimeWindow() { Max = 27600, Min = 10000}, //second city
new TimeWindow() { Max = 27000, Min = 10000}, //second city
new TimeWindow() { Max = 4800, Min = 0 },
new TimeWindow() { Max = 4800, Min = 0 }
};
Regards,
Ronen
On Fri, Feb 23, 2018 at 10:39 AM, Ben Abelshausen [email protected] wrote:
I read a bit better now sorry, can you try with the regular TSP calculation without timewindows? What result do you get then.
Also, the round-trip is most likely only sub-optimal when the route is 'open', is that what you had in mind? It's perfectly possible, and it could be optimal, to do the two other points in a route that's closed in between the others.
— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/itinero/optimization/issues/15#issuecomment-367945035, or mute the thread https://github.com/notifications/unsubscribe-auth/AjC3-R0mEN22tkGJ2eotDlA-IWM6rMdqks5tXnlPgaJpZM4SQFDq .
I just noticed that there was a small mistake in one of the coordinate that i sent you in the initial correspondence. The bug that i described to you still happens. If you are trying to reproduce the bug, please use the following locations:
Coordinate[] locations = new Coordinate[]
{
new Coordinate((float)31.803462982177734,(float)34.64567184448242),
new Coordinate((float)31.798843383789062,(float)34.6540412902832),
new Coordinate((float)31.794118881225586,(float)34.651329040527344),
new Coordinate((float)31.78878402709961,(float)34.65801239013672),
new Coordinate((float)31.787199020385742,(float)34.662925720214844),
new Coordinate((float)31.651636123657227,(float)34.55881118774414), //second city
new Coordinate((float)31.652114868164062,(float)34.55542755126953), //second city
new Coordinate((float)31.776153564453125,(float)34.632301330566406),
new Coordinate((float)31.7714900970459,(float)34.63166046142578)
};
Regards,