Travelling Salesman Problem with Time Windows

I’m trying to solve TSP problem with additional constraint — time windows.

All the standard assumptions apply:

• We start and end at given city.
• Each city is visited only once.
• We try to find the optimal path in terms of travel cost (here travel time).

Additionally each city has its own time window in format , which limits when a city can be visited:

• We cannot visit a city after its closing time.
• We can arrive at any city before it’s opening time and wait for it to open. If we do so, waiting time is added to overall time passed, but it is not added to time spent travelling. So time_spent_travelling and total_time_passed are two distinct things we need to keep track of.

I managed to write constraints that find optimal solution in terms of total_time_passed, but I need to find optimal time_spent_travelling.

Here is my logic:

And here sample data (Running it with clingo takes

I used MAX function to calculate arrival time at given cities by choosing from real arrival time or city’s opening time — whichever happened to be later. It worked nicely, so my first thought was to add additional field to location fact changing this line as follows:

This way location hold information about both time_spent_travelling and total_time_passed. While this works fine for 5 cities, with 20 cities it keeps calculating too long (I gave up after 15 minutes) — I expected the program to run roughly the same time at both situations, but apparently there is something I don’t understand here.

I also tried to store waiting times as separate facts, but it seemed to affect computing time the same way and introduced another issue of taking it into consideration in #minimize function which I couldn’t menage to solve.

So here are my questions:

• What can I do to calculate optimal value of time_spent_travelling, yet correctly considering waiting time?
• Why a small change in code, I’ve described above, has such a high computational impact on the solving process?

I’ve started using clingo recently and there is a good chance I don’t see a simple solution to this problem. It’s kind of hard to change the way you write your program, being so used to declarative programming.

The code I’ve provided can be simple run with clingo: clingo logic data

Here the result takes into consideration waiting time, which in this particular example is 9. (378 is time spent only on travelling).