Multiple traveling salesman problem with time windows

The Travelling Salesman Problem with Time Windows is similar to the TSP except that cities (or clients)
must be visited within a given time window. This added time constraint —
although it restricts the search tree[1] — renders
the problem even more difficult in practice! Indeed, the beautiful symmetry of the
TSP[2] (any permutation
of cities is a feasible solution) is broken and even the search for feasible solutions is
difficult [Savelsbergh1985].

We present the TSPTW and two instances formats: the López-Ibáñez-Blum and the da Silva-Urrutia formats. As in the case
of the
TSP, we have implemented a class to read those instances: the TSPTWData class. We also use the ePix library to
visualize feasible solutions using the TSPTWEpixData class.

9.8.1. The Travelling Salesman Problem with Time Windows

You might be surprised to learn that there is no common definition that is widely accepted within the scientific
community. The basic idea is to find a “tour” that visits each node within a time window but several variants exist.

We will use the definition given in Rodrigo Ferreira da Silva and Sebastián Urrutia’s 2010 article [Ferreira2010].
Instead of visiting cities as in the TSP, we visit and service customers.

[Ferreira2010]

R. Ferreira da Silva and S. Urrutia. A General VNS heuristic for the traveling salesman problem with time windows, Discrete Optimization, V.7, Issue 4, pp. 203-211, 2010.

The Travelling Salesman Problem with Time Windows (TSPTW) consists in finding a minimum cost tour starting and ending
at a given depot and visiting all customers. Each customer has:

You only can (and must) visit each client once. The costs on the arcs represent the travel times (and sometimes also the
service times). The total cost of a tour is the sum of the costs on the arcs
used in the
tour. The ready and due times of a client define a time window within which the client has
to be served. You are allowed to visit the client before the ready time but you’ll have to wait until
the ready time before you can service her. Due times must be respected and tours that fail to serve clients before their
due time are considered infeasible.

Let’s illustrate a visit to a client . To do so, let’s define:

In real application, the time spent at a client might be limited to the service. For instance, you might wait in front
of the client’s office. It’s common to consider that you start to service and leave as soon as possible and
this is our assumption in this chapter

Some authors ([Dash2010] for instance) assign two costs on the edges: a travel cost and a travel time. While
the travel times must respect the time windows constraints, the objective value is the sum of the travel costs on the
edges. In this chapter, we only have one cost on the edges. The objective value and the real travel time are different: you might
have to wait before servicing a client.

[Dash2010]

S. Dash, O. Günlük, A. Lodi, and A. Tramontani. A Time Bucket Formulation for the Traveling Salesman Problem with Time Windows, INFORMS Journal on Computing, v24, pp 132-147, 2012 (published online before print on December 29, 2010).

Often, some conditions are applied to the time windows (in theory or practice). The only
condition[3] we will impose
is that ,
i.e. we impose that the bounds of the time windows must be non negative integers. This also implies that the time windows
and the servicing times are finite.

[3]	This condition doesn’t hold in Rodrigo Ferreira da Silva and Sebastián Urrutia’s definition of a TSPTW. In their article, they ask for (at least theoretically) , i.e. non negative real numbers and .

The practical difficulty of the TSPTW is such that only instances with about 100 nodes have been solved to optimality[4] and heuristics rarely challenge instances with more than 400 nodes.

The
difficulty of the problem not only depends on the number of nodes but also on the “quality” of the time windows.
Not many attempts can be found in the scientific literature about exact or heuristic algorithms using CP to solve the TSPTW.
Actually, not so many attempts have been successful in solving this difficult problem in general.
The scientific literature on this problem is hence scarce.

We refer the interested reader to the two web pages cited in the next sub-section for some relevant literature.

