PGROUTING  3.2
fleet.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: solution.cpp
4 
5 Copyright (c) 2015 pgRouting developers
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 Pgr_pickDeliver* Fleet::problem;
41 
45 Pgr_messages&
47  return problem->msg;
48 }
49 
50 Fleet::Fleet(const Fleet &fleet) :
51  m_trucks(fleet.m_trucks),
52  m_used(fleet.m_used),
53  m_un_used(fleet.m_un_used)
54  {}
55 
57  const std::vector<Vehicle_t> &vehicles, double factor) :
58  m_used(),
59  m_un_used() {
60  build_fleet(vehicles, factor);
61  Identifiers<size_t> unused(m_trucks.size());
62  m_un_used = unused;
63  }
64 
65 
68  ENTERING(msg());
69  auto idx = m_un_used.front();
70  msg().log << "Available vehicles: " << m_un_used << "\n";
71  msg().log << "NOT Available vehicles: " << m_used << "\n";
72  msg().log << "getting idx" << idx << "\n";
73  pgassertwm(idx < m_trucks.size(), msg().log.str());
74  m_used += idx;
75  if (m_un_used.size() > 1) m_un_used -= idx;
76  EXITING(msg());
77  return m_trucks[idx];
78 }
79 
80 
82 Fleet::get_truck(size_t order) {
83 #if 0
84  msg().log << "Available vehicles: " << m_un_used << "\n";
85  msg().log << "NOT Available vehicles: " << m_used << "\n";
86 #endif
87  auto idx = m_un_used.front();
88 
89  for (const auto &i : m_un_used) {
90  if (m_trucks[i].feasable_orders().has(order)) {
91  idx = i;
92  msg().log << "getting idx" << idx << "\n";
93  m_used += idx;
94  if (m_un_used.size() > 1) m_un_used -= idx;
95  return m_trucks[idx];
96  }
97  }
98 
99  /*
100  * using phoney truck
101  */
102  pgassert(false);
103  return m_trucks.back();
104 
105  for (auto truck : m_trucks) {
106  if (truck.feasable_orders().has(order)) {
107  idx = truck.idx();
108  msg().log << "idx" << idx << "size" << m_trucks.size();
109  pgassertwm(idx < m_trucks.size(), msg().get_log());
110  m_used += idx;
111  if (m_un_used.size() > 1) m_un_used -= idx;
112  break;
113  }
114  }
115  return m_trucks[idx];
116 }
117 
118 
119 
120 
121 void
123  Vehicle_t vehicle,
124  double factor,
125  const Vehicle_node &starting_site,
126  const Vehicle_node &ending_site) {
127  pgassert(starting_site.is_start() && ending_site.is_end());
128  pgassert(starting_site.opens() <= starting_site.closes());
129  pgassert(ending_site.opens() <= ending_site.closes());
130 
131 
132  for (int i = 0; i < vehicle.cant_v; ++i) {
133  m_trucks.push_back(Vehicle_pickDeliver(
134  m_trucks.size(),
135  vehicle.id,
136  starting_site,
137  ending_site,
138  vehicle.capacity,
139  vehicle.speed,
140  factor));
141 #if 0
142  msg().log << "inserting vehicle: " << m_trucks.back().tau() << "\n";
143 #endif
144  pgassert((m_trucks.back().idx() + 1) == m_trucks.size());
145  pgassert(m_trucks.back().is_ok());
146  }
147 }
148 
159 bool
161  std::vector<Vehicle_t> vehicles,
162  double factor) {
163  /*
164  * creating a phoney truck with max capacity and max window
165  * with the start & end points of the first vehicle given
166  */
167  vehicles.push_back({
168  /*
169  * id, capacity
170  */
171  -1,
172  std::numeric_limits<double>::infinity(),
173 
174  vehicles[0].speed,
175  vehicles[0].start_x,
176  vehicles[0].start_y,
177  vehicles[0].start_node_id,
178 
179  /*
180  * cant_v, start_open_t, start_close_t, start_service_t
181  */
182  1,
183  0,
184  std::numeric_limits<double>::infinity(),
185  0,
186 
187  vehicles[0].end_x,
188  vehicles[0].end_y,
189  vehicles[0].end_node_id,
190  /*
191  * end_open_t, end_close_t, end_service_t
192  */
193  0,
194  std::numeric_limits<double>::infinity(),
195  0});
196 
197 
198  for (auto vehicle : vehicles) {
199  if (vehicle.cant_v < 0) {
200  throw std::make_pair(std::string("Illegal number of vehicles found"), vehicle.cant_v);
201  }
202 
203  if (vehicle.capacity < 0) {
204  throw std::make_pair(std::string("Illegal value for capacity found"), vehicle.capacity);
205  }
206 
207  if (!problem->get_cost_matrix().empty()) {
208  if (!problem->get_cost_matrix().has_id(vehicle.start_node_id)) {
209  throw std::make_pair(std::string("Unable to find node on matrix"), vehicle.start_node_id);
210  }
211  if (!problem->get_cost_matrix().has_id(vehicle.end_node_id)) {
212  throw std::make_pair(std::string("Unable to find node on matrix"), vehicle.end_node_id);
213  }
214  }
215 
216  if (!(vehicle.start_open_t <= vehicle.start_close_t
217  && vehicle.end_open_t <= vehicle.end_close_t
218  && vehicle.start_open_t <= vehicle.end_close_t)) {
219  msg().error << "Illegal values found on vehicle";
220  msg().log << "On vehicle " << vehicle.id
221  << " a condition is not met, verify that:"
222  << "\nvehicle.start_open_t <= vehicle.start_close_t\t"
223  << vehicle.start_open_t << " <= " << vehicle.start_close_t
224  << "\nvehicle.end_open_t <= vehicle.end_close_t\t"
225  << vehicle.end_open_t << " <= " << vehicle.end_close_t
226  << "\nvehicle.start_open_t <= vehicle.end_close_t\t"
227  << vehicle.start_open_t << " <= " << vehicle.end_close_t;
228 
229  throw std::make_pair(msg().get_error(), msg().get_log());
230  }
231 
232  /*
233  * Matrix version
234  */
235  auto starting_site = Vehicle_node({problem->get_nodes().size(), vehicle, Tw_node::NodeType::kStart});
236  problem->add_node(starting_site);
237  auto ending_site = Vehicle_node({problem->get_nodes().size(), vehicle, Tw_node::NodeType::kEnd});
238  problem->add_node(ending_site);
239 
240  pgassert(starting_site.opens() <= starting_site.closes());
241  pgassert(ending_site.opens() <= ending_site.closes());
242  pgassert(starting_site.is_start() && ending_site.is_end());
243 
244  add_vehicle(vehicle, factor, starting_site, ending_site);
245  }
246  Identifiers<size_t> unused(m_trucks.size());
247  m_un_used = unused;
248  return true;
249 }
250 
251 
252 bool
254  ENTERING(msg());
255  if (!msg().get_error().empty()) return false;
256  for (auto truck : m_trucks) {
257  if (!truck.is_ok()) {
258  msg().error << "Illegal values found on vehicle";
259  msg().log << "On vehicle " << truck.id()
260  << " a condition is not met, verify that:\n"
261  << "- start_open <= start_close\n"
262  << "- end_open <= end_close\n"
263  << "- capacity > 0\n";
264  return false;
265  }
266 
267  if (!(truck.start_site().is_start()
268  && truck.end_site().is_end())) {
269  pgassertwm(false, "should never pass through here");
270  msg().error << "Illegal values found on vehicle";
271  return false;
272  }
273  if (!truck.is_feasable()) {
274  msg().error << "Truck is not feasible";
275  return false;
276  }
277  }
278  EXITING(msg());
279  return true;
280 }
281 
287 bool
288 Fleet::is_order_ok(const Order &order) const {
289  for (const auto &truck : m_trucks) {
290  if (!order.is_valid(truck.speed())) continue;
291  if (truck.is_order_feasable(order)) {
292  return true;
293  }
294  }
295  return false;
296 }
297 
298 Fleet&
299 Fleet::operator=(const Fleet &fleet) {
300  m_trucks = fleet.m_trucks;
301  m_used = fleet.m_used;
302  m_un_used = fleet.m_un_used;
303  return *this;
304 }
305 
307 Fleet::operator[](size_t i) {
308  pgassert(i < m_trucks.size());
309  return m_trucks[i];
310 }
311 
312 void
314  for (auto &truck : m_trucks) {
315  truck.set_compatibles(orders);
316  }
317 }
318 
319 /*
320  * FRIENDS
321  */
322 
323 std::ostream&
324 operator << (std::ostream &log, const Fleet &f) {
325  log << "fleet\n";
326  for (const auto &v : f.m_trucks) {
327  log << v;
328  }
329  log << "end fleet\n";
330 
331  return log;
332 }
333 
334 
335 } // namespace vrp
336 } // namespace pgrouting
pgrouting::vrp::Fleet::m_used
Identifiers< size_t > m_used
Definition: fleet.h:89
pgr_pickDeliver.h
pgrouting::vrp::Order::is_valid
bool is_valid(double speed) const
validate a pickup/delivery order
Definition: order.cpp:94
pgrouting::vrp::Fleet::operator=
Fleet & operator=(const Fleet &fleet)
Definition: fleet.cpp:299
Vehicle_t::capacity
double capacity
Definition: vehicle_t.h:42
pgrouting::vrp::Fleet
Definition: fleet.h:47
dnode.h
pgrouting::vrp::Fleet::problem
static Pgr_pickDeliver * problem
The problem.
Definition: fleet.h:110
EXITING
#define EXITING(x)
Definition: pgr_messages.h:94
pgrouting::vrp::Fleet::is_order_ok
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:288
pgrouting::vrp::Fleet::m_un_used
Identifiers< size_t > m_un_used
Definition: fleet.h:90
pgrouting::vrp::Tw_node::is_end
bool is_end() const
is_end
Definition: tw_node.cpp:126
pgrouting::vrp::Fleet::add_vehicle
void add_vehicle(Vehicle_t, double factor, const Vehicle_node &, const Vehicle_node &)
Definition: fleet.cpp:122
ENTERING
#define ENTERING(x)
Definition: pgr_messages.h:93
pgrouting::vrp::Vehicle_node
Extend Tw_node to evaluate the vehicle at node level.
Definition: vehicle_node.h:48
pgrouting::vrp::Pgr_pickDeliver::get_nodes
std::vector< Vehicle_node > get_nodes() const
Definition: pgr_pickDeliver.h:88
pgassertwm
#define pgassertwm(expr, msg)
Adds a message to the assertion.
Definition: pgr_assert.h:117
pgrouting::vrp::operator<<
std::ostream & operator<<(std::ostream &log, const Swap_info &d)
Definition: book_keeping.cpp:47
pgrouting::Pgr_messages::error
std::ostringstream error
Stores the error information.
Definition: pgr_messages.h:85
pgrouting::Pgr_messages::log
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:81
pgrouting::vrp::Pgr_pickDeliver::msg
Pgr_messages msg
message controller for all classes
Definition: pgr_pickDeliver.h:99
pgrouting::vrp::Fleet::is_fleet_ok
bool is_fleet_ok() const
Definition: fleet.cpp:253
Vehicle_t
Definition: vehicle_t.h:40
pgrouting::vrp::Fleet::msg
static Pgr_messages & msg()
the problem message
Definition: fleet.cpp:46
pgassert
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:94
pgrouting::vrp::Vehicle_pickDeliver
Definition: vehicle_pickDeliver.h:47
pgrouting::tsp::Dmatrix::has_id
bool has_id(int64_t id) const
original id -> true
Definition: Dmatrix.cpp:79
Identifiers::size
size_t size() const
Definition: identifiers.hpp:78
pgrouting::vrp::Pgr_pickDeliver::get_cost_matrix
pgrouting::tsp::Dmatrix get_cost_matrix() const
Definition: pgr_pickDeliver.h:92
Vehicle_t::cant_v
int64_t cant_v
Definition: vehicle_t.h:49
pgrouting::vrp::Tw_node::closes
double closes() const
Returns the closing time.
Definition: tw_node.h:79
pgrouting::vrp::Tw_node::is_start
bool is_start() const
@ {
Definition: tw_node.cpp:88
pgrouting::vrp::Fleet::m_trucks
std::vector< Vehicle_pickDeliver > m_trucks
Definition: fleet.h:88
Vehicle_t::speed
double speed
Definition: vehicle_t.h:43
pgrouting::vrp::Order
Definition: order.h:42
Identifiers::front
T front() const
Definition: identifiers.hpp:80
pgrouting::vrp::Fleet::get_truck
Vehicle_pickDeliver get_truck()
Definition: fleet.cpp:67
pgrouting::vrp::Fleet::size
size_t size() const
Definition: fleet.h:78
pgrouting::vrp::Tw_node::opens
double opens() const
Returns the opening time.
Definition: tw_node.h:76
pgrouting::tsp::Dmatrix::empty
bool empty() const
Definition: Dmatrix.h:118
pgrouting::vrp::PD_Orders
Definition: pd_orders.h:48
pgrouting::vrp::Fleet::Fleet
Fleet()=default
Vehicle_t::id
int64_t id
Definition: vehicle_t.h:41
pgrouting::vrp::Fleet::set_compatibles
void set_compatibles(const PD_Orders &orders)
Definition: fleet.cpp:313
pgrouting::vrp::Pgr_pickDeliver::add_node
void add_node(const Vehicle_node &node)
Definition: pgr_pickDeliver.cpp:128
pgrouting::vrp::Fleet::operator[]
Vehicle_pickDeliver & operator[](size_t i)
Definition: fleet.cpp:307
pgrouting
Book keeping class for swapping orders between vehicles.
Definition: pgr_alphaShape.cpp:56
pgrouting::vrp::Fleet::build_fleet
bool build_fleet(std::vector< Vehicle_t > vehicles, double factor)
build the fleet
Definition: fleet.cpp:160
Identifiers< size_t >
fleet.h