PGROUTING  2.5
vehicle_pickDeliver.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: vehicle_pickDeliver.cpp
4 
5 Copyright (c) 2016 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 
27 
28 #include <iostream>
29 #include <deque>
30 #include <set>
31 #include <string>
32 #include <sstream>
33 #include <limits>
34 
35 
36 #include "cpp_common/pgr_assert.h"
37 #include "vrp/order.h"
38 #include "vrp/vehicle.h"
39 #include "vrp/pgr_pickDeliver.h"
40 
41 
42 
43 namespace pgrouting {
44 namespace vrp {
45 
46 Order
48  Identifiers<size_t> orders) const {
49  invariant();
50  pgassert(!empty());
51 
52  // auto orders(of_this_subset);
53  auto worse_order(m_orders[*orders.begin()]);
54  auto delta_duration((std::numeric_limits<double>::max)());
55  auto curr_duration(duration());
56  while (!orders.empty()) {
57  auto truck(*this);
58  auto order = m_orders[*orders.begin()];
59  pgassert(truck.has_order(order));
60  orders -= order.idx();
61  truck.erase(order);
62  auto delta = truck.duration() - curr_duration;
63  if (delta < delta_duration) {
64  worse_order = order;
65  delta_duration = delta;
66  }
67  }
68  return worse_order;
69 }
70 
71 
72 Order
74  invariant();
75  pgassert(!empty());
76  return m_orders[m_path[1].idx()];
77 }
78 
79 
81  size_t id,
82  size_t kind,
83  const Vehicle_node &starting_site,
84  const Vehicle_node &ending_site,
85  double p_capacity,
86  double p_speed,
87  double factor) :
88  Vehicle(id, kind, starting_site, ending_site, p_capacity, p_speed, factor),
89  cost((std::numeric_limits<double>::max)()) {
90  ENTERING();
92  invariant();
93  EXITING();
94  }
95 
96 
97 
98 bool
100  return m_orders_in_vehicle.has(order.idx());
101 }
102 
103 
104 void
106  invariant();
107  pgassert(!has_order(order));
108 
109  auto pick_pos(position_limits(order.pickup()));
110  auto deliver_pos(position_limits(order.delivery()));
111 #ifndef NDEBUG
112  std::ostringstream err_log;
113  err_log << "\n\tpickup limits (low, high) = ("
114  << pick_pos.first << ", "
115  << pick_pos.second << ") "
116  << "\n\tdeliver limits (low, high) = ("
117  << deliver_pos.first << ", "
118  << deliver_pos.second << ") "
119  << "\noriginal" << tau();
120 #endif
121 
122  if (pick_pos.second < pick_pos.first) {
123  /* pickup generates twv evrywhere,
124  * so put the order as last */
125  push_back(order);
126  return;
127  }
128 
129  if (deliver_pos.second < deliver_pos.first) {
130  /* delivery generates twv evrywhere,
131  * so put the order as last */
132  push_back(order);
133  return;
134  }
135  /*
136  * Because delivery positions were estimated without
137  * the pickup:
138  * - increase the upper limit position estimation
139  */
140  ++deliver_pos.second;
141 
142 
143  auto d_pos_backup(deliver_pos);
144  auto best_pick_pos = m_path.size();
145  auto best_deliver_pos = m_path.size() + 1;
146  auto current_duration(duration());
147  auto min_delta_duration = (std::numeric_limits<double>::max)();
148  auto found(false);
149  pgassertwm(!has_order(order), err_log.str());
150  while (pick_pos.first <= pick_pos.second) {
151 #ifndef NDEBUG
152  err_log << "\n\tpickup cycle limits (low, high) = ("
153  << pick_pos.first << ", "
154  << pick_pos.second << ") ";
155 #endif
156  Vehicle::insert(pick_pos.first, order.pickup());
157 #ifndef NDEBUG
158  err_log << "\npickup inserted: " << tau();
159 #endif
160 
161  while (deliver_pos.first <= deliver_pos.second) {
162  Vehicle::insert(deliver_pos.first, order.delivery());
163  m_orders_in_vehicle += order.idx();
164  pgassertwm(has_order(order), err_log.str());
165 #ifndef NDEBUG
166  err_log << "\ndelivery inserted: " << tau();
167 #endif
168  if (is_feasable()) {
170  auto delta_duration = duration()-current_duration;
171  if (delta_duration < min_delta_duration) {
172 #ifndef NDEBUG
173  err_log << "\nsuccess" << tau();
174 #endif
175  min_delta_duration = delta_duration;
176  best_pick_pos = pick_pos.first;
177  best_deliver_pos = deliver_pos.first;
178  found = true;
179  }
180  }
181  Vehicle::erase(deliver_pos.first);
182 #ifndef NDEBUG
183  err_log << "\ndelivery erased: " << tau();
184 #endif
185  ++deliver_pos.first;
186  }
187  Vehicle::erase(pick_pos.first);
188 #ifndef NDEBUG
189  err_log << "\npickup erased: " << tau();
190 #endif
191  m_orders_in_vehicle -= order.idx();
192  pgassertwm(!has_order(order), err_log.str());
193 
194  deliver_pos = d_pos_backup;
195 #ifndef NDEBUG
196  err_log << "\n\trestoring deliver limits (low, high) = ("
197  << deliver_pos.first << ", "
198  << deliver_pos.second << ") ";
199 #endif
200  ++pick_pos.first;
201  }
202  pgassertwm(!has_order(order), err_log.str());
203  if (!found) {
204  /* order causes twv
205  * so put the order as last */
206  push_back(order);
207  return;
208  }
209  Vehicle::insert(best_pick_pos, order.pickup());
210  Vehicle::insert(best_deliver_pos, order.delivery());
211 
212  m_orders_in_vehicle += order.idx();
213  pgassertwm(is_feasable(), err_log.str());
214  pgassertwm(has_order(order), err_log.str());
215  pgassertwm(!has_cv(), err_log.str());
216  invariant();
217 }
218 
219 
220 void
222  invariant();
223  pgassert(!has_order(order));
224 
225  m_orders_in_vehicle += order.idx();
226  m_path.insert(m_path.end() - 1, order.pickup());
227  m_path.insert(m_path.end() - 1, order.delivery());
228  evaluate(m_path.size() - 3);
229 
230  pgassert(has_order(order));
231 #if 0
232  pgassert(!has_cv());
233 #endif
234  invariant();
235 }
236 
237 
238 void
240  invariant();
241  pgassert(!has_order(order));
242 
243  m_orders_in_vehicle += order.idx();
244  m_path.insert(m_path.begin() + 1, order.delivery());
245  m_path.insert(m_path.begin() + 1, order.pickup());
246  evaluate(1);
247 
248  pgassert(has_order(order));
249 #if 0
250  pgassert(!has_cv());
251 #endif
252  invariant();
253 }
254 
255 
256 void
258  int kind,
259  Identifiers<size_t> &unassigned,
260  Identifiers<size_t> &assigned) {
262 #if 0
263  msg.log << "unasigned" << unassigned << "\n";
264  msg.log << "m_feasable_orders" << m_feasable_orders << "\n";
265 #endif
266  auto current_feasable = m_feasable_orders * unassigned;
267 
268  while (!current_feasable.empty()) {
269 #if 0
270  msg.log << "current_feasable" << current_feasable << "\n";
271 #endif
272  auto order = m_orders[current_feasable.front()];
273 
274  switch (kind) {
275  case 1:
276  push_back(order);
278  assigned += order.idx();
279  unassigned -= order.idx();
280  invariant();
281  return;
282  break;
283  case 2:
284  push_back(order);
285  break;
286  case 3:
287  push_front(order);
288  break;
289  case 4:
290  insert(order);
291  break;
292  case 5:
293  order = m_orders[m_orders.find_best_J(current_feasable)];
294  insert(order);
295  break;
296  case 6:
297  order = m_orders[m_orders.find_best_I(current_feasable)];
298  insert(order);
299  break;
300  default: pgassert(false);
301  }
302  if (orders_size() == 1 && !is_feasable()) {
303  pgassert(false);
304  }
305 
306  if (!is_feasable()) {
307  erase(order);
308  } else {
309  assigned += order.idx();
310  unassigned -= order.idx();
311  if (kind == 5) {
312  current_feasable = m_orders[order.idx()].subsetJ(
313  current_feasable);
314  }
315  if (kind == 6) {
316  current_feasable = m_orders[order.idx()].subsetI(
317  current_feasable);
318  }
319  }
320 
321  current_feasable -= order.idx();
322  invariant();
323  }
324 
326  invariant();
327 }
328 
329 
330 void
332  invariant();
333  pgassert(has_order(order));
334 
335 
336  Vehicle::erase(order.pickup());
337  Vehicle::erase(order.delivery());
338  m_orders_in_vehicle -= order.idx();
339 
340  invariant();
341  pgassert(!has_order(order));
342 }
343 
344 
345 
346 size_t
348  invariant();
349  pgassert(!empty());
350 
351  auto pick_itr = m_path.rbegin();
352  while (pick_itr != m_path.rend() && !pick_itr->is_pickup()) {
353  ++pick_itr;
354  }
355 
356  pgassert(pick_itr->is_pickup());
357 
358  auto deleted_pick_idx = pick_itr->idx();
359 
360  for (const auto o : m_orders) {
361  if (o.pickup().idx() == deleted_pick_idx) {
362  erase(o);
363  invariant();
364  return o.idx();
365  }
366  }
367  pgassert(false);
368  return 0;
369 }
370 
371 
372 
373 size_t
375  invariant();
376  pgassert(!empty());
377 
378  auto pick_itr = m_path.begin();
379  while (pick_itr != m_path.end() && !pick_itr->is_pickup()) {
380  ++pick_itr;
381  }
382 
383  pgassert(pick_itr->is_pickup());
384 
385  auto deleted_pick_idx = pick_itr->idx();
386 
387  for (const auto o : m_orders) {
388  if (o.pickup().idx() == deleted_pick_idx) {
389  erase(o);
390  invariant();
391  return o.idx();
392  }
393  }
394 
395  pgassert(false);
396  return 0;
397 }
398 
399 void
401  m_orders = orders;
402  for (const auto o : orders) {
403  if (is_order_feasable(o)) m_feasable_orders += o.idx();
404  }
406 }
407 
408 bool
410  auto test_truck = *this;
411  test_truck.push_back(order);
412  return test_truck.is_feasable();
413 }
414 
415 
416 } // namespace vrp
417 } // namespace pgrouting
418 
419 
std::pair< POS, POS > position_limits(const Vehicle_node node) const
Definition: vehicle.cpp:388
bool has(const T other) const
true ids() has element
Definition: identifiers.hpp:97
const PD_Orders & orders() const
bool has_order(const Order &order) const
void push_back(const Order &order)
puts an order at the end of the truck
void push_front(const Order &order)
Puts an order at the end front of the truck.
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
const_iterator begin() const
Definition: identifiers.hpp:80
const Vehicle_node & pickup() const
The delivery node identifier.
Definition: order.cpp:88
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
void do_while_feasable(int kind, Identifiers< size_t > &unassigned, Identifiers< size_t > &assigned)
Identifiers< size_t > m_feasable_orders
orders that fit in the truck
Extend Tw_node to evaluate the vehicle at node level.
Definition: vehicle_node.h:48
STL namespace.
size_t pop_back()
The order that is picked last is removed.
double duration() const
Definition: vehicle.h:228
Vehicle with time windows.
Definition: vehicle.h:72
void clear()
Definition: identifiers.hpp:83
double speed() const
Definition: vehicle.cpp:536
void invariant() const
Invariant The path must:
Definition: vehicle.cpp:47
Cost cost() const
Definition: vehicle.cpp:166
#define EXITING()
Definition: pgr_messages.h:119
size_t find_best_J(Identifiers< size_t > &within_this_set) const
Definition: pd_orders.cpp:165
size_t find_best_I(Identifiers< size_t > &within_this_set) const
Definition: pd_orders.cpp:184
#define ENTERING()
Definition: pgr_messages.h:118
void set_compatibles(const PD_Orders &orders)
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
void insert(const Order &order)
Inserts an order.
bool empty() const
return true when no nodes are in the truck
Definition: vehicle.cpp:354
Order get_worse_order(Identifiers< size_t > of_this_subset) const
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
Assertions Handling.
static Pgr_messages msg
Definition: pd_problem.h:48
bool has_cv() const
Definition: vehicle.h:252
void set_compatibles(double speed)
Definition: pd_orders.cpp:156
void erase(const Vehicle_node &node)
Erase node.id()
Definition: vehicle.cpp:238
bool is_order_feasable(const Order &order) const
const Vehicle_node & delivery() const
The delivery node identifier.
Definition: order.cpp:82
bool empty() const
Definition: identifiers.hpp:78
size_t idx() const
Definition: identifier.cpp:37
bool is_feasable() const
Definition: vehicle.h:256
std::deque< Vehicle_node > m_path
Definition: vehicle.h:75
Vehicle_pickDeliver(size_t id, size_t kind, const Vehicle_node &starting_site, const Vehicle_node &ending_site, double p_capacity, double p_speed, double factor)
Identifiers< size_t > m_orders_in_vehicle
orders inserted in this vehicle