21
0 19 17 34 7 20 10 17 28 15 23 29 23 29 21 20 9 16 21 13 12
19 0 10 41 26 3 27 25 15 17 17 14 18 48 17 6 21 14 17 13 31
17 10 0 47 23 13 26 15 25 22 26 24 27 44 7 5 23 21 25 18 29
34 41 47 0 36 39 25 51 36 24 27 38 25 44 54 45 25 28 26 28 27
7 26 23 36 0 27 11 17 35 22 30 36 30 22 25 26 14 23 28 20 10
20 3 13 39 27 0 26 27 12 15 14 11 15 49 20 9 20 11 14 11 30
10 27 26 25 11 26 0 26 31 14 23 32 22 25 31 28 6 17 21 15 4
17 25 15 51 17 27 26 0 39 31 38 38 38 34 13 20 26 31 36 28 27
28 15 25 36 35 12 31 39 0 17 9 2 11 56 32 21 24 13 11 15 35
15 17 22 24 22 15 14 31 17 0 9 18 8 39 29 21 8 4 7 4 18
23 17 26 27 30 14 23 38 9 9 0 11 2 48 33 23 17 7 2 10 27
29 14 24 38 36 11 32 38 2 18 11 0 13 57 31 20 25 14 13 17 36
23 18 27 25 30 15 22 38 11 8 2 13 0 47 34 24 16 7 2 10 26
29 48 44 44 22 49 25 34 56 39 48 57 47 0 46 48 31 42 46 40 21
21 17 7 54 25 20 31 13 32 29 33 31 34 46 0 11 29 28 32 25 33
20 6 5 45 26 9 28 20 21 21 23 20 24 48 11 0 23 19 22 17 32
9 21 23 25 14 20 6 26 24 8 17 25 16 31 29 23 0 11 15 9 10
16 14 21 28 23 11 17 31 13 4 7 14 7 42 28 19 11 0 5 3 21
21 17 25 26 28 14 21 36 11 7 2 13 2 46 32 22 15 5 0 8 25
13 13 18 28 20 11 15 28 15 4 10 17 10 40 25 17 9 3 8 0 19
12 31 29 27 10 30 4 27 35 18 27 36 26 21 33 32 10 21 25 19 0
0         408
62        68
181       205
306       324
214       217
51        61
102       129
175       186
250       263
3         23
21        49
79        90
78        96
140       154
354       386
42        63
2         13
24        42
20        33
9         21
275       300

# Sum of service times: 522

!! n20w20.001    16.75 391

CUST NO. XCOORD. YCOORD. DEMAND [READY TIME] [DUE DATE] [SERVICE TIME]

    1    16.00    23.00   0.00      0.00       408.00       0.00
    2    22.00     4.00   0.00     62.00        68.00       0.00
    3    12.00     6.00   0.00    181.00       205.00       0.00
    4    47.00    38.00   0.00    306.00       324.00       0.00
    5    11.00    29.00   0.00    214.00       217.00       0.00
    6    25.00     5.00   0.00     51.00        61.00       0.00
    7    22.00    31.00   0.00    102.00       129.00       0.00
    8     0.00    16.00   0.00    175.00       186.00       0.00
    9    37.00     3.00   0.00    250.00       263.00       0.00
   10    31.00    19.00   0.00      3.00        23.00       0.00
   11    38.00    12.00   0.00     21.00        49.00       0.00
   12    36.00     1.00   0.00     79.00        90.00       0.00
   13    38.00    14.00   0.00     78.00        96.00       0.00
   14     4.00    50.00   0.00    140.00       154.00       0.00
   15     5.00     4.00   0.00    354.00       386.00       0.00
   16    16.00     3.00   0.00     42.00        63.00       0.00
   17    25.00    25.00   0.00      2.00        13.00       0.00
   18    31.00    15.00   0.00     24.00        42.00       0.00
   19    36.00    14.00   0.00     20.00        33.00       0.00
   20    28.00    16.00   0.00      9.00        21.00       0.00
   21    20.00    35.00   0.00    275.00       300.00       0.00
  999     0.00     0.00   0.00      0.00         0.00       0.00

1 17 10 20 18 19 11 6 16 2 12 13 7 14 8 3 5 9 21 4 15
378

./check_tsptw_solutions -tsptw_data_file=DSU_n20w20.001.txt
                                 -tsptw_solution_file=n20w20.001.sol

bool IsFeasibleSolution() {
  ...
  //  for loop to test each node in the tour
  for (...) {
    //  Test if we have to wait at client node
    waiting_time = ReadyTime(node) - total_time;
    if (waiting_time > 0) {
      total_time = ReadyTime(node);
    }
    if (total_time + ServiceTime(node) > DueTime(node)) {
      return false;
    }
  }
  ...
  return true;
}

