PGROUTING  3.2
Public Member Functions | Private Member Functions | Private Attributes | List of all members
pgrouting::tsp::TSP< MATRIX > Class Template Reference

#include "pgr_tsp.hpp"

Inheritance diagram for pgrouting::tsp::TSP< MATRIX >:
Inheritance graph
[legend]
Collaboration diagram for pgrouting::tsp::TSP< MATRIX >:
Collaboration graph
[legend]

Public Member Functions

 TSP (const MATRIX &_costs)
 
void annealing (double initial_temperature, double final_temperature, double cooling_factor, int64_t tries_per_temperature, int64_t max_changes_per_temperature, int64_t max_consecutive_non_changes, bool randomize, double time_limit)
 
std::string get_log () const
 
std::string get_stats () const
 
Tour get_tour () const
 
void greedyInitial (size_t idx_start=0)
 

Private Member Functions

size_t find_closest_city (size_t current_city, const std::set< size_t > &inserted) const
 
double getDeltaReverse (size_t posA, size_t posC) const
 
double getDeltaSlide (size_t posP, size_t posF, size_t posL) const
 
double getDeltaSwap (size_t posA, size_t posC) const
 
void invariant () const
 
void swapClimb ()
 
void update_if_best ()
 

Private Attributes

Tour best_tour
 
double bestCost
 
double current_cost
 
Tour current_tour
 
double epsilon
 
size_t improve_count
 
std::ostringstream log
 
size_t n
 
size_t reverse_count
 
size_t slide_count
 
size_t swap_count
 
int updatecalls
 

Detailed Description

template<typename MATRIX>
class pgrouting::tsp::TSP< MATRIX >

Definition at line 77 of file pgr_tsp.hpp.

Constructor & Destructor Documentation

◆ TSP()

template<typename MATRIX >
pgrouting::tsp::TSP< MATRIX >::TSP ( const MATRIX &  _costs)
inlineexplicit

Definition at line 86 of file pgr_tsp.hpp.

87  : MATRIX(_costs),
88  current_tour(_costs.size()),
89  best_tour(_costs.size()),
90  epsilon(0.000001),
91  n(_costs.size()),
92  updatecalls(0),
93  swap_count(0),
94  slide_count(0),
95  reverse_count(0),
96  improve_count(0) {
97  pgassert(n == MATRIX::size());
98  bestCost = MATRIX::tourCost(best_tour);
99  current_cost = MATRIX::tourCost(current_tour);
100  pgassert(bestCost == current_cost);
101  }

References pgrouting::tsp::TSP< MATRIX >::best_tour, pgrouting::tsp::TSP< MATRIX >::bestCost, pgrouting::tsp::TSP< MATRIX >::current_cost, pgrouting::tsp::TSP< MATRIX >::current_tour, pgrouting::tsp::TSP< MATRIX >::n, and pgassert.

Member Function Documentation

◆ annealing()

template<typename MATRIX >
void pgrouting::tsp::TSP< MATRIX >::annealing ( double  initial_temperature,
double  final_temperature,
double  cooling_factor,
int64_t  tries_per_temperature,
int64_t  max_changes_per_temperature,
int64_t  max_consecutive_non_changes,
bool  randomize,
double  time_limit 
)

Definition at line 429 of file pgr_tsp.cpp.

