SUMO - Simulation of Urban MObility
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
RORouteAggregator.h
Go to the documentation of this file.
1 /****************************************************************************/
9 // Handles grouping of routes to supply input for BulkStarRouter
10 /****************************************************************************/
11 // SUMO, Simulation of Urban MObility; see http://sumo.dlr.de/
12 // Copyright (C) 2012-2015 DLR (http://www.dlr.de/) and contributors
13 /****************************************************************************/
14 //
15 // This file is part of SUMO.
16 // SUMO is free software: you can redistribute it and/or modify
17 // it under the terms of the GNU General Public License as published by
18 // the Free Software Foundation, either version 3 of the License, or
19 // (at your option) any later version.
20 //
21 /****************************************************************************/
22 #ifndef RORouteAggregator_h
23 #define RORouteAggregator_h
24 
25 
26 // ===========================================================================
27 // included modules
28 // ===========================================================================
29 #ifdef _MSC_VER
30 #include <windows_config.h>
31 #else
32 #include <config.h>
33 #endif
34 
35 #include <string>
36 #include <algorithm>
37 #include <foreign/rtree/RTree.h>
40 #include <router/ROEdge.h>
42 
43 
44 // ===========================================================================
45 // class definitions
46 // ===========================================================================
47 //
49 
50 public:
51 
57  // simple version: group by destination edge
58  SameTargetMap stm;
60  if (vehicles.size() == 0) {
61  throw ProcessError("No vehicles loaded");
62  }
63  // XXX @todo: use a configurable default vehicle
64  const ROVehicle* defaultVehicle = vehicles.begin()->second;
65  for (NamedObjectCont<ROVehicle*>::IDMap::const_iterator it = vehicles.begin(); it != vehicles.end(); it++) {
66  ROVehicle* veh = it->second;
67  stm[veh->getRouteDefinition()->getDestination()].push_back(veh);
68  }
69  WRITE_MESSAGE("Loaded " + toString(vehicles.size()) + " vehicles with " + toString(stm.size()) + " unique destinations");
70 
71  // merge nearby destinations for efficiency
72  const int MERGE_DISTANCE = 6; // XXX @todo make configurable
73  for (int i = 1; i <= MERGE_DISTANCE; i++) {
74  stm = mergeTargets(stm, MERGE_DISTANCE);
75  }
76  WRITE_MESSAGE("Kept " + toString(stm.size()) + " unique destinations after merging");
77 
78  // skip precomputation if not enough vehicles have the same destination
79  // this value could be set automatically: num_edges / avg_number_of_nodes_visited_for_astar
80  const size_t SKIP_LIMIT = 11; // XXX @todo make configurable
81  int num_prepared = 0;
82  int num_unprepared = 0;
83  int num_routes_prepared = 0;
84  int num_routes_unprepared = 0;
85  // process by destination edge
86  for (SameTargetMap::iterator it = stm.begin(); it != stm.end(); it++) {
87  const ROEdge* dest = it->first;
88  VehVec& bulkVehicles = it->second;
89  bool skip = false;
90  if (bulkVehicles.size() < SKIP_LIMIT) {
91  skip = true;
92  num_routes_unprepared += (int)bulkVehicles.size();
93  num_unprepared += 1;
94  } else {
95  num_routes_prepared += (int)bulkVehicles.size();
96  num_prepared += 1;
97  }
98  router.prepare(dest, defaultVehicle, skip);
99  for (VehVec::iterator it = bulkVehicles.begin(); it != bulkVehicles.end(); it++) {
100  ROVehicle* veh = *it;
101  RORouteDef* routeDef = veh->getRouteDefinition();
102  routeDef->preComputeCurrentRoute(router, veh->getDepartureTime(), *veh);
103  }
104  }
105  WRITE_MESSAGE("Performed pre-computation for " + toString(num_prepared) + " destinations");
106  WRITE_MESSAGE("Skipped pre-computation for " + toString(num_unprepared) + " destinations");
107  WRITE_MESSAGE("Computed " + toString(num_routes_prepared) + " routes with pre-computation");
108  WRITE_MESSAGE("Computed " + toString(num_routes_unprepared) + " routes without pre-computation");
109  }
110 
111 private:
112  typedef std::vector<ROVehicle*> VehVec;
113  typedef std::map<const ROEdge*, VehVec> SameTargetMap;
114  typedef std::set<const ROEdge*> EdgeSet;
115 
116 
119 
120  ComparatorNumVehicles(SameTargetMap& sameTargetMap):
121  mySameTargetMap(sameTargetMap) {}
122 
123  bool operator()(const ROEdge* const a, const ROEdge* const b) {
124  return (mySameTargetMap[a].size() > mySameTargetMap[b].size());
125  }
126 
127  SameTargetMap& mySameTargetMap;
128 
129  private:
132 
133  };
134 
135 
136  static SameTargetMap mergeTargets(SameTargetMap& stm, const int distance) {
137  SameTargetMap result;
138  // we want to merg edges with few vehicles to edges with many vehicles
139  // so we have to sort by number of vehicles first
140  ConstROEdgeVector heap;
141  heap.reserve(stm.size());
142  ComparatorNumVehicles cmp(stm);
143  for (SameTargetMap::iterator it = stm.begin(); it != stm.end(); it++) {
144  heap.push_back(it->first);
145  }
146  make_heap(heap.begin(), heap.end(), cmp);
147  while (heap.size() > 0) {
148  const ROEdge* dest = heap.front();
149  pop_heap(heap.begin(), heap.end(), cmp);
150  heap.pop_back();
151  if (stm.count(dest) > 0 && // dest has not been merged yet
152  stm[dest].size() > 0) { // for some strange reason 0-length vectors are found despite erase
153  result[dest] = stm[dest];
154  stm.erase(dest);
155  EdgeSet nearby = getNearby(dest, distance);
156  for (EdgeSet::iterator it = nearby.begin(); it != nearby.end(); it++) {
157  const ROEdge* nearEdge = *it;
158  if (stm.count(nearEdge) > 0) {
159  // nearEdge occurs as destination and has not been merged yet
160  result[dest].insert(result[dest].end(), stm[nearEdge].begin(), stm[nearEdge].end());
161  stm.erase(nearEdge);
162  }
163  }
164  }
165  }
166  return result;
167  }
168 
169 
170  static EdgeSet getNearby(const ROEdge* edge, const int distance) {
171  EdgeSet result;
172  result.insert(edge);
173  EdgeSet fringe(result);
174  for (int i = 0; i < distance; i++) {
175  fringe = approachingEdges(fringe);
176  result.insert(fringe.begin(), fringe.end());
177  }
178  return result;
179  }
180 
181 
182  static EdgeSet approachingEdges(EdgeSet edges) {
183  EdgeSet result;
184  for (EdgeSet::iterator it = edges.begin(); it != edges.end(); it++) {
185  result.insert((*it)->getPredecessors().begin(), (*it)->getPredecessors().end());
186  }
187  return result;
188  }
189 
190 
191 };
192 
193 
194 #endif
195 
196 /****************************************************************************/
197 
SUMOTime getDepartureTime() const
Returns the time the vehicle starts at, 0 for triggered vehicles.
Definition: ROVehicle.h:112
ComparatorNumVehicles(SameTargetMap &sameTargetMap)
ROVehicleCont & getVehicles()
return vehicles for use by RouteAggregator
Definition: RONet.h:407
static SameTargetMap mergeTargets(SameTargetMap &stm, const int distance)
static EdgeSet approachingEdges(EdgeSet edges)
void preComputeCurrentRoute(SUMOAbstractRouter< ROEdge, ROVehicle > &router, SUMOTime begin, const ROVehicle &veh) const
Builds the complete route (or chooses her from the list of alternatives, when existing) ...
Definition: RORouteDef.cpp:105
static void processAllRoutes(RONet &net, SUMOAbstractRouter< ROEdge, ROVehicle > &router)
precomputes all routes grouped by their destination edge
std::vector< const ROEdge * > ConstROEdgeVector
Definition: ROEdge.h:59
A map of named object pointers.
A vehicle as used by router.
Definition: ROVehicle.h:60
virtual void prepare(const E *, const V *, bool)
unsigned int size() const
Returns the number of items within the container.
std::string toString(const T &t, std::streamsize accuracy=OUTPUT_ACCURACY)
Definition: ToString.h:53
const ROEdge * getDestination() const
Definition: RORouteDef.cpp:333
A basic edge for routing applications.
Definition: ROEdge.h:73
const IDMap & getMyMap() const
The router's network representation.
Definition: RONet.h:72
std::map< const ROEdge *, VehVec > SameTargetMap
Base class for a vehicle's route definition.
Definition: RORouteDef.h:63
bool operator()(const ROEdge *const a, const ROEdge *const b)
ComparatorNumVehicles & operator=(const ComparatorNumVehicles &)
Invalidated assignment operator.
std::set< const ROEdge * > EdgeSet
RORouteDef * getRouteDefinition() const
Returns the definition of the route the vehicle takes.
Definition: ROVehicle.h:83
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:201
static EdgeSet getNearby(const ROEdge *edge, const int distance)
std::vector< ROVehicle * > VehVec