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