PGROUTING  2.4
 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 
30 #ifndef SRC_TSP_SRC_PGR_TSP_HPP_
31 #define SRC_TSP_SRC_PGR_TSP_HPP_
32 #pragma once
33 
34 #include <sstream>
35 #include <vector>
36 #include <set>
37 #include <string>
38 
39 #include "../../common/src/pgr_types.h"
40 #include "../../common/src/pgr_assert.h"
41 #include "./Dmatrix.h"
42 #include "./eucledianDmatrix.h"
43 #include "./tour.h"
44 
45 
46 namespace pgrouting {
47 namespace tsp {
48 
49 template < typename MATRIX >
50 class TSP: public MATRIX {
51  public:
52  using MATRIX::distance;
53  using MATRIX::tourCost;
54  using MATRIX::get_row;
55 
56  /*
57  * function members
58  */
59  explicit TSP(const MATRIX &_costs)
60  : MATRIX(_costs),
61  current_tour(_costs.size()),
62  best_tour(_costs.size()),
63  epsilon(0.000001),
64  n(_costs.size()),
65  updatecalls(0),
66  swap_count(0),
67  slide_count(0),
68  reverse_count(0),
69  improve_count(0) {
70  pgassert(n == MATRIX::size());
71  bestCost = MATRIX::tourCost(best_tour);
72  current_cost = MATRIX::tourCost(current_tour);
74  }
75 
76 
77  Tour get_tour() const {return best_tour;}
78 
79  std::string get_stats() const {
80  std::ostringstream log1;
81  log1
82  << "\nTotal swaps: " << swap_count
83  << "\nTotal slides: " << slide_count
84  << "\nTotal reverses: " << reverse_count
85  << "\nTimes best tour changed: " << improve_count;
86  return log1.str();}
87 
88  std::string get_log() const {
89  return log.str();}
90 
91  void greedyInitial(size_t idx_start = 0);
92  void annealing(
93  double initial_temperature,
94  double final_temperature,
95  double cooling_factor,
96  int64_t tries_per_temperature,
97  int64_t max_changes_per_temperature,
98  int64_t max_consecutive_non_changes,
99  bool randomize,
100  double time_limit);
101 
102 
103  private:
106  double bestCost;
107  double current_cost;
108  double epsilon;
109  size_t n;
110 
112 
113  std::ostringstream log;
114  size_t swap_count;
115  size_t slide_count;
118 
119  private:
120  void invariant() const;
121 
122  size_t find_closest_city(
123  size_t current_city,
124  const std::set<size_t> inserted) const;
125 
126  double getDeltaSlide(
127  size_t posP,
128  size_t posF,
129  size_t posL) const;
130 
131  void swapClimb();
132 
133  double getDeltaSwap(
134  size_t posA,
135  size_t posC) const;
136 
137  double getDeltaReverse(
138  size_t posA,
139  size_t posC) const;
140 
141  void update_if_best();
142 };
143 
144 } // namespace tsp
145 } // namespace pgrouting
146 
147 #include "pgr_tsp.cpp"
148 
149 #endif // SRC_TSP_SRC_PGR_TSP_HPP_
double getDeltaSlide(size_t posP, size_t posF, size_t posL) const
Definition: pgr_tsp.cpp:225
double getDeltaReverse(size_t posA, size_t posC) const
Definition: pgr_tsp.cpp:370
double getDeltaSwap(size_t posA, size_t posC) const
Definition: pgr_tsp.cpp:317
void greedyInitial(size_t idx_start=0)
Definition: pgr_tsp.cpp:144
#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:102
void update_if_best()
Definition: pgr_tsp.cpp:85
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:430
void invariant() const
Definition: pgr_tsp.cpp:74
std::string get_stats() const
Definition: pgr_tsp.hpp:79
Tour get_tour() const
Definition: pgr_tsp.hpp:77
std::string get_log() const
Definition: pgr_tsp.hpp:88
std::ostringstream log
Definition: pgr_tsp.hpp:113
TSP(const MATRIX &_costs)
Definition: pgr_tsp.hpp:59