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