PGROUTING  2.6-dev
tw_node.cpp
Go to the documentation of this file.
1 /*PGR-GNU*****************************************************************
2 
3 FILE: tw_node.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/tw_node.h"
27 
28 #include <limits>
29 #include <string>
30 
31 #include "cpp_common/pgr_assert.h"
32 #include "vrp/pgr_pickDeliver.h"
33 
34 
35 namespace pgrouting {
36 namespace vrp {
37 
38 
39 double
40 Tw_node::travel_time_to(const Tw_node &to, double speed) const {
46  auto from = problem->m_base_nodes[idx()].get();
47  auto destination = problem->m_base_nodes[to.idx()].get();
48  pgassert(speed != 0);
50  return from->distance(destination) / speed;
51 }
52 
53 
54 /*
55  * I -> J = (*this)
56  */
57 double
58 Tw_node::arrival_j_opens_i(const Tw_node &I, double speed) const {
59  if (m_type == kStart) return (std::numeric_limits<double>::max)();
60  return I.opens() + I.service_time() + I.travel_time_to(*this, speed);
61 }
62 
63 double
64 Tw_node::arrival_j_closes_i(const Tw_node &I, double speed) const {
65  if (m_type == kStart) return (std::numeric_limits<double>::max)();
66  return I.closes() + I.service_time() + I.travel_time_to(*this, speed);
67 }
68 
69 
70 
71 
72 bool
73 Tw_node::is_compatible_IJ(const Tw_node &I, double speed) const {
74  /*
75  * I /-> kStart
76  */
77  if (m_type == kStart) return false;
78  /*
79  * kEnd /-> (*this)
80  */
81  if (I.m_type == kEnd) return false;
82 
83  return !is_late_arrival(arrival_j_opens_i(I, speed));
84 }
85 
86 bool
87 Tw_node::is_partially_compatible_IJ(const Tw_node &I, double speed) const {
88  return
89  is_compatible_IJ(I, speed)
90  && !is_early_arrival(arrival_j_opens_i(I, speed))
91  && is_late_arrival(arrival_j_closes_i(I, speed));
92 }
93 
94 bool
95 Tw_node::is_tight_compatible_IJ(const Tw_node &I, double speed) const {
96  return
97  is_compatible_IJ(I, speed)
98  && !is_early_arrival(arrival_j_opens_i(I, speed))
99  && !is_late_arrival(arrival_j_closes_i(I, speed));
100 }
101 
102 bool
104  const Tw_node &I,
105  double speed) const {
106  return
107  is_compatible_IJ(I, speed)
108  && is_early_arrival(arrival_j_opens_i(I, speed));
109 }
110 
111 bool
112 Tw_node::is_waitTime_compatible_IJ(const Tw_node &I, double speed) const {
113  return
114  is_compatible_IJ(I, speed)
115  && is_early_arrival(arrival_j_opens_i(I, speed));
116 }
117 
118 
119 std::string Tw_node::type_str() const {
120  switch (type()) {
121  case kStart: return "START"; break;
122  case kEnd: return "END"; break;
123  case kDump: return "DUMP"; break;
124  case kLoad: return "LOAD"; break;
125  case kPickup: return "PICKUP"; break;
126  case kDelivery: return "DELIVERY"; break;
127  default: return "UNKNOWN";
128  }
129 }
130 
131 bool
133  return
134  m_type == kStart
135  && (opens() < closes())
136  && (service_time() >= 0)
137  && (demand() == 0);
138 }
139 
140 bool
142  return m_type == kPickup
143  && (opens() < closes())
144  && (service_time() >= 0)
145  && (demand() > 0);
146 }
147 
148 
149 bool
151  return m_type == kDelivery
152  && (opens() < closes())
153  && (service_time() >= 0)
154  && (demand() < 0);
155 }
156 
157 
158 bool
160  return m_type == kDump
161  && (opens() < closes())
162  && (service_time() >= 0)
163  && (demand() <= 0);
164 }
165 
166 
167 bool
169  return m_type == kLoad
170  && (opens() < closes())
171  && (service_time() >= 0)
172  && (demand() >= 0);
173 }
174 
175 
176 bool
178  return m_type == kEnd
179  && (opens() < closes())
180  && (service_time() >= 0)
181  && (demand() == 0);
182 }
183 
184 
185 bool
186 Tw_node::operator ==(const Tw_node &other) const {
187  if (&other == this) return true;
188  auto lhs = static_cast<const Node&>(
189  *problem->m_base_nodes[idx()].get());
190  auto rhs = static_cast<const Node&>(
191  *problem->m_base_nodes[other.idx()].get());
192  return lhs == rhs;
193 }
194 
195 
196 
197 bool Tw_node::is_valid() const {
198  switch (type()) {
199  case kStart:
200  return is_start();
201  break;
202 
203  case kEnd:
204  return is_end();
205  break;
206 
207  case kDump:
208  return is_dump();
209  break;
210 
211  case kDelivery:
212  return is_delivery();
213  break;
214 
215  case kPickup:
216  return is_pickup();
217  break;
218 
219  case kLoad:
220  return is_load();
221  break;
222 
223  default:
224  return false;
225  break;
226  }
227 
228  return false;
229 }
230 
231 
233  size_t id,
235  NodeType type) :
236  Identifier(id, data.pick_node_id),
237  m_order(data.id),
238  m_opens(data.pick_open_t),
239  m_closes(data.pick_close_t),
240  m_service_time(data.pick_service_t),
241  m_demand(data.demand),
242  m_type(type) {
243  if (m_type == kDelivery) {
245  m_opens = data.deliver_open_t;
246  m_closes = data.deliver_close_t;
248  m_demand *= -1;
249  }
250  }
251 
253  size_t id,
254  Vehicle_t data,
255  NodeType type) :
256  Identifier(id, data.start_node_id),
257  m_opens(data.start_open_t),
258  m_closes(data.start_close_t),
259  m_service_time(data.start_service_t),
260  m_demand(0),
261  m_type(type) {
262  if (m_type == kEnd) {
263  reset_id(data.end_node_id);
264  m_opens = data.end_open_t;
265  m_closes = data.end_close_t;
267  }
268  }
269 
270 
272 std::ostream& operator << (std::ostream &log, const Tw_node &n) {
273  log << static_cast<const Node&>(
274  *n.problem->m_base_nodes[n.idx()].get())
275  << "[opens = " << n.m_opens
276  << "\tcloses = " << n.m_closes
277  << "\tservice = " << n.m_service_time
278  << "\tdemand = " << n.m_demand
279  << "\ttype = " << n.type_str()
280  << "]"
281  << "\n";
282  return log;
283 }
284 
285 } // namespace vrp
286 } // namespace pgrouting
287 
double m_opens
opening time of the node
Definition: tw_node.h:274
double demand() const
Returns the demand associated with this node.
Definition: tw_node.h:82
bool is_load() const
is_Load
Definition: tw_node.cpp:168
bool is_valid() const
Definition: tw_node.cpp:197
bool is_early_arrival(double arrival_time) const
True when arrivalTime is before it opens.
Definition: tw_node.h:187
double end_service_t
Definition: vehicle_t.h:81
bool is_end() const
is_end
Definition: tw_node.cpp:177
static Pgr_pickDeliver * problem
Definition: pd_problem.h:51
double m_demand
The demand for the Node.
Definition: tw_node.h:277
std::vector< std::unique_ptr< Base_node > > m_base_nodes
The Node class defines a point in 2D space with an id.
Definition: node.h:50
double end_close_t
Definition: vehicle_t.h:80
double end_open_t
Definition: vehicle_t.h:79
bool operator==(const Tw_node &rhs) const
Definition: tw_node.cpp:186
bool is_compatible_IJ(const Tw_node &I, double speed) const
Definition: tw_node.cpp:73
bool is_partially_waitTime_compatible_IJ(const Tw_node &I, double speed) const
Definition: tw_node.cpp:103
double service_time() const
Returns the service time for this node.
Definition: tw_node.h:86
double m_closes
closing time of the node
Definition: tw_node.h:275
dump site, empties truck
Definition: tw_node.h:63
double opens() const
Returns the opening time.
Definition: tw_node.h:76
load site, fills the truck
Definition: tw_node.h:64
int64_t m_order
order to which it belongs
Definition: tw_node.h:273
#define pgassert(expr)
Uses the standard assert syntax.
Definition: pgr_assert.h:81
int64_t end_node_id
Definition: vehicle_t.h:77
bool is_late_arrival(double arrival_time) const
True when arrivalTime is after it closes.
Definition: tw_node.h:192
bool is_waitTime_compatible_IJ(const Tw_node &I, double speed) const
Definition: tw_node.cpp:112
std::string type_str() const
Definition: tw_node.cpp:119
bool is_start() const
@ {
Definition: tw_node.cpp:132
bool is_tight_compatible_IJ(const Tw_node &I, double speed) const
Definition: tw_node.cpp:95
NodeType type() const
Returns the type of this node.
Definition: tw_node.h:89
bool is_partially_compatible_IJ(const Tw_node &I, double speed) const
Definition: tw_node.cpp:87
double closes() const
Returns the closing time.
Definition: tw_node.h:79
bool is_pickup() const
is_pickup
Definition: tw_node.cpp:141
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
Assertions Handling.
bool is_delivery() const
is_delivery
Definition: tw_node.cpp:150
bool is_dump() const
is_dump
Definition: tw_node.cpp:159
Extends the Node class to create a Node with time window attributes.
Definition: tw_node.h:57
void reset_id(int64_t)
Definition: identifier.cpp:47
NodeType m_type
The demand for the Node.
Definition: tw_node.h:278
size_t idx() const
Definition: identifier.cpp:37
double arrival_j_closes_i(const Tw_node &I, double speed) const
The actual arrival time at this node, given that: this node is visited directly after other node and ...
Definition: tw_node.cpp:64
double travel_time_to(const Tw_node &other, double speed) const
time = distance / speed.
Definition: tw_node.cpp:40
friend std::ostream & operator<<(std::ostream &log, const Tw_node &node)
Print the contents of a Twnode object.
Definition: tw_node.cpp:272
double arrival_j_opens_i(const Tw_node &I, double speed) const
@ {
Definition: tw_node.cpp:58