437  {
438  invariant();
439  clock_t start_time(clock());
440 
441  if (randomize) {
442  std::srand(static_cast<unsigned int>(time(NULL)));
443  } else {
444  std::srand(1);
445  }
446 
447 
448 
449 
450  /* annealing schedule */
451  for (; final_temperature < temperature; temperature *= cooling_factor) {
452  invariant();
453 
454  log << "\nCycle(" << temperature <<") ";
455 
456  /*
457  how many times the tour changed in current temperature
458  */
459  int64_t pathchg = 0;
460  size_t enchg = 0;
461  int64_t non_change = 0;
462  for (int64_t j = 0; j < tries_per_temperature; j++) {
463  ++non_change;
464 
465  auto which = rand(2);
466  // which = 1;
467  switch (which) {
468  case 0: {
469  /* reverse */
470  pgassert(n > 2);
471 
472  auto c1 = std::rand() % n;
473  auto c2 = std::rand() % n;
474 
475  if (c1 == c2) c2 = succ(c2, n);
476  if (c1 == (c2 - 1)) c2 = succ(c2, n);
477  if (c1 > c2) std::swap(c1, c2);
478 
479  pgassert(c1 != c2);
480  pgassert(c1 < n && c2 < n);
481  pgassert(c1 < c2);
482 
483  auto energyChange = getDeltaReverse(c1, c2);
484 
485  if ( (energyChange < 0
486  && epsilon < std::fabs(energyChange))
487  || (0 < energyChange
488  && (
489  static_cast<double>(std::rand()) /
490  static_cast<double>(RAND_MAX))
491  < exp(-energyChange / temperature))) {
492  if (energyChange < 0) ++enchg;
493  ++reverse_count;
494  ++pathchg;
495  non_change = 0;
496  current_cost += energyChange;
497  current_tour.reverse(c1, c2);
498  update_if_best();
499  }
500  }
501  break;
502  case 1: {
503  /* slide */
504  if (n <= 3) {
505  break;
506  }
507 
508  pgassert(n > 3);
509 
510  auto first = std::rand() % n;
511  auto last = std::rand() % n;
512 
513  if (first == last) last = succ(last, n);
514  if (first > last) std::swap(first, last);
515  if (first == 0 && last == (n - 1)) {
516  first = succ(first, n);
517  }
518 
519  pgassert((n - (last - first) - 1) > 0);
520  auto place = std::rand() % (n - (last - first) - 1);
521  place = place < first? place :
522  last + (place - first) + 1;
523 
524 
525  pgassert((place < first
526  || place > last)
527  && (first < last));
528 
529  auto energyChange = getDeltaSlide(
530  place, first, last);
531 
532  if ((energyChange < 0
533  && epsilon < std::fabs(energyChange))
534  || (0 < energyChange
535  && (static_cast<double>(std::rand())
536  / static_cast<double>(RAND_MAX))
537  < exp(-energyChange / temperature))) {
538  if (energyChange < 0) ++enchg;
539  ++slide_count;
540  ++pathchg;
541  non_change = 0;
542  current_cost += energyChange;
543  current_tour.slide(place, first, last);
544  update_if_best();
545  }
546  }
547  break;
548  } // switch
549 
550 
551  if (max_changes_per_temperature < pathchg
552  && max_consecutive_non_changes < non_change ) {
553  break;
554  }
555  } // for tries per temperature
556 
557  swapClimb();
558  clock_t current_time(clock());
559  double elapsed_time = static_cast<double>(
560  current_time - start_time) / CLOCKS_PER_SEC;
561  if (time_limit < elapsed_time) {
562  break;
563  }
564  log << "\ttotal changes =" << pathchg
565  << "\t" << enchg << " were because delta energy < 0";
566  if (pathchg == 0) break; /* if no change then quit */
567  } // for temperatures
568 }

References pgassert, rand(), and succ().

Referenced by do_pgr_euclideanTSP(), and do_pgr_tsp().

◆ find_closest_city()

template<typename MATRIX >
size_t pgrouting::tsp::TSP< MATRIX >::find_closest_city ( size_t  current_city,
const std::set< size_t > &  inserted 
) const
private

Definition at line 202 of file pgr_tsp.hpp.

204  {
205  invariant();
206 
207  auto distance_row(get_row(current_city));
208  pgassert(distance_row.size() == n);
209 
210 #ifndef NDEBUG
211  std::ostringstream err;
212  for (const auto &d : distance_row) {
213  err << d << ", ";
214  }
215 #endif
216 
217  size_t best_city = 0;
218  auto best_distance = (std::numeric_limits<double>::max)();
219 #ifndef NDEBUG
220  bool found(false);
221 #endif
222 
223  for (size_t i = 0; i < distance_row.size(); ++i) {
224  if (i == current_city) continue;
225  if (inserted.find(i) != inserted.end()) continue;
226  if (distance_row[i] < best_distance) {
227  best_city = i;
228  best_distance = distance_row[i];
229 #ifndef NDEBUG
230  found = true;
231 #endif
232  }
233  }
234  pgassertwm(found, err.str());
235 
236  invariant();
237  return best_city;
238 }

References pgassert, and pgassertwm.

◆ get_log()

