Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2025 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 : /****************************************************************************/
14 : /// @file RailwayRouter.h
15 : /// @author Jakob Erdmann
16 : /// @date Tue, 25 Feb 2020
17 : ///
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
28 : #include <utils/foxtools/fxheader.h>
29 : #endif
30 : #include <utils/common/MsgHandler.h>
31 : #include <utils/common/SUMOTime.h>
32 : #include <utils/common/ToString.h>
33 : #include <utils/iodevices/OutputDevice.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 : // ===========================================================================
44 : /**
45 : * @class RailwayRouter
46 : * The router for rail vehicles for track networks where some sections may be used in both directions
47 : * and trains may reverse depending on location and train length
48 : *
49 : * Example (assume each track section is 100m long) running from left to right and a negative sign indicates reverse direction
50 : *
51 : * A C D
52 : * .______.______.______.
53 : * ._____/
54 : * B
55 : *
56 : * Consider a train of 200m length that enters on B and must move to A (with a reversal):
57 : * The necessary route is B C D -D -C -A were D,-D are needed for the train to fully pass the switch
58 : *
59 : * We shadow the normal edge graph with a railEdge graph to include virtual
60 : * turnarounds that look at the train length.
61 : * The graph extension takes place via RailEdge::init()
62 : * For edge C we create a virtual turnaround (as successor of C) that connectes C with -C and is then expanded to C D -D -C for trains longer than 100m.
63 : * The expension takes place via RailEdge::insertOriginalEdges()
64 : *
65 : */
66 : template<class E, class V>
67 : class RailwayRouter : public SUMOAbstractRouter<E, V> {
68 :
69 : private:
70 :
71 :
72 : typedef RailEdge<E, V> _RailEdge;
73 : typedef SUMOAbstractRouter<_RailEdge, V> _InternalRouter;
74 : typedef DijkstraRouter<_RailEdge, V> _InternalDijkstra;
75 : typedef std::map<const E*, double> Prohibitions;
76 :
77 : public:
78 :
79 : /// Constructor
80 602 : RailwayRouter(const std::vector<E*>& edges, bool unbuildIsWarning, typename SUMOAbstractRouter<E, V>::Operation effortOperation,
81 : typename SUMOAbstractRouter<E, V>::Operation ttOperation = nullptr, bool silent = false,
82 : bool havePermissions = false, const bool haveRestrictions = false, double maxTrainLength = 5000,
83 : double reversalPenalty = 60) :
84 : SUMOAbstractRouter<E, V>("RailwayRouter", unbuildIsWarning, effortOperation, ttOperation, havePermissions, haveRestrictions),
85 602 : myInternalRouter(nullptr), myOriginal(nullptr), mySilent(silent),
86 602 : myMaxTrainLength(maxTrainLength),
87 1204 : myLastFrom(nullptr)
88 : {
89 602 : myReversalPenalty = reversalPenalty;
90 602 : myStaticOperation = effortOperation;
91 242085 : for (const E* const edge : edges) {
92 241483 : myInitialEdges.push_back(edge->getRailwayRoutingEdge());
93 : }
94 602 : }
95 :
96 : /// Destructor
97 1938 : virtual ~RailwayRouter() {
98 656 : delete myInternalRouter;
99 2594 : }
100 :
101 367 : SUMOAbstractRouter<E, V>* clone() {
102 367 : return new RailwayRouter<E, V>(this);
103 : }
104 :
105 : /** @brief Builds the route between the given edges using the minimum effort at the given time
106 : The definition of the effort depends on the wished routing scheme */
107 29253 : bool compute(const E* from, const E* to, const V* const vehicle, SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
108 29253 : ensureInternalRouter();
109 29253 : if (vehicle->getLength() > myMaxTrainLength) {
110 15 : WRITE_WARNINGF("Vehicle '%' with length % exceeds configured value of --railway.max-train-length %",
111 : vehicle->getID(), toString(vehicle->getLength()), toString(myMaxTrainLength));
112 : }
113 29253 : return _compute(from, to, vehicle, msTime, into, silent, false);
114 : }
115 :
116 96 : void prohibit(const Prohibitions& toProhibit) {
117 96 : ensureInternalRouter();
118 : std::map<const _RailEdge*, double> railEdges;
119 111 : for (auto item : toProhibit) {
120 15 : railEdges[item.first->getRailwayRoutingEdge()] = item.second;
121 : }
122 96 : myInternalRouter->prohibit(railEdges);
123 : this->myProhibited = toProhibit;
124 : #ifdef RailwayRouter_DEBUG_ROUTES
125 : std::cout << "RailRouter numProhibitions=" << toProhibit.size() << "\n";
126 : #endif
127 96 : }
128 :
129 :
130 57048 : double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
131 57048 : double effort = SUMOAbstractRouter<E, V>::recomputeCosts(edges, v, msTime, lengthp);
132 : const E* prev = nullptr;
133 : // reversal corrections
134 57048 : double timeCorrection = STEPS2TIME(msTime);
135 1334729 : for (const E* const e : edges) {
136 1277681 : if (prev != nullptr && e->getBidiEdge() == prev) {
137 15218 : if (e->getLength() > v->getLength()) {
138 : // vehicle doesn't need to drive to the end of the edge
139 : // @note exact timing correction for time-dependent effort is not done
140 15157 : const double savingsFactor = 1 - v->getLength() / e->getLength();
141 : double effortCorrection = 0;
142 15157 : double lengthCorrection = 0.;
143 15157 : effortCorrection += this->getEffort(prev, v, timeCorrection);
144 15157 : this->updateViaCost(prev, e, v, timeCorrection, effortCorrection, lengthCorrection);
145 15157 : effort -= savingsFactor * effortCorrection;
146 15157 : if (lengthp != nullptr) {
147 0 : *lengthp -= savingsFactor * lengthCorrection;
148 : }
149 : }
150 15218 : effort += myReversalPenalty;
151 : }
152 : prev = e;
153 : }
154 57048 : return effort;
155 : }
156 :
157 62 : inline void setBulkMode(const bool mode) {
158 62 : if (myInternalRouter != nullptr) {
159 62 : myInternalRouter->setBulkMode(mode);
160 : }
161 62 : }
162 :
163 : private:
164 367 : RailwayRouter(RailwayRouter* other) :
165 : SUMOAbstractRouter<E, V>(other),
166 367 : myInternalRouter(nullptr),
167 367 : myOriginal(other),
168 367 : mySilent(other->mySilent),
169 367 : myMaxTrainLength(other->myMaxTrainLength)
170 367 : {}
171 :
172 29349 : void ensureInternalRouter() {
173 29349 : if (myInternalRouter == nullptr) {
174 1312 : myInternalRouter = new _InternalDijkstra(getRailEdges(), this->myErrorMsgHandler == MsgHandler::getWarningInstance(), &getTravelTimeStatic,
175 656 : nullptr, mySilent, nullptr, this->myHavePermissions, this->myHaveRestrictions);
176 : }
177 29349 : }
178 :
179 29284 : bool _compute(const E* from, const E* to, const V* const vehicle, SUMOTime msTime, std::vector<const E*>& into, bool silent, bool avoidUnsafeBackTracking) {
180 : // 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)
181 : // if reversals are forbidden (negative penalty), we don't need to check this
182 : std::vector<double> backLengths;
183 29284 : double backDist = myReversalPenalty >= 0 ? vehicle->getLength() - from->getLength() : 0;
184 : const E* start = from;
185 29805 : while (backDist > 0) {
186 915 : const E* prev = getStraightPredecessor(start, into, (int)backLengths.size());
187 915 : if (prev == nullptr) {
188 : #ifdef RailwayRouter_DEBUG_ROUTES
189 : std::cout << " Could not determine back edge for vehicle '" << vehicle->getID() << "' when routing from edge '" << from->getID() << "' at time=" << time2string(msTime) << "\n";
190 : #endif
191 : //WRITE_WARNING("Could not determine back edge for vehicle '" + vehicle->getID() + "' when routing from edge '" + from->getID() + "' at time=" + time2string(msTime));
192 : break;
193 : }
194 552 : backDist -= prev->getLength();
195 552 : if (avoidUnsafeBackTracking && prev->getSuccessors().size() > 1) {
196 : bool foundSwitch = false;
197 54 : for (const E* succ : prev->getSuccessors()) {
198 54 : if (succ != start && succ != prev->getBidiEdge()) {
199 : foundSwitch = true;
200 : break;
201 : }
202 : }
203 31 : if (foundSwitch) {
204 : break;
205 : }
206 : }
207 521 : backLengths.push_back(prev->getLength() + (backLengths.empty()
208 521 : ? MIN2(vehicle->getLength(), from->getLength())
209 : : backLengths.back()));
210 : start = prev;
211 : }
212 :
213 : std::vector<const _RailEdge*> intoTmp;
214 29284 : if (myLastFrom != start) {
215 27901 : myInternalRouter->setBulkMode(false);
216 : }
217 29284 : bool success = myInternalRouter->compute(start->getRailwayRoutingEdge(), to->getRailwayRoutingEdge(), vehicle, msTime, intoTmp, silent);
218 29284 : myLastFrom = start;
219 : #ifdef RailwayRouter_DEBUG_ROUTES
220 : std::cout << "RailRouter veh=" << vehicle->getID() << " from=" << from->getID() << " to=" << to->getID() << " t=" << time2string(msTime)
221 : << " safe=" << avoidUnsafeBackTracking << " success=" << success << " into=" << toString(into) << "\n";
222 : #endif
223 29284 : if (success) {
224 : const size_t intoSize = into.size();
225 29232 : int backIndex = (int)backLengths.size();
226 426174 : for (const _RailEdge* railEdge : intoTmp) {
227 396942 : if (railEdge->getOriginal() != nullptr) {
228 389222 : backIndex--;
229 : }
230 : // prevent premature reversal on back edge (extend train length)
231 396942 : const double length = backIndex >= 0 ? backLengths[backIndex] : vehicle->getLength();
232 396942 : railEdge->insertOriginalEdges(length, into);
233 : }
234 : #ifdef RailwayRouter_DEBUG_ROUTES
235 : std::cout << "RailRouter: internal result=" << toString(intoTmp) << "\n";
236 : std::cout << "RailRouter: expanded result=" << toString(into) << "\n";
237 : std::cout << "RailRouter: backLengths=" << toString(backLengths) << " bls=" << backLengths.size() << " intoSize=" << intoSize << " final result=" << toString(into) << "\n";
238 : #endif
239 29232 : if (backLengths.size() > 0) {
240 : // skip the virtual back-edges
241 : into.erase(into.begin() + intoSize, into.begin() + intoSize + backLengths.size());
242 406 : if (*(into.begin() + intoSize) != from) {
243 31 : if (!avoidUnsafeBackTracking) {
244 : // try again, this time with more safety (but unable to
245 : // make use of turn-arounds on short edge)
246 : into.erase(into.begin() + intoSize, into.end());
247 : // we are starting from a different edge and are thus violating the assumptions of bulk mode
248 31 : success = _compute(from, to, vehicle, msTime, into, silent, true);
249 : return success;
250 : } else {
251 0 : WRITE_WARNING("Railway routing failure due to turn-around on short edge '" + from->getID()
252 : + "' for vehicle '" + vehicle->getID() + "' time=" + time2string(msTime) + ".");
253 : }
254 : }
255 : }
256 29201 : if (this->myProhibited.size() > 0) {
257 : // make sure that turnarounds don't use prohibited edges
258 90 : for (const E* e : into) {
259 81 : if (this->myProhibited.find(e) != this->myProhibited.end()) {
260 : into.clear();
261 : success = false;
262 : break;
263 : }
264 : }
265 : }
266 : }
267 : return success;
268 :
269 29284 : }
270 :
271 767 : const std::vector<_RailEdge*>& getRailEdges() {
272 767 : if (myOriginal != nullptr) {
273 111 : return myOriginal->getRailEdges();
274 : }
275 : #ifdef HAVE_FOX
276 656 : FXMutexLock locker(myLock);
277 : #endif
278 656 : if (myRailEdges.empty()) {
279 545 : myRailEdges = myInitialEdges;
280 545 : int numericalID = myInitialEdges.back()->getNumericalID() + 1;
281 38155 : for (_RailEdge* railEdge : myInitialEdges) {
282 37610 : railEdge->init(myRailEdges, numericalID, myMaxTrainLength, myReversalPenalty >= 0);
283 : }
284 : }
285 656 : return myRailEdges;
286 : }
287 :
288 1265981 : static inline double getTravelTimeStatic(const RailEdge<E, V>* const edge, const V* const veh, double time) {
289 1265981 : if (edge->getOriginal() != nullptr) {
290 1189393 : return (*myStaticOperation)(edge->getOriginal(), veh, time);
291 : } else {
292 : // turnaround edge
293 76588 : if (edge->isVirtual()) {
294 : // add up time for replacement edges
295 : std::vector<const E*> repl;
296 56536 : edge->insertOriginalEdges(veh->getLength(), repl);
297 : assert(repl.size() > 0);
298 : double seenDist = 0;
299 : double result = 0;
300 : repl.pop_back(); // last edge must not be used fully
301 216860 : for (const E* e : repl) {
302 160324 : result += (*myStaticOperation)(e, veh, time + result);
303 160324 : seenDist += e->getLength();
304 : }
305 56536 : const double lengthOnLastEdge = MAX2(0.0, veh->getLength() - seenDist);
306 56536 : return result + myReversalPenalty + lengthOnLastEdge * myReversalPenaltyFactor;
307 56536 : } else {
308 : // if the edge from which this turnaround starts is longer
309 : // than the vehicle then we are overstimating the cost
310 : // (because the turnaround may happen before driving to the end)
311 : // However, unless the vehicle starts on this edge, we should be taking a
312 : // virtual turnaround at the end of the previous edge. Otherwise, the exaggerated cost doesn't
313 20052 : return myReversalPenalty;
314 : }
315 : }
316 : }
317 :
318 :
319 915 : static const E* getStraightPredecessor(const E* edge, std::vector<const E*>& prevRoute, int backIndex) {
320 : const E* result = nullptr;
321 : #ifdef RailwayRouter_DEBUG_ROUTES
322 : std::cout << " getStraightPredecessor edge=" << edge->getID() << " prevRouteSize=" << prevRoute.size() << " backIndex=" << backIndex << "\n";
323 : #endif
324 915 : if ((int)prevRoute.size() > backIndex) {
325 126 : return prevRoute[(int)prevRoute.size() - 1 - backIndex];
326 : }
327 1920 : for (const E* cand : edge->getPredecessors()) {
328 1224 : if (!cand->isInternal() && cand->getBidiEdge() != edge) {
329 : //std::cout << " cand=" << cand->getID() << "\n";
330 612 : if (result == nullptr) {
331 : result = cand;
332 : } else {
333 : // predecessor not unique. Better abort with a warning
334 : return nullptr;
335 : }
336 : }
337 : }
338 : return result;
339 : }
340 :
341 : private:
342 : _InternalRouter* myInternalRouter;
343 : RailwayRouter<E, V>* const myOriginal;
344 : /// @brief a RailEdge for every existing edge, filled on construction (but not in clones)
345 : std::vector<_RailEdge*> myInitialEdges;
346 : /// @brief complete rail network filled on demand (but not in clones)
347 : std::vector<_RailEdge*> myRailEdges;
348 :
349 : /// @brief whether to suppress warning/error if no route was found
350 : const bool mySilent;
351 :
352 : const double myMaxTrainLength;
353 :
354 : /// @brief track previous edge for correct bulk routing
355 : const E* myLastFrom;
356 :
357 : #ifdef HAVE_FOX
358 : /// The mutex used to avoid concurrent updates of myRailEdges
359 : mutable FXMutex myLock;
360 : #endif
361 :
362 : /// @brief The object's operation to perform. (hack)
363 : static typename SUMOAbstractRouter<E, V>::Operation myStaticOperation;
364 :
365 : static double myReversalPenalty;
366 : static double myReversalPenaltyFactor;
367 :
368 : private:
369 : /// @brief Invalidated assignment operator
370 : RailwayRouter& operator=(const RailwayRouter& s);
371 :
372 : };
373 :
374 : template<class E, class V>
375 : typename SUMOAbstractRouter<E, V>::Operation RailwayRouter<E, V>::myStaticOperation(nullptr);
376 : template<class E, class V>
377 : double RailwayRouter<E, V>::myReversalPenalty(60);
378 : template<class E, class V>
379 : double RailwayRouter<E, V>::myReversalPenaltyFactor(0.2); // 1/v
|
