PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
vehicle.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: vehicle.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 "./vehicle.h"
27 
28 #include <deque>
29 #include <iostream>
30 #include <algorithm>
31 #include <tuple>
32 #include <limits>
33 #include <string>
34 #include <utility>
35 #include <vector>
36 
37 #include "../../common/src/pgr_assert.h"
38 
39 #include "./pgr_pickDeliver.h"
40 
41 
42 namespace pgrouting {
43 namespace vrp {
44 
45 
46 void
48  pgassert(m_path.size() >= 2);
49  pgassert(m_path.front().is_start());
50  pgassert(m_path.back().is_end());
51 }
52 
53 size_t
54 Vehicle::insert(std::pair<POS, POS> position_limits, const Vehicle_node &node) {
55  invariant();
56  pgassert(position_limits.first <= m_path.size());
57  pgassert(position_limits.second <= m_path.size());
58 
59  auto low = position_limits.first;
60  auto high = position_limits.second;
61  auto best = low;
62 
63 
64  insert(low, node);
65 
66  Vehicle::Cost best_cost(cost());
67 
68 
69  while (low < high) {
70  swap(low, low + 1);
71  ++low;
72  if (cost_compare(best_cost, cost())) {
73  best_cost = cost();
74  best = low;
75  }
76  }
77  return best;
78 
79  pgassert(best < m_path.size());
80  pgassert(m_path[best].id() == node.id());
81  invariant();
82 }
83 
84 
85 
86 
87 bool
88 Vehicle::cost_compare(const Cost &lhs, const Cost &rhs) const {
89  /*
90  * capacity violations
91  */
92  if (std::get<1>(lhs) < std::get<1>(rhs))
93  return true;
94  if (std::get<1>(lhs) > std::get<1>(rhs))
95  return false;
96 
97  /*
98  * time window violations
99  */
100  if (std::get<0>(lhs) < std::get<0>(rhs))
101  return true;
102  if (std::get<0>(lhs) > std::get<0>(rhs))
103  return false;
104 
105  /*
106  * waiting time
107  */
108  if (std::get<3>(lhs) < std::get<3>(rhs))
109  return true;
110  if (std::get<3>(lhs) > std::get<3>(rhs))
111  return false;
112 
113  /*
114  * duration
115  */
116  if (std::get<4>(lhs) < std::get<4>(rhs))
117  return true;
118  if (std::get<4>(lhs) > std::get<4>(rhs))
119  return false;
120 
121  /*
122  * truck size
123  */
124  if (std::get<2>(lhs) < std::get<2>(rhs))
125  return true;
126  if (std::get<2>(lhs) > std::get<2>(rhs))
127  return false;
128 
129  return false;
130 }
131 
132 
133 
134 void
136  int vid,
137  std::vector< General_vehicle_orders_t > &result) const {
138  /* postgres numbering starts with 1 */
139  int i(1);
140  for (const auto p_stop : m_path) {
142  {vid, i,
143  p_stop.original_id(),
144  p_stop.travel_time(),
145  p_stop.arrival_time(),
146  p_stop.wait_time(),
147  p_stop.service_time(),
148  p_stop.departure_time()};
149  result.push_back(data);
150  ++i;
151  }
152 }
153 
154 
156 Vehicle::cost() const {
157  return std::make_tuple(
158  twvTot(), cvTot(), m_path.size(),
160 }
161 
162 
163 void
165  invariant();
166  pgassert(at <= m_path.size());
167 
168  m_path.insert(m_path.begin() + at, node);
169  evaluate(at);
170 
171  pgassert(at < m_path.size());
172  pgassert(m_path[at].id() == node.id());
173  invariant();
174 }
175 
176 
177 double
178 Vehicle::deltaTime(const Vehicle_node &node, POS pos) const {
179  /*
180  * .... POS POS+1 ....
181  * .... POS node POS+1 ....
182  *
183  */
184  auto prev = m_path[pos-1];
185  auto next = m_path[pos];
186  auto original_time = next.travel_time();
187  auto tt_p_n = prev.travel_time_to(node);
188  tt_p_n = node.is_early_arrival(prev.departure_time() + tt_p_n) ?
189  node.closes() - prev.departure_time()
190  : tt_p_n;
191 
192  auto tt_n_x = node.travel_time_to(next);
193  tt_p_n = next.is_early_arrival(
194  prev.departure_time() + tt_p_n + node.service_time() + tt_n_x) ?
195  next.closes() - (prev.departure_time() + tt_p_n + node.service_time())
196  : tt_n_x;
197 
198  return (tt_p_n + tt_n_x) - original_time;
199 }
200 
201 
202 
203 
204 size_t
206  invariant();
207 
208  double min_delta = (std::numeric_limits<double>::max)();
209  POS min_pos = after_pos;
210 
211  for (POS pos = after_pos; pos < m_path.size(); ++pos) {
212  if (!m_path[pos].is_start()) {
213  auto tt = deltaTime(node, pos);
214 
215  if (tt < min_delta) {
216  min_delta = tt;
217  min_pos = pos;
218  }
219  }
220  }
221  insert(min_pos, node);
222 
223  invariant();
224  return min_pos;
225 }
226 
227 void
229  invariant();
230 
231  POS pos = 0;
232  for ( ; pos < m_path.size() ; ++pos) {
233  if (node.id() == m_path[pos].id())
234  break;
235  }
236 
237  erase(pos);
238  evaluate(pos);
239 
240  invariant();
241 }
242 
243 
244 /*
245  * before: S E
246  * after: S N E
247  *
248  * before: S n1 n2 ... n E
249  * after: S N n1 n2 ... n E
250  */
251 void
253  invariant();
254 
255  /* insert evaluates */
256  insert(1, node);
257 
258  invariant();
259 }
260 
261 /*
262  * before: S E
263  * after: S N E
264  *
265  * before: S n1 n2 ... n E
266  * after: S n1 n2 ... n N E
267  */
268 void
270  invariant();
271 
272  /* insert evaluates */
273  insert(m_path.size() - 1, node);
274 
275  invariant();
276 }
277 
278 void
280  invariant();
281  pgassert(m_path.size() > 2);
282 
283  /* erase evaluates */
284  erase(m_path.size() - 2);
285 
286  invariant();
287 }
288 
289 void
291  invariant();
292  pgassert(m_path.size() > 2);
293 
294  /* erase evaluates */
295  erase(1);
296 
297  invariant();
298 }
299 
300 
301 
302 void
304  invariant();
305 
306  pgassert(m_path.size() > 2);
307  pgassert(at < m_path.size());
308  pgassert(!m_path[at].is_start());
309  pgassert(!m_path[at].is_end());
310 
311  m_path.erase(m_path.begin() + at);
312  evaluate(at);
313 
314  invariant();
315 }
316 
317 void
319  invariant();
320  pgassert(m_path.size() > 3);
321  pgassert(!m_path[i].is_start());
322  pgassert(!m_path[i].is_end());
323  pgassert(!m_path[j].is_start());
324  pgassert(!m_path[j].is_end());
325 
326  std::swap(m_path[i], m_path[j]);
327  i < j ? evaluate(i) : evaluate(j);
328 
329  invariant();
330 }
331 
332 
333 void
335  invariant();
336 
337  evaluate(0);
338 
339  invariant();
340 }
341 
342 bool
343 Vehicle::empty() const {
344  invariant();
345  return m_path.size() <= 2;
346 }
347 
348 void
350  invariant();
351  // preconditions
352  pgassert(from < m_path.size());
353 
354 
355  auto node = m_path.begin() + from;
356 
357  while (node != m_path.end()) {
358  if (node == m_path.begin()) {
359  node->evaluate(max_capacity);
360  } else {
361  node->evaluate(*(node - 1), max_capacity);
362  }
363 
364  ++node;
365  }
366  invariant();
367 }
368 
369 std::deque< Vehicle_node >
370 Vehicle::path() const {
371  invariant();
372  return m_path;
373 }
374 
375 
376 std::pair<size_t, size_t>
378  POS high = getPosHighLimit(node);
379  POS low = getPosLowLimit(node);
380  return std::make_pair(low, high);
381 }
382 
383 
384 /*
385  * start searching from postition low = pos(E)
386  *
387  * S 1 2 3 4 5 6 7 ..... E
388  * node -> E
389  * node -> ...
390  * node -> 7
391  * node -> 6
392  * node -> 5
393  * node /-> 4
394  *
395  * return low_limit = 5
396  *
397  */
398 size_t
400  invariant();
401 
402  POS low = 0;
403  POS high = m_path.size();
404  POS low_limit = high;
405 
406  /* J == m_path[low_limit - 1] */
407  while (low_limit > low
408  && m_path[low_limit - 1].is_compatible_IJ(nodeI)) {
409  --low_limit;
410  }
411 
412  invariant();
413  return low_limit;
414 }
415 
416 
417 /*
418  * start searching from postition low = pos(S)
419  *
420  * S 1 2 3 4 5 6 7 ..... E
421  * S -> node
422  * 1 -> node
423  * 2 -> node
424  * ...
425  * 6 -> node
426  * 7 /-> node
427  *
428  * returns high_limit = 7
429  */
430 size_t
432  invariant();
433 
434  POS low = 0;
435  POS high = m_path.size();
436  POS high_limit = low;
437 
438  /* I == m_path[high_limit] */
439  while (high_limit < high
440  && nodeJ.is_compatible_IJ(m_path[high_limit])) {
441  ++high_limit;
442  }
443 
444  invariant();
445  return high_limit;
446 }
447 
448 
449 
451  ID p_id,
452  const Vehicle_node &starting_site,
453  const Vehicle_node &ending_site,
454  double p_max_capacity) :
455  m_id(p_id),
456  max_capacity(p_max_capacity) {
457  m_path.clear();
458  m_path.push_back(starting_site);
459  m_path.push_back(ending_site);
460  evaluate(0);
461  invariant();
462  }
463 
464 
465 
466 
467 std::string
468 Vehicle::tau() const {
469  std::ostringstream log;
470  log << "Truck " << id() << " (";
471  for (const auto p_stop : m_path) {
472  if (!(p_stop == m_path.front()))
473  log << ", ";
474  log << p_stop.original_id();
475  }
476  log << ")" << " \t(cv, twv, wait_time, duration) = ("
477  << cvTot() << ", "
478  << twvTot() << ", "
479  << total_wait_time() << ", "
480  << duration() << ")";
481 
482  return log.str();
483 }
484 
485 /****** FRIENDS *******/
486 
487 std::ostream&
488 operator << (std::ostream &log, const Vehicle &v) {
489  v.invariant();
490  int i(0);
491  log << "\n\n****************** TRUCK " << v.id() << "***************";
492  for (const auto &path_stop : v.path()) {
493  log << "\nPath_stop" << ++i << "\n";
494  log << path_stop;
495  }
496  return log;
497 }
498 
499 bool
500 operator<(const Vehicle &lhs, const Vehicle &rhs) {
501  lhs.invariant();
502  rhs.invariant();
503 
504  if (lhs.m_path.size() < rhs.m_path.size()) return true;
505 
506  /* here because sizes are equal */
507 
508  if (lhs.m_path.back().total_travel_time()
509  < lhs.m_path.back().total_travel_time()) return true;
510 
511  return false;
512 }
513 
514 } // namespace vrp
515 } // namespace pgrouting
516 
std::pair< POS, POS > position_limits(const Vehicle_node node) const
Definition: vehicle.cpp:377
POS getPosLowLimit(const Vehicle_node &node) const
Definition: vehicle.cpp:399
bool is_early_arrival(double arrival_time) const
True when arrivalTime is before it opens.
Definition: tw_node.h:196
POS getPosHighLimit(const Vehicle_node &node) const
Definition: vehicle.cpp:431
std::deque< Vehicle_node > path() const
@ {
Definition: vehicle.cpp:370
POS insert_less_travel_time(const Vehicle_node &node, POS after_pos=0)
Definition: vehicle.cpp:205
double travel_time_to(const Node &other) const
time = distance / speed.
Definition: tw_node.cpp:40
Extend Tw_node to evaluate the vehicle at node level.
Definition: vehicle_node.h:46
void swap(POS i, POS j)
Swap two nodes in the path.
Definition: vehicle.cpp:318
bool operator<(const Vehicle &lhs, const Vehicle &rhs)
Definition: vehicle.cpp:500
void pop_front()
Evaluated: pop_front a node to the path.
Definition: vehicle.cpp:290
Vehicle(ID id, const Vehicle_node &starting_site, const Vehicle_node &ending_site, double max_capacity)
Definition: vehicle.cpp:450
int cvTot() const
Definition: vehicle.h:231
double total_wait_time() const
Definition: vehicle.h:216
double duration() const
Definition: vehicle.h:213
Vehicle with time windows.
Definition: vehicle.h:62
double service_time() const
Returns the service time for this node.
Definition: tw_node.h:97
void invariant() const
Invariant The path must:
Definition: vehicle.cpp:47
Cost cost() const
@ {
Definition: vehicle.cpp:156
PGDLLEXPORT Datum vrp(PG_FUNCTION_ARGS)
Definition: VRP.c:732
void insert(POS pos, Vehicle_node node)
@ {
Definition: vehicle.cpp:164
bool is_compatible_IJ(const Tw_node &I) const
Definition: tw_node.cpp:65
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::string tau() const
Definition: vehicle.cpp:468
void get_postgres_result(int vid, std::vector< General_vehicle_orders_t > &result) const
Definition: vehicle.cpp:135
double deltaTime(const Vehicle_node &node, POS pos) const
Definition: vehicle.cpp:178
bool empty() const
return true when no nodes are in the truck
Definition: vehicle.cpp:343
void pop_back()
Evaluated: pop_back a node to the path.
Definition: vehicle.cpp:279
bool cost_compare(const Cost &, const Cost &) const
Definition: vehicle.cpp:88
double closes() const
Returns the closing time.
Definition: tw_node.h:91
void push_front(const Vehicle_node &node)
Evaluated: push_back a node to the path.
Definition: vehicle.cpp:252
void erase(const Vehicle_node &node)
Erase node.id()
Definition: vehicle.cpp:228
size_t id() const
@ {
Definition: node.h:51
void push_back(const Vehicle_node &node)
Evaluated: push_back a node to the path.
Definition: vehicle.cpp:269
std::tuple< int, int, size_t, double, double > Cost
Definition: vehicle.h:74
std::deque< Vehicle_node > m_path
Definition: vehicle.h:67
int twvTot() const
Definition: vehicle.h:228
std::ostream & operator<<(std::ostream &log, const Node &node)
Definition: node.cpp:41