template<typename MATRIX >
std::string pgrouting::tsp::TSP< MATRIX >::get_log ( ) const
inline

Definition at line 115 of file pgr_tsp.hpp.

115  {
116  return log.str();}

References pgrouting::tsp::TSP< MATRIX >::log.

Referenced by do_pgr_euclideanTSP(), and do_pgr_tsp().

◆ get_stats()

template<typename MATRIX >
std::string pgrouting::tsp::TSP< MATRIX >::get_stats ( ) const
inline

Definition at line 106 of file pgr_tsp.hpp.

106  {
107  std::ostringstream log1;
108  log1
109  << "\nTotal swaps: " << swap_count
110  << "\nTotal slides: " << slide_count
111  << "\nTotal reverses: " << reverse_count
112  << "\nTimes best tour changed: " << improve_count;
113  return log1.str();}

References pgrouting::tsp::TSP< MATRIX >::improve_count, pgrouting::tsp::TSP< MATRIX >::reverse_count, pgrouting::tsp::TSP< MATRIX >::slide_count, and pgrouting::tsp::TSP< MATRIX >::swap_count.

Referenced by do_pgr_euclideanTSP(), and do_pgr_tsp().

◆ get_tour()

template<typename MATRIX >
Tour pgrouting::tsp::TSP< MATRIX >::get_tour ( ) const
inline

Definition at line 104 of file pgr_tsp.hpp.

104 {return best_tour;}

References pgrouting::tsp::TSP< MATRIX >::best_tour.

Referenced by do_pgr_euclideanTSP(), and do_pgr_tsp().

◆ getDeltaReverse()

template<typename MATRIX >
double pgrouting::tsp::TSP< MATRIX >::getDeltaReverse ( size_t  posA,
size_t  posC 
) const
private

Definition at line 369 of file pgr_tsp.cpp.

369  {
370  invariant();
371 
372  if (posA == (posC - 1)) return 0;
373  auto a = current_tour.cities[posA];
374  auto b = current_tour.cities[succ(posA, n)];
375 
376  auto c = current_tour.cities[posC];
377  auto d = current_tour.cities[succ(posC, n)];
378 
379 
380 #ifndef NDEBUG
381  auto delta =
382  distance(a, c) + distance(b, d) - distance(a, b) - distance(c, d);
383  auto new_tour(current_tour);
384  new_tour.reverse(posA, posC);
385  auto exactDelta = tourCost(new_tour) - tourCost(current_tour);
386 
387  std::ostringstream log;
388  log << "exactDelta(" << exactDelta
389  << ") - delta(" << delta
390  << ") = "
391  << exactDelta - delta
392  << " = "
393  << (exactDelta - delta)
394  << " epsilon = " << epsilon;
395  pgassertwm(std::fabs((exactDelta - delta)) < epsilon, log.str());
396 #endif
397 
398  invariant();
399  return distance(a, c) + distance(b, d) - distance(a, b) - distance(c, d);
400 }

References pgassertwm, and succ().

◆ getDeltaSlide()

template<typename MATRIX >
double pgrouting::tsp::TSP< MATRIX >::getDeltaSlide ( size_t  posP,
size_t  posF,
size_t  posL 
) const
private

Definition at line 224 of file pgr_tsp.cpp.

