PGROUTING  2.5
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 "vrp/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 "cpp_common/pgr_assert.h"
38 
39 #include "vrp/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].idx() == node.idx());
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 std::vector<General_vehicle_orders_t>
136  int vid) const {
137  std::vector<General_vehicle_orders_t> result;
138  /* postgres numbering starts with 1 */
139  int stop_seq(1);
140  msg.log << "getting solution: " << tau() << "\n";
141  for (const auto p_stop : m_path) {
142  General_vehicle_orders_t data = {
143  vid,
144  id(),
145  stop_seq,
146  /* order_id
147  * The order_id is invalid for stops type 0 and 5
148  */
149  (p_stop.type() == 0 || p_stop.type() == 5)? -1 : p_stop.order(),
150  p_stop.id(),
151  p_stop.type(),
152  p_stop.cargo(),
153  p_stop.travel_time(),
154  p_stop.arrival_time(),
155  p_stop.wait_time(),
156  p_stop.service_time(),
157  p_stop.departure_time()};
158  result.push_back(data);
159  ++stop_seq;
160  }
161  return result;
162 }
163 
164 
166 Vehicle::cost() const {
167  return std::make_tuple(
168  twvTot(), cvTot(), m_path.size(),
170 }
171 
172 
173 void
175  invariant();
176  pgassert(at <= m_path.size());
177 
178  m_path.insert(m_path.begin() + at, node);
179  evaluate(at);
180 
181  pgassert(at < m_path.size());
182  pgassert(m_path[at].idx() == node.idx());
183  invariant();
184 }
185 
186 
187 double
188 Vehicle::deltaTime(const Vehicle_node &node, POS pos) const {
189  /*
190  * .... POS POS+1 ....
191  * .... POS node POS+1 ....
192  *
193  */
194  auto prev = m_path[pos-1];
195  auto next = m_path[pos];
196  auto original_time = next.travel_time();
197  auto tt_p_n = prev.travel_time_to(node, speed());
198  tt_p_n = node.is_early_arrival(prev.departure_time() + tt_p_n) ?
199  node.closes() - prev.departure_time()
200  : tt_p_n;
201 
202  auto tt_n_x = node.travel_time_to(next, speed());
203  tt_p_n = next.is_early_arrival(
204  prev.departure_time() + tt_p_n + node.service_time() + tt_n_x) ?
205  next.closes() - (prev.departure_time() + tt_p_n + node.service_time())
206  : tt_n_x;
207 
208  return (tt_p_n + tt_n_x) - original_time;
209 }
210 
211 
212 
213 
214 size_t
216  invariant();
217 
218  double min_delta = (std::numeric_limits<double>::max)();
219  POS min_pos = after_pos;
220 
221  for (POS pos = after_pos; pos < m_path.size(); ++pos) {
222  if (!m_path[pos].is_start()) {
223  auto tt = deltaTime(node, pos);
224 
225  if (tt < min_delta) {
226  min_delta = tt;
227  min_pos = pos;
228  }
229  }
230  }
231  insert(min_pos, node);
232 
233  invariant();
234  return min_pos;
235 }
236 
237 void
239  invariant();
240 
241  POS pos = 0;
242  for ( ; pos < m_path.size() ; ++pos) {
243  if (node.idx() == m_path[pos].idx())
244  break;
245  }
246 
247  erase(pos);
249  evaluate(pos);
250 
251  invariant();
252 }
253 
254 
255 /*
256  * before: S E
257  * after: S N E
258  *
259  * before: S n1 n2 ... n E
260  * after: S N n1 n2 ... n E
261  */
262 void
264  invariant();
265 
266  /* insert evaluates */
267  insert(1, node);
268 
269  invariant();
270 }
271 
272 /*
273  * before: S E
274  * after: S N E
275  *
276  * before: S n1 n2 ... n E
277  * after: S n1 n2 ... n N E
278  */
279 void
281  invariant();
282 
283  /* insert evaluates */
284  insert(m_path.size() - 1, node);
285 
286  invariant();
287 }
288 
289 void
291  invariant();
292  pgassert(m_path.size() > 2);
293 
294  /* erase evaluates */
295  erase(m_path.size() - 2);
296 
297  invariant();
298 }
299 
300 void
302  invariant();
303  pgassert(m_path.size() > 2);
304 
305  /* erase evaluates */
306  erase(1);
307 
308  invariant();
309 }
310 
311 
312 
313 void
315  invariant();
316 
317  pgassert(m_path.size() > 2);
318  pgassert(at < m_path.size());
319  pgassert(!m_path[at].is_start());
320  pgassert(!m_path[at].is_end());
321 
322  m_path.erase(m_path.begin() + at);
323  evaluate(at);
324 
325  invariant();
326 }
327 
328 void
330  invariant();
331  pgassert(m_path.size() > 3);
332  pgassert(!m_path[i].is_start());
333  pgassert(!m_path[i].is_end());
334  pgassert(!m_path[j].is_start());
335  pgassert(!m_path[j].is_end());
336 
337  std::swap(m_path[i], m_path[j]);
338  i < j ? evaluate(i) : evaluate(j);
339 
340  invariant();
341 }
342 
343 
344 void
346  invariant();
347 
348  evaluate(0);
349 
350  invariant();
351 }
352 
353 bool
354 Vehicle::empty() const {
355  invariant();
356  return m_path.size() <= 2;
357 }
358 
359 void
361  invariant();
362  // preconditions
363  pgassert(from < m_path.size());
364 
365 
366  auto node = m_path.begin() + from;
367 
368  while (node != m_path.end()) {
369  if (node == m_path.begin()) {
370  node->evaluate(m_capacity);
371  } else {
372  node->evaluate(*(node - 1), m_capacity, speed());
373  }
374 
375  ++node;
376  }
377  invariant();
378 }
379 
380 std::deque< Vehicle_node >
381 Vehicle::path() const {
382  invariant();
383  return m_path;
384 }
385 
386 
387 std::pair<size_t, size_t>
389  POS high = getPosHighLimit(node);
390  POS low = getPosLowLimit(node);
391  return std::make_pair(low, high);
392 }
393 
394 
395 /*
396  * start searching from postition low = pos(E)
397  *
398  * S 1 2 3 4 5 6 7 ..... E
399  * node -> E
400  * node -> ...
401  * node -> 7
402  * node -> 6
403  * node -> 5
404  * node /-> 4
405  *
406  * return low_limit = 5
407  *
408  */
409 size_t
411  invariant();
412 
413  POS low = 0;
414  POS high = m_path.size();
415  POS low_limit = high;
416 
417  /* J == m_path[low_limit - 1] */
418  while (low_limit > low
419  && m_path[low_limit - 1].is_compatible_IJ(nodeI, speed())) {
420  --low_limit;
421  }
422 
423  invariant();
424  return low_limit;
425 }
426 
427 
428 /*
429  * start searching from postition low = pos(S)
430  *
431  * S 1 2 3 4 5 6 7 ..... E
432  * S -> node
433  * 1 -> node
434  * 2 -> node
435  * ...
436  * 6 -> node
437  * 7 /-> node
438  *
439  * returns high_limit = 7
440  */
441 size_t
443  invariant();
444 
445  POS low = 0;
446  POS high = m_path.size();
447  POS high_limit = low;
448 
449  /* I == m_path[high_limit] */
450  while (high_limit < high
451  && nodeJ.is_compatible_IJ(m_path[high_limit], speed())) {
452  ++high_limit;
453  }
454 
455  invariant();
456  return high_limit;
457 }
458 
459 bool
460 Vehicle::is_ok() const {
461  pgassert((m_path.front().opens() <= m_path.front().closes())
462  && (m_path.back().opens() <= m_path.back().closes())
463  && (m_capacity > 0));
464  return (start_site().opens() <= start_site().closes())
465  && (end_site().opens() <= end_site().closes())
466  && (m_capacity > 0);
467 }
468 
470  size_t p_idx,
471  int64_t p_id,
472  const Vehicle_node &starting_site,
473  const Vehicle_node &ending_site,
474  double p_m_capacity,
475  double p_speed,
476  double p_factor) :
477  Identifier(p_idx, p_id),
478  m_capacity(p_m_capacity),
479  m_factor(p_factor),
480  m_speed(p_speed) {
481  ENTERING();
482  m_path.clear();
483  pgassert(starting_site.opens() <= starting_site.closes());
484  pgassert(ending_site.opens() <= ending_site.closes());
485  pgassert(capacity() > 0);
486  msg.log << "p_idx: " << p_idx << "\t idx(): " << idx() << "\n";
487  msg.log << "p_id: " << p_id << "\tid(): " << id() << "\n" ;
488 
489  m_path.push_back(starting_site);
490  m_path.push_back(ending_site);
491 
492  evaluate(0);
493  msg.log << tau() << "\n";
494  invariant();
495  EXITING();
496  }
497 
499  Identifier(v.idx(), v.id()),
500  PD_problem(),
501  m_path(v.m_path),
503  m_factor(v.m_factor),
504  m_speed(v.m_speed) {
505 #if 0
506  ENTERING();
507  msg.log << v.tau() << "\n";
508  msg.log << tau() << "\n";
509  EXITING();
510 #endif
511 }
512 
513 
514 
515 std::string
516 Vehicle::tau() const {
517  pgassert(m_path.size() > 1);
518  std::ostringstream log;
519  log << "Truck " << id() << "(" << idx() << ")"
520  << " (";
521  for (const auto p_stop : m_path) {
522  if (!(p_stop == m_path.front()))
523  log << ", ";
524  log << p_stop.id();
525  }
526  log << ")" << " \t(cv, twv, wait_time, duration) = ("
527  << cvTot() << ", "
528  << twvTot() << ", "
529  << total_wait_time() << ", "
530  << duration() << ")";
531 
532  return log.str();
533 }
534 
535 double
536 Vehicle::speed() const {
537  return m_speed/m_factor;
538 }
539 
540 /****** FRIENDS *******/
541 
542 std::ostream&
543 operator << (std::ostream &log, const Vehicle &v) {
544  v.invariant();
545  int i(0);
546  log << "\n\n****************** " << v.idx() << "th VEHICLE*************\n";
547  log << "id = " << v.id()
548  << "\tcapacity = " << v.m_capacity
549  << "\tfactor = " << v.m_factor << "\n"
550  << "\tspeed = " << v.m_speed << "\n"
551  << "\tnew speed = " << v.speed() << "\n";
552 
553  for (const auto &path_stop : v.path()) {
554  log << "Path_stop" << ++i << "\n";
555  log << path_stop << "\n";
556  }
557  return log;
558 }
559 
560 bool
561 operator<(const Vehicle &lhs, const Vehicle &rhs) {
562  lhs.invariant();
563  rhs.invariant();
564 
565  if (lhs.m_path.size() < rhs.m_path.size()) return true;
566 
567  /* here because sizes are equal */
568 
569  if (lhs.m_path.back().total_travel_time()
570  < lhs.m_path.back().total_travel_time()) return true;
571 
572  return false;
573 }
574 
575 } // namespace vrp
576 } // namespace pgrouting
577 
std::pair< POS, POS > position_limits(const Vehicle_node node) const
Definition: vehicle.cpp:388
POS getPosLowLimit(const Vehicle_node &node) const
Definition: vehicle.cpp:410
bool is_early_arrival(double arrival_time) const
True when arrivalTime is before it opens.
Definition: tw_node.h:187
Vehicle_node start_site() const
Definition: vehicle.h:262
friend std::ostream & operator<<(std::ostream &log, const Vehicle &v)
@ {
Definition: vehicle.cpp:543
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
POS getPosHighLimit(const Vehicle_node &node) const
Definition: vehicle.cpp:442
int64_t id() const
Definition: identifier.cpp:42
Vehicle(const Vehicle &)
Definition: vehicle.cpp:498
std::deque< Vehicle_node > path() const
@ {
Definition: vehicle.cpp:381
POS insert_less_travel_time(const Vehicle_node &node, POS after_pos=0)
Definition: vehicle.cpp:215
Extend Tw_node to evaluate the vehicle at node level.
Definition: vehicle_node.h:48
void swap(POS i, POS j)
Swap two nodes in the path.
Definition: vehicle.cpp:329
void pop_front()
Evaluated: pop_front a node to the path.
Definition: vehicle.cpp:301
int cvTot() const
Definition: vehicle.h:246
double total_wait_time() const
Definition: vehicle.h:231
double duration() const
Definition: vehicle.h:228
Vehicle with time windows.
Definition: vehicle.h:72
bool is_compatible_IJ(const Tw_node &I, double speed) const
Definition: tw_node.cpp:73
double service_time() const
Returns the service time for this node.
Definition: tw_node.h:86
double speed() const
Definition: vehicle.cpp:536
void invariant() const
Invariant The path must:
Definition: vehicle.cpp:47
bool is_ok() const
Definition: vehicle.cpp:460
double opens() const
Returns the opening time.
Definition: tw_node.h:76
Cost cost() const
Definition: vehicle.cpp:166
double capacity() const
Definition: vehicle.h:271
#define EXITING()
Definition: pgr_messages.h:119
#define ENTERING()
Definition: pgr_messages.h:118
void insert(POS pos, Vehicle_node node)
@ {
Definition: vehicle.cpp:174
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::string tau() const
Definition: vehicle.cpp:516
double deltaTime(const Vehicle_node &node, POS pos) const
Definition: vehicle.cpp:188
bool empty() const
return true when no nodes are in the truck
Definition: vehicle.cpp:354
friend bool operator<(const Vehicle &lhs, const Vehicle &rhs)
Definition: vehicle.cpp:561
void pop_back()
Evaluated: pop_back a node to the path.
Definition: vehicle.cpp:290
bool cost_compare(const Cost &, const Cost &) const
Definition: vehicle.cpp:88
double closes() const
Returns the closing time.
Definition: tw_node.h:79
Vehicle_node end_site() const
Definition: vehicle.h:265
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
Assertions Handling.
static Pgr_messages msg
Definition: pd_problem.h:48
void push_front(const Vehicle_node &node)
Evaluated: push_back a node to the path.
Definition: vehicle.cpp:263
void erase(const Vehicle_node &node)
Erase node.id()
Definition: vehicle.cpp:238
void push_back(const Vehicle_node &node)
Evaluated: push_back a node to the path.
Definition: vehicle.cpp:280
std::tuple< int, int, size_t, double, double > Cost
Definition: vehicle.h:86
size_t idx() const
Definition: identifier.cpp:37
std::vector< General_vehicle_orders_t > get_postgres_result(int vid) const
Definition: vehicle.cpp:135
std::deque< Vehicle_node > m_path
Definition: vehicle.h:75
double travel_time_to(const Tw_node &other, double speed) const
time = distance / speed.
Definition: tw_node.cpp:40
int twvTot() const
Definition: vehicle.h:243