pgRouting  2.2
pgRouting extends the PostGIS / PostgreSQL geospatial database to provide geospatial routing functionality.
 All Classes Functions Variables Pages
VRP_Solver.h
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 #ifndef VRPSOLVER_H
25 #define VRPSOLVER_H
26 
27 #include <vector>
28 #include <map>
29 #include <queue>
30 #include <string>
31 #include <stdlib.h>
32 #include <iostream>
33 #include <algorithm>
34 #include <math.h>
35 #include <stdio.h>
36 #include <string.h>
37 #include <set>
38 
39 #define MAXIMUM_TRY 15
40 #define TOTAL_NUMBER_OF_SEARCH 15
41 #define MAXIMUM_MOVE_FREQUENCY 15
42 
43 #define INF (1e15)
44 
45 typedef std::pair<int, int> PII;
46 
47 #define max(a,b) ((a)>(b))?(a):(b)
48 
49 // Structure for Point, Geo coordinates can be represented with it
50 typedef struct
51 {
52  double X, Y;
53 }Point;
54 
55 // Structure to keep cost, distance and traveltime. If distance/ traveltime is missing, there may be a negative flag
56 typedef struct
57 {
58  double cost, distance, traveltime;
59 }CostPack;
60 
61 
62 // Class for holding vehicle information which consist of capacity, and cost_per_km
63 // For first version we will use homogeneous cost
65 {
66 public:
67  CVehicleInfo();
68  ~CVehicleInfo();
69 
70  bool init();
71 
72  bool loadUnit(int lUnit);
73  bool unloadUnit(int lUnit);
74  int getRemainingCapacity(){return (m_iCapacity - m_iCurrentLoad);}
75 
76  int getCurrentLoad(){return m_iCurrentLoad;}
77 
78  int getCapacity(){return m_iCapacity;}
79  void setCapacity(int capacity){m_iCapacity = capacity;}
80 
81  int getId(){return (this->m_iVehicleId);}
82  void setId(int id){m_iVehicleId = id;}
83 
84  double getCostPerKM(){return m_dCostPerKM;}
85  void setCostPerKM(double cost){m_dCostPerKM = cost;}
86 
87  friend bool operator != (const CVehicleInfo& cur, const CVehicleInfo& that);
88 
89 
90  //CVehicleInfo( CVehicleInfo const& );
91  //CVehicleInfo& operator = (const CVehicleInfo& vehicleInfo);
92 
93 private:
94  int m_iCapacity;
95  int m_iCurrentLoad;
96  int m_iVehicleId;
97  double m_dCostPerKM;
98 
99 };
100 
101 
102 
103 // Class to represent Orders. Each order is consist of open_time, close_time and sevice_time, its location and number of units ordered.
105 {
106 public:
107  COrderInfo();
108  ~COrderInfo();
109 
110  int getOpenTime(){return m_iOrderOpenTime;}
111  void setOpenTime(int openTime){m_iOrderOpenTime = openTime;}
112 
113  int getCloseTime(){return m_iOrderCloseTime;}
114  void setCloseTime(int closeTime){m_iOrderCloseTime = closeTime;}
115 
116  int getServiceTime(){return m_iOrderServiceTime;}
117  void setServiceTime(int serviceTime){m_iOrderServiceTime = serviceTime;}
118 
119  int getOrderUnit(){return m_iOrderUnitCount;}
120  void setOrderUnit(int orderUnit){m_iOrderUnitCount = orderUnit;}
121 
122  Point getOrderLocation(){return m_ptOrderLocation;}
123  void setOrderLocation(Point location){m_ptOrderLocation = location;}
124 
125  int getOrderId(){return m_iOrderId; }
126  void setOrderId(int orderId){m_iOrderId = orderId;}
127 
128 
129  //COrderInfo( COrderInfo const& );
130  //COrderInfo& operator = (const COrderInfo& solution);
131 
132 private:
133  int m_iOrderOpenTime;
134  int m_iOrderCloseTime;
135  int m_iOrderServiceTime;
136  int m_iOrderUnitCount;
137  int m_iOrderId;
138 
139  Point m_ptOrderLocation;
140 };
141 
142 
143 // Class to represent Depot information. Each depot will have it's Open_Time and Close_Time. The Depot that will open earliest will have open time 0
144 // and all other time will be normalized with respect to it. For the first version there will be only one depot
146 {
147 public:
148  CDepotInfo();
149  ~CDepotInfo();
150 
151  int getOpenTime(){return m_iDepotOpenTime;}
152  void setOpenTime(int openTime){m_iDepotOpenTime = openTime;}
153 
154  int getCloseTime(){return m_iDepotCloseTime;}
155  void setCloseTime(int closeTime){m_iDepotCloseTime = closeTime;}
156 
157  int getDepotId(){return m_iDepotId;}
158  void setDepotId(int id){m_iDepotId = id;}
159 
160  Point getDepotLocation(){return m_ptDepotLocation;}
161  void setDepotLocation(Point location){m_ptDepotLocation = location;}
162 
163  //CDepotInfo( CDepotInfo const& );
164  //CDepotInfo& operator = (const CDepotInfo& solution);
165 
166 private:
167  int m_iDepotOpenTime;
168  int m_iDepotCloseTime;
169 
170  int m_iDepotId;
171 
172  Point m_ptDepotLocation;
173 };
174 
175 // Class to represent information of a Tour. A Tour starts from a depot and ends in a depot. On the way it serves several orders.
176 // Each Tour has a vehicle ID and the list of Orders it serves in appropriate order. It also has the total Distance, Cost and Time assciated.
178 {
179 public:
180  CTourInfo();
181  ~CTourInfo();
182 
183  void init();
184 
185  int getRemainingCapacity();
186 
187  int getVehicleId(){return m_vehicleInfo.getId();}
188 
189  CVehicleInfo& getVehicleInfo(){return m_vehicleInfo;}
190  void setVehicleInfo(CVehicleInfo vehicleInfo){m_vehicleInfo = vehicleInfo;}
191 
192  int getStartDepot(){return m_iStartDepotId;}
193  void setStartDepot(int depotId){m_iStartDepotId = depotId;}
194 
195  int getEndDepot(){return m_iEndDepotId;}
196  void setEndDepot(int depotId){m_iEndDepotId = depotId;}
197 
198  size_t getServedOrderCount(){return m_viOrderIds.size();}
199 
200  void updateCost(double cost, double distance, double travelTime);
201 
202  void setStartTime(std::vector<int> vStartTime){m_viStartTime = vStartTime;}
203 
204 
205  bool insertOrder(int orderId, int pos);
206  bool removeOrder(int pos);
207 
208 
209  double getDistance(){return m_dTotalDistance;}
210 
211  double getCost(){return m_dTotalCost;}
212 
213  double getTravelTime(){return m_dTotalTraveltime;}
214 
215  std::vector<int> getOrderVector(){return m_viOrderIds;}
216 
217  int getStartTime(int pos){if( (unsigned int) pos >= m_viStartTime.size()) return 0;
218  else return m_viStartTime[pos];}
219 
220  friend bool operator== (const CTourInfo& cur, const CTourInfo& that);
221 
222 
223  //bool operator != (const CTourInfo& that)
224  //{
225  // return(!(*this == that));
226  //}
227 
228  //CTourInfo( CTourInfo const& );
229  //CTourInfo& operator = (const CTourInfo& solution);
230 
231 
232 private:
233  CVehicleInfo m_vehicleInfo;
234  int m_iStartDepotId;
235  int m_iEndDepotId;
236  int m_iOrdersServed;
237  std::vector<int> m_viOrderIds;
238  std::vector<int> m_viStartTime;
239  double m_dTotalCost;
240  double m_dTotalDistance;
241  double m_dTotalTraveltime;
242 };
243 
244 
245 
246 // This class will represent a solution of a VRP problem. A solution will be consist of multiple tour.
247 // It also contains the number of vehicle used, number of orders served and total cost, distance and traveltime.
249 {
250 public:
251  CSolutionInfo();
252  ~CSolutionInfo();
253 
254  int getVehicleUsed(){return m_iVehicleUsed;}
255  int getOrderServed(){return m_iOrdersServed;}
256  //int getVehicleUsed(){return m_iVehicleUsed;}
257 
258  bool addTour(CTourInfo& tour);
259  CTourInfo& getTour(int pos){return m_vtourAll[pos];}
260 
261  size_t getTourCount(){return (m_vtourAll.size());}
262 
263  size_t getUnservedOrderCount(){return m_vUnservedOrderId.size();}
264  size_t getUnusedVehicleCount(){return m_vUnusedVehicles.size();}
265 
266  int getUnusedVehicleAt(int pos){return m_vUnusedVehicles[pos];}
267 
268  void removeVehicle(int pos){m_vUnusedVehicles.erase(m_vUnusedVehicles.begin() + pos);}
269  void removeOrder(int pos){m_vUnservedOrderId.erase(m_vUnservedOrderId.begin() + pos);}
270 
271  double getTotalCost(){return m_dTotalCost;}
272  double getTotalDistance(){return m_dTotalDistance;}
273  double getTotalTravelTime(){return m_dTotalTravelTime;}
274  int getUnservedOrderAt(int pos){return m_vUnservedOrderId[pos];}
275  //void addOrderAtTour(int tourIndex, int insertIndex, int orderIndex);
276 
277  void replaceTourAt(int index, CTourInfo curTour);
278  void replaceTour(CTourInfo curTour);
279 
280  bool init(std::vector<int> vecOrder, int iTotalOrder, std::vector<int> vecVehicle);
281 
282  std::vector<CTourInfo> getTourInfoVector(){return m_vtourAll;}
283 
284  //CTourInfo( CTourInfo const& );
285  //CTourInfo& operator = (const CTourInfo& solution);
286 
287 private:
288  std::vector<CTourInfo> m_vtourAll;
289  std::vector<int> m_vUnservedOrderId;
290  std::vector<int> m_vUnusedVehicles;
291  int m_iVehicleUsed;
292  int m_iOrdersServed;
293  int m_iTotalOrders;
294  double m_dTotalCost;
295  double m_dTotalDistance;
296  double m_dTotalTravelTime;
297 };
298 
300 {
301 public:
302 
303  CMoveInfo();
304  ~CMoveInfo();
305 
306  bool isBetter( CMoveInfo *pVRPMove );
307 
308  void reverseMove();
309  void setInitialTour(CTourInfo pTourData);
310  void setInitialTour(CTourInfo pTourData1, CTourInfo pTourData2);
311  void setModifiedTour(CTourInfo pTourData);
312  void setModifiedTour(CTourInfo pTourData1, CTourInfo pTourData2);
313 
314  bool getModifiedTourAt(int index, CTourInfo& tourInfo);
315  size_t getModifiedTourCount() const { return m_vModifiedTour.size();}
316  double getModifiedTourCost() const;
317  void getInitialTour(CTourInfo &TourData);
318  void getInitialTour(CTourInfo &TourData1, CTourInfo &TourData2);
319 
320  friend bool operator == (const CMoveInfo& cur, const CMoveInfo& that);
321 
322 
323  //bool operator != (const CMoveInfo& that)
324  //{
325  // return(!(*this == that));
326  //}
327 
328  //CMoveInfo( CMoveInfo const& );
329  //CMoveInfo& operator = (const CMoveInfo& solution);
330 
331 private:
332 
333  void clearInitialTour();
334  void clearModifiedTour();
335 
336  std::vector<CTourInfo> m_vInitialTour;
337  std::vector<CTourInfo> m_vModifiedTour;
338 };
339 
340 
341 
342 
343 // This is the main class that will solve the VRP problem. It will use the previous classes to represent the problem and the solution.
344 // It will also have pre generated point to point distance/ cost/ traveltime information in maps.
346 {
347 public:
348  CVRPSolver();
349  ~CVRPSolver();
350 
351  bool init();
352 
353  bool addDepot(CDepotInfo depotInfo);
354  bool addOrder(COrderInfo orderInfo);
355  bool addVehicle(CVehicleInfo vehicleInfo);
356 
357  CostPack getOrderToOrderCost(int firstOrder, int secondOrder);
358  CostPack getDepotToOrderCost(int depotId, int orderId);
359  CostPack getOrderToDepotCost(int depotId, int orderId);
360 
361  bool addOrderToOrderCost(int firstOrder, int secondOrder, CostPack cost);
362  bool addDepotToOrderCost(int depotId, int orderId, CostPack cost);
363  bool addOrderToDepotCost(int depotId, int orderId, CostPack cost);
364 
365  void removeVehicle(int vehicleIndex)
366  {m_viUnusedVehicleIndex.erase(m_viUnusedVehicleIndex.begin() + vehicleIndex, m_viUnusedVehicleIndex.begin() + vehicleIndex+1);}
367 
368  void removeOrder(int orderIndex)
369  {m_viUnservedOrderIndex.erase(m_viUnservedOrderIndex.begin() + orderIndex, m_viUnservedOrderIndex.begin() + orderIndex + 1);}
370 
371  bool solveVRP(std::string& strError);
372 
373  bool getSolution(CSolutionInfo& solution, std::string& strError);
374  CSolutionInfo generateInitialSolution();
375  bool updateFinalSolution(CSolutionInfo& solutionInfo);
376  std::pair<int,double> getPotentialInsert(CTourInfo& curTour, COrderInfo& curOrder);
377  CostPack getCostForInsert(CTourInfo& curTour, COrderInfo& curOrder, int pos);
378  bool tabuSearch(CSolutionInfo& solutionInfo);
379  int getServiceTime(int order_id){return (m_vOrderInfos[m_mapOrderIdToIndex[order_id]].getServiceTime());}
380 
381  bool insertOrder(CTourInfo& tourInfo, int orderId, int pos);
382  void applyBestMoveInCurrentSolution(CSolutionInfo& solutionInfo, CMoveInfo& bestMove );
383  void insertUnservedOrders(CSolutionInfo& solutionInfo);
384  //void attemptFeasibleNodeExchange(CSolutionInfo& solutionInfo);
385  void attempVehicleExchange(CSolutionInfo& solutionInfo);
386  //CMoveInfo identifyPotentialMove();
387  void updateTabuCount(CMoveInfo& bestMove);
388 
389  bool isTabuMove(CMoveInfo& curMove);
390  bool updateTourCosts(CTourInfo& tourInfo);
391  bool addOrderAtTour(CSolutionInfo& solutionInfo, int tourIndex, int insertIndex, int orderIndex);
392 
393 
394 private:
395  bool m_bIsReadyToSolve;
396  std::vector<CVehicleInfo> m_vVehicleInfos;
397  std::vector<COrderInfo> m_vOrderInfos;
398  std::vector<CDepotInfo> m_vDepotInfos;
399 
400  std::map<int, int> m_mapOrderIdToIndex;
401  std::map<int, int> m_mapVehicleIdToIndex;
402  std::map<int, int> m_mapDepotIdToIndex;
403 
404  std::map<std::pair<int, int>, CostPack> m_mapOrderToOrderCost;
405  std::map<std::pair<int, int>, CostPack> m_mapDepotToOrderrCost;
406  std::map<std::pair<int, int>, CostPack> m_mapOrderToDepotCost;
407 
408  /*
409  std::map<CMoveInfo, int> m_mapMoveFrequency;
410  std::map<CMoveInfo, std::pair<int, int> > m_mapTabuCount;
411  std::set<CMoveInfo> m_sTabuList;
412  */
413 
414  std::vector<CMoveInfo> m_veMoves;
415 
416  bool m_bIsSolutionReady;
417  CSolutionInfo m_solutionFinal;
418 
419 private:
420  std::vector<int> m_viUnservedOrderIndex;
421  std::vector<int> m_viUnusedVehicleIndex;
422  int m_iGeneratedSolutionCount;
423  int m_iStepsSinceLastSolution;
424  bool m_bFoundOptimal;
425 
426 };
427 
428 #endif