TSPTW instance of type da Silva-Urrutia format
Solution is feasible!
Loaded obj value: 378, Computed obj value: 387
Total computed travel time: 391
TSPTW file DSU_n20w20.001.txt (n=21, min=2, max=59, sym? yes)
(!! n20w20.001 16.75 391 )

TSPTW instance of type López-Ibáñez-Blum format
Solution is feasible!
Loaded obj value: 378, Computed obj value: 378
Total computed travel time: 387
TSPTW file LIB_n20w20.001.txt (n=21, min=2, max=57, sym? yes)

LoadTSPTWFile(const std::string& filename);

bool IsInstanceLoaded() const;

int64 CumulTime(RoutingModel::NodeIndex from,
                RoutingModel::NodeIndex to) const {
  return Distance(from, to) + ServiceTime(from);
}

void LoadTSPTWSolutionFile(const std::string& filename);

bool IsSolutionLoaded() const;
bool IsSolution() const;
bool IsFeasibleSolution() const;

RoutingModel routing(...);
...
TSPTWData data(...);
...
TSPTWEpixData(const RoutingModel& routing,
              const TSPTWData& data);

void WriteSolutionFile(const Assignment * solution,
                       const std::string & epix_filename)
void WriteSolutionFile(const std::string & tpstw_solution_filename,
                       const std::string & epix_filename);

DEFINE_int32(epix_width, 10, "Width of the pictures in cm.");
DEFINE_int32(epix_height, 10, "Height  of the pictures in cm.");

./elaps -pdf epix_file.xp

DEFINE_bool(tsptw_epix_labels, false, "Print labels or not?");
DEFINE_bool(tsptw_epix_time_windows, false,
                                      "Print time windows or not?");

./tsptw_solution_to_epix TSPTW_instance_file TSPTW_solution_file >
                                                epix_file.xp

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:

% THE TRAVELING SALESMAN WITH TIME WINDOWS

% DESC ------------------------------------------------------------------------------------
% visited(city, arrive_step)
% travel(dest_city, depart_step)
% location(city, arrive_step, when_visited (summary travel time))
% place(name, opening_time, closing_time)
% path(from, to, travel_cost)

% Warunki ----------------------------------------------------------------------------------

% Start and end must be in the same city
:- not location(Place, t, _), location(Place, 0, _).

% Paths are symmetrical
path(A, B, COST) :- path(B, A, COST).

% In each step, there can be only one travel from one city to another
{ travel(Place, T) : place(Place, _, _) } 1 :- T = 0..t-1.

% If there was a travel to a city, that city has been visited (this way starting city is not visited at the beginning)
visited(Place, T) :- travel(Place, T).

% We cannot visit a city, we've been to before
:- travel(Place, T1), visited(Place, T2), T1 > T2.

% We cannot travel to city, we are staying right now
:- travel(Place, T), location(Place, T, _).

% We cannot go to somewhere, to where leads no path
:- travel(To, T), location(From, T, _), not path(From, To, _).

% We cannot travel to city if we arrive after it's closing time
:- travel(TO, T), location(From, T, TOTAL_TIME), path(From, TO, TRAVEL_TIME), place(TO, OPENED_FROM, OPENED_TO), TOTAL_TIME + TRAVEL_TIME > OPENED_TO.

% If we started travel to city A at step T, we must have reached it at step T + 1
% City might me not opened yet, so our travel time is MAX of (CITY_OPENED_TIME, ARRIVAL_TIME)
% max = ((a+b)+|a-b|)/2
% min = ((a+b)-|a-b|)/2
location(To, T + 1, ((ARRIVAL+OPENED_FROM)+|ARRIVAL-OPENED_FROM|)/2) :-  travel(To, T), location(From, T, C1) , path(From, To, C2), place(To, OPENED_FROM, _), ARRIVAL = C1+C2.

% There isn't a single city, we haven't visited
:- place(Place, _, _), not visited(Place, _).

% Find minimal travel time (Arrival time at starting city)
result(C) :- location(_, t, C).
#minimize{C : result(C)}.

