Eclipse SUMO - Simulation of Urban MObility
RORouteDef.cpp
Go to the documentation of this file.
1/****************************************************************************/
2// Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3// Copyright (C) 2002-2022 German Aerospace Center (DLR) and others.
4// This program and the accompanying materials are made available under the
5// terms of the Eclipse Public License 2.0 which is available at
6// https://www.eclipse.org/legal/epl-2.0/
7// This Source Code may also be made available under the following Secondary
8// Licenses when the conditions for such availability set forth in the Eclipse
9// Public License 2.0 are satisfied: GNU General Public License, version 2
10// or later which is available at
11// https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html
12// SPDX-License-Identifier: EPL-2.0 OR GPL-2.0-or-later
13/****************************************************************************/
20// Base class for a vehicle's route definition
21/****************************************************************************/
22#include <config.h>
23
24#include <string>
25#include <iterator>
26#include <algorithm>
29#include <utils/common/Named.h>
35#include "ROEdge.h"
36#include "RORoute.h"
39#include "RORouteDef.h"
40#include "ROVehicle.h"
41
42// ===========================================================================
43// static members
44// ===========================================================================
45bool RORouteDef::myUsingJTRR(false);
46
47// ===========================================================================
48// method definitions
49// ===========================================================================
50RORouteDef::RORouteDef(const std::string& id, const int lastUsed,
51 const bool tryRepair, const bool mayBeDisconnected) :
52 Named(StringUtils::convertUmlaute(id)),
53 myPrecomputed(nullptr), myLastUsed(lastUsed), myTryRepair(tryRepair),
54 myMayBeDisconnected(mayBeDisconnected),
55 myDiscardSilent(false) {
56}
57
58
60 for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
61 if (myRouteRefs.count(*i) == 0) {
62 delete *i;
63 }
64 }
65}
66
67
68void
70 myAlternatives.push_back(alt);
71}
72
73
74void
76 std::copy(alt->myAlternatives.begin(), alt->myAlternatives.end(),
77 back_inserter(myAlternatives));
78 std::copy(alt->myAlternatives.begin(), alt->myAlternatives.end(),
79 std::inserter(myRouteRefs, myRouteRefs.end()));
80}
81
82
85 SUMOTime begin, const ROVehicle& veh) const {
86 if (myPrecomputed == nullptr) {
87 preComputeCurrentRoute(router, begin, veh);
88 }
89 return myPrecomputed;
90}
91
92
93void
95 SUMOTime begin, const ROVehicle& veh) const {
96 myNewRoute = false;
98 const bool ignoreErrors = oc.getBool("ignore-errors");
99 assert(myAlternatives[0]->getEdgeVector().size() > 0);
101 if (myAlternatives[0]->getFirst()->prohibits(&veh) && (!oc.getBool("repair.from")
102 // do not try to reassign starting edge for trip input
103 || myMayBeDisconnected || myAlternatives[0]->getEdgeVector().size() < 2)) {
104 mh->inform("Vehicle '" + veh.getID() + "' is not allowed to depart on edge '" +
105 myAlternatives[0]->getFirst()->getID() + "'.");
106 return;
107 } else if (myAlternatives[0]->getLast()->prohibits(&veh) && (!oc.getBool("repair.to")
108 // do not try to reassign destination edge for trip input
109 || myMayBeDisconnected || myAlternatives[0]->getEdgeVector().size() < 2)) {
110 // this check is not strictly necessary unless myTryRepair is set.
111 // However, the error message is more helpful than "no connection found"
112 mh->inform("Vehicle '" + veh.getID() + "' is not allowed to arrive on edge '" +
113 myAlternatives[0]->getLast()->getID() + "'.");
114 return;
115 }
116 const bool skipTripRouting = (oc.exists("write-trips") && oc.getBool("write-trips")
118 if ((myTryRepair && !skipTripRouting) || myUsingJTRR) {
119 ConstROEdgeVector newEdges;
120 if (repairCurrentRoute(router, begin, veh, myAlternatives[0]->getEdgeVector(), newEdges)) {
121 if (myAlternatives[0]->getEdgeVector() != newEdges) {
122 if (!myMayBeDisconnected) {
123 WRITE_WARNING("Repaired route of vehicle '" + veh.getID() + "'.");
124 }
125 myNewRoute = true;
126 RGBColor* col = myAlternatives[0]->getColor() != nullptr ? new RGBColor(*myAlternatives[0]->getColor()) : nullptr;
127 myPrecomputed = new RORoute(myID, 0, myAlternatives[0]->getProbability(), newEdges, col, myAlternatives[0]->getStops());
128 } else {
130 }
131 }
132 return;
133 }
135 || OptionsCont::getOptions().getBool("remove-loops"))
136 && (skipTripRouting || myAlternatives[myLastUsed]->isValid(veh, ignoreErrors))) {
138 } else {
139 // build a new route to test whether it is better
140 ConstROEdgeVector oldEdges;
141 oldEdges.push_back(myAlternatives[0]->getFirst());
142 oldEdges.push_back(myAlternatives[0]->getLast());
143 ConstROEdgeVector edges;
144 repairCurrentRoute(router, begin, veh, oldEdges, edges);
145 // check whether the same route was already used
146 int cheapest = -1;
147 for (int i = 0; i < (int)myAlternatives.size(); i++) {
148 if (edges == myAlternatives[i]->getEdgeVector()) {
149 cheapest = i;
150 break;
151 }
152 }
153 if (cheapest >= 0) {
154 myPrecomputed = myAlternatives[cheapest];
155 } else {
156 RGBColor* col = myAlternatives[0]->getColor() != nullptr ? new RGBColor(*myAlternatives[0]->getColor()) : nullptr;
157 myPrecomputed = new RORoute(myID, 0, 1, edges, col, myAlternatives[0]->getStops());
158 myNewRoute = true;
159 }
160 }
161}
162
163
164bool
166 SUMOTime begin, const ROVehicle& veh,
167 ConstROEdgeVector oldEdges, ConstROEdgeVector& newEdges) const {
168 MsgHandler* mh = (OptionsCont::getOptions().getBool("ignore-errors") ?
170 const int initialSize = (int)oldEdges.size();
171 if (initialSize == 1) {
172 if (myUsingJTRR) {
174 bool ok = router.compute(oldEdges.front(), nullptr, &veh, begin, newEdges);
175 myDiscardSilent = ok && newEdges.size() == 0;
176 } else {
177 newEdges = oldEdges;
178 }
179 } else {
180 if (oldEdges.front()->prohibits(&veh)) {
181 // option repair.from is in effect
182 const std::string& frontID = oldEdges.front()->getID();
183 for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
184 if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
185 i = oldEdges.erase(i);
186 } else {
187 WRITE_MESSAGE("Changing invalid starting edge '" + frontID
188 + "' to '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
189 break;
190 }
191 }
192 }
193 if (oldEdges.size() == 0) {
194 mh->inform("Could not find new starting edge for vehicle '" + veh.getID() + "'.");
195 return false;
196 }
197 if (oldEdges.back()->prohibits(&veh)) {
198 // option repair.to is in effect
199 const std::string& backID = oldEdges.back()->getID();
200 // oldEdges cannot get empty here, otherwise we would have left the stage when checking "from"
201 while (oldEdges.back()->prohibits(&veh) || oldEdges.back()->isInternal()) {
202 oldEdges.pop_back();
203 }
204 WRITE_MESSAGE("Changing invalid destination edge '" + backID
205 + "' to edge '" + oldEdges.back()->getID() + "' for vehicle '" + veh.getID() + "'.");
206 }
207 ConstROEdgeVector mandatory = veh.getMandatoryEdges(oldEdges.front(), oldEdges.back());
208 assert(mandatory.size() >= 2);
209 // removed prohibited
210 for (ConstROEdgeVector::iterator i = oldEdges.begin(); i != oldEdges.end();) {
211 if ((*i)->prohibits(&veh) || (*i)->isInternal()) {
212 // no need to check the mandatories here, this was done before
213 i = oldEdges.erase(i);
214 } else {
215 ++i;
216 }
217 }
218 // reconnect remaining edges
219 if (mandatory.size() > oldEdges.size() && initialSize > 2) {
220 WRITE_MESSAGE("There are stop edges which were not part of the original route for vehicle '" + veh.getID() + "'.");
221 }
222 const ConstROEdgeVector& targets = mandatory.size() > oldEdges.size() ? mandatory : oldEdges;
223 newEdges.push_back(targets.front());
224 ConstROEdgeVector::iterator nextMandatory = mandatory.begin() + 1;
225 int lastMandatory = 0;
226 for (ConstROEdgeVector::const_iterator i = targets.begin() + 1;
227 i != targets.end() && nextMandatory != mandatory.end(); ++i) {
228 const ROEdge* prev = *(i - 1);
229 const ROEdge* cur = *i;
230 if (prev->isConnectedTo(*cur, veh.getVClass()) && (!isRailway(veh.getVClass()) || prev->getBidiEdge() != cur)) {
231 newEdges.push_back(cur);
232 } else {
233 if (initialSize > 2) {
234 // only inform if the input is (probably) not a trip
235 WRITE_MESSAGE("Edge '" + (*(i - 1))->getID() + "' not connected to edge '" + (*i)->getID() + "' for vehicle '" + veh.getID() + "'.");
236 }
237 const ROEdge* last = newEdges.back();
238 newEdges.pop_back();
239 if (last->isTazConnector() && newEdges.size() > 1) {
240 // assume this was a viaTaz
241 last = newEdges.back();
242 newEdges.pop_back();
243 }
244// router.setHint(targets.begin(), i, &veh, begin);
245 if (!router.compute(last, *i, &veh, begin, newEdges)) {
246 // backtrack: try to route from last mandatory edge to next mandatory edge
247 // XXX add option for backtracking in smaller increments
248 // (i.e. previous edge to edge after *i)
249 // we would then need to decide whether we have found a good
250 // tradeoff between faithfulness to the input data and detour-length
251 ConstROEdgeVector edges;
252 if (lastMandatory >= (int)newEdges.size() || last == newEdges[lastMandatory] || !router.compute(newEdges[lastMandatory], *nextMandatory, &veh, begin, edges)) {
253 mh->inform("Mandatory edge '" + (*i)->getID() + "' not reachable by vehicle '" + veh.getID() + "'.");
254 return false;
255 }
256 while (*i != *nextMandatory) {
257 ++i;
258 }
259 newEdges.erase(newEdges.begin() + lastMandatory + 1, newEdges.end());
260 std::copy(edges.begin() + 1, edges.end(), back_inserter(newEdges));
261 }
262 }
263 if (*i == *nextMandatory) {
264 nextMandatory++;
265 lastMandatory = (int)newEdges.size() - 1;
266 }
267 }
268 }
269 return true;
270}
271
272
273void
275 const ROVehicle* const veh, RORoute* current, SUMOTime begin) {
276 if (myTryRepair || myUsingJTRR) {
277 if (myNewRoute) {
278 delete myAlternatives[0];
279 myAlternatives[0] = current;
280 }
281 const double costs = router.recomputeCosts(current->getEdgeVector(), veh, begin);
282 if (costs < 0) {
283 throw ProcessError("Route '" + getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
284 }
285 current->setCosts(costs);
286 return;
287 }
288 // add the route when it's new
289 if (myNewRoute) {
290 myAlternatives.push_back(current);
291 }
292 // recompute the costs and (when a new route was added) scale the probabilities
293 const double scale = double(myAlternatives.size() - 1) / double(myAlternatives.size());
294 for (RORoute* const alt : myAlternatives) {
295 // recompute the costs for all routes
296 const double newCosts = router.recomputeCosts(alt->getEdgeVector(), veh, begin);
297 if (newCosts < 0.) {
298 throw ProcessError("Route '" + current->getID() + "' (vehicle '" + veh->getID() + "') is not valid.");
299 }
300 assert(myAlternatives.size() != 0);
301 if (myNewRoute) {
302 if (alt == current) {
303 // set initial probability and costs
304 alt->setProbability(1. / (double) myAlternatives.size());
305 alt->setCosts(newCosts);
306 } else {
307 // rescale probs for all others
308 alt->setProbability(alt->getProbability() * scale);
309 }
310 }
312 }
313 assert(myAlternatives.size() != 0);
315 const bool keepRoute = RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().keepRoute();
316 if (!RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().keepAllRoutes() && !keepRoute) {
317 // remove with probability of 0 (not mentioned in Gawron)
318 for (std::vector<RORoute*>::iterator i = myAlternatives.begin(); i != myAlternatives.end();) {
319 if ((*i)->getProbability() == 0) {
320 delete *i;
321 i = myAlternatives.erase(i);
322 } else {
323 i++;
324 }
325 }
326 }
327 int maxNumber = RouteCostCalculator<RORoute, ROEdge, ROVehicle>::getCalculator().getMaxRouteNumber();
328 if ((int)myAlternatives.size() > maxNumber) {
329 const RORoute* last = myAlternatives[myLastUsed];
330 // only keep the routes with highest probability
331 sort(myAlternatives.begin(), myAlternatives.end(), [](const RORoute * const a, const RORoute * const b) {
332 return a->getProbability() > b->getProbability();
333 });
334 if (keepRoute) {
335 for (int i = 0; i < (int)myAlternatives.size(); i++) {
336 if (myAlternatives[i] == last) {
337 myLastUsed = i;
338 break;
339 }
340 }
341 if (myLastUsed >= maxNumber) {
343 myLastUsed = maxNumber - 1;
344 }
345 }
346 for (std::vector<RORoute*>::iterator i = myAlternatives.begin() + maxNumber; i != myAlternatives.end(); i++) {
347 delete *i;
348 }
349 myAlternatives.erase(myAlternatives.begin() + maxNumber, myAlternatives.end());
350 }
351 // rescale probabilities
352 double newSum = 0.;
353 for (const RORoute* const alt : myAlternatives) {
354 newSum += alt->getProbability();
355 }
356 assert(newSum > 0);
357 // @note newSum may be larger than 1 for numerical reasons
358 for (RORoute* const alt : myAlternatives) {
359 alt->setProbability(alt->getProbability() / newSum);
360 }
361
362 // find the route to use
363 if (!keepRoute) {
364 double chosen = RandHelper::rand();
365 myLastUsed = 0;
366 for (const RORoute* const alt : myAlternatives) {
367 chosen -= alt->getProbability();
368 if (chosen <= 0) {
369 return;
370 }
371 myLastUsed++;
372 }
373 }
374}
375
376
377const ROEdge*
379 return myAlternatives[0]->getLast();
380}
381
382
385 bool asAlternatives, bool withExitTimes, bool withCost, bool withLength) const {
386 if (asAlternatives) {
388 for (int i = 0; i != (int)myAlternatives.size(); i++) {
389 myAlternatives[i]->writeXMLDefinition(dev, veh, true, true, withExitTimes, withLength);
390 }
391 dev.closeTag();
392 return dev;
393 } else {
394 return myAlternatives[myLastUsed]->writeXMLDefinition(dev, veh, withCost, false, withExitTimes, withLength);
395 }
396}
397
398
400RORouteDef::copy(const std::string& id, const SUMOTime stopOffset) const {
402 for (const RORoute* const route : myAlternatives) {
403 RGBColor* col = route->getColor() != nullptr ? new RGBColor(*route->getColor()) : nullptr;
404 RORoute* newRoute = new RORoute(id, route->getCosts(), route->getProbability(), route->getEdgeVector(), col, route->getStops());
405 newRoute->addStopOffset(stopOffset);
406 result->addLoadedAlternative(newRoute);
407 }
408 return result;
409}
410
411
412double
414 double sum = 0.;
415 for (std::vector<RORoute*>::const_iterator i = myAlternatives.begin(); i != myAlternatives.end(); i++) {
416 sum += (*i)->getProbability();
417 }
418 return sum;
419}
420
421
422/****************************************************************************/
long long int SUMOTime
Definition: GUI.h:36
#define WRITE_MESSAGE(msg)
Definition: MsgHandler.h:267
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:265
std::vector< const ROEdge * > ConstROEdgeVector
Definition: ROEdge.h:54
bool isRailway(SVCPermissions permissions)
Returns whether an edge with the given permission is a railway edge.
@ SUMO_TAG_ROUTE_DISTRIBUTION
distribution of a route
@ SUMO_ATTR_LAST
static MsgHandler * getErrorInstance()
Returns the instance to add errors to.
Definition: MsgHandler.cpp:79
virtual void inform(std::string msg, bool addType=true)
adds a new error to the list
Definition: MsgHandler.cpp:116
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:66
Base class for objects which have an id.
Definition: Named.h:54
std::string myID
The name of the object.
Definition: Named.h:125
const std::string & getID() const
Returns the id.
Definition: Named.h:74
A storage for options typed value containers)
Definition: OptionsCont.h:89
bool exists(const std::string &name) const
Returns the information whether the named option is known.
bool getBool(const std::string &name) const
Returns the boolean-value of the named option (only for Option_Bool)
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:59
Static storage of an output device and its base (abstract) implementation.
Definition: OutputDevice.h:61
OutputDevice & writeAttr(const SumoXMLAttr attr, const T &val)
writes a named attribute
Definition: OutputDevice.h:251
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.
bool closeTag(const std::string &comment="")
Closes the most recently opened tag and optionally adds a comment.
A basic edge for routing applications.
Definition: ROEdge.h:70
const ROEdge * getBidiEdge() const
return opposite superposable/congruent edge, if it exist and 0 else
Definition: ROEdge.h:520
bool isTazConnector() const
Definition: ROEdge.h:159
bool isConnectedTo(const ROEdge &e, const SUMOVehicleClass vClass) const
returns the information whether this edge is directly connected to the given
Definition: ROEdge.cpp:438
SUMOVehicleClass getVClass() const
Definition: RORoutable.h:109
const std::string & getID() const
Returns the id of the routable.
Definition: RORoutable.h:91
Base class for a vehicle's route definition.
Definition: RORouteDef.h:53
RORoute * myPrecomputed
precomputed route for out-of-order computation
Definition: RORouteDef.h:148
void addLoadedAlternative(RORoute *alternative)
Adds a single alternative loaded from the file An alternative may also be generated during DUA.
Definition: RORouteDef.cpp:69
RORouteDef(const std::string &id, const int lastUsed, const bool tryRepair, const bool mayBeDisconnected)
Constructor.
Definition: RORouteDef.cpp:50
double getOverallProb() const
Returns the sum of the probablities of the contained routes.
Definition: RORouteDef.cpp:413
std::vector< RORoute * > myAlternatives
The alternatives.
Definition: RORouteDef.h:154
OutputDevice & writeXMLDefinition(OutputDevice &dev, const ROVehicle *const veh, bool asAlternatives, bool withExitTimes, bool withCost, bool withLength) const
Saves the built route / route alternatives.
Definition: RORouteDef.cpp:384
RORoute * buildCurrentRoute(SUMOAbstractRouter< ROEdge, ROVehicle > &router, SUMOTime begin, const ROVehicle &veh) const
Triggers building of the complete route (via preComputeCurrentRoute) or returns precomputed route.
Definition: RORouteDef.cpp:84
const bool myMayBeDisconnected
Definition: RORouteDef.h:163
void addAlternativeDef(const RORouteDef *alternative)
Adds an alternative loaded from the file.
Definition: RORouteDef.cpp:75
virtual ~RORouteDef()
Destructor.
Definition: RORouteDef.cpp:59
bool myDiscardSilent
Whether this route should be silently discarded.
Definition: RORouteDef.h:166
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:94
static bool myUsingJTRR
Definition: RORouteDef.h:168
bool myNewRoute
Information whether a new route was generated.
Definition: RORouteDef.h:160
void addAlternative(SUMOAbstractRouter< ROEdge, ROVehicle > &router, const ROVehicle *const, RORoute *current, SUMOTime begin)
Adds an alternative to the list of routes.
Definition: RORouteDef.cpp:274
const bool myTryRepair
Definition: RORouteDef.h:162
int myLastUsed
Index of the route used within the last step.
Definition: RORouteDef.h:151
std::set< RORoute * > myRouteRefs
Routes which are deleted someplace else.
Definition: RORouteDef.h:157
const ROEdge * getDestination() const
Definition: RORouteDef.cpp:378
RORouteDef * copy(const std::string &id, const SUMOTime stopOffset) const
Returns a deep copy of the route definition.
Definition: RORouteDef.cpp:400
bool repairCurrentRoute(SUMOAbstractRouter< ROEdge, ROVehicle > &router, SUMOTime begin, const ROVehicle &veh, ConstROEdgeVector oldEdges, ConstROEdgeVector &newEdges) const
Builds the complete route (or chooses her from the list of alternatives, when existing)
Definition: RORouteDef.cpp:165
A complete router's route.
Definition: RORoute.h:52
void addStopOffset(const SUMOTime offset)
Adapts the until time of all stops by the given offset.
Definition: RORoute.h:193
const ConstROEdgeVector & getEdgeVector() const
Returns the list of edges this route consists of.
Definition: RORoute.h:152
void setCosts(double costs)
Sets the costs of the route.
Definition: RORoute.cpp:64
A vehicle as used by router.
Definition: ROVehicle.h:50
SUMOTime getDepartureTime() const
Returns the time the vehicle starts at, 0 for triggered vehicles.
Definition: ROVehicle.h:92
ConstROEdgeVector getMandatoryEdges(const ROEdge *requiredStart, const ROEdge *requiredEnd) const
compute mandatory edges
Definition: ROVehicle.cpp:170
static double rand(SumoRNG *rng=nullptr)
Returns a random real number in [0, 1)
Definition: RandHelper.cpp:94
Abstract base class providing static factory method.
static RouteCostCalculator< R, E, V > & getCalculator()
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)=0
Builds the route between the given edges using the minimum effort at the given time The definition of...
Some static methods for string processing.
Definition: StringUtils.h:41
NLOHMANN_BASIC_JSON_TPL_DECLARATION void swap(nlohmann::NLOHMANN_BASIC_JSON_TPL &j1, nlohmann::NLOHMANN_BASIC_JSON_TPL &j2) noexcept(//NOLINT(readability-inconsistent-declaration-parameter-name) is_nothrow_move_constructible< nlohmann::NLOHMANN_BASIC_JSON_TPL >::value &&//NOLINT(misc-redundant-expression) is_nothrow_move_assignable< nlohmann::NLOHMANN_BASIC_JSON_TPL >::value)
exchanges the values of two JSON objects
Definition: json.hpp:21884