PGROUTING  2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_pickDeliver.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: pgr_pickDeliver.cpp
4 
5 Copyright (c) 2015 pgRouting developers
6 Mail: project@pgrouting.org
7 
8 ------
9 
10 This program is free software; you can redistribute it and/or modify
11 it under the terms of the GNU General Public License as published by
12 the Free Software Foundation; either version 2 of the License, or
13 (at your option) any later version.
14 
15 This program is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 GNU General Public License for more details.
19 
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 
24  ********************************************************************PGR-GNU*/
25 
26 #include "vrp/pgr_pickDeliver.h"
27 
28 #include <sstream>
29 #include <string>
30 #include <vector>
31 #include <algorithm>
32 #include <utility>
33 
34 #include "cpp_common/pgr_assert.h"
35 
36 #include "vrp/vehicle_node.h"
38 #include "vrp/order.h"
39 #include "vrp/pd_orders.h"
40 #include "vrp/fleet.h"
41 #include "vrp/solution.h"
42 #include "vrp/initial_solution.h"
43 #include "vrp/optimize.h"
44 
45 namespace pgrouting {
46 namespace vrp {
47 
48 
49 // TODO(vicky) delete this function
50 bool
52  ENTERING();
53  if (m_nodes.empty() && m_base_nodes.empty()) return true;
54 
55  pgassertwm(m_nodes.size() == m_base_nodes.size(), msg.get_log().c_str());
56  for (size_t i = 0; i < m_nodes.size() ; ++i) {
57  pgassertwm(m_nodes[i].id() == m_base_nodes[i]->id(),
58  msg.get_log().c_str());
59  pgassertwm(m_nodes[i].idx() == m_base_nodes[i]->idx(),
60  msg.get_log().c_str());
61  }
62  EXITING();
63  return true;
64 }
65 
68  pgassert(false);
69  /*
70  * Optimize a solution
71  */
72 #if 1
73  msg.log << "max_cycles: " << m_max_cycles << "\n";
74  Optimize opt_solution(solution, m_max_cycles);
75 #else
76  Optimize opt_solution(solution, 1);
77 #endif
78  msg.log << opt_solution.best_solution.tau("optimized");
79  return opt_solution.best_solution;
80 }
81 
82 void
84  auto initial_sols = solutions;
85 
86  if (m_initial_id == 0) {
87  msg.log << "trying all \n";
88  for (int i = 1; i < 7; ++i) {
89  initial_sols.push_back(Initial_solution(i, m_orders.size()));
90  msg.log << "solution " << i << "\n" << initial_sols.back().tau();
91  // TODO(vicky) calculate the time it takes
92  msg.log << "Initial solution " << i
93  << " duration: " << initial_sols.back().duration();
94  }
95  } else {
96  msg.log << "only trying " << m_initial_id << "\n";
97  initial_sols.push_back(Initial_solution(m_initial_id, m_orders.size()));
98  // TODO(vicky) calculate the time it takes
99  msg.log << "Initial solution " << m_initial_id
100  << " duration: " << initial_sols[0].duration();
101  }
102 
103 
104  /*
105  * Sorting solutions: the best is at the back
106  */
107  pgassert(!initial_sols.empty());
108  std::sort(initial_sols.begin(), initial_sols.end(), []
109  (const Solution &lhs, const Solution &rhs) -> bool {
110  return rhs < lhs;
111  });
112 
113 #if 1
114  solutions.push_back(Optimize(initial_sols.back(), m_max_cycles));
115 #else
116  solutions.push_back(initial_sols.back());
117 #endif
118  pgassert(!solutions.empty());
119 
120  msg.log << "best solution duration = " << solutions.back().duration();
121 }
122 
123 
124 
125 std::vector< General_vehicle_orders_t >
127  auto result = solutions.back().get_postgres_result();
128 
129  General_vehicle_orders_t aggregates = {
130  /*
131  * Vehicle id = -2 indicates its an aggregate row
132  *
133  * (twv, cv, fleet, wait, duration)
134  */
135  -2, // summary row on vehicle_number
136  solutions.back().twvTot(), // on vehicle_id
137  solutions.back().cvTot(), // on vehicle_seq
138  -1, // on order_id
139  -1, // on stop_id
140  -2, // on stop_type (gets increased later by one so it gets -1)
141  -1, // not accounting total loads
142  solutions.back().total_travel_time(),
143  -1, // not accounting arrival_travel_time
144  solutions.back().wait_time(),
145  solutions.back().total_service_time(),
146  solutions.back().duration(),
147  };
148  result.push_back(aggregates);
149 
150 
151 #ifndef NDEBUG
152  for (const auto sol : solutions) {
153  msg.log << sol.tau();
154  }
155 #endif
156  return result;
157 }
158 
163  const std::vector<PickDeliveryOrders_t> &pd_orders,
164  const std::vector<Vehicle_t> &vehicles,
165  const pgrouting::tsp::Dmatrix &cost_matrix,
166  double factor,
167  size_t p_max_cycles,
168  int initial) :
169  PD_problem(this),
170  m_initial_id(initial),
171  m_max_cycles(p_max_cycles),
172  m_node_id(0),
173  m_nodes(),
174  m_base_nodes(),
175  m_cost_matrix(cost_matrix),
176  m_orders(pd_orders),
177  m_trucks(vehicles, factor) {
178  ENTERING();
179  pgassert(!pd_orders.empty());
180  pgassert(!vehicles.empty());
182  pgassert(m_initial_id > 0 && m_initial_id < 7);
183  pgassert(nodesOK());
184 
185  if (!msg.get_error().empty()) {
186  return;
187  }
188 
189  pgassert(m_trucks.msg.get_error().empty());
190  pgassert(msg.get_error().empty());
191 
192  msg.log << "\n Checking fleet ...";
193  if (!m_trucks.is_fleet_ok()) {
194  pgassert(msg.get_error().empty());
195  pgassert(!m_trucks.msg.get_error().empty());
197  return;
198  }
199  msg.log << "fleet OK \n";
200 
201 #if 0
202  for (const auto t : m_trucks) {
203  msg.log << t << "\n";
204  }
205  for (const auto &o : m_orders) {
206  msg.log << o << "\n";
207  }
208 #endif
209 
210  /*
211  * check the (S, P, D, E) order on all vehicles
212  * stop when a feasible truck is found
213  */
214  msg.log << "\n Checking orders";
215  for (const auto &o : m_orders) {
216  if (!m_trucks.is_order_ok(o)) {
217  msg.error << "Order not feasible on any truck was found";
218  msg.log << "The order "
219  << o.id()
220  << " is not feasible on any truck";
221  msg.log << "\n" << o;
222 #if 0
223  double old_speed(0);
224  for (auto t : m_trucks) {
225  if (old_speed == t.speed()) continue;
226  old_speed = t.speed();
227  msg.log << "****** With speed: " << t.speed() << "\n";
228  msg.log << t.start_site() << "\n";
229  msg.log << o.pickup() << "\n";
230  msg.log << "travel time to "
231  << t.start_site().travel_time_to(
232  o.pickup(), t.speed()) << "\n";
233 
234  msg.log << o.delivery() << "\n";
235  msg.log << t.end_site() << "\n";
236  msg.log << "travel time to "
237  << t.start_site().travel_time_to(
238  o.delivery(), t.speed())
239  << "\n";
240  t.push_back(o);
241  }
242 #endif
243  return;
244  }
245  }
246  msg.log << "orders OK \n";
247 
248  m_trucks.set_compatibles(m_orders);
249 #if 0
250  msg.error << "foo";
251  for (const auto t : m_trucks) {
252  msg.log << t << "\n";
253  }
254 #endif
255  EXITING();
256  } // constructor
257 
258 
259 
260 /***** Constructor for the eculedian version *******/
261 
263  const std::vector<PickDeliveryOrders_t> &pd_orders,
264  const std::vector<Vehicle_t> &vehicles,
265  double factor,
266  size_t p_max_cycles,
267  int initial) :
268  PD_problem(this),
269  m_initial_id(initial),
270  m_max_cycles(p_max_cycles),
271  m_node_id(0),
272  m_nodes(),
273  m_base_nodes(),
274  m_cost_matrix(),
275  m_orders(pd_orders),
276  m_trucks(vehicles, factor) {
277  ENTERING();
278  pgassert(!pd_orders.empty());
279  pgassert(!vehicles.empty());
281  pgassert(factor > 0);
282  pgassert(m_initial_id > 0 && m_initial_id < 7);
283 
284  if (!msg.get_error().empty()) {
285  return;
286  }
287 
288  pgassert(m_trucks.msg.get_error().empty());
289  pgassert(msg.get_error().empty());
290 
291  msg.log << "\n Checking fleet";
292  if (!m_trucks.is_fleet_ok()) {
294  pgassert(!m_trucks.msg.get_error().empty());
295  return;
296  }
297 
298  pgassert(m_trucks.msg.get_error().empty());
299 
300 
301 #ifndef NDEBUG
302  for (const auto t : m_trucks) {
303  msg.log << t << "\n";
304  }
305  for (const auto &o : m_orders) {
306  msg.log << o << "\n";
307  }
308 #endif
309 
310  /*
311  * check the (S, P, D, E) order on all vehicles
312  * stop when a feasible truck is found
313  */
314  msg.log << "\n Checking orders";
315  for (const auto &o : m_orders) {
316  if (!m_trucks.is_order_ok(o)) {
317  msg.error << "Order not feasible on any truck was found";
318  msg.log << "The order "
319  << o.pickup().order()
320  << " is not feasible on any truck";
321  msg.log << "\n" << o;
322  return;
323  }
324  }
325 
326  m_trucks.set_compatibles(m_orders);
327  EXITING();
328  } // constructor
329 
330 
331 } // namespace vrp
332 } // namespace pgrouting
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
std::vector< std::unique_ptr< Base_node > > m_base_nodes
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
std::string get_log() const
get_log
Solution optimize(const Solution init_solution)
std::vector< Solution > solutions
std::string get_error() const
get_error
#define EXITING()
Definition: pgr_messages.h:119
std::ostringstream error
Stores the error information.
Definition: pgr_messages.h:106
#define ENTERING()
Definition: pgr_messages.h:118
std::vector< Vehicle_node > m_nodes
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
pgrouting::tsp::Dmatrix m_cost_matrix
size_t size() const
Definition: pd_orders.h:78
double empty() const
Definition: Dmatrix.h:116
bool is_fleet_ok() const
Definition: fleet.cpp:291
std::string tau(const std::string &title="Tau") const
Definition: solution.cpp:153
Assertions Handling.
static Pgr_messages msg
Definition: pd_problem.h:48
Pgr_pickDeliver(const std::vector< PickDeliveryOrders_t > &pd_orders, const std::vector< Vehicle_t > &vehicles, double factor, size_t max_cycles, int initial)
size_t m_max_cycles
maximum cycles in the optimization
int m_initial_id
used define the initial solution algorithm to be used
std::vector< General_vehicle_orders_t > get_postgres_result() const