-
Notifications
You must be signed in to change notification settings - Fork 2
Expand file tree
/
Copy pathEvcSolver.Method.cpp
More file actions
1034 lines (914 loc) · 44.9 KB
/
Copy pathEvcSolver.Method.cpp
File metadata and controls
1034 lines (914 loc) · 44.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// ===============================================================================================
// Evacuation Solver: CASPER implementation
// Description: Core of the CASPER algorithm implementation
//
// Copyright (C) 2014 Kaveh Shahabi
// Distributed under the Apache Software License, Version 2.0. (See accompanying file LICENSE.txt)
//
// Author: Kaveh Shahabi
// URL: http://github.com/spatial-computing/CASPER
// ===============================================================================================
#include "stdafx.h"
#include "NameConstants.h"
#include "EvcSolver.h"
#include "FibonacciHeap.h"
HRESULT EvcSolver::SolveMethod(INetworkQueryPtr ipNetworkQuery, IGPMessages* pMessages, ITrackCancel* pTrackCancel, IStepProgressorPtr ipStepProgressor, std::shared_ptr<EvacueeList> AllEvacuees,
std::shared_ptr<NAVertexCache> vcache, std::shared_ptr<NAEdgeCache> ecache, std::shared_ptr<SafeZoneTable> safeZoneList, double & carmaSec, std::vector<unsigned int> & CARMAExtractCounts,
INetworkDatasetPtr ipNetworkDataset, unsigned int & EvacueesWithRestrictedSafezone, std::vector<double> & GlobalEvcCostAtIteration,
std::vector<size_t> & EffectiveIterationCount, std::shared_ptr<DynamicDisaster> dynamicDisasters)
{
// creating the heap for the Dijkstra search
MyFibonacciHeap<NAEdgePtr, NAEdgePtrHasher, NAEdgePtrEqual> heap(NAEdge::GetHeapKeyHur);
NAEdgeMap closedList;
auto carmaClosedList = std::shared_ptr<NAEdgeMapTwoGen>(new DEBUG_NEW_PLACEMENT NAEdgeMapTwoGen());
NAVertexPtr neighbor = nullptr, finalVertex = nullptr, myVertex = nullptr;
SafeZonePtr BetterSafeZone = nullptr;
NAEdgePtr myEdge = nullptr;
HRESULT hr = S_OK;
VARIANT_BOOL keepGoing;
double populationLeft, population2Route, TimeToBeat = 0.0f, newCost, globalMinPop2Route = 0.0, minPop2Route = -1.0, globalDeltaCost = 0.0, MaxPathCostSoFar = 0.0, addedCostAsPenalty = 0.0, EvcStartTime = 0.0;
std::vector<NAVertexPtr>::const_iterator vit;
INetworkJunctionPtr ipCurrentJunction = nullptr;
INetworkElementPtr ipJunctionElement = nullptr;
bool separationRequired, foundRestrictedSafezone;
auto sortedEvacuees = std::shared_ptr<std::vector<EvacueePtr>>(new DEBUG_NEW_PLACEMENT std::vector<EvacueePtr>());
unsigned int countEvacueesInOneBucket = 0, countCASPERLoops = 0, sumVisitedDirtyEdge = 0;
int pathGenerationCount = -1, EvacueeProcessOrder = -1;
size_t CARMAClosedSize = 0, sumVisitedEdge = 0, NumberOfEvacueesInIteration = 0, LocalIteration = 0;
long progressBaseValue = 0l;
auto leafs = std::shared_ptr<NAEdgeContainer>(new DEBUG_NEW_PLACEMENT NAEdgeContainer(200));
std::vector<NAEdgePtr> readyEdges;
HANDLE proc = GetCurrentProcess();
BOOL dummy;
FILETIME cpuTimeS, cpuTimeE, sysTimeS, sysTimeE, createTime, exitTime;
ArrayList<NAEdgePtr> * adj = nullptr;
ATL::CString statusMsg, AlgName;
CARMASort RevisedCarmaSortCriteria = this->CarmaSortCriteria;
auto detachedPaths = std::shared_ptr<std::vector<EvcPathPtr>>(new DEBUG_NEW_PLACEMENT std::vector<EvcPathPtr>());
CARMAExtractCounts.clear();
switch (solverMethod)
{
case EvcSolverMethod::CASPERSolver:
AlgName = _T("CASPER");
break;
case EvcSolverMethod::SPSolver:
AlgName = _T("SP");
break;
case EvcSolverMethod::CCRPSolver:
AlgName = _T("CCRP");
break;
default:
AlgName = _T("the");
break;
}
// initialize all dynamic changes and prepare for loop
size_t countDynamic = dynamicDisasters->ResetDynamicChanges();
// Setup a message on our step progress bar indicating that we are traversing the network
if (ipStepProgressor && !AllEvacuees->empty())
{
// Setup our progress bar based on the number of Evacuee points
if (FAILED(hr = ipStepProgressor->put_MinRange(0))) goto END_OF_FUNC;
if (FAILED(hr = ipStepProgressor->put_MaxRange((long)(countDynamic * AllEvacuees->size())))) goto END_OF_FUNC;
if (FAILED(hr = ipStepProgressor->put_StepValue(1))) goto END_OF_FUNC;
}
sortedEvacuees->reserve(AllEvacuees->size());
EvacueesWithRestrictedSafezone = 0;
if (FAILED(hr = ipNetworkQuery->CreateNetworkElement(esriNETJunction, &ipJunctionElement))) goto END_OF_FUNC;
ipCurrentJunction = ipJunctionElement;
if (FAILED(hr = DeterminMinimumPop2Route(AllEvacuees, ipNetworkDataset, globalMinPop2Route, separationRequired))) goto END_OF_FUNC;
// dynamic CASPER loop
for (NumberOfEvacueesInIteration = dynamicDisasters->NextDynamicChange(AllEvacuees, ecache, EvcStartTime, pathGenerationCount); NumberOfEvacueesInIteration > 0;
NumberOfEvacueesInIteration = dynamicDisasters->NextDynamicChange(AllEvacuees, ecache, EvcStartTime, pathGenerationCount))
{
LocalIteration = 0;
minPop2Route = -1.0; // this will insure that the first CARMA after each dynamic change will be FullSPT
/// Let's do an experiment and see if this is needed
RevisedCarmaSortCriteria = this->CarmaSortCriteria;
do // iteration loop
{
if (ipStepProgressor)
{
if (FAILED(hr = ipStepProgressor->put_Position(progressBaseValue + (long)(AllEvacuees->size() - NumberOfEvacueesInIteration)))) goto END_OF_FUNC;
statusMsg.Format(_T("Performing %s search (time %.2f, pass %d)"), AlgName, EvcStartTime, GlobalEvcCostAtIteration.size() + 1);
}
do
{
// Indexing all the population by their surrounding vertices this will be used to sort them by network distance to safe zone. Also time the carma loops.
dummy = GetProcessTimes(proc, &createTime, &exitTime, &sysTimeS, &cpuTimeS);
if (FAILED(hr = CARMALoop(ipNetworkQuery, ipStepProgressor, pMessages, pTrackCancel, AllEvacuees, RevisedCarmaSortCriteria, sortedEvacuees, vcache, ecache, safeZoneList, CARMAClosedSize,
carmaClosedList, leafs, CARMAExtractCounts, globalMinPop2Route, minPop2Route, separationRequired))) goto END_OF_FUNC;
dummy = GetProcessTimes(proc, &createTime, &exitTime, &sysTimeE, &cpuTimeE);
carmaSec += (*((__int64 *)&cpuTimeE)) - (*((__int64 *)&cpuTimeS)) + (*((__int64 *)&sysTimeE)) - (*((__int64 *)&sysTimeS));
if (ipStepProgressor) { if (FAILED(hr = ipStepProgressor->put_Message(ATL::CComBSTR(statusMsg)))) goto END_OF_FUNC; }
countEvacueesInOneBucket = 0;
sumVisitedDirtyEdge = 0;
sumVisitedEdge = 0;
for (const auto currentEvacuee : *sortedEvacuees)
{
// Check to see if the user wishes to continue or cancel the solve (i.e., check whether or not the user has hit the ESC key to stop processing)
if (pTrackCancel)
{
if (FAILED(hr = pTrackCancel->Continue(&keepGoing))) goto END_OF_FUNC;
if (keepGoing == VARIANT_FALSE)
{
hr = E_ABORT;
goto END_OF_FUNC;
}
}
_ASSERT_EXPR(currentEvacuee->Status != EvacueeStatus::CARMALooking, L"CARMA did not make up his mind on this evacuee");
if (currentEvacuee->Status != EvacueeStatus::Unprocessed) continue;
// Step the progress bar before continuing to the next Evacuee point
if (ipStepProgressor) ipStepProgressor->Step();
currentEvacuee->ProcessOrder = ++EvacueeProcessOrder;
MaxPathCostSoFar = max(MaxPathCostSoFar, currentEvacuee->PredictedCost);
countEvacueesInOneBucket++;
countCASPERLoops++;
populationLeft = currentEvacuee->Population;
while (populationLeft > 0.0)
{
// It's now safe to collect-n-clean on the graph (ecache & vcache).
// clean used-up vertices from GC
vcache->CollectAndRelease();
// the next 'if' is a distinctive feature by CASPER that CCRP does not have
// and can actually improve routes even with a STEP traffic model
if (this->solverMethod == EvcSolverMethod::CCRPSolver) population2Route = 1.0;
else if (this->solverMethod == EvcSolverMethod::CASPERSolver && separationRequired)
{
if (populationLeft - globalMinPop2Route < globalMinPop2Route) population2Route = populationLeft;
else population2Route = globalMinPop2Route;
}
else population2Route = populationLeft;
// populate the heap with vertices associated with the current evacuee
readyEdges.clear();
for (auto const & v : *(currentEvacuee->VerticesAndRatio))
if (FAILED(hr = PrepareVerticesForHeap(v, vcache, ecache, &closedList, readyEdges, population2Route, solverMethod, selfishRatio, MaxPathCostSoFar, QueryDirection::Backward))) goto END_OF_FUNC;
for (const auto & e : readyEdges) heap.Insert(e);
TimeToBeat = CASPER_INFINITY;
BetterSafeZone = nullptr;
finalVertex = nullptr;
foundRestrictedSafezone = false;
// reduce the effect of previous CASPER loop heap extract for the purpose of dirty edge ratio. This will encourage more CARMA loops.
sumVisitedDirtyEdge = (unsigned int)(sumVisitedDirtyEdge * 0.9);
sumVisitedEdge = (size_t)(sumVisitedEdge * 0.9);
// Continue traversing the network while the heap has remaining junctions in it
// this is the actual Dijkstra code with the Fibonacci Heap
while (!heap.empty())
{
// Remove the next junction EID from the top of the stack
myEdge = heap.DeleteMin();
myVertex = myEdge->ToVertex;
_ASSERT_EXPR(!closedList.Exist(myEdge), L"closedList violation happened");
if (FAILED(hr = closedList.Insert(myEdge)))
{
// closedList violation happened
pMessages->AddError(-myEdge->EID, ATL::CComBSTR(L"ClosedList Violation Error."));
hr = ATL::AtlReportError(this->GetObjectCLSID(), _T("ClosedList Violation Error."), IID_INASolver);
goto END_OF_FUNC;
}
if (myEdge->GetDirtyState() != EdgeDirtyState::CleanState) sumVisitedDirtyEdge++;
// Check for destinations. If a new destination has been found then we should
// first flag this so later we can use to generate route. Also we should
// update the new TimeToBeat value for proper termination.
if (safeZoneList->CheckDiscoveredSafePoint(ecache, myVertex, myEdge, finalVertex, TimeToBeat, BetterSafeZone, costPerDensity,
population2Route, solverMethod, globalDeltaCost, foundRestrictedSafezone)) UpdatePeakMemoryUsage();
if (FAILED(hr = ecache->QueryAdjacencies(myVertex, myEdge, QueryDirection::Forward, &adj))) goto END_OF_FUNC;
for (const auto & currentEdge : *adj)
{
// if edge has already been discovered then no need to heap it
if (closedList.Exist(currentEdge)) continue;
newCost = myVertex->GVal + currentEdge->GetCost(population2Route, this->solverMethod, &globalDeltaCost);
if (newCost >= CASPER_INFINITY) continue;
if (heap.IsVisited(currentEdge)) // edge has been visited before. update edge and decrease key.
{
neighbor = currentEdge->ToVertex;
addedCostAsPenalty = currentEdge->MaxAddedCostOnReservedPathsWithNewFlow(globalDeltaCost, MaxPathCostSoFar, newCost + neighbor->GetMinHOrZero(), this->selfishRatio);
if (neighbor->GVal + neighbor->GlobalPenaltyCost > newCost + addedCostAsPenalty + myVertex->GlobalPenaltyCost)
{
neighbor->SetBehindEdge(currentEdge);
neighbor->GVal = newCost;
neighbor->GlobalPenaltyCost = myVertex->GlobalPenaltyCost + addedCostAsPenalty;
neighbor->Previous = myVertex;
heap.UpdateKey(currentEdge);
}
}
else // unvisited edge. create new and insert in heap
{
if (FAILED(hr = currentEdge->NetEdge->QueryJunctions(nullptr, ipCurrentJunction))) goto END_OF_FUNC;
neighbor = vcache->New(ipCurrentJunction, ipNetworkQuery);
neighbor->SetBehindEdge(currentEdge);
addedCostAsPenalty = currentEdge->MaxAddedCostOnReservedPathsWithNewFlow(globalDeltaCost, MaxPathCostSoFar, newCost + neighbor->GetMinHOrZero(), this->selfishRatio);
neighbor->GlobalPenaltyCost = myVertex->GlobalPenaltyCost + addedCostAsPenalty;
neighbor->GVal = newCost;
neighbor->Previous = myVertex;
// Termination Condition: If the new vertex does have a chance to beat the already discovered safe node then add it to the heap.
if (NAEdge::GetHeapKeyHur(currentEdge) <= TimeToBeat) heap.Insert(currentEdge);
}
}
}
// collect info for Carma
sumVisitedEdge += closedList.Size();
// Find a path despite the fact that a safe zone (restricted) was found
// Address issue number 4: http://github.com/spatial-computing/CASPER/issues/4
if (!BetterSafeZone && foundRestrictedSafezone) ++EvacueesWithRestrictedSafezone;
// Generate path for this evacuee if any found
if (GeneratePath(BetterSafeZone, finalVertex, populationLeft, pathGenerationCount, currentEvacuee, population2Route, separationRequired))
MaxPathCostSoFar = max(MaxPathCostSoFar, currentEvacuee->Paths->front()->GetReserveEvacuationCost());
else currentEvacuee->Status = EvacueeStatus::Unreachable;
#ifdef DEBUG
std::wostringstream os_;
os_.precision(3);
os_ << "CARMALoop stat " << countEvacueesInOneBucket << ": " << (int)sumVisitedEdge << ',' << (int)sumVisitedDirtyEdge << ',' << sumVisitedDirtyEdge / (CARMAPerformanceRatio * sumVisitedEdge) << std::endl;
OutputDebugStringW(os_.str().c_str());
#endif
#ifdef TRACE
std::ofstream f;
f.open("c:\\evcsolver.log", std::ios_base::out | std::ios_base::app);
f.precision(3);
f << "CARMALoop stat " << countEvacueesInOneBucket << ": " << (int)sumVisitedEdge << ',' << (int)sumVisitedDirtyEdge << ',' << sumVisitedDirtyEdge / (CARMAPerformanceRatio * sumVisitedEdge) << std::endl;
f.close();
#endif
// cleanup search heap and closed-list
UpdatePeakMemoryUsage();
heap.Clear();
closedList.Clear();
} // end of while loop for multiple routes single evacuee
if (currentEvacuee->Status == EvacueeStatus::Unprocessed) currentEvacuee->Status = EvacueeStatus::Processed;
// determine if the previous round of DJs where fast enough and if not break out of the loop and have CARMALoop do something about it
if (this->solverMethod == EvcSolverMethod::CASPERSolver && sumVisitedDirtyEdge > this->CARMAPerformanceRatio * sumVisitedEdge) break;
} // end of for loop over sortedEvacuees
} while (!sortedEvacuees->empty());
UpdatePeakMemoryUsage();
// figure out how may of paths need to be detached and process again
NumberOfEvacueesInIteration = FindPathsThatNeedToBeProcessedInIteration(AllEvacuees, detachedPaths, GlobalEvcCostAtIteration, LocalIteration);
if (NumberOfEvacueesInIteration > 0)
{
RevisedCarmaSortCriteria = CARMASort::ReverseFinalCost;
EffectiveIterationCount.push_back(NumberOfEvacueesInIteration);
}
} while (NumberOfEvacueesInIteration > 0);
progressBaseValue += (long)AllEvacuees->size();
}
END_OF_FUNC:
_ASSERT_EXPR(hr >= 0 || hr == E_ABORT, L"SolveMethod function exit with error");
#ifdef TRACE
std::ofstream f;
f.open("c:\\evcsolver.log", std::ios_base::out | std::ios_base::app);
f << "Search exit: " << hr << std::endl;
f.close();
#endif
carmaSec = carmaSec / 10000000.0;
return hr;
}
size_t EvcSolver::FindPathsThatNeedToBeProcessedInIteration(std::shared_ptr<EvacueeList> AllEvacuees, std::shared_ptr<std::vector<EvcPathPtr>> detachedPaths,
std::vector<double> & GlobalEvcCostAtIteration, size_t & LocalIteration) const
{
std::vector<EvcPathPtr> allPaths;
std::vector<EvacueePtr> EvacueesForNextIteration;
std::unordered_set<NAEdgePtr, NAEdgePtrHasher, NAEdgePtrEqual> touchededges;
// Recalculate all path costs and then list them in a sorted manner by descending final cost
for (const auto & evc : *AllEvacuees)
if (evc->Status != EvacueeStatus::Unreachable)
{
evc->FinalCost = 0.0;
for (const auto & path : *evc->Paths)
if (path->IsActive())
{
path->CalculateFinalEvacuationCost(initDelayCostPerPop, EvcSolverMethod::CASPERSolver);
allPaths.push_back(path);
}
}
if (allPaths.empty()) return 0;
std::sort(allPaths.begin(), allPaths.end(), EvcPath::MoreThanFinalCost);
// setting up the best ratios
const double minRatioOfLongestPath = allPaths.front()->GetMinCostRatio();
const double ThreasholdForCost = max(0.15, minRatioOfLongestPath);
const double ThreasholdForPathOverlap = 0.4;
// collect what is the global evacuation time at each iteration and check that we're not getting worse
GlobalEvcCostAtIteration.push_back(allPaths.front()->GetFinalEvacuationCost());
// instead of assuming iteration is equal size of GlobalEvcCostAtIteration, we now ask that from the solver function.
// it is garanteed that at least 'Iteration' many loops happened before and hence GlobalEvcCostAtIteration.size() >= Iteration
// the number 'Iteration' referes to the loops that happened since the last dynamic change
++LocalIteration;
size_t GolbalIteration = GlobalEvcCostAtIteration.size();
size_t MaxEvacueesInIteration = size_t(allPaths.size() / (pow(1.0 / iterateRatio, LocalIteration)));
if (LocalIteration > 1)
{
// check if it got worse and then undo it
if (GlobalEvcCostAtIteration[GolbalIteration - 1] >= GlobalEvcCostAtIteration[GolbalIteration - 2])
{
std::sort(detachedPaths->begin(), detachedPaths->end(), EvcPath::LessThanPathOrder2);
for (const auto & path : *detachedPaths) path->CleanYourEvacueePaths(solverMethod, touchededges);
for (const auto & path : *detachedPaths) path->ReattachToEvacuee(solverMethod, touchededges);
NAEdge::HowDirtyExhaustive(touchededges.begin(), touchededges.end(), solverMethod, 1.0);
detachedPaths->clear();
GlobalEvcCostAtIteration.pop_back();
return 0;
}
// since we're not going to undo then we don't need the detached paths. Let's cleanup and collect new paths.
for (const auto & path : *detachedPaths) delete path;
detachedPaths->clear();
}
// And the next step is to find 'bad' paths and detach them so that the next iteration can find new paths for these evacuees.
// If no `bad` paths where found then we leave `EvacueesForNextIteration` empty so that the solver terminates and returns.
for (const auto & path : allPaths)
{
if (EvacueesForNextIteration.size() >= MaxEvacueesInIteration) break;
path->DoesItNeedASecondChance(ThreasholdForCost, ThreasholdForPathOverlap, EvacueesForNextIteration, GlobalEvcCostAtIteration[GolbalIteration - 1], solverMethod);
}
// Now that we know which evacuees are going to be processed again, let's reset their values and detach their paths.
std::sort(EvacueesForNextIteration.begin(), EvacueesForNextIteration.end(), EvcPath::MoreThanPathOrder1);
for (const auto & evc : EvacueesForNextIteration) EvcPath::DetachPathsFromEvacuee(evc, solverMethod, touchededges, detachedPaths);
NAEdge::HowDirtyExhaustive(touchededges.begin(), touchededges.end(), solverMethod, 1.0);
return EvacueesForNextIteration.size();
}
HRESULT EvcSolver::CARMALoop(INetworkQueryPtr ipNetworkQuery, IStepProgressorPtr ipStepProgressor, IGPMessages* pMessages, ITrackCancel* pTrackCancel, std::shared_ptr<EvacueeList> Evacuees, CARMASort RevisedCarmaSortCriteria,
std::shared_ptr<std::vector<EvacueePtr>> SortedEvacuees, std::shared_ptr<NAVertexCache> vcache, std::shared_ptr<NAEdgeCache> ecache, std::shared_ptr<SafeZoneTable> safeZoneList, size_t & closedSize,
std::shared_ptr<NAEdgeMapTwoGen> closedList, std::shared_ptr<NAEdgeContainer> leafs, std::vector<unsigned int> & CARMAExtractCounts, double globalMinPop2Route, double & minPop2Route, bool separationRequired)
{
HRESULT hr = S_OK;
// performing pre-process: Here we will mark each vertex/junction with a heuristic value indicating
// true distance to closest safe zone using backward traversal and Dijkstra
MyFibonacciHeap<NAEdgePtr, NAEdgePtrHasher, NAEdgePtrEqual> heap(NAEdge::GetHeapKeyNonHur); // creating the heap for the dijkstra search
NAVertexPtr neighbor = nullptr;
INetworkElementPtr ipElementEdge = nullptr;
VARIANT val;
val.vt = VT_R8; // double variant value
NAVertexPtr myVertex = nullptr;
NAEdgePtr myEdge = nullptr;
INetworkElementPtr ipJunctionElement = nullptr;
double newCost, SearchRadius, prevMinPop2Route = minPop2Route;
VARIANT_BOOL keepGoing;
INetworkJunctionPtr ipCurrentJunction = nullptr;
std::vector<NAEdgePtr> readyEdges;
readyEdges.reserve(safeZoneList->size());
unsigned int CARMAExtractCount = 0;
ArrayList<NAEdgePtr> * adj = nullptr;
ATL::CString statusMsg;
bool ShouldCARMACheckForDecreasedCost = false, FullSPTSelected = false;
std::vector<NAEdgePtr> removedDirty; removedDirty.reserve(10000);
const std::function<bool(EvacueePtr, EvacueePtr)> SortFunctions[7] =
{ Evacuee::LessThanObjectID, Evacuee::LessThan, Evacuee::LessThan, Evacuee::MoreThan, Evacuee::MoreThan, Evacuee::ReverseFinalCost, Evacuee::ReverseEvacuationCost };
// keeping reachable evacuees in a new hashtable for better access
// also keep unreachable ones in the redundant list
/// TODO what heppens here is that some evacuee may change location (DynamicCASPER) and hence the previous leafs
/// may not be the same edges to discover them again. In case of a DSPT this may mislead CARMA.
/// Also this is even more interesting when the evacuee is stuck
NAEvacueeVertexTable EvacueePairs;
EvacueePairs.InsertReachable(Evacuees, CarmaSortCriteria, leafs); // this is very important to be 'CarmaSortCriteria' with capital 'C'
SortedEvacuees->clear();
#ifdef TRACE
std::ofstream f;
#endif
if (FAILED(hr = ipNetworkQuery->CreateNetworkElement(esriNETJunction, &ipJunctionElement))) return hr;
ipCurrentJunction = ipJunctionElement;
// if this list is not empty, it means we are going to have another CARMA loop
if (!EvacueePairs.empty())
{
if (ipStepProgressor)
{
statusMsg.Format(_T("CARMA Loop %d: ..."), CARMAExtractCounts.size() + 1);
if (FAILED(hr = ipStepProgressor->put_Message(ATL::CComBSTR(statusMsg)))) return hr;
}
// search for min population on graph evacuees left to be routed. The next if has to be in-tune with what population will be routed next.
// the h values should always be an underestimation
minPop2Route = 1.0; // separable CCRPSolver and any case of SPSolver
if ((this->solverMethod == EvcSolverMethod::CASPERSolver) || (this->solverMethod == EvcSolverMethod::CCRPSolver && !separationRequired))
{
minPop2Route = CASPER_INFINITY;
for (const auto & e : *Evacuees)
{
if (e->Status != EvacueeStatus::CARMALooking || e->Population <= 0.0) continue;
minPop2Route = min(minPop2Route, e->Population);
}
if (separationRequired) minPop2Route = min(globalMinPop2Route, minPop2Route);
}
minPop2Route = max(minPop2Route, 1.0);
// generally speaking we use FullSPT if the user wants it or if the mimPop2Route has changed.
// if the minPop has changed it means pretty much all edges are dirty and there is no point checking them or do DSPT.
// later in the code we also check if there are too many dirty edges and in that case we also revert back to FullSPT.
FullSPTSelected = ThreeGenCARMA == VARIANT_FALSE || minPop2Route != prevMinPop2Route /*|| CARMAExtractCounts.empty()*/;
if (FullSPTSelected) closedList->Clear(NAEdgeMapGeneration::AllGens); // Full SPT
else closedList->MarkAllAsOldGen(); // DSPT option
// This is where the new dynamic CARMA starts. At this point you have to clear the dirty section of the carma tree.
// also keep the previous leafs only if they are still in closedList. They help re-discover EvacueePairs
MarkDirtyEdgesAsUnVisited(closedList->oldGen, leafs, removedDirty, ShouldCARMACheckForDecreasedCost);
if (ipStepProgressor)
{
if (FullSPTSelected) statusMsg.Format(_T("CARMA Loop %d: Full SPT"), CARMAExtractCounts.size() + 1);
else if (ShouldCARMACheckForDecreasedCost) statusMsg.Format(_T("CARMA Loop %d: Fully-Dynamic SPT"), CARMAExtractCounts.size() + 1);
else statusMsg.Format(_T("CARMA Loop %d: Semi-Dynamic SPT"), CARMAExtractCounts.size() + 1);
if (FAILED(hr = ipStepProgressor->put_Message(ATL::CComBSTR(statusMsg)))) return hr;
}
#ifdef DEBUG
std::wostringstream os_;
os_ << statusMsg.GetBuffer(statusMsg.GetLength()) << std::endl;
OutputDebugStringW(os_.str().c_str());
statusMsg.ReleaseBuffer();
#endif
// pre-add dirty edges to heap with their old clean parents instead of checking it during loop
if (FAILED(hr = FindDirtyEdgesWithACleanParent(ecache, vcache, ipNetworkQuery, closedList, leafs, removedDirty))) return hr;
// prepare and insert safe zone vertices into the heap
for (const auto & z : *safeZoneList)
{
if (FAILED(hr = PrepareVerticesForHeap(z.second->VertexAndRatio, vcache, ecache, closedList->oldGen, readyEdges, minPop2Route, solverMethod, 0.0, 0.0, QueryDirection::Forward))) return hr;
}
for (const auto & h : readyEdges)
{
// since this turns out to be a safe zone edge we should force the previous edge to be null in the tree
h->TreePrevious = nullptr;
heap.Insert(h);
}
// Now insert leaf edges in heap like the destination edges
// do I have to insert leafs even if DSPT is off? It does not matter cause closedList is cleaned and hence all leafs will be removed anyway.
if (FAILED(hr = InsertLeafEdgesToHeap(ipNetworkQuery, vcache, ecache, heap, leafs))) return hr;
// we're done with all these leafs. let's clean up and collect new ones for the next round.
leafs->Clear();
SearchRadius = CASPER_INFINITY;
// Continue traversing the network while the heap has remaining junctions in it
// this is the actual Dijkstra code with backward network traversal. it will only update h value.
while (!heap.empty())
{
// Remove the next junction EID from the top of the queue
myEdge = heap.DeleteMin();
_ASSERT_EXPR(!closedList->Exist(myEdge), L"CARMA closedList violation");
if (FAILED(hr = closedList->Insert(myEdge)))
{
// closedList violation happened
pMessages->AddError(-myEdge->EID, ATL::CComBSTR(L"CARMA ClosedList Violation."));
return ATL::AtlReportError(this->GetObjectCLSID(), _T("CARMA ClosedList Violation."), IID_INASolver);
}
myVertex = myEdge->ToVertex;
// Check to see if the user wishes to continue or cancel the solve
if (pTrackCancel)
{
if (FAILED(hr = pTrackCancel->Continue(&keepGoing))) return hr;
if (keepGoing == VARIANT_FALSE) return E_ABORT;
}
// check if this edge decreased its cost
CARMAExtractCount++;
// Code to build the CARMA Tree
if (myVertex->Previous)
{
if (myEdge->TreePrevious) myEdge->TreePrevious->TreeNext.unordered_erase(myEdge, NAEdge::IsEqualNAEdgePtr);
myEdge->TreePrevious = myVertex->Previous->GetBehindEdge();
myEdge->TreePrevious->TreeNext.push_back(myEdge);
}
// part to check if this branch of DJ tree needs expanding to update heuristics. This update should know if this is the first time this vertex is coming out
// in this 'CARMALoop' round. Only then we can be sure whether to update to min or update absolutely to this new value.
myVertex->UpdateYourHeuristic();
myEdge->SetClean(this->solverMethod, minPop2Route);
// termination condition and evacuee discovery
// if we've found all evacuees and we're beyond the search radius then instead of adding to the heap, we add it to the leafs list so that the next carma
// loop we can use it to expand the rest of the tree ... if this branch was needed. Not adding the edge to the heap will basically render this edge invisible to the
// future carma loops and can cause problems / inconsistancies. This is an attempt to solve the bug in issue 8: http://github.com/spatial-computing/CASPER/issues/8
if (EvacueePairs.empty())
{
UpdatePeakMemoryUsage();
leafs->Insert(myEdge);
SearchRadius = min(SearchRadius, myVertex->GVal);
continue;
}
EvacueePairs.RemoveDiscoveredEvacuees(myVertex, myEdge, SortedEvacuees, minPop2Route, solverMethod);
if (FAILED(hr = ecache->QueryAdjacencies(myVertex, myEdge, QueryDirection::Backward, &adj))) return hr;
for (const auto & currentEdge : *adj)
{
if (FAILED(hr = currentEdge->NetEdge->QueryJunctions(ipCurrentJunction, nullptr))) return hr;
newCost = myVertex->GVal + currentEdge->GetCost(minPop2Route, solverMethod);
if (newCost >= CASPER_INFINITY) continue;
if (closedList->Exist(currentEdge, NAEdgeMapGeneration::OldGen))
{
if (ShouldCARMACheckForDecreasedCost)
{
neighbor = vcache->New(ipCurrentJunction, ipNetworkQuery);
if (newCost < neighbor->GetH(currentEdge->EID))
{
neighbor->SetBehindEdge(currentEdge);
neighbor->GVal = newCost;
neighbor->Previous = myVertex;
closedList->Erase(currentEdge, NAEdgeMapGeneration::OldGen);
heap.Insert(currentEdge);
}
}
}
else
{
if (!closedList->Exist(currentEdge, NAEdgeMapGeneration::NewGen))
{
if (heap.IsVisited(currentEdge)) // vertex has been visited before. update vertex and decrease key.
{
neighbor = currentEdge->ToVertex;
if (neighbor->GVal > newCost)
{
neighbor->SetBehindEdge(currentEdge);
neighbor->GVal = newCost;
neighbor->Previous = myVertex;
heap.UpdateKey(currentEdge);
}
}
else // unvisited vertex. create new and insert into heap
{
neighbor = vcache->New(ipCurrentJunction, ipNetworkQuery);
neighbor->SetBehindEdge(currentEdge);
neighbor->GVal = newCost;
neighbor->Previous = myVertex;
heap.Insert(currentEdge);
}
}
}
}
}
#ifdef DEBUG
std::wostringstream os2;
os2 << "CARMA Extract Count = " << CARMAExtractCount << std::endl;
OutputDebugStringW(os2.str().c_str());
#endif
_ASSERT_EXPR(EvacueePairs.empty(), L"Carma loop ended after scanning all the graph");
// set new default heuristic value
vcache->UpdateHeuristicForOutsideVertices(SearchRadius, CARMAExtractCounts.empty());
CARMAExtractCounts.push_back(CARMAExtractCount);
}
// load discovered evacuees into sorted list
EvacueePairs.LoadSortedEvacuees(SortedEvacuees);
std::sort(SortedEvacuees->begin(), SortedEvacuees->end(), SortFunctions[RevisedCarmaSortCriteria]);
UpdatePeakMemoryUsage();
closedSize = closedList->Size();
#ifdef TRACE
f.open("c:\\evcsolver.log", std::ios_base::out | std::ios_base::app);
f << "CARMA visited edges = " << closedSize << std::endl;
f.close();
#endif
return hr;
}
void EvcSolver::MarkDirtyEdgesAsUnVisited(NAEdgeMap * closedList, std::shared_ptr<NAEdgeContainer> oldLeafs, std::vector<NAEdgePtr> & removedDirty, bool & ShouldCARMACheckForDecreasedCost) const
{
std::vector<NAEdgePtr> dirtyVisited;
NAEdgeIterator j;
NAEdgePtr leaf = nullptr;
dirtyVisited.reserve(closedList->Size() / 2);
auto tempLeafs = std::shared_ptr<NAEdgeContainer>(new DEBUG_NEW_PLACEMENT NAEdgeContainer(1000));
removedDirty.clear();
ShouldCARMACheckForDecreasedCost = false;
// the assumption here is that the minPop2Route has not changhes since last carma loop
// so only the edges that have recently been used in a path are dirty. so no need for a howdirty call. just a getdirtystate call is enough.
closedList->GetDirtyEdges(dirtyVisited);
for (const auto & d : dirtyVisited)
{
ShouldCARMACheckForDecreasedCost |= d->GetDirtyState() == EdgeDirtyState::CostDecreased;
if (closedList->Exist(d))
{
leaf = d;
while (leaf->TreePrevious && leaf->GetDirtyState() != EdgeDirtyState::CleanState) leaf = leaf->TreePrevious;
NonRecursiveMarkAndRemove(leaf, closedList, removedDirty);
// What is the definition of a leaf edge? An edge that has a previous (so it's not a destination edge) and has at least one dirty child edge.
// So the usual for loop is going to insert destination dirty edges and the rest are in the leafs list.
tempLeafs->Insert(leaf);
}
}
// removing previously identified leafs from closedList
for (j = oldLeafs->begin(); j != oldLeafs->end(); j++)
{
if ((j->second & 1) && closedList->Exist(j->first, esriNEDAlongDigitized))
{
closedList->Erase(j->first, esriNEDAlongDigitized);
tempLeafs->Insert(j->first, esriNEDAlongDigitized);
}
if ((j->second & 2) && closedList->Exist(j->first, esriNEDAgainstDigitized))
{
closedList->Erase(j->first, esriNEDAgainstDigitized);
tempLeafs->Insert(j->first, esriNEDAgainstDigitized);
}
}
oldLeafs->Clear();
oldLeafs->Insert(tempLeafs);
}
void EvcSolver::NonRecursiveMarkAndRemove(NAEdgePtr head, NAEdgeMap * closedList, std::vector<NAEdgePtr> & removedDirty) const
{
NAEdgePtr e = nullptr;
std::stack<NAEdgePtr> subtree;
subtree.push(head);
while (!subtree.empty())
{
e = subtree.top();
subtree.pop();
closedList->Erase(e);
removedDirty.push_back(e);
for (const auto & i : e->TreeNext)
{
i->TreePrevious = nullptr;
subtree.push(i);
}
e->TreeNext.clear();
}
}
HRESULT InsertLeafEdgeToHeap(INetworkQueryPtr ipNetworkQuery, std::shared_ptr<NAVertexCache> vcache, MyFibonacciHeap<NAEdgePtr, NAEdgePtrHasher, NAEdgePtrEqual> & heap, NAEdge * leaf)
{
HRESULT hr = S_OK;
INetworkElementPtr fe, te;
INetworkJunctionPtr f, t;
// if it does not have a previous, then it's not a leaf ... it's a destination edge and it will be added to the heap at 'PrepareVerticesForHeap'
if (leaf->TreePrevious)
{
// leaf by definition has to be a clean edge with a positive clean cost
_ASSERT(leaf->GetCleanCost() > 0.0);
_ASSERT(leaf->GetDirtyState() == EdgeDirtyState::CleanState);
if (FAILED(hr = ipNetworkQuery->CreateNetworkElement(esriNETJunction, &fe))) return hr;
if (FAILED(hr = ipNetworkQuery->CreateNetworkElement(esriNETJunction, &te))) return hr;
f = fe; t = te;
if (FAILED(hr = leaf->NetEdge->QueryJunctions(f, t))) return hr;
NAVertexPtr fPtr = vcache->New(f);
NAVertexPtr tPtr = vcache->Get(t);
fPtr->SetBehindEdge(leaf);
fPtr->GVal = tPtr->GetH(leaf->TreePrevious->EID) + leaf->GetCleanCost();
fPtr->Previous = nullptr;
_ASSERT(fPtr->GVal < CASPER_INFINITY);
heap.Insert(leaf);
}
return hr;
}
HRESULT InsertLeafEdgesToHeap(INetworkQueryPtr ipNetworkQuery, std::shared_ptr<NAVertexCache> vcache, std::shared_ptr<NAEdgeCache> ecache, MyFibonacciHeap<NAEdgePtr, NAEdgePtrHasher, NAEdgePtrEqual> & heap,
std::shared_ptr<NAEdgeContainer> leafs)
{
HRESULT hr = S_OK;
NAEdgePtr leaf;
for (NAEdgeIterator i = leafs->begin(); i != leafs->end(); i++)
{
if (i->second & 1)
{
leaf = ecache->Get(i->first, esriNEDAlongDigitized);
if (FAILED(hr = InsertLeafEdgeToHeap(ipNetworkQuery, vcache, heap, leaf))) return hr;
}
if (i->second & 2)
{
leaf = ecache->Get(i->first, esriNEDAgainstDigitized);
if (FAILED(hr = InsertLeafEdgeToHeap(ipNetworkQuery, vcache, heap, leaf))) return hr;
}
}
return hr;
}
HRESULT FindDirtyEdgesWithACleanParent(std::shared_ptr<NAEdgeCache> ecache, std::shared_ptr<NAVertexCache> vcache, INetworkQueryPtr ipNetworkQuery, std::shared_ptr<NAEdgeMapTwoGen> closedList,
std::shared_ptr<NAEdgeContainer> Leafs, std::vector<NAEdgePtr> & removedDirty)
{
HRESULT hr = S_OK;
NAVertexPtr toVertex = nullptr;
ArrayList<NAEdgePtr> * adj = nullptr;
double betterH, tempH;
INetworkElementPtr te;
NAEdgePtr betterParent = nullptr;
if (FAILED(hr = ipNetworkQuery->CreateNetworkElement(esriNETJunction, &te))) return hr;
INetworkJunctionPtr t = te;
for (const auto e : removedDirty)
{
betterParent = nullptr;
betterH = CASPER_INFINITY;
if (FAILED(hr = e->NetEdge->QueryJunctions(nullptr, t))) return hr;
toVertex = vcache->New(t, ipNetworkQuery);
if (FAILED(hr = ecache->QueryAdjacencies(toVertex, e, QueryDirection::Forward, &adj))) return hr;
// Loop through all adjacent edges and update their cost value
for (const auto & tempEdge : *adj)
{
// it has to be present in closed list from previous CARMA loop
// it has to have a previous otherwise it cannot be a leaf
if (tempEdge->TreePrevious && closedList->Exist(tempEdge, NAEdgeMapGeneration::OldGen))
{
tempH = toVertex->GetH(tempEdge->EID);
if (!betterParent || tempH < betterH) { betterParent = tempEdge; betterH = tempH; }
}
}
// for this border dirty edge we add the best parent it has
if (betterParent)
{
Leafs->Insert(betterParent);
closedList->Erase(betterParent, NAEdgeMapGeneration::OldGen);
}
}
return hr;
}
HRESULT PrepareVerticesForHeap(NAVertexPtr point, std::shared_ptr<NAVertexCache> vcache, std::shared_ptr<NAEdgeCache> ecache, NAEdgeMap * closedList, std::vector<NAEdgePtr> & readyEdges, double pop,
EvcSolverMethod solverMethod, double selfishRatio, double MaxEvacueeCostSoFar, QueryDirection dir)
{
HRESULT hr = S_OK;
NAVertexPtr temp;
NAEdgePtr edge;
double globalDeltaPenalty = 0.0, edgeCost = 0.0;
ArrayList<NAEdgePtr> * adj = nullptr;
// Remember vertex gval is now only ratio along edge
temp = vcache->New(point->Junction);
temp->SetBehindEdge(point->GetBehindEdge());
temp->GVal = point->GVal;
temp->GlobalPenaltyCost = point->GlobalPenaltyCost;
temp->Junction = point->Junction;
temp->Previous = nullptr;
edge = temp->GetBehindEdge();
// check to see if the edge you're about to insert is not in the closedList
if (edge)
{
if (!closedList->Exist(edge))
{
edgeCost = edge->GetCost(pop, solverMethod, &globalDeltaPenalty) /* / edge->OriginalCost*/;
if (edgeCost >= CASPER_INFINITY) temp->GVal = CASPER_INFINITY;
else temp->GVal = point->GVal * edgeCost;
temp->GlobalPenaltyCost = edge->MaxAddedCostOnReservedPathsWithNewFlow(globalDeltaPenalty, MaxEvacueeCostSoFar, temp->GVal + temp->GetMinHOrZero(), selfishRatio);
readyEdges.push_back(edge);
}
else _ASSERT(false);
}
else
{
// if the start point was a single junction, then all the adjacent edges can be start edges
if (FAILED(hr = ecache->QueryAdjacencies(temp, nullptr, dir, &adj))) return hr;
for (const auto & edge : *adj)
{
if (closedList->Exist(edge)) continue; // DSPT condition .... only dirty destination edges are inserted.
temp = vcache->New(point->Junction);
temp->Previous = nullptr;
temp->SetBehindEdge(edge);
edgeCost = edge->GetCost(pop, solverMethod, &globalDeltaPenalty) /* / edge->OriginalCost*/;
if (edgeCost >= CASPER_INFINITY) temp->GVal = CASPER_INFINITY;
else temp->GVal = point->GVal * edgeCost;
temp->GlobalPenaltyCost = edge->MaxAddedCostOnReservedPathsWithNewFlow(globalDeltaPenalty, MaxEvacueeCostSoFar, temp->GVal + temp->GetMinHOrZero(), selfishRatio);
readyEdges.push_back(edge);
}
}
return hr;
}
bool EvcSolver::GeneratePath(SafeZonePtr BetterSafeZone, NAVertexPtr finalVertex, double & populationLeft, int & pathGenerationCount, EvacueePtr currentEvacuee, double population2Route, bool separationRequired) const
{
double leftCap, edgePortion;
EvcPath * path = nullptr;
// generate evacuation route if a destination has been found
if (BetterSafeZone)
{
// First find out about remaining capacity of this path
NAVertexPtr temp = finalVertex;
if (this->solverMethod == EvcSolverMethod::CCRPSolver)
{
if (separationRequired)
{
population2Route = 0.0;
while (temp->Previous)
{
leftCap = temp->GetBehindEdge()->LeftCapacity();
if (this->solverMethod == EvcSolverMethod::CCRPSolver || leftCap > 0.0) population2Route = min(population2Route, leftCap);
temp = temp->Previous;
}
if (population2Route <= 0.0) population2Route = populationLeft;
population2Route = min(population2Route, populationLeft);
}
else population2Route = populationLeft;
}
populationLeft -= population2Route;
// create a new path for this portion of the population
path = new DEBUG_NEW_PLACEMENT EvcPath(initDelayCostPerPop, population2Route, ++pathGenerationCount, currentEvacuee, BetterSafeZone);
// special case for the last edge. We have to sub-curve it based on the safe point location along the edge
if (BetterSafeZone->getBehindEdge())
{
edgePortion = BetterSafeZone->getPositionAlong();
if (edgePortion > 0.0) path->AddSegment(solverMethod, new DEBUG_NEW_PLACEMENT PathSegment(BetterSafeZone->getBehindEdge(), 0.0, edgePortion));
}
while (finalVertex->Previous)
{
if (finalVertex->GetBehindEdge()) path->AddSegment(solverMethod, new DEBUG_NEW_PLACEMENT PathSegment(finalVertex->GetBehindEdge()));
finalVertex = finalVertex->Previous;
}
// special case for the first edge. We have to curve it based on the evacuee point location along the edge
if (finalVertex->GetBehindEdge())
{
// search for mother vertex and its position along the edge
edgePortion = 1.0;
for (const auto & v : *currentEvacuee->VerticesAndRatio)
if (v->EID == finalVertex->EID)
{
edgePortion = v->GVal;
break;
}
// path can be empty if the source and destination are the same vertex
PathSegmentPtr lastAdded = path->empty() ? nullptr : path->front();
if (lastAdded && NAEdge::IsEqualNAEdgePtr(lastAdded->Edge, finalVertex->GetBehindEdge()))
{
lastAdded->SetFromRatio(1.0 - edgePortion);
}
else if (edgePortion > 0.0)
{
path->AddSegment(solverMethod, new DEBUG_NEW_PLACEMENT PathSegment(finalVertex->GetBehindEdge(), 1.0 - edgePortion, 1.0));
}
}
if (path->empty())
{
delete path;
path = nullptr;
}
else
{
path->shrink_to_fit();
currentEvacuee->Paths->push_front(path);
BetterSafeZone->Reserve(path->GetRoutedPop());
}
}
else
{
populationLeft = 0.0; // since no path could be found for this evacuee, we assume the rest of the population at this location have no path as well
}
return path != nullptr;
}
// This is where i figure out what is the smallest population that I should route (or try to route)
// at each CASPER loop. Obviously this globalMinPop2Route has to be less than the population of any evacuee point.
// Also CASPER and CARMA should be in sync at this number otherwise all the h values are useless.
HRESULT EvcSolver::DeterminMinimumPop2Route(std::shared_ptr<EvacueeList> Evacuees, INetworkDatasetPtr ipNetworkDataset, double & globalMinPop2Route, bool & separationRequired) const
{
double minPop = CASPER_INFINITY, maxPop = 1.0, CommonCostOfEdgeInUnits = 1.0, avgPop = 0.0;
HRESULT hr = S_OK;
INetworkAttributePtr costAttrib;
esriNetworkAttributeUnits unit;
size_t count = 0;
globalMinPop2Route = 0.0;
separationRequired = Evacuees->IsSeperable();
if (separationRequired && this->solverMethod == EvcSolverMethod::CASPERSolver)
{
for (const auto & e : *Evacuees)
if (e->Population > 0.0)
{
count++;
avgPop += e->Population;
if (e->Population > maxPop) maxPop = e->Population;
if (e->Population < minPop) minPop = e->Population;
}
avgPop = avgPop / count;
// read cost attribute unit
if (SUCCEEDED(hr = ipNetworkDataset->get_AttributeByID(costAttributeID, &costAttrib)))
{
if (FAILED(hr = costAttrib->get_Units(&unit))) return hr;
CommonCostOfEdgeInUnits = GetUnitPerDay(unit, 25.0) / (60.0 * 24.0);
}
if ((initDelayCostPerPop > 0.0 && CommonCostOfEdgeInUnits / initDelayCostPerPop <= SaturationPerCap) ||
maxPop <= SaturationPerCap)
{
// the maximum possible flow on common edge is not enough to cause congestion alone so separation is not required.
separationRequired = false;
globalMinPop2Route = 0.0;
}
else
{
separationRequired = true;
globalMinPop2Route = SaturationPerCap / 3.0;
// We don't want the minimum routable population to be less than one-forth of the minimum population of any evacuee point. That just makes CASPER too slow.
if (globalMinPop2Route * 4.0 < minPop) globalMinPop2Route = minPop / 4.0;
if (globalMinPop2Route < 1.0) globalMinPop2Route = 1.0;
}
}
return hr;
}
void EvcSolver::UpdatePeakMemoryUsage()
{
_ASSERTE(_CrtCheckMemory());
PROCESS_MEMORY_COUNTERS pmc;
if (!hProcessPeakMemoryUsage) hProcessPeakMemoryUsage = GetCurrentProcess();
if (GetProcessMemoryInfo(hProcessPeakMemoryUsage, &pmc, sizeof(pmc))) peakMemoryUsage = max(peakMemoryUsage, pmc.PagefileUsage);
}
HRESULT PrepareUnvisitedVertexForHeap(INetworkJunctionPtr junction, NAEdgePtr edge, NAEdgePtr prevEdge, double edgeCost, NAVertexPtr myVertex, std::shared_ptr<NAEdgeCache> ecache,
std::shared_ptr<NAEdgeMapTwoGen> closedList, std::shared_ptr<NAVertexCache> vcache, INetworkQueryPtr ipNetworkQuery, bool checkOldClosedlist)
{
HRESULT hr = S_OK;
NAVertexPtr betterMyVertex;
NAEdgePtr betterEdge = nullptr;
double betterH, tempH;
NAVertexPtr tempVertex, neighbor;
ArrayList<NAEdgePtr> * adj = nullptr;
// Dynamic CARMA: at this step we have to check if there is any better previous edge for this new one in closed-list
// this is the vertex at the center of two edges... we have to check its heuristics to see if the new twempEdge is any better.
tempVertex = vcache->Get(myVertex->EID);
betterH = myVertex->GVal;
if (checkOldClosedlist)
{
if (FAILED(hr = ecache->QueryAdjacencies(myVertex, edge, QueryDirection::Forward, &adj))) return hr;
// Loop through all adjacent edges and update their cost value
for (const auto & tempEdge : *adj)