PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
vehicle_pickDeliver.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: vehicle_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 "./vehicle_pickDeliver.h"
27 
28 #include <iostream>
29 #include <deque>
30 #include <set>
31 #include <string>
32 #include <sstream>
33 #include <limits>
34 
35 
36 #include "./../../common/src/pgr_assert.h"
37 #include "./order.h"
38 #include "./vehicle.h"
39 #include "./pgr_pickDeliver.h"
40 
41 
42 
43 namespace pgrouting {
44 namespace vrp {
45 
46 Order
48  std::set<size_t> orders) const {
49  invariant();
50  pgassert(!empty());
51 
52  // auto orders(of_this_subset);
53  auto worse_order(problem->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(problem->orders()[*orders.begin()]);
59  pgassert(truck.has_order(order));
60  orders.erase(orders.begin());
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 problem->order_of(m_path[1]);
77 }
78 
79 
81  size_t id,
82  const Vehicle_node &starting_site,
83  const Vehicle_node &ending_site,
84  double max_capacity,
85  const Pgr_pickDeliver *p_problem) :
86  Vehicle(id, starting_site, ending_site, max_capacity),
87  cost((std::numeric_limits<double>::max)()),
88  problem(p_problem) {
89  orders_in_vehicle.clear();
90 
91  invariant();
92  }
93 
94 
95 
96 bool
98  return !(orders_in_vehicle.find(order.id()) == orders_in_vehicle.end());
99 }
100 
101 
102 void
104  invariant();
105  pgassert(!has_order(order));
106 
107  auto pick_pos(position_limits(order.pickup()));
108  auto deliver_pos(position_limits(order.delivery()));
109 #ifndef NDEBUG
110  std::ostringstream err_log;
111  err_log << "\n\tpickup limits (low, high) = ("
112  << pick_pos.first << ", "
113  << pick_pos.second << ") "
114  << "\n\tdeliver limits (low, high) = ("
115  << deliver_pos.first << ", "
116  << deliver_pos.second << ") "
117  << "\noriginal" << tau();
118 #endif
119 
120  if (pick_pos.second < pick_pos.first) {
121  /* pickup generates twv evrywhere,
122  * so put the order as last */
123  push_back(order);
124  return;
125  }
126 
127  if (deliver_pos.second < deliver_pos.first) {
128  /* delivery generates twv evrywhere,
129  * so put the order as last */
130  push_back(order);
131  return;
132  }
133  /*
134  * Because delivery positions were estimated without
135  * the pickup:
136  * - increase the upper limit position estimation
137  */
138  ++deliver_pos.second;
139 
140 
141  auto d_pos_backup(deliver_pos);
142  auto best_pick_pos = m_path.size();
143  auto best_deliver_pos = m_path.size() + 1;
144  auto current_duration(duration());
145  auto min_delta_duration = (std::numeric_limits<double>::max)();
146  auto found(false);
147  pgassertwm(!has_order(order), err_log.str());
148  while (pick_pos.first <= pick_pos.second) {
149 #ifndef NDEBUG
150  err_log << "\n\tpickup cycle limits (low, high) = ("
151  << pick_pos.first << ", "
152  << pick_pos.second << ") ";
153 #endif
154  Vehicle::insert(pick_pos.first, order.pickup());
155 #ifndef NDEBUG
156  err_log << "\npickup inserted: " << tau();
157 #endif
158 
159  while (deliver_pos.first <= deliver_pos.second) {
160  Vehicle::insert(deliver_pos.first, order.delivery());
161  orders_in_vehicle.insert(order.id());
162  pgassertwm(has_order(order), err_log.str());
163 #ifndef NDEBUG
164  err_log << "\ndelivery inserted: " << tau();
165 #endif
166  if (is_feasable()) {
168  auto delta_duration = duration()-current_duration;
169  if (delta_duration < min_delta_duration) {
170 #ifndef NDEBUG
171  err_log << "\nsuccess" << tau();
172 #endif
173  min_delta_duration = delta_duration;
174  best_pick_pos = pick_pos.first;
175  best_deliver_pos = deliver_pos.first;
176  found = true;
177  }
178  }
179  Vehicle::erase(deliver_pos.first);
180 #ifndef NDEBUG
181  err_log << "\ndelivery erased: " << tau();
182 #endif
183  ++deliver_pos.first;
184  }
185  Vehicle::erase(pick_pos.first);
186 #ifndef NDEBUG
187  err_log << "\npickup erased: " << tau();
188 #endif
189  orders_in_vehicle.erase(order.id());
190  pgassertwm(!has_order(order), err_log.str());
191 
192  deliver_pos = d_pos_backup;
193 #ifndef NDEBUG
194  err_log << "\n\trestoring deliver limits (low, high) = ("
195  << deliver_pos.first << ", "
196  << deliver_pos.second << ") ";
197 #endif
198  ++pick_pos.first;
199  }
200  pgassertwm(!has_order(order), err_log.str());
201  if (!found) {
202  /* order causes twv
203  * so put the order as last */
204  push_back(order);
205  return;
206  }
207  Vehicle::insert(best_pick_pos, order.pickup());
208  Vehicle::insert(best_deliver_pos, order.delivery());
209 
210  orders_in_vehicle.insert(order.id());
211  pgassertwm(is_feasable(), err_log.str());
212  pgassertwm(has_order(order), err_log.str());
213  pgassertwm(!has_cv(), err_log.str());
214  invariant();
215 }
216 
217 void
219  invariant();
220  pgassert(!has_order(order));
221 
222  orders_in_vehicle.insert(order.id());
223  m_path.insert(m_path.end() - 1, order.pickup());
224  m_path.insert(m_path.end() - 1, order.delivery());
225  evaluate(m_path.size() - 3);
226 
227  pgassert(has_order(order));
228 #if 0
229  pgassert(!has_cv());
230 #endif
231  invariant();
232 }
233 
234 void
236  invariant();
237  pgassert(!has_order(order));
238 
239  orders_in_vehicle.insert(order.id());
240  m_path.insert(m_path.begin() + 1, order.delivery());
241  m_path.insert(m_path.begin() + 1, order.pickup());
242  evaluate(1);
243 
244  pgassert(has_order(order));
245 #if 0
246  pgassert(!has_cv());
247 #endif
248  invariant();
249 }
250 
251 
252 void
254  invariant();
255  pgassert(has_order(order));
256 
257 
258  Vehicle::erase(order.pickup());
259  Vehicle::erase(order.delivery());
260  orders_in_vehicle.erase(orders_in_vehicle.find(order.id()));
261 
262  invariant();
263  pgassert(!has_order(order));
264 }
265 
266 
267 
268 size_t
270  invariant();
271  pgassert(!empty());
272 
273  auto pick_itr = m_path.rbegin();
274  while (pick_itr != m_path.rend() && !pick_itr->is_pickup()) {
275  ++pick_itr;
276  }
277 
278  pgassert(pick_itr->is_pickup());
279 
280  ID deleted_pick_id = pick_itr->id();
281 
282 
283  auto delivery_id = problem->node(deleted_pick_id).Did();
284 
285  m_path.erase((pick_itr + 1).base());
286 
287  auto delivery_itr = m_path.rbegin();
288  while (delivery_itr != m_path.rend()
289  && !(delivery_itr->id() ==delivery_id)) {
290  ++delivery_itr;
291  }
292 
293  pgassert(delivery_itr->is_delivery());
294  pgassert(delivery_itr->Pid() == deleted_pick_id);
295 
296  m_path.erase((delivery_itr + 1).base());
297 
298 
299  /* figure out from where the evaluation is needed */
300  evaluate(1);
301 
302  ID deleted_order_id(
303  problem->order_of(problem->node(deleted_pick_id)).id());
304 
305  orders_in_vehicle.erase(orders_in_vehicle.find(deleted_order_id));
306 
307  invariant();
308  return deleted_order_id;
309 }
310 
311 
312 
313 size_t
315  invariant();
316  pgassert(!empty());
317 
318  auto pick_itr = m_path.begin();
319  while (pick_itr != m_path.end() && !pick_itr->is_pickup()) {
320  ++pick_itr;
321  }
322 
323  pgassert(pick_itr->is_pickup());
324 
325  ID deleted_pick_id = pick_itr->id();
326 
327 
328  auto delivery_id = problem->node(deleted_pick_id).Did();
329 
330  m_path.erase(pick_itr);
331 
332  auto delivery_itr = m_path.begin();
333  while (delivery_itr != m_path.end()
334  && !(delivery_itr->id() == delivery_id)) {
335  ++delivery_itr;
336  }
337 
338  pgassert(delivery_itr->is_delivery());
339  pgassert(delivery_itr->Pid() == deleted_pick_id);
340 
341  m_path.erase(delivery_itr);
342 
343  evaluate(1);
344 
345  ID deleted_order_id(
346  problem->order_of(problem->node(deleted_pick_id)).id());
347 
348  orders_in_vehicle.erase(orders_in_vehicle.find(deleted_order_id));
349 
350  invariant();
351  return deleted_order_id;
352 }
353 
354 
355 } // namespace vrp
356 } // namespace pgrouting
357 
358 
std::pair< POS, POS > position_limits(const Vehicle_node node) const
Definition: vehicle.cpp:377
bool has_order(const Order &order) const
Order get_worse_order(std::set< size_t > of_this_subset) 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
size_t id() const
Definition: order.h:57
const Vehicle_node & pickup() const
Definition: order.cpp:106
Extend Tw_node to evaluate the vehicle at node level.
Definition: vehicle_node.h:46
ID pop_back()
The order that is picked last is removed.
double duration() const
Definition: vehicle.h:213
Vehicle with time windows.
Definition: vehicle.h:62
void invariant() const
Invariant The path must:
Definition: vehicle.cpp:47
PGDLLEXPORT Datum vrp(PG_FUNCTION_ARGS)
Definition: VRP.c:732
void insert(POS pos, Vehicle_node node)
@ {
Definition: vehicle.cpp:164
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
std::string tau() const
Definition: vehicle.cpp:468
void insert(const Order &order)
Inserts an order.
bool empty() const
return true when no nodes are in the truck
Definition: vehicle.cpp:343
const Order order_of(const Vehicle_node &node) const
bool has_cv() const
Definition: vehicle.h:237
const Vehicle_node & node(ID id) const
void erase(const Vehicle_node &node)
Erase node.id()
Definition: vehicle.cpp:228
Vehicle_pickDeliver(ID id, const Vehicle_node &starting_site, const Vehicle_node &ending_site, double max_capacity, const Pgr_pickDeliver *p_problem)
const Vehicle_node & delivery() const
Definition: order.cpp:102
const std::vector< Order > & orders() const
bool is_feasable() const
Definition: vehicle.h:240
size_t Did() const
Definition: tw_node.h:72
std::deque< Vehicle_node > m_path
Definition: vehicle.h:67