224  {
225  invariant();
226 #ifndef NDEBUG
227  std::ostringstream err;
228  err << "\tplace" << place
229  << "\tfirst" << first
230  << "\tlast" << last
231  << "\tn" << n;
232 #endif
233 
234  pgassertwm(place < first || place > last, err.str());
235  pgassertwm(first < last, err.str());
236  pgassertwm(last < n, err.str());
237  pgassertwm(place < n, err.str());
238  pgassertwm(first < n, err.str());
239 
240  /*
241  * Initial state
242  * [...f] [f+1 ... l] [l+1 ...p] [p+1 ...]
243  *
244  * final state
245  * [...f] [l+1 ... p] [f+1 ...l] [p+1 ...]
246  *
247  *
248  * Initial state
249  * [f+1 ... l]
250  * : :
251  * [...f] [l+1 ...p] [p+1 ...]
252  *
253  * final state
254  * [f+1 ... l]
255  * : :
256  * [...f] [l+1 ...p] [p+1 ...]
257  *
258  */
259 
260  auto cityP = current_tour.cities[place];
261  auto cityF = current_tour.cities[first];
262  auto cityL = current_tour.cities[last];
263  auto cityP1 = current_tour.cities[succ(place, n)];
264  auto cityF1 = current_tour.cities[succ(first, n)];
265  auto cityL1 = current_tour.cities[succ(last, n)];
266 
267  auto delta(
268  distance(cityF, cityL1)
269  + distance(cityP, cityF1)
270  + distance(cityL, cityP1)
271  - distance(cityF, cityF1)
272  - distance(cityL, cityL1)
273  - distance(cityP, cityP1));
274 
275 #ifndef NDEBUG
276  Tour new_tour(current_tour);
277  new_tour.slide(place, first, last);
278 
279  err << "\ncurrent_tour:";
280  for (const auto id : current_tour.cities) {
281  err << id << ", ";
282  }
283 
284  err << "\nnew_tour:";
285  for (const auto id : new_tour.cities) {
286  err << id << ", ";
287  }
288 
289  auto exactDelta = tourCost(new_tour) - tourCost(current_tour);
290  err << "\n"
291  << exactDelta
292  << " - " << delta
293  << " = "
294  << exactDelta - delta
295  << " = "
296  << std::fabs(exactDelta - delta);
297  pgassertwm(std::fabs((exactDelta - delta)) < epsilon, err.str());
298 #endif
299 
300  invariant();
301  return delta;
302 }

References pgrouting::tsp::Tour::cities, pgassertwm, pgrouting::tsp::Tour::slide(), and succ().

◆ getDeltaSwap()

template<typename MATRIX >
double pgrouting::tsp::TSP< MATRIX >::getDeltaSwap ( size_t  posA,
size_t  posC 
) const
private

Definition at line 316 of file pgr_tsp.cpp.

316  {
317  invariant();
318 
319  if (succ(posE, n ) == posA) std::swap(posA, posE);
320  if (succ(posA, n) == posE) {
321  auto b = current_tour.cities[pred(posA, n)];
322  auto a = current_tour.cities[posA];
323 
324  auto e = current_tour.cities[posE];
325  auto f = current_tour.cities[succ(posE, n)];
326  return distance(b, e) + distance(e, a) + distance(a, f)
327  - distance(b, a) - distance(a, e) - distance(e, f);
328  }
329 
330  auto b = current_tour.cities[pred(posA, n)];
331  auto a = current_tour.cities[posA];
332  auto c = current_tour.cities[succ(posA, n)];
333 
334  auto d = current_tour.cities[pred(posE, n)];
335  auto e = current_tour.cities[posE];
336  auto f = current_tour.cities[succ(posE, n)];
337 
338 #ifndef NDEBUG
339  auto delta = distance(b, e)
340  + distance(e, c) + distance(d, a) + distance(a, f)
341  - distance(b, a) - distance(a, c) - distance(d, e) - distance(e, f);
342  auto new_tour(current_tour);
343  new_tour.swap(posA, posE);
344  auto exactDelta = tourCost(new_tour) - tourCost(current_tour);
345  std::ostringstream log;
346  log << exactDelta
347  << " - " << delta
348  << " = "
349  << exactDelta - delta
350  << " = "
351  << std::fabs(exactDelta - delta);
352 
353  pgassertwm(std::fabs((exactDelta - delta)) < epsilon, log.str());
354 #endif
355 
356  invariant();
357  return distance(b, e) + distance(e, c) + distance(d, a) + distance(a, f)
358  - distance(b, a) - distance(a, c) - distance(d, e) - distance(e, f);
359 }

References pgassertwm, pred(), and succ().

◆ greedyInitial()

template<typename MATRIX >
void pgrouting::tsp::TSP< MATRIX >::greedyInitial ( size_t  idx_start = 0)

Definition at line 143 of file pgr_tsp.cpp.