#show location/3.

And here sample data (Running it with clingo takes ~ 30s):

% Cities count
#const t=21.

% Starting point
location(city_0, 0, 0).

% City list in format (name, opening_time, closing_time)
place(city_0, 0, 408).
place(city_1, 62, 68).
place(city_2, 181, 205).
place(city_3, 306, 324).
place(city_4, 214, 217).
place(city_5, 51, 61).
place(city_6, 102, 129).
place(city_7, 175, 186).
place(city_8, 250, 263).
place(city_9, 3, 23).
place(city_10, 21, 49).
place(city_11, 79, 90).
place(city_12, 78, 96).
place(city_13, 140, 154).
place(city_14, 354, 386).
place(city_15, 42, 63).
place(city_16, 2, 13).
place(city_17, 24, 42).
place(city_18, 20, 33).
place(city_19, 9, 21).
place(city_20, 275, 300).

% Distance between cities (from, to, travel_cost)
path(city_0, city_1, 19).
path(city_0, city_2, 17).
path(city_0, city_3, 34).
path(city_0, city_4, 7).
path(city_0, city_5, 20).
path(city_0, city_6, 10).
path(city_0, city_7, 17).
path(city_0, city_8, 28).
path(city_0, city_9, 15).
path(city_0, city_10, 23).
path(city_0, city_11, 29).
path(city_0, city_12, 23).
path(city_0, city_13, 29).
path(city_0, city_14, 21).
path(city_0, city_15, 20).
path(city_0, city_16, 9).
path(city_0, city_17, 16).
path(city_0, city_18, 21).
path(city_0, city_19, 13).
path(city_0, city_20, 12).
path(city_1, city_2, 10).
path(city_1, city_3, 41).
path(city_1, city_4, 26).
path(city_1, city_5, 3).
path(city_1, city_6, 27).
path(city_1, city_7, 25).
path(city_1, city_8, 15).
path(city_1, city_9, 17).
path(city_1, city_10, 17).
path(city_1, city_11, 14).
path(city_1, city_12, 18).
path(city_1, city_13, 48).
path(city_1, city_14, 17).
path(city_1, city_15, 6).
path(city_1, city_16, 21).
path(city_1, city_17, 14).
path(city_1, city_18, 17).
path(city_1, city_19, 13).
path(city_1, city_20, 31).
path(city_2, city_3, 47).
path(city_2, city_4, 23).
path(city_2, city_5, 13).
path(city_2, city_6, 26).
path(city_2, city_7, 15).
path(city_2, city_8, 25).
path(city_2, city_9, 22).
path(city_2, city_10, 26).
path(city_2, city_11, 24).
path(city_2, city_12, 27).
path(city_2, city_13, 44).
path(city_2, city_14, 7).
path(city_2, city_15, 5).
path(city_2, city_16, 23).
path(city_2, city_17, 21).
path(city_2, city_18, 25).
path(city_2, city_19, 18).
path(city_2, city_20, 29).
path(city_3, city_4, 36).
path(city_3, city_5, 39).
path(city_3, city_6, 25).
path(city_3, city_7, 51).
path(city_3, city_8, 36).
path(city_3, city_9, 24).
path(city_3, city_10, 27).
path(city_3, city_11, 38).
path(city_3, city_12, 25).
path(city_3, city_13, 44).
path(city_3, city_14, 54).
path(city_3, city_15, 45).
path(city_3, city_16, 25).
path(city_3, city_17, 28).
path(city_3, city_18, 26).
path(city_3, city_19, 28).
path(city_3, city_20, 27).
path(city_4, city_5, 27).
path(city_4, city_6, 11).
path(city_4, city_7, 17).
path(city_4, city_8, 35).
path(city_4, city_9, 22).
path(city_4, city_10, 30).
path(city_4, city_11, 36).
path(city_4, city_12, 30).
path(city_4, city_13, 22).
path(city_4, city_14, 25).
path(city_4, city_15, 26).
path(city_4, city_16, 14).
path(city_4, city_17, 23).
path(city_4, city_18, 28).
path(city_4, city_19, 20).
path(city_4, city_20, 10).
path(city_5, city_6, 26).
path(city_5, city_7, 27).
path(city_5, city_8, 12).
path(city_5, city_9, 15).
path(city_5, city_10, 14).
path(city_5, city_11, 11).
path(city_5, city_12, 15).
path(city_5, city_13, 49).
path(city_5, city_14, 20).
path(city_5, city_15, 9).
path(city_5, city_16, 20).
path(city_5, city_17, 11).
path(city_5, city_18, 14).
path(city_5, city_19, 11).
path(city_5, city_20, 30).
path(city_6, city_7, 26).
path(city_6, city_8, 31).
path(city_6, city_9, 14).
path(city_6, city_10, 23).
path(city_6, city_11, 32).
path(city_6, city_12, 22).
path(city_6, city_13, 25).
path(city_6, city_14, 31).
path(city_6, city_15, 28).
path(city_6, city_16, 6).
path(city_6, city_17, 17).
path(city_6, city_18, 21).
path(city_6, city_19, 15).
path(city_6, city_20, 4).
path(city_7, city_8, 39).
path(city_7, city_9, 31).
path(city_7, city_10, 38).
path(city_7, city_11, 38).
path(city_7, city_12, 38).
path(city_7, city_13, 34).
path(city_7, city_14, 13).
path(city_7, city_15, 20).
path(city_7, city_16, 26).
path(city_7, city_17, 31).
path(city_7, city_18, 36).
path(city_7, city_19, 28).
path(city_7, city_20, 27).
path(city_8, city_9, 17).
path(city_8, city_10, 9).
path(city_8, city_11, 2).
path(city_8, city_12, 11).
path(city_8, city_13, 56).
path(city_8, city_14, 32).
path(city_8, city_15, 21).
path(city_8, city_16, 24).
path(city_8, city_17, 13).
path(city_8, city_18, 11).
path(city_8, city_19, 15).
path(city_8, city_20, 35).
path(city_9, city_10, 9).
path(city_9, city_11, 18).
path(city_9, city_12, 8).
path(city_9, city_13, 39).
path(city_9, city_14, 29).
path(city_9, city_15, 21).
path(city_9, city_16, 8).
path(city_9, city_17, 4).
path(city_9, city_18, 7).
path(city_9, city_19, 4).
path(city_9, city_20, 18).
path(city_10, city_11, 11).
path(city_10, city_12, 2).
path(city_10, city_13, 48).
path(city_10, city_14, 33).
path(city_10, city_15, 23).
path(city_10, city_16, 17).
path(city_10, city_17, 7).
path(city_10, city_18, 2).
path(city_10, city_19, 10).
path(city_10, city_20, 27).
path(city_11, city_12, 13).
path(city_11, city_13, 57).
path(city_11, city_14, 31).
path(city_11, city_15, 20).
path(city_11, city_16, 25).
path(city_11, city_17, 14).
path(city_11, city_18, 13).
path(city_11, city_19, 17).
path(city_11, city_20, 36).
path(city_12, city_13, 47).
path(city_12, city_14, 34).
path(city_12, city_15, 24).
path(city_12, city_16, 16).
path(city_12, city_17, 7).
path(city_12, city_18, 2).
path(city_12, city_19, 10).
path(city_12, city_20, 26).
path(city_13, city_14, 46).
path(city_13, city_15, 48).
path(city_13, city_16, 31).
path(city_13, city_17, 42).
path(city_13, city_18, 46).
path(city_13, city_19, 40).
path(city_13, city_20, 21).
path(city_14, city_15, 11).
path(city_14, city_16, 29).
path(city_14, city_17, 28).
path(city_14, city_18, 32).
path(city_14, city_19, 25).
path(city_14, city_20, 33).
path(city_15, city_16, 23).
path(city_15, city_17, 19).
path(city_15, city_18, 22).
path(city_15, city_19, 17).
path(city_15, city_20, 32).
path(city_16, city_17, 11).
path(city_16, city_18, 15).
path(city_16, city_19, 9).
path(city_16, city_20, 10).
path(city_17, city_18, 5).
path(city_17, city_19, 3).
path(city_17, city_20, 21).
path(city_18, city_19, 8).
path(city_18, city_20, 25).
path(city_19, city_20, 19).

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:

%Before:
location(To, T + 1, ((ARRIVAL+OPENED_FROM)+|ARRIVAL-OPENED_FROM|)/2) :-  travel(To, T), location(From, T, C1) , path(From, To, C2), place(To, OPENED_FROM, _), ARRIVAL = C1+C2.
%After:
location(To, T + 1, ((ARRIVAL+OPENED_FROM)+|ARRIVAL-OPENED_FROM|)/2, TRAVEL_TIME + C2) :-  travel(To, T), location(From, T, C1, TRAVEL_TIME) , path(From, To, C2), place(To, OPENED_FROM, _), ARRIVAL = C1+C2.

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

My output:

Solving...
Answer: 1
location(city_0,0,0) location(city_16,1,9) location(city_9,2,17) location(city_19,3,21) location(city_17,4,24) location(city_10,5,31) location(city_18,6,33) location(city_5,7,51) location(city_15,8,60) location(city_1,9,66) location(city_11,10,80) location(city_12,11,93) location(city_6,12,115) location(city_13,13,140) location(city_7,14,175) location(city_2,15,190) location(city_4,16,214) location(city_8,17,250) location(city_20,18,285) location(city_3,19,312) location(city_14,20,366) location(city_0,21,387)
Optimization: 387
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 387
Calls        : 1
Time         : 27.654s (Solving: 0.10s 1st Model: 0.04s Unsat: 0.06s)
CPU Time     : 27.651s
(base) igor@i:~/projects/transInfo/TSPTW/src$ clingo dane logika
clingo version 5.4.0
Reading from dane ...
Solving...
Answer: 1
location(city_0,0,0) location(city_16,1,9) location(city_9,2,17) location(city_19,3,21) location(city_17,4,24) location(city_10,5,31) location(city_18,6,33) location(city_5,7,51) location(city_15,8,60) location(city_1,9,66) location(city_11,10,80) location(city_12,11,93) location(city_6,12,115) location(city_13,13,140) location(city_7,14,175) location(city_2,15,190) location(city_4,16,214) location(city_8,17,250) location(city_20,18,285) location(city_3,19,312) location(city_14,20,366) location(city_0,21,387)
Optimization: 387
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 387
Calls        : 1
Time         : 29.682s (Solving: 0.09s 1st Model: 0.03s Unsat: 0.06s)
CPU Time     : 29.680s

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

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

