TSPTW - makespan objective & experimental evaluation

[Romain Fontaine]

​​​​​Dear all,

I am a PhD student working on optimization of delivery tours in an urban context.
I have developed a solver for the Time Dependent (TD) TSP with Time Windows (TW). A scientific paper presenting it has been submitted to a journal, and the solver will be made (freely) available online after acceptance of the paper.

I have already compared my solver to other academic solvers both on TD-TSPTW instances and on constant (i.e. TSPTW) instances, and I would like to compare it to OR-Tools as well, but technical issues are preventing me from doing it.
My apologies for the many questions below. I however believe that the answers provided will help the OR-Tools community. Also, I will publish results here as a follow-up, hopefully helping people solving instances of this problem (or related ones).

I would like to make a fair comparison of OR-Tools to my solver on TSPTW instances from the literature. It would be done in terms of convergence speed, i.e. by plotting the evolution of the gap (%) to the optimal solution with respect to time.

The execution time will be limited to one hour, and the main benchmarks considered are available at [1] (instances are heterogeneous, both in terms of TW tightness and number of customers).

I have started to implement the OR-Tools solver using C++ (source code attached), but I have several questions for which I did not find an answer in the documentation :

a) Objective function
I would like to minimize the makespan instead of the sum of travel times. In other words, I would like to minimize the sum of travel times, including the potential waiting times (i.e. when the vehicle arrives before the opening of a TW).

In the attached source code, the sum of travel times is minimized: using instance "inst.txt", the objective value (and travel time) are 938 units, while the total duration is 2660 units (I would like to minimize the total duration).

b) Routing options
[2] provides i) a list of strategies to obtain a first solution and ii) a list of local search algorithms.
As it seems costly to try every possible combination, I was thinking of running each local search algorithm with the AUTOMATIC first solution strategy.
Does this seem fair enough ?
Do you have suggestions of configurations that are known to perform better than others ?

c) Non deterministic algorithms
It seems to me that some algorithms of [2] are non-deterministic. Is it possible to set a custom random seed (for reproducibility) ?

d) Exact algorithms
Does OR-Tools provide an exact algorithm for solving instances of this problem (i.e. an algorithm that finds the optimal solution and proves its optimality, given enough time and memory) ?

e) Logging each improvement in solution quality
To compare the convergence speed of two algorithms, I need to log each improvement found by OR-Tools (i.e. the time and new best-known objective value), in order to compute the evolution of solution quality with respect to time.
Using RoutingSearchParameters::set_log_search(true) provides this information, but it is very verbose (as it logs each solution found, instead of improving solutions only) and I believe it may decrease performance when benchmarking.

f) Objective value threshold
The attached program currently executes until reaching a time limit, but I would like to allow it terminating early when the optimal solution has been found (i.e. the best known solution reaches a threshold passed as a CLI parameter).

It seems like e) and f) could both be solved trivially using a callback (i.e. called each time a new solution is found ?), but did not find this feature in the documentation...

Thank you for reading this (long) message, any help will be appreciated !
Sincerely,
Romain Fontaine

[1] https://lopez-ibanez.eu/tsptw-instances
[2] https://developers.google.com/optimization/routing/routing_options

[watchdogs132]

" c) Non-deterministic algorithms

It seems to me that some algorithms of [2] are non-deterministic. Is it possible to set a custom random seed (for reproducibility) ?"

- Actually, I think the algorithms (first solution strategy and local search) are deterministic, at least from my experience.  I asked a question related to this here. To add some randomness, you can maybe change the order of the nodes.

" b) Routing options
[2] provides i) a list of strategies to obtain a first solution and ii) a list of local search algorithms.
As it seems costly to try every possible combination, I was thinking of running each local search algorithm with the AUTOMATIC first solution strategy.
Does this seem fair enough?
Do you have suggestions of configurations that are known to perform better than others ?"

- You can have a look at parameters and default parameters (related) to tinker with the algorithms.  From my own tinkering,  I found that switching SAVINGS method to parallel (it was sequential by default) improved results for CVRP.

[Romain Fontaine]

Thank you @watchdogs132 for your help.

Could somebody tell me if it is possible to change the objective function to include waiting times (when arriving before the opening of a time window) ?

[watchdogs132]

https://developers.google.com/optimization/routing/dimensions

Section on slack variable.

[Romain Fontaine]

Thank you,

If I understood correctly, dimensions are used to enforce constraints (TWs in my case). 

I indeed set "slack_max" to a large value in order to allow waiting. 

However, the objective function does not include these waiting times (only the sum of costs is considered).