143  {
144  invariant();
145 
146  std::set<size_t> pending(best_tour.cities.begin(), best_tour.cities.end());
147  std::set<size_t> inserted;
148  std::vector<size_t> tour_to_be;
149 
150  auto current_city = idx_start;
151 
152 #ifndef NDEBUG
153  std::ostringstream err;
154  auto ps(pending.size());
155 #endif
156 
157  pending.erase(idx_start);
158 
159 #ifndef NDEBUG
160  pgassert(pending.size() == (ps - 1));
161 #endif
162 
163  tour_to_be.push_back(current_city);
164  inserted.insert(current_city);
165 
166  while (!pending.empty()) {
167  auto next_city = find_closest_city(current_city, inserted);
168  tour_to_be.push_back(next_city);
169  inserted.insert(next_city);
170 
171 #ifndef NDEBUG
172  auto ps(pending.size());
173  err << "before";
174  for (const auto p : pending) {
175  err << p << ",";
176  }
177 #endif
178 
179  pending.erase(next_city);
180 
181 #ifndef NDEBUG
182  err << "\nafter deleting" << next_city << ":\t";
183  for (const auto p : pending) {
184  err << p << ",";
185  }
186  pgassertwm(pending.size() == (ps - 1), err.str());
187 #endif
188 
189  current_city = next_city;
190  }
191 
192  pgassert(tour_to_be.size() == n);
193  current_tour = Tour(tour_to_be);
194  current_cost = tourCost(current_tour);
195  update_if_best();
196  swapClimb();
197 
198  invariant();
199  return;
200 }

References pgassert, and pgassertwm.

Referenced by do_pgr_euclideanTSP(), and do_pgr_tsp().

◆ invariant()

template<typename MATRIX >
void pgrouting::tsp::TSP< MATRIX >::invariant
private

Definition at line 73 of file pgr_tsp.cpp.

73  {
74  /* the calculated value & the actual value are the same */
75  pgassert(std::fabs(tourCost(current_tour) - current_cost) < epsilon);
76  pgassert(std::fabs(tourCost(best_tour) - bestCost) < epsilon);
77  pgassert(n == MATRIX::ids.size());
78  pgassert(n == current_tour.size());
79  pgassert(n == best_tour.size());
80 }

References pgassert.

◆ swapClimb()

template<typename MATRIX >
void pgrouting::tsp::TSP< MATRIX >::swapClimb
private

Definition at line 404 of file pgr_tsp.cpp.

404  {
405  invariant();
406  pgassert(n > 2);
407 
408  // auto first = std::rand() % n;
409  // for (size_t first = std::rand() % n; first < n; first++) {
410  for (size_t first = 0; first < n; first++) {
411  for (size_t last = first + 1; last < n; last++) {
412  pgassert(first < last);
413 
414  auto energyChange = getDeltaSwap(first, last);
415 
416  if (energyChange < 0 && epsilon < std::fabs(energyChange)) {
417  ++swap_count;
418  current_cost += energyChange;
419  current_tour.swap(first, last);
420  update_if_best();
421  }
422  }
423  }
424  invariant();
425 }

References pgassert.

◆ update_if_best()

template<typename MATRIX >
void pgrouting::tsp::TSP< MATRIX >::update_if_best
private

Definition at line 84 of file pgr_tsp.cpp.

84  {
85  invariant();
86  ++updatecalls;
87 
88  if (current_cost < bestCost) {
89  ++improve_count;
90  best_tour = current_tour;
91  bestCost = current_cost;
92  }
93 
94  invariant();
95 }

Member Data Documentation

◆ best_tour

template<typename MATRIX >
Tour pgrouting::tsp::TSP< MATRIX >::best_tour
private

Definition at line 132 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::get_tour(), and pgrouting::tsp::TSP< MATRIX >::TSP().

◆ bestCost

template<typename MATRIX >
double pgrouting::tsp::TSP< MATRIX >::bestCost
private

Definition at line 133 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::TSP().

◆ current_cost

template<typename MATRIX >
double pgrouting::tsp::TSP< MATRIX >::current_cost
private

Definition at line 134 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::TSP().

◆ current_tour

template<typename MATRIX >
Tour pgrouting::tsp::TSP< MATRIX >::current_tour
private

Definition at line 131 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::TSP().

◆ epsilon

template<typename MATRIX >
double pgrouting::tsp::TSP< MATRIX >::epsilon
private

Definition at line 135 of file pgr_tsp.hpp.

◆ improve_count

template<typename MATRIX >
size_t pgrouting::tsp::TSP< MATRIX >::improve_count
private

Definition at line 144 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::get_stats().

◆ log

template<typename MATRIX >
std::ostringstream pgrouting::tsp::TSP< MATRIX >::log
private

