pgRouting
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 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 #include <iostream>
26 #include <deque>
27 #include <set>
28 #include <string>
29 #include <sstream>
30 #include <limits>
31 
32 
33 #include "./../../common/src/pgr_assert.h"
34 #include "./order.h"
35 #include "./vehicle.h"
36 #include "./vehicle_pickDeliver.h"
37 #include "./pgr_pickDeliver.h"
38 
39 
40 
41 namespace pgrouting {
42 namespace vrp {
43 
44 Order
46  std::set<size_t> orders) const {
47  invariant();
48  pgassert(!empty());
49 
50  // auto orders(of_this_subset);
51  auto worse_order(problem->orders()[*orders.begin()]);
52  auto delta_duration((std::numeric_limits<double>::max)());
53  auto curr_duration(duration());
54  while (!orders.empty()) {
55  auto truck(*this);
56  auto order(problem->orders()[*orders.begin()]);
57  pgassert(truck.has_order(order));
58  orders.erase(orders.begin());
59  truck.erase(order);
60  auto delta = truck.duration() - curr_duration;
61  if (delta < delta_duration) {
62  worse_order = order;
63  delta_duration = delta;
64  }
65  }
66  return worse_order;
67 }
68 
69 
70 Order
72  invariant();
73  pgassert(!empty());
74  return problem->order_of(m_path[1]);
75 }
76 
77 
79  size_t id,
80  const Vehicle_node &starting_site,
81  const Vehicle_node &ending_site,
82  double max_capacity,
83  const Pgr_pickDeliver *p_problem) :
84  Vehicle(id, starting_site, ending_site, max_capacity),
85  cost((std::numeric_limits<double>::max)()),
86  problem(p_problem) {
87  orders_in_vehicle.clear();
88 
89  invariant();
90  }
91 
92 
93 
94 bool
96  return !(orders_in_vehicle.find(order.id()) == orders_in_vehicle.end());
97 }
98 
99 
100 void
102  invariant();
103  pgassert(!has_order(order));
104 
105  auto pick_pos(position_limits(order.pickup()));
106  auto deliver_pos(position_limits(order.delivery()));
107 #ifndef NDEBUG
108  std::ostringstream err_log;
109  err_log << "\n\tpickup limits (low, high) = ("
110  << pick_pos.first << ", "
111  << pick_pos.second << ") "
112  << "\n\tdeliver limits (low, high) = ("
113  << deliver_pos.first << ", "
114  << deliver_pos.second << ") "
115  << "\noriginal" << tau();
116 #endif
117 
118  if (pick_pos.second < pick_pos.first) {
119  /* pickup generates twv evrywhere,
120  * so put the order as last */
121  push_back(order);
122  return;
123  }
124 
125  if (deliver_pos.second < deliver_pos.first) {
126  /* delivery generates twv evrywhere,
127  * so put the order as last */
128  push_back(order);
129  return;
130  }
131  /*
132  * Because delivery positions were estimated without
133  * the pickup:
134  * - increase the upper limit position estimation
135  */
136  ++deliver_pos.second;
137 
138 
139  auto d_pos_backup(deliver_pos);
140  auto best_pick_pos = m_path.size();
141  auto best_deliver_pos = m_path.size() + 1;
142  auto current_duration(duration());
143  auto min_delta_duration = (std::numeric_limits<double>::max)();
144  auto found(false);
145  pgassertwm(!has_order(order), err_log.str());
146  while (pick_pos.first <= pick_pos.second) {
147 #ifndef NDEBUG
148  err_log << "\n\tpickup cycle limits (low, high) = ("
149  << pick_pos.first << ", "
150  << pick_pos.second << ") ";
151 #endif
152  Vehicle::insert(pick_pos.first, order.pickup());
153 #ifndef NDEBUG
154  err_log << "\npickup inserted: " << tau();
155 #endif
156 
157  while (deliver_pos.first <= deliver_pos.second) {
158  Vehicle::insert(deliver_pos.first, order.delivery());
159  orders_in_vehicle.insert(order.id());
160  pgassertwm(has_order(order), err_log.str());
161 #ifndef NDEBUG
162  err_log << "\ndelivery inserted: " << tau();
163 #endif
164  if (is_feasable()) {
166  auto delta_duration = duration()-current_duration;
167  if (delta_duration < min_delta_duration) {
168 #ifndef NDEBUG
169  err_log << "\nsuccess" << tau();
170 #endif
171  min_delta_duration = delta_duration;
172  best_pick_pos = pick_pos.first;
173  best_deliver_pos = deliver_pos.first;
174  found = true;
175  }
176  }
177  Vehicle::erase(deliver_pos.first);
178 #ifndef NDEBUG
179  err_log << "\ndelivery erased: " << tau();
180 #endif
181  ++deliver_pos.first;
182  }
183  Vehicle::erase(pick_pos.first);
184 #ifndef NDEBUG
185  err_log << "\npickup erased: " << tau();
186 #endif
187  orders_in_vehicle.erase(order.id());
188  pgassertwm(!has_order(order), err_log.str());
189 
190  deliver_pos = d_pos_backup;
191 #ifndef NDEBUG
192  err_log << "\n\trestoring deliver limits (low, high) = ("
193  << deliver_pos.first << ", "
194  << deliver_pos.second << ") ";
195 #endif
196  ++pick_pos.first;
197  }
198  pgassertwm(!has_order(order), err_log.str());
199  if (!found) {
200  /* order causes twv
201  * so put the order as last */
202  push_back(order);
203  return;
204  }
205  Vehicle::insert(best_pick_pos, order.pickup());
206  Vehicle::insert(best_deliver_pos, order.delivery());
207 
208  orders_in_vehicle.insert(order.id());
209  pgassertwm(is_feasable(), err_log.str());
210  pgassertwm(has_order(order), err_log.str());
211  pgassertwm(!has_cv(), err_log.str());
212  invariant();
213 }
214 
215 void
217  invariant();
218  pgassert(!has_order(order));
219 
220  orders_in_vehicle.insert(order.id());
221  m_path.insert(m_path.end() - 1, order.pickup());
222  m_path.insert(m_path.end() - 1, order.delivery());
223  evaluate(m_path.size() - 3);
224 
225  pgassert(has_order(order));
226  pgassert(!has_cv());
227  invariant();
228 }
229 
230 void
232  invariant();
233  pgassert(!has_order(order));
234 
235  orders_in_vehicle.insert(order.id());
236  m_path.insert(m_path.begin() + 1, order.delivery());
237  m_path.insert(m_path.begin() + 1, order.pickup());
238  evaluate(1);
239 
240  pgassert(has_order(order));
241  pgassert(!has_cv());
242  invariant();
243 }
244 
245 
246 void
248  invariant();
249  pgassert(has_order(order));
250 
251 
252  Vehicle::erase(order.pickup());
253  Vehicle::erase(order.delivery());
254  orders_in_vehicle.erase(orders_in_vehicle.find(order.id()));
255 
256  invariant();
257  pgassert(!has_order(order));
258 }
259 
260 
261 
262 size_t
264  invariant();
265  pgassert(!empty());
266 
267  auto pick_itr = m_path.rbegin();
268  while (pick_itr != m_path.rend() && !pick_itr->is_pickup()) {
269  ++pick_itr;
270  }
271 
272  pgassert(pick_itr->is_pickup());
273 
274  ID deleted_pick_id = pick_itr->id();
275 
276 
277  auto delivery_id = problem->node(deleted_pick_id).Did();
278 
279  m_path.erase((pick_itr + 1).base());
280 
281  auto delivery_itr = m_path.rbegin();
282  while (delivery_itr != m_path.rend()
283  && !(delivery_itr->id() ==delivery_id)) {
284  ++delivery_itr;
285  }
286 
287  pgassert(delivery_itr->is_delivery());
288  pgassert(delivery_itr->Pid() == deleted_pick_id);
289 
290  m_path.erase((delivery_itr + 1).base());
291 
292 
293  /* figure out from where the evaluation is needed */
294  evaluate(1);
295 
296  ID deleted_order_id(
297  problem->order_of(problem->node(deleted_pick_id)).id());
298 
299  orders_in_vehicle.erase(orders_in_vehicle.find(deleted_order_id));
300 
301  invariant();
302  return deleted_order_id;
303 }
304 
305 
306 
307 size_t
309  invariant();
310  pgassert(!empty());
311 
312  auto pick_itr = m_path.begin();
313  while (pick_itr != m_path.end() && !pick_itr->is_pickup()) {
314  ++pick_itr;
315  }
316 
317  pgassert(pick_itr->is_pickup());
318 
319  ID deleted_pick_id = pick_itr->id();
320 
321 
322  auto delivery_id = problem->node(deleted_pick_id).Did();
323 
324  m_path.erase(pick_itr);
325 
326  auto delivery_itr = m_path.begin();
327  while (delivery_itr != m_path.end()
328  && !(delivery_itr->id() == delivery_id)) {
329  ++delivery_itr;
330  }
331 
332  pgassert(delivery_itr->is_delivery());
333  pgassert(delivery_itr->Pid() == deleted_pick_id);
334 
335  m_path.erase(delivery_itr);
336 
337  evaluate(1);
338 
339  ID deleted_order_id(
340  problem->order_of(problem->node(deleted_pick_id)).id());
341 
342  orders_in_vehicle.erase(orders_in_vehicle.find(deleted_order_id));
343 
344  invariant();
345  return deleted_order_id;
346 }
347 
348 
349 } // namespace vrp
350 } // namespace pgrouting
351 
352 
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:730
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