Multiple Traveling Salesman Problem (mTSP)

Summary: The Multiple Traveling Salesman Problem ((m)TSP) is a generalization of the Traveling Salesman Problem (TSP) in which more than one salesman is allowed. Given a set of cities, one depot where (m) salesmen are located, and a cost metric, the objective of the (m)TSP is to determine a tour for each salesman such that the total tour cost is minimized and that each city is visited exactly once by only one salesman.

Case Study Contents

Problem Statement

The Multiple Traveling Salesman Problem ((m)TSP) is a generalization of the Traveling Salesman Problem (TSP) in which more than one salesman is allowed. Given a set of cities, one depot (where (m) salesmen are located), and a cost metric, the objective of the (m)TSP is to determine a set of routes for (m) salesmen so as to minimize the total cost of the (m) routes. The cost metric can represent cost, distance, or time. The requirements on the set of routes are:

• All of the routes must start and end at the (same) depot.
• Each city must be visited exactly once by only one salesman.

The (m)TSP is a relaxation of the vehicle routing problem (VRP); if the vehicle capacity in the VRP is a sufficiently large value so as not to restrict the vehicle capacity, then the problem is the same as the (m)TSP. Therefore, all of the formulations and solution approaches for the VRP are valid for the (m)TSP. The (m)TSP is a generalization of the TSP; if the value of (m) is 1, then the (m)TSP problem is the same as the TSP. Therefore, all of the formulations and solution approaches for the (m)TSP are valid for the TSP.

Bektas (2006) lists a number of variations on the (m)TSP.