Definition at line 140 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::get_log().

◆ n

template<typename MATRIX >
size_t pgrouting::tsp::TSP< MATRIX >::n
private

Definition at line 136 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::TSP().

◆ reverse_count

template<typename MATRIX >
size_t pgrouting::tsp::TSP< MATRIX >::reverse_count
private

Definition at line 143 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::get_stats().

◆ slide_count

template<typename MATRIX >
size_t pgrouting::tsp::TSP< MATRIX >::slide_count
private

Definition at line 142 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::get_stats().

◆ swap_count

template<typename MATRIX >
size_t pgrouting::tsp::TSP< MATRIX >::swap_count
private

Definition at line 141 of file pgr_tsp.hpp.

Referenced by pgrouting::tsp::TSP< MATRIX >::get_stats().

◆ updatecalls

template<typename MATRIX >
int pgrouting::tsp::TSP< MATRIX >::updatecalls
private

Definition at line 138 of file pgr_tsp.hpp.

The documentation for this class was generated from the following files:
pgrouting::tsp::TSP::getDeltaReverse
double getDeltaReverse(size_t posA, size_t posC) const
Definition: pgr_tsp.cpp:369
pgrouting::tsp::TSP::updatecalls
int updatecalls
Definition: pgr_tsp.hpp:138
pgrouting::tsp::TSP::invariant
void invariant() const
Definition: pgr_tsp.cpp:73
pgrouting::tsp::TSP::improve_count
size_t improve_count
Definition: pgr_tsp.hpp:144
pgrouting::tsp::TSP::slide_count
size_t slide_count
Definition: pgr_tsp.hpp:142
pgrouting::tsp::TSP::best_tour
Tour best_tour
Definition: pgr_tsp.hpp:132
pgassertwm
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:117
pgrouting::tsp::TSP::swap_count
size_t swap_count
Definition: pgr_tsp.hpp:141
rand
static size_t rand(size_t n)
Definition: pgr_tsp.cpp:49
pgrouting::tsp::TSP::epsilon
double epsilon
Definition: pgr_tsp.hpp:135
pgassert
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
pgrouting::tsp::TSP::current_tour
Tour current_tour
Definition: pgr_tsp.hpp:131
pgrouting::tsp::TSP::bestCost
double bestCost
Definition: pgr_tsp.hpp:133
pgrouting::tsp::Tour::size
size_t size() const
Definition: tour.h:57
pred
static size_t pred(size_t i, size_t n)
Definition: pgr_tsp.cpp:64
pgrouting::tsp::Tour::cities
std::vector< size_t > cities
Definition: tour.h:156
pgrouting::tsp::TSP::n
size_t n
Definition: pgr_tsp.hpp:136
pgrouting::tsp::TSP::getDeltaSwap
double getDeltaSwap(size_t posA, size_t posC) const
Definition: pgr_tsp.cpp:316
pgrouting::tsp::TSP::find_closest_city
size_t find_closest_city(size_t current_city, const std::set< size_t > &inserted) const
Definition: pgr_tsp.hpp:202
pgrouting::tsp::Tour::swap
void swap(size_t c1, size_t c2)
Definition: tour.cpp:90
pgrouting::tsp::TSP::getDeltaSlide
double getDeltaSlide(size_t posP, size_t posF, size_t posL) const
Definition: pgr_tsp.cpp:224
pgrouting::tsp::Tour::slide
void slide(size_t place, size_t first, size_t last)
Definition: tour.cpp:56
pgrouting::tsp::TSP::current_cost
double current_cost
Definition: pgr_tsp.hpp:134
pgrouting::tsp::TSP::update_if_best
void update_if_best()
Definition: pgr_tsp.cpp:84
pgrouting::tsp::TSP::swapClimb
void swapClimb()
Definition: pgr_tsp.cpp:404
pgrouting::tsp::TSP::log
std::ostringstream log
Definition: pgr_tsp.hpp:140
pgrouting::tsp::TSP::reverse_count
size_t reverse_count
Definition: pgr_tsp.hpp:143
succ
static size_t succ(size_t i, size_t n)
Definition: pgr_tsp.cpp:57
pgrouting::tsp::Tour::reverse
void reverse(size_t c1, size_t c2)
Definition: tour.cpp:47