Eclipse SUMO - Simulation of Urban MObility
RailwayRouter.h
Go to the documentation of this file.
1 /****************************************************************************/
2 // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3 // Copyright (C) 2001-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 /****************************************************************************/
18 // The RailwayRouter builds a special network for railway routing to handle train reversal restrictions (delegates to a SUMOAbstractRouter)
19 /****************************************************************************/
20 #pragma once
21 #include <config.h>
22 
23 #include <string>
24 #include <vector>
25 #include <algorithm>
26 #include <assert.h>
27 #ifdef HAVE_FOX
29 #endif
31 #include <utils/common/SUMOTime.h>
32 #include <utils/common/ToString.h>
34 #include "SUMOAbstractRouter.h"
35 #include "DijkstraRouter.h"
36 #include "RailEdge.h"
37 
38 
39 //#define RailwayRouter_DEBUG_ROUTES
40 
41 // ===========================================================================
42 // class definitions
43 // ===========================================================================
66 template<class E, class V>
67 class RailwayRouter : public SUMOAbstractRouter<E, V> {
68 
69 private:
70 
71 
75 
76 public:
77 
79  RailwayRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename SUMOAbstractRouter<E, V>::Operation effortOperation,
80  typename SUMOAbstractRouter<E, V>::Operation ttOperation = nullptr, bool silent = false,
81  const bool havePermissions = false, const bool haveRestrictions = false, double maxTrainLength = 5000) :
82  SUMOAbstractRouter<E, V>("RailwayRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
83  myInternalRouter(nullptr), myOriginal(nullptr), mySilent(silent),
84  myMaxTrainLength(maxTrainLength) {
85  myStaticOperation = effortOperation;
86  for (const E* const edge : edges) {
87  myInitialEdges.push_back(edge->getRailwayRoutingEdge());
88  }
89  }
90 
92  virtual ~RailwayRouter() {
93  delete myInternalRouter;
94  }
95 
97  return new RailwayRouter<E, V>(this);
98  }
99 
102  bool compute(const E* from, const E* to, const V* const vehicle, SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
104  if (vehicle->getLength() > myMaxTrainLength) {
105  WRITE_WARNINGF("Vehicle '%' with length % exceeds configured value of --railway.max-train-length %",
106  vehicle->getID(), toString(vehicle->getLength()), toString(myMaxTrainLength));
107  }
108  // make sure that the vehicle can turn-around when starting on a short edge (the virtual turn-around for this lies backwards along the route / track)
109  std::vector<double> backLengths;
110  double backDist = vehicle->getLength() - from->getLength();
111  const E* start = from;
112  while (backDist > 0) {
113  const E* prev = getStraightPredecessor(start);
114  if (prev == nullptr) {
115  //WRITE_WARNING("Could not determine back edge for vehicle '" + vehicle->getID() + "' when routing from edge '" + from->getID() + "' at time=" + time2string(msTime));
116  break;
117  }
118  backDist -= prev->getLength();
119  backLengths.push_back(prev->getLength() + (backLengths.empty() ? from->getLength() : backLengths.back()));
120  start = prev;
121  }
122 
123  std::vector<const _RailEdge*> intoTmp;
124  bool success = myInternalRouter->compute(start->getRailwayRoutingEdge(), to->getRailwayRoutingEdge(), vehicle, msTime, intoTmp, silent);
125 #ifdef RailwayRouter_DEBUG_ROUTES
126  std::cout << "RailRouter veh=" << vehicle->getID() << " from=" << from->getID() << " to=" << to->getID() << " t=" << time2string(msTime) << " success=" << success << "\n";
127 #endif
128  if (success) {
129  const size_t intoSize = into.size();
130  const int backIndex = (int)backLengths.size() - 1;;
131  for (const _RailEdge* railEdge : intoTmp) {
132  // prevent premature reversal on back edge (extend train length)
133  const double length = backIndex >= 0 ? backLengths[backIndex] : vehicle->getLength();
134  railEdge->insertOriginalEdges(length, into);
135  }
136 #ifdef RailwayRouter_DEBUG_ROUTES
137  std::cout << "RailRouter: internal result=" << toString(intoTmp) << "\n";
138  std::cout << "RailRouter: expanded result=" << toString(into) << "\n";
139 #endif
140  if (backLengths.size() > 0) {
141  // skip the virtual back-edges
142  into.erase(into.begin() + intoSize, into.begin() + intoSize + backLengths.size());
143 #ifdef RailwayRouter_DEBUG_ROUTES
144  std::cout << "RailRouter: backLengths=" << toString(backLengths) << " final result=" << toString(into) << "\n";
145 #endif
146  if (*(into.begin() + intoSize) != from) {
147  WRITE_WARNING("Railway routing failure due to turn-around on short edge '" + from->getID()
148  + "' for vehicle '" + vehicle->getID() + "' time=" + time2string(msTime) + ".");
149  }
150  }
151  }
152  return success;
153  }
154 
155  void prohibit(const std::vector<E*>& toProhibit) {
157  std::vector<_RailEdge*> railEdges;
158  for (E* edge : toProhibit) {
159  railEdges.push_back(edge->getRailwayRoutingEdge());
160  }
161  myInternalRouter->prohibit(railEdges);
162  }
163 
164 
165 private:
167  SUMOAbstractRouter<E, V>(other),
168  myInternalRouter(nullptr),
169  myOriginal(other),
170  mySilent(other->mySilent),
172  {}
173 
175  if (myInternalRouter == nullptr) {
177  nullptr, mySilent, nullptr, this->myHavePermissions, this->myHaveRestrictions);
178  }
179  }
180 
181  const std::vector<_RailEdge*>& getRailEdges() {
182  if (myOriginal != nullptr) {
183  return myOriginal->getRailEdges();
184  }
185 #ifdef HAVE_FOX
186  FXMutexLock locker(myLock);
187 #endif
188  if (myRailEdges.empty()) {
190  int numericalID = myInitialEdges.back()->getNumericalID() + 1;
191  for (_RailEdge* railEdge : myInitialEdges) {
192  railEdge->init(myRailEdges, numericalID, myMaxTrainLength);
193  }
194  }
195  return myRailEdges;
196  }
197 
198  static inline double getTravelTimeStatic(const RailEdge<E, V>* const edge, const V* const veh, double time) {
199  if (edge->getOriginal() != nullptr) {
200  return (*myStaticOperation)(edge->getOriginal(), veh, time);
201  } else {
202  // turnaround edge
203  if (edge->isVirtual()) {
204  // add up time for replacement edges
205  std::vector<const E*> repl;
206  edge->insertOriginalEdges(veh->getLength(), repl);
207  assert(repl.size() > 0);
208  double seenDist = 0;
209  double result = 0;
210  repl.pop_back(); // last edge must not be used fully
211  for (const E* e : repl) {
212  result += (*myStaticOperation)(e, veh, time + result);
213  seenDist += e->getLength();
214  }
215  const double lengthOnLastEdge = MAX2(0.0, veh->getLength() - seenDist);
216  return result + myReversalPenalty + lengthOnLastEdge * myReversalPenaltyFactor;
217  } else {
218  // XXX if the edge from which this turnaround starts is longer
219  // than the vehicle, we could return a negative value here
220  // because the turnaround may happen once the vehicle has driven onto the edge
221  return myReversalPenalty;
222  }
223  }
224  }
225 
226 
227  static const E* getStraightPredecessor(const E* edge) {
228  const E* result = nullptr;
229  //std::cout << " getStraightPredecessor edge=" << edge->getID() << "\n";
230  for (const E* cand : edge->getPredecessors()) {
231  if (!cand->isInternal() && cand->getBidiEdge() != edge) {
232  //std::cout << " cand=" << cand->getID() << "\n";
233  if (result == nullptr) {
234  result = cand;
235  } else {
236  // predecessor not unique. Better abort with a warning
237  return nullptr;
238  }
239  }
240  }
241  return result;
242  }
243 
244 private:
248  std::vector<_RailEdge*> myInitialEdges;
250  std::vector<_RailEdge*> myRailEdges;
251 
253  const bool mySilent;
254 
255  const double myMaxTrainLength;
256 
257 #ifdef HAVE_FOX
259  mutable FXMutex myLock;
260 #endif
261 
264 
265  static double myReversalPenalty;
266  static double myReversalPenaltyFactor;
267 
268 private:
271 
272 };
273 
274 template<class E, class V>
276 template<class E, class V>
278 template<class E, class V>
280 
281 
#define WRITE_WARNINGF(...)
Definition: MsgHandler.h:281
#define WRITE_WARNING(msg)
Definition: MsgHandler.h:280
std::string time2string(SUMOTime t)
convert SUMOTime to string
Definition: SUMOTime.cpp:68
long long int SUMOTime
Definition: SUMOTime.h:32
T MAX2(T a, T b)
Definition: StdDefs.h:80
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:46
Computes the shortest path through a network using the Dijkstra algorithm.
static MsgHandler * getWarningInstance()
Returns the instance to add warnings to.
Definition: MsgHandler.cpp:67
the edge type representing backward edges
Definition: RailEdge.h:38
void insertOriginalEdges(double length, std::vector< const E * > &into) const
Definition: RailEdge.h:173
const E * getOriginal() const
Returns the original edge.
Definition: RailEdge.h:162
bool isVirtual() const
Definition: RailEdge.h:252
SUMOAbstractRouter< _RailEdge, V > _InternalRouter
Definition: RailwayRouter.h:73
static double myReversalPenaltyFactor
RailwayRouter< E, V > *const myOriginal
RailwayRouter(RailwayRouter *other)
DijkstraRouter< _RailEdge, V > _InternalDijkstra
Definition: RailwayRouter.h:74
const std::vector< _RailEdge * > & getRailEdges()
std::vector< _RailEdge * > myInitialEdges
a RailEdge for every existing edge, filled on construction (but not in clones)
std::vector< _RailEdge * > myRailEdges
complete rail network filled on demand (but not in clones)
const bool mySilent
whether to suppress warning/error if no route was found
bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)
Builds the route between the given edges using the minimum effort at the given time The definition of...
RailwayRouter(const std::vector< E * > &edges, bool unbuildIsWarning, typename SUMOAbstractRouter< E, V >::Operation effortOperation, typename SUMOAbstractRouter< E, V >::Operation ttOperation=nullptr, bool silent=false, const bool havePermissions=false, const bool haveRestrictions=false, double maxTrainLength=5000)
Constructor.
Definition: RailwayRouter.h:79
static const E * getStraightPredecessor(const E *edge)
SUMOAbstractRouter< E, V > * clone()
Definition: RailwayRouter.h:96
_InternalRouter * myInternalRouter
static SUMOAbstractRouter< E, V >::Operation myStaticOperation
The object's operation to perform. (hack)
const double myMaxTrainLength
void ensureInternalRouter()
RailEdge< E, V > _RailEdge
Definition: RailwayRouter.h:72
static double myReversalPenalty
static double getTravelTimeStatic(const RailEdge< E, V > *const edge, const V *const veh, double time)
RailwayRouter & operator=(const RailwayRouter &s)
Invalidated assignment operator.
virtual ~RailwayRouter()
Destructor.
Definition: RailwayRouter.h:92
void prohibit(const std::vector< E * > &toProhibit)
MsgHandler *const myErrorMsgHandler
the handler for routing errors
const bool myHavePermissions
whether edge permissions need to be considered
virtual void prohibit(const std::vector< E * > &toProhibit)
const bool myHaveRestrictions
whether edge restrictions need to be considered
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...