pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
pickDeliver/src/Route.h
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2014 Manikata Kondeti
4 mani.iiit123@gmail.com
5 
6 ------
7 
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2 of the License, or
11 (at your option) any later version.
12 
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17 
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 
22 ********************************************************************PGR-GNU*/
23 
24 
25 #pragma once
26 
27 #include <vector>
28 #include <algorithm>
29 #include "pdp.hpp"
30 
31 class Route {
32  public:
33  int twv;
34  int cv;
35  double dis;
36  std::vector < int64_t > path;
37  double capacity;
38  Depot depot;
39 
40  Route(int _capacity, const Depot &_depot) :
41  twv(0),
42  cv(0),
43  dis(0),
44  capacity(_capacity),
45  depot(_depot) {
46  path.clear();
47  }
48  void update(const Customers &c);
49  double cost() const;
50  bool insertOrder(const Customers &c, const Pickup &order);
51  void append(const Customers &c, const Pickup &order);
52  void remove(const State &S);
53  int RemoveOrder(
54  const Customers &customers,
55  const Pickup &p);
56  bool has_violation(const Customers &customers);
57  bool has_twv(const Customers &customers);
58 };
59 
60 
61 /*
62  * Returns:
63  * 1 - when the order was found and removed
64  * 0 - When the order was not found
65  */
66 int
67 Route::RemoveOrder(
68  const Customers &customers,
69  const Pickup &pickup) {
70  Route oldRoute = *this;
71  oldRoute.update(customers);
72 
73 
74  auto pickup_pos = find(path.begin(), path.end(), pickup.Pid);
75 
76  if (pickup_pos != path.end()) {
77  path.erase(pickup_pos);
78  auto delivery_pos = find(path.begin(), path.end(), pickup.Did);
79  path.erase(delivery_pos);
80 
81  update(customers);
82  return ((dis < depot.Ltime)
83  && (twv < oldRoute.twv || cv < oldRoute.cv || dis < oldRoute.dis))? 1: 2;
84  } else {
85  return 0;
86  }
87 }
88 
89 void
90 Route::append(const Customers &customers,
91  const Pickup &pickup) {
92  path.push_back(pickup.Pid);
93  path.push_back(pickup.Did);
94  update(customers);
95 }
96 
97 
98 void
99 Route::update(const Customers &customers) {
100  dis = 0;
101  twv = 0;
102  cv = 0;
103  int load = 0;
104  double agg_cost = 0;
105  int prev_node = 0;
106  for (const auto &node : path) {
107  /*
108  * Between nodes
109  */
110  agg_cost += CalculateDistance(customers[prev_node], customers[node]);
111 
112  if (agg_cost < customers[node].Etime) {
113  /*
114  * Arrving before the opening time, adjust time, moving it to the opening time
115  */
116  agg_cost = customers[node].Etime;
117  }
118  if (customers[node].Ltime < agg_cost) {
119  /*
120  * arrived after closing time
121  */
122  ++twv;
123  }
124  agg_cost += customers[node].Stime;
125  load += customers[node].demand;
126  if (load > capacity || load < 0) {
127  ++cv;
128  }
129  prev_node = node;
130  }
131  /*
132  * Going back to the depot
133  */
134  agg_cost += CalculateDistance(customers[prev_node], depot);
135  if (depot.Ltime < agg_cost) {
136  ++twv;
137  }
138 
139  if (load != 0) {
140  ++cv;
141  }
142  dis = agg_cost;
143  return;
144 }
145 
146 
147 double
148 Route::cost() const {
149  return (0.3*dis)+(0.5*twv)+(0.2*cv);
150 }
151 
152 bool
153 Route::has_violation(const Customers &customers) {
154  update(customers);
155  return (twv > 0 || cv > 0);
156 }
157 
158 bool
159 Route::has_twv(const Customers &customers) {
160  update(customers);
161  return (twv > 0);
162 }
163 
164 
165 bool
166 Route::insertOrder(const Customers &customers, const Pickup &order) {
167  /*
168  * inserting only on a route that does not have twv or cv
169  */
170  if (has_violation(customers)) return false;
171 
172 
173  path.insert(path.begin(), order.Pid);
174  /*
175  * The pickup is in:
176  */
177  int Ppos = 0;
178  int i;
179  for (i = 1; i < (int)path.size(); i++) {
180  /*
181  * Inserting without creating violation
182  */
183  if (!has_twv(customers)) break;
184  std::swap(path[Ppos], path[i]);
185  Ppos = i;
186  }
187 
188  path.push_back(order.Did);
189  /*
190  * The delivery is in:
191  */
192  int Dpos = path.size() - 1;
193 
194  int j;
195  for (j = Dpos; Ppos < j; --j) {
196  if (!has_violation(customers)) break;
197  std::swap(path[j], path[Dpos]);
198  Dpos = j;
199  }
200 
201  /*
202  * Here 2 thngs can happen
203  * We inserted succesfully without violation
204  * Inserting created a violation
205  */
206 
207 
208  if (has_violation(customers)) {
209  RemoveOrder(customers, order);
210  return false;
211  }
212 
213  /*
214  * .... Ppos a b c d Dpos ....
215  *
216  * The current route
217  */
218  update(customers);
219  Route bestRoute = *this;
220  Route currRoute = *this;
221 
222  for (i = Ppos; i < Dpos; i++) {
223  *this = currRoute;
224  /*
225  * .... Ppos a b c d Dpos ....
226  */
227  std::swap(path[Ppos], path[i]);
228  Ppos = i;
229  currRoute = *this;
230 
231  /*
232  * for the same position of Ppos
233  * - move the D
234  * - keep track of the best
235  */
236  for (j = Dpos; Ppos < j; j--) {
237  std::swap(path[j], path[Dpos]);
238  Dpos = j;
239  if (!has_violation(customers)
240  && dis < bestRoute.dis) {
241  bestRoute = *this;
242  bestRoute.update(customers);
243  }
244  }
245  }
246 
247  *this = bestRoute;
248 
249  return true;
250 }
251 
252 void Route::remove(const State &S) {
253  twv = S.twv;
254  cv = S.cv;
255  dis = S.dis;
256  path = S.path;
257 }
Definition: pdp.hpp:44
Definition: pdp.hpp:57
Definition: pdp.hpp:31