PGROUTING  2.6
fleet.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: solution.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/fleet.h"
27 
28 #include <vector>
29 #include <memory>
30 #include <utility>
31 #include <limits>
32 
33 #include "vrp/dnode.h"
34 #include "vrp/pgr_pickDeliver.h"
35 
36 namespace pgrouting {
37 namespace vrp {
38 
39 
40 Fleet::Fleet(const Fleet &fleet) :
41  PD_problem(),
42  m_trucks(fleet.m_trucks),
43  used(fleet.used),
44  un_used(fleet.un_used)
45  {}
46 
48  const std::vector<Vehicle_t> &vehicles, double factor) :
49  PD_problem(),
50  used(),
51  un_used() {
52  build_fleet(vehicles, factor);
53  Identifiers<size_t> unused(m_trucks.size());
54  un_used = unused;
55  }
56 
57 
60  ENTERING();
61  auto idx = un_used.front();
62  msg.log << "Available vehicles: " << un_used << "\n";
63  msg.log << "NOT Available vehicles: " << used << "\n";
64  msg.log << "getting idx" << idx << "\n";
65  pgassertwm(idx < m_trucks.size(), msg.log.str());
66  used += idx;
67  if (un_used.size() > 1) un_used -= idx;
68  EXITING();
69  return m_trucks[idx];
70 }
71 
72 void
74  used -= id;
75  un_used += id;
76 }
77 
79 Fleet::get_truck(size_t order) {
80  msg.log << "Available vehicles: " << un_used << "\n";
81  msg.log << "NOT Available vehicles: " << used << "\n";
82  auto idx = un_used.front();
83 
84  for (const auto i : un_used) {
85  if (m_trucks[i].feasable_orders().has(order)) {
86  idx = i;
87  msg.log << "getting idx" << idx << "\n";
88  used += idx;
89  if (un_used.size() > 1) un_used -= idx;
90  return m_trucks[idx];
91  }
92  }
93 
94  /*
95  * using phoney truck
96  */
97  pgassert(false);
98  return m_trucks.back();
99 
100  for (auto truck : m_trucks) {
101  if (truck.feasable_orders().has(order)) {
102  idx = truck.idx();
103  msg.log << "idx" << idx << "size" << m_trucks.size();
104  pgassertwm(idx < m_trucks.size(), msg.get_log());
105  used += idx;
106  if (un_used.size() > 1) un_used -= idx;
107  break;
108  }
109  }
110  return m_trucks[idx];
111 }
112 
113 
115 Fleet::get_truck(const Order order) {
116  auto id = m_trucks.front().idx();
117  for (auto truck : m_trucks) {
118  if (truck.feasable_orders().has(order.idx())) {
119  id = truck.idx();
120  msg.log << "id" << id
121  << "size" << m_trucks.size();
122  pgassertwm(id < m_trucks.size(), msg.get_log());
123  used += id;
124  if (un_used.size() > 1) un_used -= id;
125  break;
126  }
127  }
128  return m_trucks[id];
129 }
130 
131 
132 void
134  Vehicle_t vehicle,
135  double factor,
136  std::unique_ptr<Base_node> b_start,
137  const Vehicle_node &starting_site,
138  std::unique_ptr<Base_node> b_end,
139  const Vehicle_node &ending_site) {
140  pgassert(starting_site.is_start() && ending_site.is_end());
141  pgassert(starting_site.opens() <= starting_site.closes());
142  pgassert(ending_site.opens() <= ending_site.closes());
143 
144  problem->add_base_node(std::move(b_start));
145  problem->add_base_node(std::move(b_end));
146  problem->add_node(starting_site);
147  problem->add_node(ending_site);
148 
149  for (int i = 0; i < vehicle.cant_v; ++i) {
150  m_trucks.push_back(Vehicle_pickDeliver(
151  m_trucks.size(),
152  vehicle.id,
153  starting_site,
154  ending_site,
155  vehicle.capacity,
156  vehicle.speed,
157  factor));
158  msg.log << "inserting vehicle: " << m_trucks.back().tau() << "\n";
159  pgassert((m_trucks.back().idx() + 1) == m_trucks.size());
160  pgassert(m_trucks.back().is_ok());
161  }
162 }
163 
174 bool
176  std::vector<Vehicle_t> vehicles,
177  double factor) {
178  /*
179  * creating a phoney truck with max capacity and max window
180  * with the start & end points of the first vehicle given
181  */
182  vehicles.push_back({
183  /*
184  * id, capacity
185  */
186  -1,
187  std::numeric_limits<double>::infinity(),
188 
189  vehicles[0].speed,
190  vehicles[0].start_x,
191  vehicles[0].start_y,
192  vehicles[0].start_node_id,
193 
194  /*
195  * cant_v, start_open_t, start_close_t, start_service_t
196  */
197  1,
198  0,
199  std::numeric_limits<double>::infinity(),
200  0,
201 
202  vehicles[0].end_x,
203  vehicles[0].end_y,
204  vehicles[0].end_node_id,
205  /*
206  * end_open_t, end_close_t, end_service_t
207  */
208  0,
209  std::numeric_limits<double>::infinity(),
210  0});
211 
212 
213  for (auto vehicle : vehicles) {
214  if (vehicle.cant_v < 0) {
215  msg.error << "Illegal number of vehicles found vehicle";
216  msg.log << vehicle.cant_v << "< 0 on vehicle " << vehicle.id;
217  return false;
218  }
219 
220  if (problem->m_cost_matrix.empty()) {
221  /*
222  * Euclidean version
223  */
224  auto b_start = create_b_start<Node>(vehicle, problem->node_id());
225  auto starting_site = Vehicle_node(
226  {problem->node_id()++, vehicle, Tw_node::NodeType::kStart});
227 
228  auto b_end = create_b_end<Node>(vehicle, problem->node_id());
229  auto ending_site = Vehicle_node(
230  {problem->node_id()++, vehicle, Tw_node::NodeType::kEnd});
231 
232  if (!(starting_site.is_start() && ending_site.is_end()
233  && starting_site.opens() <= starting_site.closes()
234  && ending_site.opens() <= ending_site.closes())) {
235  msg.clear();
236  msg.error << "Illegal values found on vehicle";
237  msg.log << "On vehicle " << vehicle.id
238  << " a condition is not met:\n"
239  << "starting_site.is_start: "
240  << (starting_site.is_start()? "YES" : "NO") << "\n"
241  << "ending_site.is_end: "
242  << (ending_site.is_end()? "YES" : "NO") << "\n"
243  << "verify that:\n"
244  << "- start_open <= start_close: "
245  << starting_site.opens()
246  << "<" << starting_site.closes() << "\n"
247  << "- end_open <= end_close: "
248  << ending_site.opens()
249  << "<" << ending_site.closes() << "\n"
250  << "- capacity > 0\n";
251  pgassert(!msg.get_error().empty());
252  return false;
253  }
254  pgassert(starting_site.is_start());
255  pgassert(ending_site.is_end());
256 
257  pgassert(starting_site.opens() <= starting_site.closes());
258  pgassert(ending_site.opens() <= ending_site.closes());
259  pgassertwm(
260  starting_site.is_start() && ending_site.is_end(),
261  msg.get_error().c_str());
262  add_vehicle(vehicle, factor,
263  std::move(b_start), starting_site,
264  std::move(b_end), ending_site);
265  } else {
266  /*
267  * Matrix version
268  */
269  auto b_start = create_b_start<Dnode>(vehicle, problem->node_id());
270  auto starting_site = Vehicle_node(
271  {problem->node_id()++, vehicle, Tw_node::NodeType::kStart});
272 
273  auto b_end = create_b_end<Dnode>(vehicle, problem->node_id());
274  auto ending_site = Vehicle_node(
275  {problem->node_id()++, vehicle, Tw_node::NodeType::kEnd});
276 
277  if (!(starting_site.is_start() && ending_site.is_end()
278  && starting_site.opens() <= starting_site.closes()
279  && ending_site.opens() <= ending_site.closes())) {
280  msg.clear();
281  msg.error << "Illegal values found on vehicle";
282  msg.log << "On vehicle " << vehicle.id
283  << " a condition is not met, verify that:\n"
284  << "starting_site.is_start()"
285  << starting_site.is_start() << "\n"
286  << "ending_site.is_start()"
287  << ending_site.is_end() << "\n"
288  << "- start_open <= start_close\n"
289  << starting_site.opens() << "<"
290  << starting_site.closes() << "\n"
291  << "- end_open <= end_close\n"
292  << ending_site.opens() << "<"
293  << ending_site.closes() << "\n"
294  << "- capacity > 0\n";
295  pgassert(!msg.get_error().empty());
296  return false;
297  }
298  pgassert(starting_site.is_start());
299  pgassert(ending_site.is_end());
300 
301  pgassert(starting_site.opens() <= starting_site.closes());
302  pgassert(ending_site.opens() <= ending_site.closes());
303  pgassert(starting_site.is_start() && ending_site.is_end());
304  add_vehicle(vehicle, factor,
305  std::move(b_start), starting_site,
306  std::move(b_end), ending_site);
307  }
308  }
309  Identifiers<size_t> unused(m_trucks.size());
310  un_used = unused;
311  return true;
312 }
313 
314 
315 bool
317  ENTERING();
318  if (!msg.get_error().empty()) return false;
319  for (auto truck : m_trucks) {
320  if (!truck.is_ok()) {
321  msg.error << "Illegal values found on vehicle";
322  msg.log << "On vehicle " << truck.id()
323  << " a condition is not met, verify that:\n"
324  << "- start_open <= start_close\n"
325  << "- end_open <= end_close\n"
326  << "- capacity > 0\n";
327  return false;
328  }
329 
330  if (!(truck.start_site().is_start()
331  && truck.end_site().is_end())) {
332  pgassertwm(false, "should never pass through here");
333  msg.error << "Illegal values found on vehicle";
334  return false;
335  }
336  if (!truck.is_feasable()) {
337  msg.error << "Truck is not feasible";
338  return false;
339  }
340  }
341  EXITING();
342  return true;
343 }
344 
350 bool
351 Fleet::is_order_ok(const Order &order) const {
352  for (const auto truck : m_trucks) {
353  if (!order.is_valid(truck.speed())) continue;
354  if (truck.is_order_feasable(order)) {
355  return true;
356  }
357  }
358  return false;
359 }
360 
362 Fleet::operator[](size_t i) {
363  pgassert(i < m_trucks.size());
364  return m_trucks[i];
365 }
366 
367 void
369  for (auto &truck : m_trucks) {
370  truck.set_compatibles(orders);
371  }
372 }
373 
374 /*
375  * FRIENDS
376  */
377 
378 std::ostream&
379 operator << (std::ostream &log, const Fleet &f) {
380  log << "fleet\n";
381  for (const auto v : f.m_trucks) {
382  log << v;
383  }
384  log << "end fleet\n";
385 
386  return log;
387 }
388 
389 
390 } // namespace vrp
391 } // namespace pgrouting
void add_base_node(std::unique_ptr< Base_node > node_ptr)
double capacity
Definition: vehicle_t.h:62
void add_node(const Vehicle_node &node)
std::vector< Vehicle_pickDeliver > m_trucks
Definition: fleet.h:50
bool is_end() const
is_end
Definition: tw_node.cpp:177
static Pgr_pickDeliver * problem
Definition: pd_problem.h:51
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:104
bool is_valid(double speed) const
validate a pickup/delivery order
Definition: order.cpp:94
bool build_fleet(std::vector< Vehicle_t > vehicles, double factor)
build the fleet
Definition: fleet.cpp:175
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
Vehicle_pickDeliver get_truck()
Definition: fleet.cpp:59
std::string get_log() const
get_log
Extend Tw_node to evaluate the vehicle at node level.
Definition: vehicle_node.h:48
double opens() const
Returns the opening time.
Definition: tw_node.h:76
void add_vehicle(Vehicle_t, double factor, std::unique_ptr< Base_node >, const Vehicle_node &, std::unique_ptr< Base_node >, const Vehicle_node &)
Definition: fleet.cpp:133
int64_t cant_v
Definition: vehicle_t.h:69
std::string get_error() const
get_error
#define EXITING()
Definition: pgr_messages.h:119
friend std::ostream & operator<<(std::ostream &log, const Fleet &v)
Definition: fleet.cpp:379
std::ostringstream error
Stores the error information.
Definition: pgr_messages.h:106
#define ENTERING()
Definition: pgr_messages.h:118
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
pgrouting::tsp::Dmatrix m_cost_matrix
double empty() const
Definition: Dmatrix.h:116
void release_truck(size_t id)
Definition: fleet.cpp:73
bool is_start() const
@ {
Definition: tw_node.cpp:132
bool is_order_ok(const Order &order) const
Given an order, Cycle trhugh all the trucks to verify if the order can be served by at least one truc...
Definition: fleet.cpp:351
bool is_fleet_ok() const
Definition: fleet.cpp:316
double speed
Definition: vehicle_t.h:63
double closes() const
Returns the closing time.
Definition: tw_node.h:79
size_t size() const
Definition: identifiers.hpp:77
Vehicle_pickDeliver & operator[](size_t i)
Definition: fleet.cpp:362
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
static Pgr_messages msg
Definition: pd_problem.h:48
Identifiers< size_t > used
Definition: fleet.h:95
T front() const
Definition: identifiers.hpp:79
Identifiers< size_t > un_used
Definition: fleet.h:96
int64_t id
Definition: vehicle_t.h:61
size_t idx() const
Definition: identifier.cpp:37
void set_compatibles(const PD_Orders &orders)
Definition: fleet.cpp:368