pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
pickDeliver/src/Solution.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 #pragma once
25 
26 #include <vector>
27 
28 #include "./Route.h"
29 
30 class Solution {
31  public:
32  Solution() {
33  cost_total = 0, twv_total = 0, cv_total = 0, dis_total = 0;
34  }
35  // Variables
36  int twv_total;
37  int cv_total;
38  int dis_total;
39  double cost_total;
40  std::vector<Route> routes;
41  // Methods
42  void dump() const;
43  double getCost() const;
44  Solution getBestofNeighborhood(const Solution S,
45  const std::vector<Customer> &c,
46  const std::vector<Pickup> &p) const;
47  void UpdateSol(const Customers &customers);
48 };
49 
51  public:
52  Neighborhoods() {}
53  Solution BestSPI(const Solution S,
54  const std::vector<Customer> &customers,
55  const std::vector<Pickup> &pickups) const;
56 };
57 
58 void
59 Solution::UpdateSol(const Customers &customers) {
60  cost_total = 0, twv_total = 0, cv_total = 0, dis_total = 0;
61  routes.erase(std::remove_if(routes.begin(), routes.end(),
62  [] (const Route &r)
63  {return r.path.empty();}),
64  routes.end());
65  for (auto &r : routes) {
66  r.update(customers);
67  twv_total += r.twv;
68  dis_total += r.dis;
69  cv_total += r.cv;
70  cost_total += r.cost();
71  }
72 }
73 
74 
75 // Methods in Solution
76 
77 
78 double
79 Solution::getCost() const {
80  double cost_total = 0;
81  for (const auto &r : routes) {
82  cost_total += r.cost();
83  }
84  return cost_total;
85 }
86 
88 Solution::getBestofNeighborhood(const Solution S,
89  const std::vector<Customer> &customers,
90  const std::vector<Pickup> &pickups) const {
91  Neighborhoods N;
92  Solution S1;
93  S1 = N.BestSPI(S, customers, pickups);
94  return S1;
95 }
96 
97 
99 Neighborhoods::BestSPI(const Solution S,
100  const Customers &customers,
101  const Pickups &pickups) const {
102  Solution CurrSol, BestSol, TempSol;
103  CurrSol = BestSol = S;
104  std::vector<Pickup> OrderRequests = pickups;
105  State TempState;
106 
107  BestSol.UpdateSol(customers);
108  // Main SPI
109  for (const auto &order : OrderRequests) {
110  // Order Find and Remove it!
111  CurrSol = BestSol;
112  for (unsigned int route_remove = 0;
113  route_remove < CurrSol.routes.size();
114  route_remove++) {
115 
116  int OK = CurrSol.routes[route_remove].RemoveOrder(customers,order);
117 
118  if (OK != 1) continue;
119  TempSol = CurrSol;
120  TempSol.UpdateSol(customers);
121 
122  for (auto &route : TempSol.routes) {
123  int OK = route.insertOrder(customers, order);
124  if (!OK) continue;
125  TempSol.UpdateSol(customers);
126  if (TempSol.getCost() < BestSol.getCost()) {
127  BestSol = TempSol;
128  CurrSol = TempSol;
129  break;
130  }
131  /*
132  * the order was inserted but the distance was not best
133  */
134  route.RemoveOrder(customers, order);
135  }
136  }
137  }
138 
139  return BestSol;
140 }
Definition: pdp.hpp:57