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).

Travelling salesman problem with time windows

Travelling Salesman Problem with time windows The code here uses a metaheuristic to come up with a solution to an NP-hard problem The code tries to solve the travelling salesman problem with time windows using the iterated greedy algorithm. The proposed algorithm makes use of the Variable Neighborhood Search (VNS) method to get a list of neighborhood solutions through destruction and construction of solution components. The problem described here refers to a salesman visiting different customers on his route in a particular order to optimize the cost of travel as well as minimize the loss due to seeing the customers outside the time windows described for each customer. The salesman must visit the customers inside the time windows or else bear the penalty associated with it. The algorithm consists of random parameters like NFT0, lambda and number of nodes cij is a matrix of distances between the i and j nodes in the salesman’s path ei represents the upper limit of the time window li represents the lower limit of the time window

Initially an infeasible solution is generated randomly and then the greedy algorithm is applied to the solution in order to get a feasible solution in the end.

About

Travelling Salesman Problem with time windows

Resources

Releases

Packages 0

Languages

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

Travelling salesman problem with time windows

Initially an infeasible solution is generated randomly and then the greedy algorithm is applied to the solution in order to get a feasible solution in the end.

About

Travelling Salesman Problem with time windows

Resources

Releases

Packages 0

Languages

You can’t perform that action at this time.

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.

Travelling salesman -like problem with constraints and optional cities

Concider Travelling Salesman Problem but with following changes:

The measure of distance is time of travel
Not only edges have weights — so not only travelling to city takes time, but also visiting the city takes time (the easiest way would be adding time of being in city to each incoming edge)
There is a reward assigned to each city. Once you visit a city you get its reward.
There is maximum time period within cities can be visited (eg. from June 1st to June 17th). So the maximum total distance (in this case time) is limited.
The moment of visiting a city may be constrained (eg. you can visit Chicago only on June 4th.)
Some of cities may be marked as obligatory. You have to visit all the obligatory cities and any number of non-obligatory cities (eg. Las Vegas must be visited)
The end city may be different from start city, but must be specified (eg. start point must be Washington and the end point must be Los Angeles). So the route may be no-cyclic.

The goal in this case is not to minimize travel distance (time), but to maximize total reward and meeting all constraints (total time, moment of visit, obligatory cities).

I am working on it, but I don’t want to reinvent the wheel.

Does the problem described above have any specific name? (Eg. Yes, that’s XYZ problem)
Or is it case of any well-known kind of problems (Eg. Yes, that belongs to XYZ optimisation problems)

By now I only know that it’s related to:

travelling salesman problem,
constraint satisfaction problem,
(integer) linear programming,
Vehicle Routing Problem with Time Window