4
$\begingroup$

I'm solving a time-dependent travelling salesman problem. I have data from a whole year. I'm thinking about the size of the time steps. I think that the time-steps shouldn't be too large to be realistic (in 4 hours the traffic can change significantly) but I also think that it shouldn't be too small so that the data does not have the tendency to be scewed. Is there a "best practice" size for the TD-TSP or is smaller always better?

$\endgroup$
4
$\begingroup$

[Moderators - this answer might be more appropriate in the comments - feel free to move if you agree].

When you say the size of timesteps, do you mean you have estimates of travel times for an entire year and you're looking at estimating the travel speeds for every 4 hours within the year, is this correct? So by step size you mean 'period in which I assume a constant value of travel time, which I then feed into my TSP solver'?

If this is correct, I don't believe there's any standard. However I can tell you what we do in our commercial VRP solver https://odllive.com/. Using our 'standard speeds' profile, we consider travel time in hour-sized 'buckets'/timesteps, with bucket chosen based on the departure time. A journey can span several 'buckets' (e.g. several timesteps) so that also needs to be taken account of. Pretty obviously we don't store 'buckets' for an entire year though (e.g. currently we just store them for 1 weekday profile and 1 weekend profile, giving 48 max, and we then merge buckets which are basically the same).

I would guesstimate an hour is about the minimum viable step size when you consider rush hour profiles from different cities around the world (e.g. see figure 2 in this paper).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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