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