1. Multiple depots: Instead of one depot, the multi-depot (m)TSP has a set of depots, with (m_j) salesmen at each depot (j). In the fixed destination version, a salesman returns to the same depot from which he started. In the non-fixed destination version, a salesman does not need to return to the same depot from which he started but the same number of salesmen must return as started from a particular depot. The multi-depot (m)TSP is important in robotic applications involving ground and aerial vehicles. For example, see Oberlin et al. (2009).
2. Specifications on the number of salesmen: The number of salesmen may be a fixed number (m), or the number of salesmen may be determined by the solution but bounded by an upper bound (m).
3. Fixed charges: When the number of salesmen is not fixed, there may be a fixed cost associated with activating a salesman. In the fixed charge version of the (m)TSP, the overall cost to minimize includes the fixed charges for the salesmen plus the costs for the tours.
4. Time windows: As with the TSP and the VRP, there is a variation of the (m)TSP with time windows. Associated with each node is a time window during which the node must be visited by a tour. The (m)TSPTW has many applications, such as school bus routing and airline scheduling.

Mathematical Formulation

Here we present an assignment-based integer programming formulation for the (m)TSP.

Consider a graph (G=(V,A)), where (V) is the set of (n) nodes, and (A) is the set of edges. Associated with each edge ((i,j) in A) is a cost (or distance) (c_). We assume that the depot is node 1 and there are (m) salesmen at the depot. We define a binary variable (x_) for each edge ((i,j) in A); (x_) takes the value 1 if edge ((i,j)) is included in a tour and (x_) takes the value 0 otherwise. For the subtour elimination constraints, we define an integer variable (u_i) to denote the position of node (i) in a tour, and we define a value (p) to be the maximum number of nodes that can be visited by any salesman.

Constraints
Ensure that exactly (m) salesmen depart from node 1
(sum_ x_ <1j>= m)

Ensure that exactly (m) salesmen return to node 1
(sum_ x_ = m)

Ensure that exactly one tour enters each node
(sum_ x_ = 1, forall j in V)

The Multiple Traveling Salesman Problem ((m)TSP) is a generalization of the Traveling Salesman Problem (TSP) in which more than one salesman is allowed. Given a set of cities, one depot where (m) salesmen are located, and a cost metric, the objective of the (m)TSP is to determine a tour for each salesman such that the total tour cost is minimized and that each city is visited exactly once by only one salesman.

Problem Statement

The Multiple Traveling Salesman Problem ((m)TSP) is a generalization of the Traveling Salesman Problem (TSP) in which more than one salesman is allowed. Given a set of cities, one depot (where (m) salesmen are located), and a cost metric, the objective of the (m)TSP is to determine a set of routes for (m) salesmen so as to minimize the total cost of the (m) routes. The cost metric can represent cost, distance, or time. The requirements on the set of routes are:

• All of the routes must start and end at the (same) depot.
• Each city must be visited exactly once by only one salesman.

The (m)TSP is a relaxation of the vehicle routing problem (VRP); if the vehicle capacity in the VRP is a sufficiently large value so as not to restrict the vehicle capacity, then the problem is the same as the (m)TSP. Therefore, all of the formulations and solution approaches for the VRP are valid for the (m)TSP. The (m)TSP is a generalization of the TSP; if the value of (m) is 1, then the (m)TSP problem is the same as the TSP. Therefore, all of the formulations and solution approaches for the (m)TSP are valid for the TSP.

Bektas (2006) lists a number of variations on the (m)TSP.

1. Multiple depots: Instead of one depot, the multi-depot (m)TSP has a set of depots, with (m_j) salesmen at each depot (j). In the fixed destination version, a salesman returns to the same depot from which he started. In the non-fixed destination version, a salesman does not need to return to the same depot from which he started but the same number of salesmen must return as started from a particular depot. The multi-depot (m)TSP is important in robotic applications involving ground and aerial vehicles. For example, see Oberlin et al. (2009).
2. Specifications on the number of salesmen: The number of salesmen may be a fixed number (m), or the number of salesmen may be determined by the solution but bounded by an upper bound (m).
3. Fixed charges: When the number of salesmen is not fixed, there may be a fixed cost associated with activating a salesman. In the fixed charge version of the (m)TSP, the overall cost to minimize includes the fixed charges for the salesmen plus the costs for the tours.
4. Time windows: As with the TSP and the VRP, there is a variation of the (m)TSP with time windows. Associated with each node is a time window during which the node must be visited by a tour. The (m)TSPTW has many applications, such as school bus routing and airline scheduling.

