pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_tsp.hpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2  * File: tsp_driver.cpp
3  *
4  * Generated with Template by:
5  * Copyright (c) 2015 pgRouting developers
6  * Mail: project@pgrouting.org
7  *
8  * Function's developer:
9  * Copyright (c) 2015 Celia Virginia Vergara Castillo
10  * Mail: vicky_vergara@hotmail.com
11  *
12  * ------
13  *
14  * This program is free software; you can redistribute it and/or modify
15  * it under the terms of the GNU General Public License as published by
16  * the Free Software Foundation; either version 2 of the License, or
17  * (at your option) any later version.
18  *
19  * This program is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  * GNU General Public License for more details.
23  *
24  * You should have received a copy of the GNU General Public License
25  * along with this program; if not, write to the Free Software
26  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
27  *
28  * ********************************************************************PGR-GNU*/
29 #pragma once
30 
31 #include <sstream>
32 #include <vector>
33 #include <set>
34 #include <string>
35 
36 #include "../../common/src/pgr_types.h"
37 #include "../../common/src/pgr_assert.h"
38 #include "./Dmatrix.h"
39 #include "./eucledianDmatrix.h"
40 #include "./tour.h"
41 
42 
43 namespace pgrouting {
44 namespace tsp {
45 
46 template < typename MATRIX >
47 class TSP: public MATRIX {
48  public:
49  using MATRIX::distance;
50  using MATRIX::tourCost;
51  using MATRIX::get_row;
52 
53  /*
54  * function members
55  */
56  explicit TSP(const MATRIX &_costs)
57  : MATRIX(_costs),
58  current_tour(_costs.size()),
59  best_tour(_costs.size()),
60  epsilon(0.000001),
61  n(_costs.size()),
62  updatecalls(0),
63  swap_count(0),
64  slide_count(0),
65  reverse_count(0),
66  improve_count(0) {
67  pgassert(n == MATRIX::size());
68  bestCost = MATRIX::tourCost(best_tour);
69  current_cost = MATRIX::tourCost(current_tour);
71  }
72 
73 
74  Tour get_tour() const {return best_tour;}
75 
76  std::string get_stats() const {
77  std::ostringstream log1;
78  log1
79  << "\nTotal swaps: " << swap_count
80  << "\nTotal slides: " << slide_count
81  << "\nTotal reverses: " << reverse_count
82  << "\nTimes best tour changed: " << improve_count;
83  return log1.str();}
84 
85  std::string get_log() const {
86  return log.str();}
87 
88  void greedyInitial(size_t idx_start = 0);
89  void annealing(
90  double initial_temperature,
91  double final_temperature,
92  double cooling_factor,
93  int64_t tries_per_temperature,
94  int64_t max_changes_per_temperature,
95  int64_t max_consecutive_non_changes,
96  bool randomize,
97  double time_limit);
98 
99 
100  private:
103  double bestCost;
104  double current_cost;
105  double epsilon;
106  size_t n;
107 
109 
110  std::ostringstream log;
111  size_t swap_count;
112  size_t slide_count;
115 
116  private:
117  void invariant() const;
118 
119  size_t find_closest_city(
120  size_t current_city,
121  const std::set<size_t> inserted) const;
122 
123  double getDeltaSlide(
124  size_t posP,
125  size_t posF,
126  size_t posL) const;
127 
128  void swapClimb();
129 
130  double getDeltaSwap(
131  size_t posA,
132  size_t posC) const;
133 
134  double getDeltaReverse(
135  size_t posA,
136  size_t posC) const;
137 
138  void update_if_best();
139 };
140 
141 } // namespace tsp
142 } // namespace pgrouting
143 
144 #include "pgr_tsp.cpp"
double getDeltaSlide(size_t posP, size_t posF, size_t posL) const
Definition: pgr_tsp.cpp:230
double getDeltaReverse(size_t posA, size_t posC) const
Definition: pgr_tsp.cpp:374
double getDeltaSwap(size_t posA, size_t posC) const
Definition: pgr_tsp.cpp:322
void greedyInitial(size_t idx_start=0)
Definition: pgr_tsp.cpp:149
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
size_t find_closest_city(size_t current_city, const std::set< size_t > inserted) const
Definition: pgr_tsp.cpp:107
void update_if_best()
Definition: pgr_tsp.cpp:90
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)
Definition: pgr_tsp.cpp:433
void invariant() const
Definition: pgr_tsp.cpp:79
std::string get_stats() const
Definition: pgr_tsp.hpp:76
Tour get_tour() const
Definition: pgr_tsp.hpp:74
std::string get_log() const
Definition: pgr_tsp.hpp:85
std::ostringstream log
Definition: pgr_tsp.hpp:110
TSP(const MATRIX &_costs)
Definition: pgr_tsp.hpp:56