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