PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
pgr_pickDeliver.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: pgr_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 "./pgr_pickDeliver.h"
27 
28 #include <sstream>
29 #include <string>
30 #include <vector>
31 #include <algorithm>
32 
33 #include "./../../common/src/pgr_types.h"
34 #include "./../../common/src/pgr_assert.h"
35 
36 #include "./vehicle_node.h"
37 #include "./vehicle_pickDeliver.h"
38 #include "./order.h"
39 #include "./solution.h"
40 #include "./initial_solution.h"
41 #include "./optimize.h"
42 
43 namespace pgrouting {
44 namespace vrp {
45 
46 
47 
48 Solution
49 Pgr_pickDeliver::solve(const Solution init_solution) {
50  Optimize solution(0, init_solution);
51  solution.decrease_truck();
52  solution.move_duration_based();
53  solution.move_wait_time_based();
54  solution.inter_swap();
55  return solution.best_solution;
56 }
57 
58 void
60 #if 0
61  solutions.push_back(Initial_solution(0, this));
62  solutions.push_back(Initial_solution(1, this));
63 
64  solutions.push_back(solve(solutions.back()));
65 #endif
66 
67 #if 0
68  solutions.push_back(Initial_solution(2, this));
69  solutions.push_back(solve(solutions.back()));
70  solutions.push_back(Initial_solution(3, this));
71  solutions.push_back(solve(solutions.back()));
72 #endif
73  solutions.push_back(Initial_solution(4, this));
74  solutions.push_back(solve(solutions.back()));
75 #if 0
76  solutions.push_back(Initial_solution(5, this));
77  solutions.push_back(solve(solutions.back()));
78  solutions.push_back(Initial_solution(6, this));
79  solutions.push_back(solve(solutions.back()));
80 #endif
81 
82 #if 1
83  /*
84  * Sorting solutions: the best is at the back
85  */
86  std::sort(solutions.begin(), solutions.end(), []
87  (const Solution &lhs, const Solution &rhs) -> bool {
88  return rhs < lhs;
89  });
90 #endif
91 }
92 
93 
94 
95 void
97  std::vector< General_vehicle_orders_t > &result) const {
98  solutions.back().get_postgres_result(result);
99 
100  General_vehicle_orders_t aggregates = {
101  /*
102  * Vehicle id = -1 indicates its an aggregate row
103  *
104  * (twv, cv, fleet, wait, duration)
105  */
106  -1,
107  solutions.back().twvTot(),
108  solutions.back().cvTot(),
109  solutions.back().total_travel_time(),
110  0, // not accounting arrival_travel_time
111  solutions.back().wait_time(),
112  solutions.back().total_service_time(),
113  solutions.back().duration(),
114  };
115  result.push_back(aggregates);
116 
117 
118  for (const auto sol : solutions) {
119  log << sol.tau();
120  }
121 }
122 
123 
124 
125 /***** Constructor *******/
126 
128  const Customer_t *customers_data, size_t total_customers,
129  int p_max_vehicles,
130  double p_capacity,
131  double p_speed,
132  size_t p_max_cycles,
133  std::string &error) :
134  /* Set the depot to be the first ddata found */
135  max_capacity(p_capacity),
136  m_speed(p_speed),
137  m_max_cycles(p_max_cycles),
138  max_vehicles(p_max_vehicles),
139  m_starting_site({0, customers_data[0], Tw_node::NodeType::kStart, this}),
140  m_ending_site({0, customers_data[0], Tw_node::NodeType::kEnd, this}),
141  m_original_data(customers_data, customers_data + total_customers) {
142  pgassert(m_speed > 0);
143  pgassert(m_max_cycles > 0);
144  pgassert(max_vehicles > 0);
145  std::ostringstream tmplog;
146  error = "";
147 
148  log << "\n *** Constructor of problem ***\n";
149 
150  /* sort data by id */
151  std::sort(m_original_data.begin(), m_original_data.end(),
152  [] (const Customer_t &c1, const Customer_t &c2)
153  {return c1.id < c2.id;});
154 
155  /*
156  * starting node:
157  * id must be 0
158  */
159  if (m_original_data[0].id != 0) {
160  error = "Depot node not found";
161  return;
162  }
163 
164  m_starting_site = Vehicle_node(
165  {0, customers_data[0], Tw_node::NodeType::kStart, this});
167  {1, customers_data[0], Tw_node::NodeType::kEnd, this});
168  if (!m_starting_site.is_start()) {
169  log << "DEPOT" << m_starting_site;
170  error = "Illegal values found on the starting site";
171  return;
172  }
173  pgassert(m_starting_site.is_start());
174  pgassert(m_ending_site.is_end());
175 
176  m_nodes.push_back(m_starting_site);
177  m_nodes.push_back(m_ending_site);
178 
179 
180  ID order_id(0);
181  ID node_id(2);
182  for (const auto p : m_original_data) {
183  /*
184  * skip Starting site
185  */
186  if (p.id == 0) continue;
187 
188  /*
189  * SAMPLE CORRECT INFORMATION
190  *
191  * The Pickup is 11 (pindex == 0)
192  * The Deliver is 1 (dindex == 0)
193  *
194  * id | x | y | demand | etime | Ltime | Stime | pindex | dindex
195  * 1 | 45 | 68 | -10 | 912 | 967 | 90 | 11 | 0
196  * 11 | 35 | 69 | 10 | 448 | 505 | 90 | 0 | 1
197  *
198  */
199 
200  /*
201  * skip deliveries
202  */
203  if (p.Dindex == 0) continue;
204 
205  /*
206  * pickup is found
207  */
208  Tw_node pickup({node_id++, p, Tw_node::NodeType::kPickup, this});
209  if (!pickup.is_pickup()) {
210  log << "PICKUP" << pickup;
211  tmplog << "Illegal values found on Pickup " << p.id;
212  error = tmplog.str();
213  return;
214  }
215  pgassert(pickup.is_pickup());
216 
217 
218  /*
219  * look for corresponding the delivery of the pickup
220  */
221  auto deliver_ptr = std::lower_bound(
222  m_original_data.begin(),
223  m_original_data.end(),
224  p,
225  [] (const Customer_t &delivery, const Customer_t &pick)
226  -> bool
227  {return delivery.id < pick.Dindex;});
228 
229  if (deliver_ptr == m_original_data.end()
230  || deliver_ptr->id != p.Dindex) {
231  tmplog << "For Pickup "
232  << p.id
233  << " the corresponding Delivery was not found";
234  error = tmplog.str();
235  return;
236  }
237 
238 
239  /*
240  * delivery is found
241  */
242  Tw_node delivery(
243  node_id++,
244  (*deliver_ptr),
245  Tw_node::NodeType::kDelivery,
246  this);
247  if (!delivery.is_delivery()) {
248  log << "DELIVERY" << delivery;
249  tmplog << "Illegal values found on Delivery "
250  << deliver_ptr->id;
251  error = tmplog.str();
252  return;
253  }
254  pgassert(delivery.is_delivery());
255 
256 
257  /*
258  * add into an order & check the order
259  */
260  pickup.set_Did(delivery.id());
261  delivery.set_Pid(pickup.id());
262  m_nodes.push_back(pickup);
263  m_nodes.push_back(delivery);
264 
265  m_orders.push_back(
266  Order(order_id, node(node_id - 2),
267  node(node_id - 1),
268  this));
269  pgassert(m_orders.back().pickup().is_pickup());
270  pgassert(m_orders.back().delivery().is_delivery());
271  pgassert(static_cast<Tw_node> (m_orders.back().pickup()) == pickup);
272 
273  /*
274  * check the (S, P, D, E) order
275  */
276  {
277  Vehicle_pickDeliver truck(
278  order_id,
279  m_starting_site,
280  m_ending_site,
281  max_capacity,
282  this);
283  truck.push_back(m_orders.back());
284 
285  if (!truck.is_feasable()) {
286  log << truck << "\n";
287  tmplog << "The (pickup, delivery) = ("
288  << m_orders.back().pickup().original_id() << ", "
289  << m_orders.back().delivery().original_id()
290  << ") is not feasible";
291  error = tmplog.str();
292  return;
293  }
294  pgassert(truck.is_feasable());
295  } // check
296 
297  ++order_id;
298  } // for
299 
300  /*
301  * double check we found all orders
302  */
303  if (((m_orders.size() * 2 + 1) - m_original_data.size()) != 0) {
304  error = "A pickup was not found";
305  return;
306  }
307 
308  for (auto &o : m_orders) {
309  o.setCompatibles();
310  }
311 
312  for (auto o : m_orders) {
313  log << o;
314  }
315  } // constructor
316 
317 
318 const Order
320  pgassert(node.is_pickup() || node.is_delivery());
321  if (node.is_pickup()) {
322  for (const auto o : m_orders) {
323  if (o.pickup().id() == node.id()) {
324  return o;
325  }
326  }
327  }
328  pgassert(node.is_delivery());
329 
330  for (const auto o : m_orders) {
331  if (o.delivery().id() == node.id()) {
332  return o;
333  }
334  }
335 #ifndef NDEBUG
336  std::ostringstream err_log;
337  err_log << "Order of" << node << " not found";
338 #endif
339  pgassertwm(false, err_log.str());
340  return m_orders[0];
341 }
342 
343 
344 const Vehicle_node&
346  pgassert(id < m_nodes.size());
347  pgassert(id == m_nodes[id].id());
348  return m_nodes[id];
349 }
350 
351 
352 } // namespace vrp
353 } // namespace pgrouting
void push_back(const Order &order)
puts an order at the end of the truck
Pgr_pickDeliver(const Customer_t *c1, size_t total_customers, int VehicleLength, double capacity, double speed, size_t max_cycles, std::string &error)
bool is_end() const
is_end
Definition: tw_node.cpp:172
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
Extend Tw_node to evaluate the vehicle at node level.
Definition: vehicle_node.h:46
int64_t id
Definition: pgr_types.h:228
std::vector< Solution > solutions
PGDLLEXPORT Datum vrp(PG_FUNCTION_ARGS)
Definition: VRP.c:732
void get_postgres_result(std::vector< General_vehicle_orders_t > &result) const
std::vector< Order > m_orders
std::vector< Vehicle_node > m_nodes
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
m_ending_site({0, customers_data[0], Tw_node::NodeType::kEnd, this})
const Order order_of(const Vehicle_node &node) const
bool is_pickup() const
is_pickup
Definition: tw_node.cpp:132
void set_Pid(size_t id)
Definition: tw_node.h:62
bool is_delivery() const
is_delivery
Definition: tw_node.cpp:142
Extends the Node class to create a Node with time window attributes.
Definition: tw_node.h:50
const Vehicle_node & node(ID id) const
m_original_data(customers_data, customers_data+total_customers)
size_t id() const
@ {
Definition: node.h:51
bool is_feasable() const
Definition: vehicle.h:240