pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
VRP_core.cpp
1 /*PGR-GNU*****************************************************************
2 
3 Copyright (c) 2013 Khondoker Md. Razequl Islam
4 ziboncsedu@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 #ifdef __MINGW32__
25 #include <winsock2.h>
26 #include <windows.h>
27 #endif
28 
29 #include "VRP.h"
30 #include "VRP_Solver.h"
31 #include <exception>
32 
33 #undef PGR_LOGGER_ON
34 #define PGR_LOGGER_LOC
35 #define PGR_LOGGER_FILE "/tmp/vrp-debug.log"
36 #include "../../common/src/pgr_logger.h"
37 
38 CVRPSolver solver;
39 
40 void loadOrders(vrp_orders_t *orders, int order_count, int depotId)
41 {
42  int i;
43  PGR_LOGF("%s: %d\n", "Depot ID", id)
44  for(i = 0; i < order_count; i++)
45  {
46  int id = orders[i].id;
47  PGR_LOGF("%s: %d\n", "Order ID", id)
48  if (id == depotId)
49  {
50  PGR_LOG("Got depot");
51  // This order represents Deopot
53 
54  depot.setDepotId(id);
55 
56  Point pt;
57 
58  pt.X = orders[i].x;
59  pt.Y = orders[i].y;
60 
61  depot.setDepotLocation(pt);
62 
63  int openTime = orders[i].open_time;
64  depot.setOpenTime(openTime);
65 
66  int closeTime = orders[i].close_time;
67  depot.setCloseTime(closeTime);
68 
69  solver.addDepot(depot);
70 
71  }
72  else
73  {
74  // This is an order
75  COrderInfo order;
76 
77  order.setOrderId(id);
78 
79  Point pt;
80 
81  pt.X = orders[i].x;
82  pt.Y = orders[i].y;
83 
84  order.setOrderLocation(pt);
85 
86  int demand = orders[i].order_unit;
87  order.setOrderUnit(demand);
88 
89  int openTime = orders[i].open_time;
90  order.setOpenTime(openTime);
91 
92  int closeTime = orders[i].close_time;
93  order.setCloseTime(closeTime);
94 
95  int serviceTime = orders[i].service_time;
96  order.setServiceTime(serviceTime);
97 
98  solver.addOrder(order);
99  }
100  }
101 
102 }
103 
104 void loadVehicles(vrp_vehicles_t *vehicles, int vehicle_count)
105 {
106  int i;
107  for(i = 0; i < vehicle_count; i++)
108  {
109  CVehicleInfo vehicle;
110 
111  int id = vehicles[i].id;
112  vehicle.setId(id);
113 
114  int capcity = vehicles[i].capacity;
115  vehicle.setCapacity(capcity);
116 
117  vehicle.setCostPerKM(1);
118 
119  solver.addVehicle(vehicle);
120  }
121 
122 }
123 
124 void loadDistanceMatrix(vrp_cost_element_t *costmatrix, int cost_count, int depotId)
125 {
126  int i;
127  for(i = 0; i < cost_count; i++)
128  {
129  int fromId = costmatrix[i].src_id;
130  int toId = costmatrix[i].dest_id;
131  CostPack cpack;
132  cpack.cost = costmatrix[i].cost;
133  cpack.distance = costmatrix[i].distance;
134  cpack.traveltime = costmatrix[i].traveltime;
135 
136  if(fromId == depotId)
137  solver.addDepotToOrderCost(fromId, toId, cpack);
138  else if(toId == depotId)
139  solver.addOrderToDepotCost(fromId, toId, cpack);
140  else
141  solver.addOrderToOrderCost(fromId, toId, cpack);
142  }
143 
144 }
145 
146 
147 int find_vrp_solution(vrp_vehicles_t *vehicles, size_t vehicle_count,
148  vrp_orders_t *orders, size_t order_count,
149  vrp_cost_element_t *costmatrix, size_t cost_count,
150  int depot_id,
151  vrp_result_element_t **results, size_t *result_count, char **err_msg)
152 {
153  int res;
154 
155  std::string strError;
156  try {
157  PGR_LOG("Before load order");
158  loadOrders(orders, static_cast<int>(order_count), depot_id);
159  PGR_LOG("After load order");
160  loadVehicles(vehicles, static_cast<int>(vehicle_count));
161  PGR_LOG("After load vehicles");
162  loadDistanceMatrix(costmatrix, static_cast<int>(cost_count), depot_id);
163  PGR_LOG("After load distance matrix");
164  res = solver.solveVRP(strError);
165  PGR_LOG("After VRP Solve");
166 
167  }
168  catch(std::exception& e) {
169  *err_msg = (char *) e.what();
170  return -1;
171  }
172  catch(...) {
173  *err_msg = (char *) "Caught unknown exception!";
174  return -1;
175  }
176 
177 
178  if (res < 0)
179  return res;
180  else
181  {
182  try {
183  CSolutionInfo solution;
184  CTourInfo ctour;
185  // bool bOK =
186  solver.getSolution(solution, strError);
187  auto totalRoute = solution.getTourInfoVector().size();
188  size_t totRows = 0;
189  for(size_t i = 0; i < totalRoute; i++)
190  {
191  totRows += (solution.getTour(static_cast<int>(i)).getServedOrderCount() + 2);
192  }
193  *results = (vrp_result_element_t *) malloc(totRows * sizeof(vrp_result_element_t));
194  *result_count = totRows;
195  int cnt = 0;
196  for(size_t i = 0; i < totalRoute; i++)
197  {
198  ctour = solution.getTour(static_cast<int>(i));
199  std::vector<int> vecOrder = ctour.getOrderVector();
200  auto totalOrder = vecOrder.size();
201 
202  // For start depot
203  (*results)[cnt].order_id = ctour.getStartDepot();
204  (*results)[cnt].order_pos = 0;
205  (*results)[cnt].vehicle_id = ctour.getVehicleId();
206  (*results)[cnt].arrival_time = -1;
207  (*results)[cnt].depart_time = ctour.getStartTime(0);
208  cnt++;
209 
210  // For each order
211  for(size_t j = 0; j < totalOrder; j++)
212  {
213  (*results)[cnt].order_id = vecOrder[j];
214  (*results)[cnt].order_pos = static_cast<int>(j) + 1;
215  (*results)[cnt].vehicle_id = ctour.getVehicleId();
216  (*results)[cnt].depart_time = ctour.getStartTime(static_cast<int>(j) + 1);
217  (*results)[cnt].arrival_time = ctour.getStartTime(static_cast<int>(j) + 1) - solver.getServiceTime(vecOrder[j]);
218  cnt++;
219  }
220 
221  // For return depot
222  (*results)[cnt].order_id = ctour.getEndDepot();
223  (*results)[cnt].order_pos = static_cast<int>(totalOrder) + 1;
224  (*results)[cnt].vehicle_id = ctour.getVehicleId();
225  (*results)[cnt].arrival_time = ctour.getStartTime(static_cast<int>(totalOrder) + 1);
226  (*results)[cnt].depart_time = -1;
227  cnt++;
228  }
229  }
230  catch(std::exception& e) {
231  *err_msg = (char *) e.what();
232  return -1;
233  }
234  catch(...) {
235  *err_msg = (char *) "Caught unknown exception!";
236  return -1;
237  }
238  }
239  return EXIT_SUCCESS;
240 }
241 
Definition: VRP.h:38
Definition: pdp.hpp:31