PGROUTING  2.6
pd_orders.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/pd_orders.h"
27 
28 #include <vector>
29 #include <memory>
30 #include <utility>
31 
32 #include "vrp/pgr_pickDeliver.h"
33 #include "vrp/dnode.h"
34 
35 namespace pgrouting {
36 namespace vrp {
37 
38 
40  const std::vector<PickDeliveryOrders_t> &pd_orders
41  ) {
42  build_orders(pd_orders);
43 }
44 
45 
46 void
48  const PickDeliveryOrders_t &order,
49  std::unique_ptr<Base_node> b_pick,
50  const Vehicle_node &pick,
51  std::unique_ptr<Base_node> b_drop,
52  const Vehicle_node &drop) {
53  problem->add_base_node(std::move(b_pick));
54  problem->add_base_node(std::move(b_drop));
55  problem->add_node(pick);
56  problem->add_node(drop);
57 
58  /*
59  * add into an order
60  */
61  m_orders.push_back(
62  Order(m_orders.size(), order.id,
63  pick,
64  drop));
65 }
66 
67 
68 void
70  const std::vector<PickDeliveryOrders_t> &pd_orders
71  ) {
72  ENTERING();
73  for (const auto order : pd_orders) {
74  /*
75  * SAMPLE CORRECT INFORMATION
76  *
77  * id | demand | pick_x | pick_y | pick_open_t | pick_close_t | pick_service_t | deliver_x | deliver_y | deliver_open_t | deliver_open_t | deliver_close_t | deliver_service_t
78  * 1 | 10 | 35 | 69 | 448 | 505 | 90 | 45 | 68 | 912 | 967 | 90 | 35
79  */
80 
81  if (problem->m_cost_matrix.empty()) {
82  /*
83  * Euclidean version
84  */
85  auto b_pick = create_b_pick<Node>(order, problem->node_id());
86  Vehicle_node pickup(
87  {problem->node_id()++, order, Tw_node::NodeType::kPickup});
88 
89  auto b_drop = create_b_deliver<Node>(order, problem->node_id());
90  Vehicle_node delivery({
91  problem->node_id()++,
92  order,
93  Tw_node::NodeType::kDelivery});
94 
95 
96  add_order(order,
97  std::move(b_pick), pickup,
98  std::move(b_drop), delivery);
99  } else {
100  /*
101  * matrix version
102  */
103  msg.log << "pickup \n"
104  << "pick_node_id: " << order.pick_node_id
105  << "\n";
106 
107  msg.log << "pickup \n"
108  << "deliver_node_id: " << order.deliver_node_id
109  << "\n";
110  auto b_pick = create_b_pick<Dnode>(order, problem->node_id());
111  Vehicle_node pickup(
112  {problem->node_id()++, order, Tw_node::NodeType::kPickup});
113 
114  auto b_drop = create_b_deliver<Dnode>(order, problem->node_id());
115  Vehicle_node delivery({
116  problem->node_id()++,
117  order,
118  Tw_node::NodeType::kDelivery});
119 
120  add_order(order,
121  std::move(b_pick), pickup,
122  std::move(b_drop), delivery);
123  }
124  } // for (creating orders)
125 
126  EXITING();
127 }
128 
129 bool
130 PD_Orders::is_valid(double speed) const {
131  for (const auto &o : m_orders) {
132  if (!o.is_valid(speed)) {
133  return false;
134  }
135  pgassert(o.pickup().is_pickup());
136  pgassert(o.delivery().is_delivery());
137  /* P -> D */
138  pgassert(o.delivery().is_compatible_IJ(o.pickup(), speed));
139  }
140  return true;
141 }
142 
143 Order&
145  pgassert(i < m_orders.size());
146  return m_orders[i];
147 }
148 
149 const Order&
150 PD_Orders::operator[](size_t i) const {
151  pgassert(i < m_orders.size());
152  return m_orders[i];
153 }
154 
155 void
157  for (auto &I : m_orders) {
158  for (const auto J : m_orders) {
159  I.set_compatibles(J, speed);
160  }
161  }
162 }
163 
164 size_t
166  Identifiers<size_t> &within_this_set) const {
167  pgassert(!within_this_set.empty());
168  auto best_order = within_this_set.front();
169  size_t max_size = 0;
170 
171 
172  for (auto o : within_this_set) {
173  auto size_J = m_orders[o].subsetJ(within_this_set).size();
174  if (max_size < size_J) {
175  max_size = size_J;
176  best_order = o;
177  }
178  }
179  return best_order;
180 }
181 
182 
183 size_t
185  Identifiers<size_t> &within_this_set) const {
186  pgassert(!within_this_set.empty());
187  auto best_order = within_this_set.front();
188  size_t max_size = 0;
189 
190 
191  for (auto o : within_this_set) {
192  auto size_I = m_orders[o].subsetI(within_this_set).size();
193  if (max_size < size_I) {
194  max_size = size_I;
195  best_order = o;
196  }
197  }
198  return best_order;
199 }
200 
201 
202 } // namespace vrp
203 } // namespace pgrouting
void add_base_node(std::unique_ptr< Base_node > node_ptr)
void build_orders(const std::vector< PickDeliveryOrders_t > &pd_orders)
Definition: pd_orders.cpp:69
void add_node(const Vehicle_node &node)
static Pgr_pickDeliver * problem
Definition: pd_problem.h:51
std::ostringstream log
Stores the hint information.
Definition: pgr_messages.h:102
Extend Tw_node to evaluate the vehicle at node level.
Definition: vehicle_node.h:48
#define EXITING()
Definition: pgr_messages.h:119
size_t find_best_J(Identifiers< size_t > &within_this_set) const
Definition: pd_orders.cpp:165
size_t find_best_I(Identifiers< size_t > &within_this_set) const
Definition: pd_orders.cpp:184
#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
Book keeping class for swapping orders between vehicles.
Definition: basic_edge.cpp:28
static Pgr_messages msg
Definition: pd_problem.h:48
Order & operator[](size_t o)
Definition: pd_orders.cpp:144
T front() const
Definition: identifiers.hpp:79
void set_compatibles(double speed)
Definition: pd_orders.cpp:156
bool empty() const
Definition: identifiers.hpp:78
bool is_valid(double speed) const
Definition: pd_orders.cpp:130
void add_order(const PickDeliveryOrders_t &, std::unique_ptr< Base_node >, const Vehicle_node &, std::unique_ptr< Base_node >, const Vehicle_node &)
Definition: pd_orders.cpp:47