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_Solver.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_Solver.h"
30 #include <algorithm>
31 #include <math.h>
32 #include <utility>
33 #include <map>
34 #include <set>
35 #include <string>
36 #include <vector>
37 
38 #undef PGR_LOGGER_ON
39 #define PGR_LOGGER_LOC
40 #define PGR_LOGGER_FILE "/tmp/vrp-debug.log"
41 #include "../../common/src/pgr_logger.h"
42 
43 #define DOUBLE_MAX 1e50
44 
45 bool operator != (const CVehicleInfo& cur, const CVehicleInfo& that) {
46  return(cur.m_iVehicleId != that.m_iVehicleId);
47 }
48 
49 bool operator == (const CTourInfo& cur, const CTourInfo& that) {
50  if (cur.m_vehicleInfo != that.m_vehicleInfo)
51  return false;
52  if (cur.m_viOrderIds.size() != that.m_viOrderIds.size())
53  return false;
54  auto tot = cur.m_viOrderIds.size();
55  for (size_t i = 0; i < tot; i++) {
56  if (cur.m_viOrderIds[i] != that.m_viOrderIds[i])
57  return false;
58  }
59  return true;
60 }
61 
62 bool operator == (const CMoveInfo& cur, const CMoveInfo& that) {
63  if (!(cur.m_vInitialTour == that.m_vInitialTour))
64  return false;
65  if (!(cur.m_vModifiedTour == that.m_vModifiedTour))
66  return false;
67  return true;
68 }
69 
70 
71 
73  m_iCurrentLoad = 0;
74 }
76 }
77 
78 bool CVehicleInfo::loadUnit(int lUnit) {
79  if (m_iCurrentLoad + lUnit > m_iCapacity)
80  return false;
81  m_iCurrentLoad += lUnit;
82  return true;
83 }
84 
87 
90 
92  m_dTotalCost = 0.0;
93  m_dTotalDistance = 0.0;
94  m_dTotalTraveltime = 0.0;
95 }
97 
98 bool CTourInfo::insertOrder(int orderId, int pos) {
99  m_viOrderIds.insert(m_viOrderIds.begin() + pos, orderId);
100  return true;
101 }
102 
105 }
106 
107 bool CTourInfo::removeOrder(int pos) {
108  m_viOrderIds.erase(m_viOrderIds.begin() + pos);
109  return true;
110 }
111 
112 void CTourInfo::updateCost(double cost, double distance, double travelTime) {
113  m_dTotalCost = cost;
114  m_dTotalDistance = distance;
115  m_dTotalTraveltime = travelTime;
116 }
117 
120 
122  unsigned int i;
123  for (i = 0; i < m_vtourAll.size(); i++) {
124  if (m_vtourAll[i].getVehicleId() == curTour.getVehicleId()) {
125  m_vtourAll[i] = curTour;
126  return;
127  }
128  }
129  return;
130 }
131 
132 void CSolutionInfo::replaceTourAt(int index, CTourInfo curTour) {
133  if (index < 0 || (unsigned int) index >= m_vtourAll.size())
134  return;
135  m_vtourAll[index] = curTour;
136 }
137 
138 bool CSolutionInfo::init(std::vector<int> vecOrder, int iTotalOrder, std::vector<int> vecVehicle) {
139  m_vUnservedOrderId = vecOrder;
140  m_iTotalOrders = iTotalOrder;
141  m_vUnusedVehicles = vecVehicle;
142 
143  m_vtourAll.clear();
144  m_iVehicleUsed = 0;
145  m_iOrdersServed = 0;
146  m_iTotalOrders = 0;
147  m_dTotalCost = 0;
148  m_dTotalDistance = 0;
149  m_dTotalTravelTime = 0;
150  return true;
151 }
152 
154  m_vtourAll.push_back(tour);
155  int vid = tour.getVehicleId();
156  std::vector<int>::iterator it;
157  it = std::find(m_vUnusedVehicles.begin(), m_vUnusedVehicles.end(), vid);
158  if (it != m_vUnusedVehicles.end()) {
159  m_vUnusedVehicles.erase(it);
160  }
161  m_iVehicleUsed++;
162  m_dTotalDistance += tour.getDistance();
164  m_dTotalCost += tour.getCost();
165 
166  std::vector<int> vecOrders = tour.getOrderVector();
167 
168  m_iOrdersServed += static_cast<int>(vecOrders.size());
169 
170  for (unsigned int i = 0; i < vecOrders.size(); i++) {
171  int oid = vecOrders[i];
172  it = std::find(m_vUnservedOrderId.begin(), m_vUnservedOrderId.end(), oid);
173  if (it != m_vUnservedOrderId.end()) {
174  m_vUnservedOrderId.erase(it);
175  }
176  }
177 
178  return true;
179 }
180 
183 
185  m_vInitialTour.clear();
186  m_vInitialTour.push_back(tourData);
187 }
188 
189 void CMoveInfo::setInitialTour(CTourInfo tourData1, CTourInfo tourData2) {
190  m_vInitialTour.clear();
191  m_vInitialTour.push_back(tourData1);
192  m_vInitialTour.push_back(tourData2);
193 }
194 
196  m_vModifiedTour.clear();
197  m_vModifiedTour.push_back(tourData);
198 }
199 
200 void CMoveInfo::setModifiedTour(CTourInfo tourData1, CTourInfo tourData2) {
201  m_vModifiedTour.clear();
202  m_vModifiedTour.push_back(tourData1);
203  m_vModifiedTour.push_back(tourData2);
204 }
205 
207  tourData = m_vInitialTour[0];
208 }
209 
210 void CMoveInfo::getInitialTour(CTourInfo &tourData1, CTourInfo &tourData2) {
211  tourData1 = m_vInitialTour[0];
212  tourData2 = m_vInitialTour[1];
213 }
214 
215 bool CMoveInfo::getModifiedTourAt(int index, CTourInfo& tourInfo) {
216  if (index < 0 || (unsigned int) index >= m_vModifiedTour.size())
217  return false;
218  tourInfo = m_vModifiedTour[index];
219  return true;
220 }
221 
222 
223 
225  // set a seed for the random number generator
226  // so it will generate consistent results for the same input
227  // otherwise we can not test it :(
228  srand(1726354);
229 }
231 
232 bool CVRPSolver::solveVRP(std::string& strError) {
233  // if (!m_bIsReadyToSolve)
234  // {
235  // strError = "Scenario is not ready to solve. Configure all parameter";
236  // return false;
237  // }
238  PGR_LOG("Inside Solve VRP");
239  std::vector<int> vecOrders, vecVehicles;
240  for (unsigned int i = 0; i < m_vOrderInfos.size(); i++) {
241  vecOrders.push_back(m_vOrderInfos[i].getOrderId());
242  }
243 
244  for (unsigned int i = 0; i < m_vVehicleInfos.size(); i++) {
245  vecVehicles.push_back(m_vVehicleInfos[i].getId());
246  }
247 
248  m_solutionFinal.init(vecOrders, static_cast<int>(vecOrders.size()), vecVehicles);
249  PGR_LOG("After init solution");
250  int iAttemptCount = 0;
251  while (iAttemptCount < MAXIMUM_TRY) {
252  bool bUpdateFound = false;
253  CSolutionInfo initialSolution = generateInitialSolution();
254  PGR_LOG("After Generate initial Solution");
255  iAttemptCount++;
256  bUpdateFound = updateFinalSolution(initialSolution);
257  PGR_LOG("After update final Solution");
258  bool bUpdateFound2 = tabuSearch(initialSolution);
259  PGR_LOG("After Tabu Search");
260  if ((bUpdateFound == true) || (bUpdateFound2 == true)) {
261  iAttemptCount = 0;
262  }
263  }
264  m_bIsSolutionReady = true;
265  strError += " ";
266  return true;
267 }
268 
270  CSolutionInfo initialSolution;
271  PGR_LOG("Inside gen ini sol");
272  std::vector<int> vecOrders, vecVehicles;
273  for (unsigned int i = 0; i < m_vOrderInfos.size(); i++) {
274  vecOrders.push_back(m_vOrderInfos[i].getOrderId());
275  }
276 
277  for (unsigned int i = 0; i < m_vVehicleInfos.size(); i++) {
278  vecVehicles.push_back(m_vVehicleInfos[i].getId());
279  }
280 
281  initialSolution.init(vecOrders, static_cast<int>(vecOrders.size()), vecVehicles);
282 
283  int iUnusedVehicles = static_cast<int>(initialSolution.getUnusedVehicleCount());
284  int iUnservedOrders = static_cast<int>(initialSolution.getUnservedOrderCount()); // m_viUnservedOrderIndex.size();
285  PGR_LOG("before while");
286  while (iUnusedVehicles && iUnservedOrders) {
287  CTourInfo curTour;
288 
289  int vehicleIndex = rand() % iUnusedVehicles--;
290  int vehicleInd = m_mapVehicleIdToIndex[initialSolution.getUnusedVehicleAt(vehicleIndex)];
291  curTour.setVehicleInfo(m_vVehicleInfos[vehicleInd]); // m_viUnusedVehicleIndex[vehicleIndex]
292  initialSolution.removeVehicle(vehicleIndex);
293 
294  curTour.setStartDepot(m_vDepotInfos[0].getDepotId());
295  curTour.setEndDepot(m_vDepotInfos[0].getDepotId());
296 
297  // use a random seed to start to tour. (we can use better approach in future)
298 
299  bool insertAvailable = true;
300 
301  while (insertAvailable) {
302  insertAvailable = false;
303  std::pair<int, int> PotentialInsert; // first = insert_index, second = removed_order_index;
304  std::pair<int, double> bestInsert = std::make_pair(-1, DOUBLE_MAX); // first = order_insert_index, second = cost;
305 
306  for (int i = 0; i < iUnservedOrders; ++i) {
307  int orderInd = m_mapOrderIdToIndex[initialSolution.getUnservedOrderAt(i)];
308  COrderInfo curOrder = m_vOrderInfos[orderInd];
309  std::pair<int, double> curInsert = getPotentialInsert(curTour, curOrder);
310 
311  if (curInsert.second < bestInsert.second) {
312  insertAvailable = true;
313  bestInsert = curInsert;
314  PotentialInsert = std::make_pair(curInsert.first, i);
315  }
316  }
317  if (insertAvailable) {
318  if (insertOrder(curTour, initialSolution.getUnservedOrderAt(PotentialInsert.second), PotentialInsert.first)) {
319  iUnservedOrders--;
320  initialSolution.removeOrder(PotentialInsert.second);
321  }
322  }
323  }
324 
325  initialSolution.addTour(curTour);
326  }
327 
328  return initialSolution;
329 }
330 
332  bool callUpdate = false;
333  if (curSolution.getOrderServed() > m_solutionFinal.getOrderServed()) {
334  callUpdate = true;
335  } else if (curSolution.getOrderServed() == m_solutionFinal.getOrderServed()) {
336  if (curSolution.getTotalCost() < m_solutionFinal.getTotalCost()) {
337  callUpdate = true;
338  } else if (curSolution.getTotalCost() == m_solutionFinal.getTotalCost()) {
339  if (curSolution.getTotalTravelTime() < m_solutionFinal.getTotalTravelTime()) {
340  callUpdate = true;
341  } else if (curSolution.getTotalTravelTime() == m_solutionFinal.getTotalTravelTime()) {
342  if (curSolution.getTotalDistance() < m_solutionFinal.getTotalDistance()) {
343  callUpdate = true;
344  }
345  }
346  }
347  }
348  if (callUpdate) {
349  // m_iStepsSinceLastSolution = 0;
350  m_solutionFinal = curSolution;
351 
352  // clear map and delete objects
353  // m_mpTabuCount.clear();
354  // for (std::map< CVRPTWMove*, int >::iterator it = m_mpMoveFrequency.begin();it!= m_mpMoveFrequency.end();++it)
355  // {
356  // delete (*it).first;
357  // }
358  // m_mpMoveFrequency.clear();
359  return true;
360  }
361  return false;
362 }
363 
364 std::pair<int, double> CVRPSolver::getPotentialInsert(CTourInfo& curTour, COrderInfo& curOrder) {
365  std::pair<int, double> bestInsert = std::make_pair(-1, DOUBLE_MAX);
366  if (curOrder.getOrderUnit() > curTour.getRemainingCapacity()) {
367  return bestInsert;
368  }
369  // check if ith position insert is fisible.
370  std::vector<int> vecOrderId = curTour.getOrderVector();
371  for (unsigned int i = 0; i <= vecOrderId.size(); ++i) {
372  CostPack costToOrder, costFromOrder;
373 
374  if (!i) {
375  costToOrder = getDepotToOrderCost(curTour.getStartDepot(), curOrder.getOrderId());
376  } else {
377  costToOrder = getOrderToOrderCost(vecOrderId[i-1], curOrder.getOrderId());
378  }
379 
380  double dArrivalTime = costToOrder.traveltime + curTour.getStartTime(i);
381 
382  if (dArrivalTime > curOrder.getCloseTime()) {
383  continue;
384  }
385 
386  if (i == vecOrderId.size()) {
387  costFromOrder = getOrderToDepotCost(curOrder.getOrderId(), curTour.getEndDepot());
388  } else {
389  costFromOrder = getOrderToOrderCost(curOrder.getOrderId(), vecOrderId[i]);
390  }
391 
392  dArrivalTime += curOrder.getServiceTime() + costFromOrder.traveltime;
393 
394  if (i < vecOrderId.size() && dArrivalTime > m_vOrderInfos[m_mapOrderIdToIndex[vecOrderId[i]]].getCloseTime()) {
395  continue;
396  }
397 
398  CostPack totalCost = getCostForInsert(curTour, curOrder, i);
399 
400  if (totalCost.cost < bestInsert.second) {
401  bestInsert = std::make_pair(i, totalCost.cost);
402  }
403  }
404  return bestInsert;
405 }
406 
408  m_bFoundOptimal = false;
409  updateFinalSolution(curSolution);
410 
411  int numberOfSearch = 0;
414 
415  while (numberOfSearch < TOTAL_NUMBER_OF_SEARCH) {
416  // applyBestMoveInCurrentSolution(curSolution, identifyPotentialMove(curSolution) );
417  insertUnservedOrders(curSolution);
418  // attemptFeasibleNodeExchange(curSolution);
419  attemptVehicleExchange(curSolution);
420  ++numberOfSearch;
421  }
422  return false;
423 }
424 
428 
429  updateTabuCount(bestMove);
430 
431  int totalTour = static_cast<int>(bestMove.getModifiedTourCount());
432  for (int i = 0; i < totalTour; ++i) {
433  CTourInfo tourInfo;
434  bool bIsValid = bestMove.getModifiedTourAt(i, tourInfo);
435 
436  if (bIsValid)
437  curSolution.replaceTour(tourInfo);
438  }
439  updateFinalSolution(curSolution);
440 }
441 
445  bool insertAvailable = true;
446  CMoveInfo curMove;
447  int totalUnservedOrder = static_cast<int>(m_vOrderInfos.size() - curSolution.getOrderServed());
448 
449  while (insertAvailable && totalUnservedOrder > 0) {
450  int insertTourId = -1;
451  insertAvailable = false;
452  int totalTour = static_cast<int>(curSolution.getTourInfoVector().size());
453  std::pair<int, int> PotentialInsert; // first = insert_index, second = removed_customer_index;
454  std::pair<int, double> bestInsert = std::make_pair(-1, DOUBLE_MAX); // first = customer_insert_index, second = cost;
455 
456  for (int j = 0; j < totalTour; ++j) {
457  CTourInfo curTour = curSolution.getTour(j);
458  curMove.setInitialTour(curTour);
459 
460  for (int i = 0; i < totalUnservedOrder; ++i) {
461  int ordIndex = m_mapOrderIdToIndex[curSolution.getUnservedOrderAt(i)];
462  COrderInfo curOrder = m_vOrderInfos[ordIndex];
463  std::pair<int, double> curInsert = getPotentialInsert(curTour, curOrder);
464 
465  insertOrder(curTour, i, curInsert.first);
466  curMove.setModifiedTour(curTour);
467  curMove.getInitialTour(curTour);
468 
469  // check if current move is tabu.
470  if (isTabuMove(curMove)) {
471  continue;
472  }
473 
474  if (curInsert.second < bestInsert.second) {
475  insertTourId = j;
476  insertAvailable = true;
477  bestInsert = curInsert;
478  PotentialInsert = std::make_pair(curInsert.first, i);
479  }
480  }
481  }
482  if (insertAvailable) {
483  totalUnservedOrder--;
484  curMove.setInitialTour(curSolution.getTour(insertTourId));
485 
486  addOrderAtTour(curSolution, insertTourId,
487  PotentialInsert.first,
488  PotentialInsert.second);
489 
490  curMove.setModifiedTour(curSolution.getTour(insertTourId));
491  this->updateTabuCount(curMove);
492  this->updateFinalSolution(curSolution); // this->evaluateCurrentSolution();
493  }
494  }
495 }
496 
498  int id = depotInfo.getDepotId();
499  if (m_mapDepotIdToIndex.find(id) != m_mapDepotIdToIndex.end())
500  return false;
501  m_mapDepotIdToIndex.insert(std::make_pair(id, m_vDepotInfos.size()));
502  m_vDepotInfos.push_back(depotInfo);
503 
504  return true;
505 }
506 
508  int id = orderInfo.getOrderId();
509  if (m_mapOrderIdToIndex.find(id) != m_mapOrderIdToIndex.end()) {
510  return false;
511  }
512  int index = static_cast<int>(m_vOrderInfos.size());
513  m_mapOrderIdToIndex.insert(std::make_pair(id, index));
514  m_vOrderInfos.push_back(orderInfo);
515  m_viUnservedOrderIndex.push_back(index);
516  return true;
517 }
518 
520  int id = vehicleInfo.getId();
521  if (m_mapVehicleIdToIndex.find(id) != m_mapVehicleIdToIndex.end()) {
522  return false;
523  }
524  int index = static_cast<int>(m_vVehicleInfos.size());
525  m_mapVehicleIdToIndex.insert(std::make_pair(id, index));
526  m_vVehicleInfos.push_back(vehicleInfo);
527  m_viUnusedVehicleIndex.push_back(index);
528  return true;
529 }
530 
531 bool CVRPSolver::addDepotToOrderCost(int depotId, int orderId, CostPack cost) {
532  PII depo_order = std::make_pair(depotId, orderId);
533  if (m_mapDepotToOrderrCost.find(depo_order) != m_mapDepotToOrderrCost.end()) {
534  return false;
535  }
536  m_mapDepotToOrderrCost.insert(make_pair(depo_order, cost));
537  return true;
538 }
539 
540 bool CVRPSolver::addOrderToDepotCost(int depotId, int orderId, CostPack cost) {
541  PII depo_order = std::make_pair(orderId, depotId);
542  if (m_mapOrderToDepotCost.find(depo_order) != m_mapOrderToDepotCost.end()) {
543  return false;
544  }
545  m_mapOrderToDepotCost.insert(std::make_pair(depo_order, cost));
546  return true;
547 }
548 
549 bool CVRPSolver::addOrderToOrderCost(int firstOrder, int secondOrder, CostPack cost) {
550  PII order_order = std::make_pair(firstOrder, secondOrder);
551  if (m_mapOrderToOrderCost.find(order_order) != m_mapOrderToOrderCost.end()) {
552  return false;
553  }
554  m_mapOrderToOrderCost.insert(std::make_pair(order_order, cost));
555  return true;
556 }
557 
558 bool CVRPSolver::getSolution(CSolutionInfo& solution, std::string& strError) {
559  if (m_bIsSolutionReady == true) {
560  solution = m_solutionFinal;
561  return true;
562  } else {
563  bool ret = solveVRP(strError);
564  if (ret == true) {
565  solution = m_solutionFinal;
566  return true;
567  }
568  return false;
569  }
570 }
571 
572 CostPack CVRPSolver::getDepotToOrderCost(int depotId, int orderId) {
573  PII depo_order = std::make_pair(depotId, orderId);
574 
575  if (m_mapDepotToOrderrCost.find(depo_order) != m_mapDepotToOrderrCost.end()) {
576  return(m_mapDepotToOrderrCost[depo_order]);
577  }
578  CostPack ret;
579  ret.cost = ret.distance = ret.traveltime = 1e15;
580  return ret;
581 }
582 
583 CostPack CVRPSolver::getOrderToOrderCost(int orderId1, int orderId2) {
584  PII order_order = std::make_pair(orderId1, orderId2);
585 
586  if (m_mapOrderToOrderCost.find(order_order) != m_mapOrderToOrderCost.end()) {
587  return(m_mapOrderToOrderCost[order_order]);
588  }
589  CostPack ret;
590  ret.cost = ret.distance = ret.traveltime = 1e15;
591  return ret;
592 }
593 
594 
595 CostPack CVRPSolver::getOrderToDepotCost(int depotId, int orderId) {
596  PII depo_order = std::make_pair(orderId, depotId);
597 
598  if (m_mapOrderToDepotCost.find(depo_order) != m_mapOrderToDepotCost.end()) {
599  return(m_mapOrderToDepotCost[depo_order]);
600  }
601  CostPack ret;
602  ret.cost = ret.distance = ret.traveltime = 1e15;
603  return ret;
604 }
605 
606 bool CVRPSolver::insertOrder(CTourInfo& tourInfo, int orderId, int pos) {
607  if (pos < 0 || (unsigned int) pos > tourInfo.getOrderVector().size())
608  return false;
609 
610  int orderIndex = m_mapOrderIdToIndex[orderId];
611  if (!tourInfo.getVehicleInfo().loadUnit(m_vOrderInfos[orderIndex].getOrderUnit()))
612  return false;
613  tourInfo.insertOrder(orderId, pos);
614 
615  if (!updateTourCosts(tourInfo)) {
616  tourInfo.removeOrder(pos);
617  return false;
618  }
619 
620  return true;
621 }
622 
624  std::vector<int> vecOrderId = tourInfo.getOrderVector();
625  std::vector<int> vecStartTimes;
626 
627  double dCost, dDistance, dTravelTime;
628  dCost = dDistance = dTravelTime = 0.0;
629 
630  CostPack cPack = getDepotToOrderCost(tourInfo.getStartDepot(), vecOrderId[0]);
631 
632  dCost += cPack.cost;
633  dDistance += cPack.distance;
634 
635  int ind = m_mapOrderIdToIndex[vecOrderId[0]];
636  vecStartTimes.push_back(0);
637 
638  if (dTravelTime + cPack.traveltime > m_vOrderInfos[ind].getCloseTime())
639  return false;
640 
641  dTravelTime = (std::max)(dTravelTime + cPack.traveltime + m_vOrderInfos[ind].getServiceTime(),
642  static_cast<double>(m_vOrderInfos[ind].getOpenTime() + m_vOrderInfos[ind].getServiceTime()));
643  vecStartTimes.push_back(static_cast<int>(ceil(dTravelTime)));
644 
645  unsigned int i;
646  for (i = 1; i < vecOrderId.size(); i++) {
647  cPack = getOrderToOrderCost(vecOrderId[i - 1], vecOrderId[i]);
648  dCost += cPack.cost;
649  dDistance += cPack.distance;
650 
651  ind = m_mapOrderIdToIndex[vecOrderId[i]];
652 
653  if (dTravelTime + cPack.traveltime > m_vOrderInfos[ind].getCloseTime())
654  return false;
655 
656  dTravelTime = (std::max)(dTravelTime + cPack.traveltime + m_vOrderInfos[ind].getServiceTime(),
657  static_cast<double>(m_vOrderInfos[ind].getOpenTime() + m_vOrderInfos[ind].getServiceTime()));
658 
659  vecStartTimes.push_back(static_cast<int>(ceil(dTravelTime)));
660  }
661 
662  cPack = getOrderToDepotCost(vecOrderId[i - 1], tourInfo.getEndDepot());
663  dCost += cPack.cost;
664  dDistance += cPack.distance;
665 
666  dTravelTime += cPack.traveltime;
667 
668  vecStartTimes.push_back(static_cast<int>(ceil(dTravelTime)));
669  ind = m_mapDepotIdToIndex[tourInfo.getEndDepot()];
670  if (dTravelTime > m_vDepotInfos[ind].getCloseTime())
671  return false;
672 
673  tourInfo.updateCost(dCost, dDistance, dTravelTime);
674 
675  tourInfo.setStartTime(vecStartTimes);
676 
677  return true;
678 }
679 
680 bool CVRPSolver::addOrderAtTour(CSolutionInfo &solutionInfo, int tourIndex, int insertIndex, int orderIndex) {
681  return(insertOrder(solutionInfo.getTour(tourIndex), m_vOrderInfos[orderIndex].getOrderId(), insertIndex));
682 }
683 
685  std::vector<int> vecOrderId = curTour.getOrderVector();
686 
687  vecOrderId.insert(vecOrderId.begin() + pos, curOrder.getOrderId());
688  double dCost, dDistance, dTravelTime;
689  dCost = dDistance = dTravelTime = 0.0;
690  CostPack costRet;
691 
692  costRet.cost = INF;
693  costRet.distance = INF;
694  costRet.traveltime = INF;
695 
696  CostPack cPack = getDepotToOrderCost(curTour.getStartDepot(), vecOrderId[0]);
697 
698  dCost += cPack.cost;
699  dDistance += cPack.distance;
700 
701  int ind = m_mapOrderIdToIndex[vecOrderId[0]];
702 
703  if (dTravelTime + cPack.traveltime > m_vOrderInfos[ind].getCloseTime())
704  return costRet;
705 
706  dTravelTime = (std::max)(dTravelTime + cPack.traveltime + m_vOrderInfos[ind].getServiceTime(),
707  static_cast<double>(m_vOrderInfos[ind].getOpenTime() + m_vOrderInfos[ind].getServiceTime()));
708 
709  unsigned int i;
710  for (i = 1; i < vecOrderId.size(); i++) {
711  cPack = getOrderToOrderCost(vecOrderId[i - 1], vecOrderId[i]);
712  dCost += cPack.cost;
713  dDistance += cPack.distance;
714 
715  ind = m_mapOrderIdToIndex[vecOrderId[i]];
716 
717  if (dTravelTime + cPack.traveltime > m_vOrderInfos[ind].getCloseTime())
718  return costRet;
719 
720  dTravelTime = (std::max)(dTravelTime + cPack.traveltime + m_vOrderInfos[ind].getServiceTime(),
721  static_cast<double>(m_vOrderInfos[ind].getOpenTime() + m_vOrderInfos[ind].getServiceTime()));
722  }
723 
724  cPack = getOrderToDepotCost(vecOrderId[i - 1], curTour.getEndDepot());
725  dCost += cPack.cost;
726  dDistance += cPack.distance;
727 
728  dTravelTime += cPack.traveltime;
729 
730  ind = m_mapDepotIdToIndex[curTour.getEndDepot()];
731  if (dTravelTime > m_vDepotInfos[ind].getCloseTime())
732  return costRet;
733 
734  costRet.cost = dCost - curTour.getCost();
735  costRet.distance = dDistance - curTour.getDistance();
736  costRet.traveltime = dTravelTime - curTour.getTravelTime();
737 
738  return costRet;
739 }
740 
744  CMoveInfo curMove;
745  CMoveInfo bestMove;
746 
747  int bestFreeCapacity = 0;
748  std::pair<int, int> bestSwapIndex;
749  int totalTour = static_cast<int>(solutionInfo.getTourCount());
750 
751  for (int i = 0; i < totalTour; ++i) {
752  CTourInfo firstTour = solutionInfo.getTour(i);
753  int firstTourLoad = firstTour.getVehicleInfo().getCurrentLoad();
754  int firstVehicleCapacity = firstTour.getVehicleInfo().getCapacity();
755 
756  for (int j = i + 1; j < totalTour; ++j) {
757  CTourInfo secondTour = solutionInfo.getTour(j);
758  curMove.setInitialTour(firstTour, secondTour);
759 
760  int FirstTourRemainingCapacity = firstVehicleCapacity - secondTour.getVehicleInfo().getCurrentLoad();
761 
762  int SecondTourRemainingCapacity = secondTour.getVehicleInfo().getCapacity() - firstTourLoad;
763 
764  // int prevFreeCapacity = max(secondTour.getRemainingCapacity(), firstTour.getRemainingCapacity() );
765 
766  int curFreeCapacity = (std::max)(FirstTourRemainingCapacity, SecondTourRemainingCapacity);
767 
768  if ((FirstTourRemainingCapacity > 0) && (SecondTourRemainingCapacity > 0) &&
769  // curFreeCapacity > curFreeCapacity autological compare evaluates to false (error on MAC)
770  (curFreeCapacity > bestFreeCapacity)) {
771  CVehicleInfo tempVehicle = m_vVehicleInfos[firstTour.getVehicleId()];
772  firstTour.setVehicleInfo(m_vVehicleInfos[secondTour.getVehicleId()]);
773  secondTour.setVehicleInfo(tempVehicle);
774 
775  curMove.setModifiedTour(firstTour, secondTour);
776 
777  if (!isTabuMove(curMove)) {
778  bestMove = curMove;
779  bestFreeCapacity = curFreeCapacity;
780  bestSwapIndex = std::make_pair(i, j);
781  }
782 
783  curMove.getInitialTour(firstTour, secondTour);
784  }
785  }
786  }
787  if (bestFreeCapacity > 0) {
788  CTourInfo tempTour;
789  bestMove.getModifiedTourAt(0, tempTour);
790  solutionInfo.replaceTourAt(bestSwapIndex.first, tempTour);
791  bestMove.getModifiedTourAt(1, tempTour);
792  solutionInfo.replaceTourAt(bestSwapIndex.second, tempTour);
793  updateTabuCount(bestMove);
794  updateFinalSolution(solutionInfo);
795  }
796 }
797 #if 0
798 void CVRPSolver::attemptFeasibleNodeExchange(CSolutionInfo& solutionInfo) {
801  CMoveInfo bestMove, curMove;
802 
803  int totalTour = solutionInfo.getTourCount();
804 
805  for (int i = 0; i < totalTour; ++i) {
806  CTourInfo curTour = solutionInfo.getTour(i);
807  std::vector<int> vecOrderId = curTour.getOrderVector();
808  curMove.setInitialTour(curTour);
809  int totalCustomer = curTour.getServedOrderCount();
810  std::pair<int, int> bestSwapIndex;
811  double lowestCost = DOUBLE_MAX;
812 
813  for (int j = 0; j < totalCustomer; ++j) {
814  for (int k = j + 1; k < totalCustomer; ++k) {
815  COrderInfo firstCustomer = m_vOrderInfos[m_mapOrderIdToIndex[vecOrderId[j]]];
816  COrderInfo secondCustomer = m_vOrderInfos[m_mapOrderIdToIndex[vecOrderId[k]]];
817 
818  if (curTour->isFeasibleReplace(j, pSecondCustomer) && pCurTour->isFeasibleReplace(k, pFirstCustomer)) {
819  pCurTour->removeCustomer(j, false);
820  pCurTour->addCustomer(pSecondCustomer, j);
821 
822  pCurTour->removeCustomer(k, false);
823  pCurTour->addCustomer(pFirstCustomer, k);
824 
825  pCurMove->setModifiedTour(pCurTour);
826  if (isTabuMove(pCurMove)) {
827  pCurMove->getInitialTour(pCurTour);
828  continue;
829  }
830 
831  double curTourCost = pCurTour->getTourData()->calcCost(pCurTour->getAssignedVehicle());
832  if (curTourCost < lowestCost) {
833  *pBestMove = *pCurMove;
834  lowestCost = curTourCost;
835  bestSwapIndex = std::make_pair(j, k);
836  }
837  pCurMove->getInitialTour(pCurTour);
838  }
839  }
840  }
841 
842  if (lowestCost!= DOUBLE_MAX) {
843  m_pCurrentSolution->replaceTourAt(i, pBestMove->getModifiedTourAt(0));
844  this->updateTabuCount(pBestMove);
845  this->evaluateCurrentSolution();
846  }
847  }
848  delete pCurMove;
849  delete pBestMove;
850 }
851 #endif
852 
854  m_veMoves.push_back(bestMove);
855 #if 0
856  bestMove.reverseMove();
857  CMoveInfo curMove;
858 
859  std::map< CMoveInfo, int >::iterator mpIt = m_mapMoveFrequency.find(bestMove);
860 
861  if (mpIt == m_mapMoveFrequency.end()) {
862  curMove = bestMove;
863  } else {
864  curMove = (*mpIt).first;
865  }
866 
867  m_mapMoveFrequency[curMove]++;
868 
869  if (m_mapMoveFrequency[curMove] >= MAXIMUM_MOVE_FREQUENCY) {
870  CMoveInfo tmpMove;
871  std::set<CMoveInfo>::iterator sIt = m_sTabuList.find(curMove);
872 
873  CMoveInfo tmpMove2;
874  if (sIt == m_sTabuList.end()) {
875  tmpMove2 = curMove;
876  } else {
877  tmpMove2 = (*sIt);
878  }
879  m_sTabuList.insert(tmpMove2);
880  }
881  m_mapTabuCount[curMove] = std::make_pair(m_iGeneratedSolutionCount, m_iStepsSinceLastSolution);
882  bestMove.reverseMove();
883  */
884 #endif
885 }
886 
888  size_t i, tot = m_veMoves.size();
889  for (i = 0; i < tot; i++) {
890  if (curMove == m_veMoves[i])
891  return true;
892  }
893  return false;
894 }
895 
896 
std::pair< int, double > getPotentialInsert(CTourInfo &curTour, COrderInfo &curOrder)
Definition: VRP_Solver.cpp:364
std::vector< int > m_vUnusedVehicles
Definition: VRP_Solver.h:281
int getId()
Definition: VRP_Solver.h:73
#define PGR_LOG(str)
Definition: pgr_logger.h:72
int getStartTime(int pos)
Definition: VRP_Solver.h:205
bool insertOrder(CTourInfo &tourInfo, int orderId, int pos)
Definition: VRP_Solver.cpp:606
std::vector< CTourInfo > getTourInfoVector()
Definition: VRP_Solver.h:273
int m_iGeneratedSolutionCount
Definition: VRP_Solver.h:409
int m_iOrdersServed
Definition: VRP_Solver.h:283
#define DOUBLE_MAX
Definition: VRP_Solver.cpp:43
int m_iVehicleId
Definition: VRP_Solver.h:88
CTourInfo & getTour(int pos)
Definition: VRP_Solver.h:250
int m_iVehicleUsed
Definition: VRP_Solver.h:282
size_t getUnservedOrderCount()
Definition: VRP_Solver.h:254
CostPack getOrderToDepotCost(int depotId, int orderId)
Definition: VRP_Solver.cpp:595
std::vector< CTourInfo > m_vInitialTour
Definition: VRP_Solver.h:324
bool getSolution(CSolutionInfo &solution, std::string &strError)
Definition: VRP_Solver.cpp:558
std::pair< int, int > PII
Definition: VRP_Solver.h:42
double m_dTotalDistance
Definition: VRP_Solver.h:232
int m_iTotalOrders
Definition: VRP_Solver.h:284
int getOrderId()
Definition: VRP_Solver.h:115
std::vector< int > m_viOrderIds
Definition: VRP_Solver.h:229
CVehicleInfo & getVehicleInfo()
Definition: VRP_Solver.h:177
double m_dTotalDistance
Definition: VRP_Solver.h:286
void applyBestMoveInCurrentSolution(CSolutionInfo &solutionInfo, CMoveInfo &bestMove)
Definition: VRP_Solver.cpp:425
double m_dTotalCost
Definition: VRP_Solver.h:285
std::vector< int > m_vUnservedOrderId
Definition: VRP_Solver.h:280
int getRemainingCapacity()
Definition: VRP_Solver.h:66
#define MAXIMUM_TRY
Definition: VRP_Solver.h:36
void updateTabuCount(CMoveInfo &bestMove)
Definition: VRP_Solver.cpp:853
#define INF
bool loadUnit(int lUnit)
Definition: VRP_Solver.cpp:78
bool insertOrder(int orderId, int pos)
Definition: VRP_Solver.cpp:98
bool tabuSearch(CSolutionInfo &solutionInfo)
Definition: VRP_Solver.cpp:407
double distance
Definition: VRP_Solver.h:51
int m_iCurrentLoad
Definition: VRP_Solver.h:87
void getInitialTour(CTourInfo &TourData)
Definition: VRP_Solver.cpp:206
std::vector< CTourInfo > m_vtourAll
Definition: VRP_Solver.h:279
void updateCost(double cost, double distance, double travelTime)
Definition: VRP_Solver.cpp:112
int getOrderServed()
Definition: VRP_Solver.h:246
bool operator==(const CTourInfo &cur, const CTourInfo &that)
Definition: VRP_Solver.cpp:49
std::map< std::pair< int, int >, CostPack > m_mapDepotToOrderrCost
Definition: VRP_Solver.h:392
bool solveVRP(std::string &strError)
Definition: VRP_Solver.cpp:232
bool m_bFoundOptimal
Definition: VRP_Solver.h:411
int getDepotId()
Definition: VRP_Solver.h:146
bool addOrder(COrderInfo orderInfo)
Definition: VRP_Solver.cpp:507
double getCost()
Definition: VRP_Solver.h:199
double getTotalDistance()
Definition: VRP_Solver.h:263
void setModifiedTour(CTourInfo pTourData)
Definition: VRP_Solver.cpp:195
CVehicleInfo m_vehicleInfo
Definition: VRP_Solver.h:225
double getTravelTime()
Definition: VRP_Solver.h:201
int getUnusedVehicleAt(int pos)
Definition: VRP_Solver.h:257
int getEndDepot()
Definition: VRP_Solver.h:183
double cost
Definition: VRP_Solver.h:51
int getCurrentLoad()
Definition: VRP_Solver.h:68
void setStartTime(std::vector< int > vStartTime)
Definition: VRP_Solver.h:190
bool operator!=(const CVehicleInfo &cur, const CVehicleInfo &that)
Definition: VRP_Solver.cpp:45
void setInitialTour(CTourInfo pTourData)
Definition: VRP_Solver.cpp:184
size_t getServedOrderCount()
Definition: VRP_Solver.h:186
std::map< int, int > m_mapDepotIdToIndex
Definition: VRP_Solver.h:389
bool addVehicle(CVehicleInfo vehicleInfo)
Definition: VRP_Solver.cpp:519
double getTotalTravelTime()
Definition: VRP_Solver.h:264
int getCapacity()
Definition: VRP_Solver.h:70
void replaceTourAt(int index, CTourInfo curTour)
Definition: VRP_Solver.cpp:132
CSolutionInfo m_solutionFinal
Definition: VRP_Solver.h:404
std::map< std::pair< int, int >, CostPack > m_mapOrderToDepotCost
Definition: VRP_Solver.h:393
double m_dTotalTravelTime
Definition: VRP_Solver.h:287
std::map< int, int > m_mapVehicleIdToIndex
Definition: VRP_Solver.h:388
bool addDepot(CDepotInfo depotInfo)
Definition: VRP_Solver.cpp:497
std::vector< CMoveInfo > m_veMoves
Definition: VRP_Solver.h:401
std::vector< int > getOrderVector()
Definition: VRP_Solver.h:203
double getTotalCost()
Definition: VRP_Solver.h:262
bool addOrderToOrderCost(int firstOrder, int secondOrder, CostPack cost)
Definition: VRP_Solver.cpp:549
std::vector< CVehicleInfo > m_vVehicleInfos
Definition: VRP_Solver.h:383
double m_dTotalTraveltime
Definition: VRP_Solver.h:233
bool addOrderToDepotCost(int depotId, int orderId, CostPack cost)
Definition: VRP_Solver.cpp:540
int getRemainingCapacity()
Definition: VRP_Solver.cpp:103
void insertUnservedOrders(CSolutionInfo &solutionInfo)
Definition: VRP_Solver.cpp:442
bool updateFinalSolution(CSolutionInfo &solutionInfo)
Definition: VRP_Solver.cpp:331
int getServiceTime()
Definition: VRP_Solver.h:106
bool m_bIsSolutionReady
Definition: VRP_Solver.h:403
static size_t rand(size_t n)
Definition: pgr_tsp.cpp:55
size_t getModifiedTourCount() const
Definition: VRP_Solver.h:304
int m_iCapacity
Definition: VRP_Solver.h:86
void reverseMove()
std::map< std::pair< int, int >, CostPack > m_mapOrderToOrderCost
Definition: VRP_Solver.h:391
std::vector< int > m_viUnservedOrderIndex
Definition: VRP_Solver.h:407
CostPack getDepotToOrderCost(int depotId, int orderId)
Definition: VRP_Solver.cpp:572
bool removeOrder(int pos)
Definition: VRP_Solver.cpp:107
size_t getTourCount()
Definition: VRP_Solver.h:252
void removeOrder(int pos)
Definition: VRP_Solver.h:260
void setStartDepot(int depotId)
Definition: VRP_Solver.h:181
bool getModifiedTourAt(int index, CTourInfo &tourInfo)
Definition: VRP_Solver.cpp:215
void setVehicleInfo(CVehicleInfo vehicleInfo)
Definition: VRP_Solver.h:178
double traveltime
Definition: VRP_Solver.h:51
void setEndDepot(int depotId)
Definition: VRP_Solver.h:184
size_t getUnusedVehicleCount()
Definition: VRP_Solver.h:255
bool updateTourCosts(CTourInfo &tourInfo)
Definition: VRP_Solver.cpp:623
bool addDepotToOrderCost(int depotId, int orderId, CostPack cost)
Definition: VRP_Solver.cpp:531
void attemptVehicleExchange(CSolutionInfo &solutionInfo)
Definition: VRP_Solver.cpp:741
std::vector< int > m_viUnusedVehicleIndex
Definition: VRP_Solver.h:408
int getStartDepot()
Definition: VRP_Solver.h:180
bool init(std::vector< int > vecOrder, int iTotalOrder, std::vector< int > vecVehicle)
Definition: VRP_Solver.cpp:138
int getCloseTime()
Definition: VRP_Solver.h:103
#define MAXIMUM_MOVE_FREQUENCY
Definition: VRP_Solver.h:38
bool addTour(CTourInfo &tour)
Definition: VRP_Solver.cpp:153
#define TOTAL_NUMBER_OF_SEARCH
Definition: VRP_Solver.h:37
void replaceTour(CTourInfo curTour)
Definition: VRP_Solver.cpp:121
void removeVehicle(int pos)
Definition: VRP_Solver.h:259
CostPack getCostForInsert(CTourInfo &curTour, COrderInfo &curOrder, int pos)
Definition: VRP_Solver.cpp:684
double getDistance()
Definition: VRP_Solver.h:197
int getVehicleId()
Definition: VRP_Solver.h:175
int getOrderUnit()
Definition: VRP_Solver.h:109
double m_dTotalCost
Definition: VRP_Solver.h:231
int getUnservedOrderAt(int pos)
Definition: VRP_Solver.h:265
std::vector< COrderInfo > m_vOrderInfos
Definition: VRP_Solver.h:384
int m_iStepsSinceLastSolution
Definition: VRP_Solver.h:410
std::vector< CTourInfo > m_vModifiedTour
Definition: VRP_Solver.h:325
std::map< int, int > m_mapOrderIdToIndex
Definition: VRP_Solver.h:387
std::vector< CDepotInfo > m_vDepotInfos
Definition: VRP_Solver.h:385
bool addOrderAtTour(CSolutionInfo &solutionInfo, int tourIndex, int insertIndex, int orderIndex)
Definition: VRP_Solver.cpp:680
CostPack getOrderToOrderCost(int firstOrder, int secondOrder)
Definition: VRP_Solver.cpp:583
bool isTabuMove(CMoveInfo &curMove)
Definition: VRP_Solver.cpp:887
CSolutionInfo generateInitialSolution()
Definition: VRP_Solver.cpp:269