Mathematical Formulation

Here we present an assignment-based integer programming formulation for the (m)TSP.

Consider a graph (G=(V,A)), where (V) is the set of (n) nodes, and (A) is the set of edges. Associated with each edge ((i,j) in A) is a cost (or distance) (c_{ij}). We assume that the depot is node 1 and there are (m) salesmen at the depot. We define a binary variable (x_{ij}) for each edge ((i,j) in A); (x_{ij}) takes the value 1 if edge ((i,j)) is included in a tour and (x_{ij}) takes the value 0 otherwise. For the subtour elimination constraints, we define an integer variable (u_i) to denote the position of node (i) in a tour, and we define a value (p) to be the maximum number of nodes that can be visited by any salesman.

Objective
Minimize ( sum_{(i,j) in A} c_{ij} x_{ij})

Constraints
Ensure that exactly (m) salesmen depart from node 1
(sum_{j in V: (1,j) in A} x_{1j} = m)

Ensure that exactly (m) salesmen return to node 1
(sum_{j in V: (j,1) in A} x_{j1} = m)

Ensure that exactly one tour enters each node
(sum_{i in V: (i,j) in A} x_{ij} = 1, forall j in V)

Ensure that exactly one tour exits each node
(sum_{j in V: (i,j) in A} x_{ij} = 1, forall i in V)

Include subtour elimination constraints (Miller-Tucker-Zemlin)
(u_i – u_j + p cdot x_{ij} leq p-1, forall 2 leq i neq j leq n)

The literature includes a number of alternative formulations. Some of the alternatives to the two-index variable, assignment-based formulation are a two-index variable formulation with the original subtour elimination constraints (see Laporte and Nobert, 1980), a three-index variable formulation (see Bektas, 2006), and a (k)-degree center tree-based formulation (see Christofides et al., 1981 and Laporte, 1992).

To solve this integer linear programming problem, we can use one of the NEOS Server solvers in the Mixed Integer Linear Programming (MILP) category. Each MILP solver has one or more input formats that it accepts.

GAMS Model

Click here for a GAMS model for the bayg29 instance from the TSPLIB. The formulation was provided by Erwin Kalvelagen in a blog post here.

If we submit this model to FICO-Xpress with a CPU time limit of 1 hour, we obtain a solution with a total cost of 2176 (gap of 4.3%) and the following tours:

• Tour 1: i13 – i4 – i10 – i20 – i2 – i13
  cost = 60 + 39 + 25 + 49 + 87 = 260
• Tour 2: i13 – i18 – i14 – i17 – i22 – i11 – i15 – i13
  cost = 128 + 32 + 51 + 47 + 63 + 68 + 86 = 475
• Tour 3: i13 – i24 – i8 – i28 – i12 – i6 – i1 – i13
  cost = 56 + 48 + 64 + 71 + 46 + 60 + 82 = 427
• Tour 4: i13 – i29 – i3 – i26 – i9 – i5 – i21 – i13
  cost =160 + 60 + 78 + 57 + 42 + 50 + 82 = 529
• Tour 5: i13 – i19 – i25 – i7 – i23 – i27 – i16 – i13
  cost = 71 + 52 + 72 + 111 + 74 + 48 + 57 = 485

References

• Bektas, T. 2006. The multiple traveling salesman problem: an overview of formulations and solution procedures. OMEGA: The International Journal of Management Science 34(3), 209-219.
• Christofides, N., A. Mingozzi, and P. Toth. 1981. Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Mathematical Programming 20, 255-282.
• Laporte, G. 1992. The vehicle routing problem: an overview of exact and approximate algorithms. European Journal of Operational Research 59, 345-358.
• Laporte, G. and Y. Nobert. 1980. A cutting planes algorithm for the (m)-salesmen problem. Journal of the Operational Research Society 31, 1017-1023.
• Oberlin, P., S. Rathinam, and S. Darbha. 2009. A transformation for a heterogeneous, multi-depot, multiple traveling salesman problem. In Proceedings of the American Control Conference, 1292-1297, St. Louis, June 10 – 12, 2009.