PGROUTING  2.5
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 << " a condition is not met, verify that:\n"
238  << "- start_open <= start_close\n"
239  << "- end_open <= end_close\n"
240  << "- capacity > 0\n";
241  pgassert(!msg.get_error().empty());
242  return false;
243  }
244 
245  pgassert(starting_site.opens() <= starting_site.closes());
246  pgassert(ending_site.opens() <= ending_site.closes());
247  pgassertwm(starting_site.is_start() && ending_site.is_end(), msg.get_error().c_str());
248  add_vehicle(vehicle, factor,
249  std::move(b_start), starting_site,
250  std::move(b_end), ending_site);
251  } else {
252  /*
253  * Matrix version
254  */
255  auto b_start = create_b_start<Dnode>(vehicle, problem->node_id());
256  auto starting_site = Vehicle_node(
257  {problem->node_id()++, vehicle, Tw_node::NodeType::kStart});
258 
259  auto b_end = create_b_end<Dnode>(vehicle, problem->node_id());
260  auto ending_site = Vehicle_node(
261  {problem->node_id()++, vehicle, Tw_node::NodeType::kEnd});
262 
263  if (!(starting_site.is_start() && ending_site.is_end()
264  && starting_site.opens() <= starting_site.closes()
265  && ending_site.opens() <= ending_site.closes())) {
266  msg.clear();
267  msg.error << "Illegal values found on vehicle";
268  msg.log << "On vehicle " << vehicle.id << " a condition is not met, verify that:\n"
269  << "- start_open <= start_close\n"
270  << "- end_open <= end_close\n"
271  << "- capacity > 0\n";
272  pgassert(!msg.get_error().empty());
273  return false;
274  }
275 
276  pgassert(starting_site.opens() <= starting_site.closes());
277  pgassert(ending_site.opens() <= ending_site.closes());
278  pgassert(starting_site.is_start() && ending_site.is_end());
279  add_vehicle(vehicle, factor,
280  std::move(b_start), starting_site,
281  std::move(b_end), ending_site);
282  }
283  }
284  Identifiers<size_t> unused(m_trucks.size());
285  un_used = unused;
286  return true;
287 }
288 
289 
290 bool
292  ENTERING();
293  if (!msg.get_error().empty()) return false;
294  for (auto truck : m_trucks) {
295  if (!truck.is_ok()) {
296  msg.error << "Illegal values found on vehicle";
297  msg.log << "On vehicle " << truck.id() << " a condition is not met, verify that:\n"
298  << "- start_open <= start_close\n"
299  << "- end_open <= end_close\n"
300  << "- capacity > 0\n";
301  return false;
302  }
303 
304  if (!(truck.start_site().is_start()
305  && truck.end_site().is_end())) {
306  pgassertwm(false, "should never pass through here");
307  msg.error << "Illegal values found on vehicle";
308  return false;
309  }
310  if (!truck.is_feasable()) {
311  msg.error << "Truck is not feasible";
312  return false;
313  }
314  }
315  EXITING();
316  return true;
317 }
318 
324 bool
325 Fleet::is_order_ok(const Order &order) const {
326  for (const auto truck : m_trucks) {
327  if (!order.is_valid(truck.speed())) continue;
328  if (truck.is_order_feasable(order)) {
329  return true;
330  }
331  }
332  return false;
333 }
334 
336 Fleet::operator[](size_t i) {
337  pgassert(i < m_trucks.size());
338  return m_trucks[i];
339 }
340 
341 void
343  for (auto &truck : m_trucks) {
344  truck.set_compatibles(orders);
345  }
346 }
347 
348 /*
349  * FRIENDS
350  */
351 
352 std::ostream&
353 operator << (std::ostream &log, const Fleet &f) {
354  log << "fleet\n";
355  for (const auto v : f.m_trucks) {
356  log << v;
357  }
358  log << "end fleet\n";
359 
360  return log;
361 }
362 
363 
364 } // namespace vrp
365 } // namespace pgrouting
void add_base_node(std::unique_ptr< Base_node > node_ptr)
double capacity
Definition: vehicle_t.h:66
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:182
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:73
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:353
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:325
bool is_fleet_ok() const
Definition: fleet.cpp:291
double speed
Definition: vehicle_t.h:67
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:336
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:65
size_t idx() const
Definition: identifier.cpp:37
void set_compatibles(const PD_Orders &orders)
Definition: fleet.cpp:342