Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2024 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 :
76 : public:
77 :
78 : /// Constructor
79 482 : 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 482 : myInternalRouter(nullptr), myOriginal(nullptr), mySilent(silent),
84 964 : myMaxTrainLength(maxTrainLength) {
85 482 : myStaticOperation = effortOperation;
86 143296 : for (const E* const edge : edges) {
87 142814 : myInitialEdges.push_back(edge->getRailwayRoutingEdge());
88 : }
89 482 : }
90 :
91 : /// Destructor
92 1584 : virtual ~RailwayRouter() {
93 574 : delete myInternalRouter;
94 2158 : }
95 :
96 310 : SUMOAbstractRouter<E, V>* clone() {
97 310 : return new RailwayRouter<E, V>(this);
98 : }
99 :
100 : /** @brief Builds the route between the given edges using the minimum effort at the given time
101 : The definition of the effort depends on the wished routing scheme */
102 29477 : bool compute(const E* from, const E* to, const V* const vehicle, SUMOTime msTime, std::vector<const E*>& into, bool silent = false) {
103 29477 : ensureInternalRouter();
104 29477 : if (vehicle->getLength() > myMaxTrainLength) {
105 15 : WRITE_WARNINGF("Vehicle '%' with length % exceeds configured value of --railway.max-train-length %",
106 : vehicle->getID(), toString(vehicle->getLength()), toString(myMaxTrainLength));
107 : }
108 29477 : return _compute(from, to, vehicle, msTime, into, silent, false);
109 : }
110 :
111 1674 : void prohibit(const std::vector<E*>& toProhibit) {
112 1674 : ensureInternalRouter();
113 : std::vector<_RailEdge*> railEdges;
114 3210 : for (E* edge : toProhibit) {
115 1536 : railEdges.push_back(edge->getRailwayRoutingEdge());
116 : }
117 1674 : myInternalRouter->prohibit(railEdges);
118 1674 : this->myProhibited = toProhibit;
119 : #ifdef RailwayRouter_DEBUG_ROUTES
120 : std::cout << "RailRouter prohibit=" << toString(toProhibit) << "\n";
121 : #endif
122 1674 : }
123 :
124 :
125 20376 : double recomputeCosts(const std::vector<const E*>& edges, const V* const v, SUMOTime msTime, double* lengthp = nullptr) const {
126 20376 : double effort = SUMOAbstractRouter<E, V>::recomputeCosts(edges, v, msTime, lengthp);
127 : const E* prev = nullptr;
128 : // reversal corrections
129 20376 : double timeCorrection = STEPS2TIME(msTime);
130 734317 : for (const E* const e : edges) {
131 713941 : if (prev != nullptr && e->getBidiEdge() == prev) {
132 15057 : if (e->getLength() > v->getLength()) {
133 : // vehicle doesn't need to drive to the end of the edge
134 : // @note exact timing correction for time-dependent effort is not done
135 15015 : const double savingsFactor = 1 - v->getLength() / e->getLength();
136 : double effortCorrection = 0;
137 15015 : double lengthCorrection = 0.;
138 15015 : effortCorrection += this->getEffort(prev, v, timeCorrection);
139 15015 : this->updateViaCost(prev, e, v, timeCorrection, effortCorrection, lengthCorrection);
140 15015 : effort -= savingsFactor * effortCorrection;
141 15015 : if (lengthp != nullptr) {
142 0 : *lengthp -= savingsFactor * lengthCorrection;
143 : }
144 : }
145 : }
146 : prev = e;
147 : }
148 20376 : return effort;
149 : }
150 :
151 :
152 : private:
153 310 : RailwayRouter(RailwayRouter* other) :
154 : SUMOAbstractRouter<E, V>(other),
155 310 : myInternalRouter(nullptr),
156 310 : myOriginal(other),
157 310 : mySilent(other->mySilent),
158 310 : myMaxTrainLength(other->myMaxTrainLength)
159 310 : {}
160 :
161 31151 : void ensureInternalRouter() {
162 31151 : if (myInternalRouter == nullptr) {
163 1148 : myInternalRouter = new _InternalDijkstra(getRailEdges(), this->myErrorMsgHandler == MsgHandler::getWarningInstance(), &getTravelTimeStatic,
164 574 : nullptr, mySilent, nullptr, this->myHavePermissions, this->myHaveRestrictions);
165 : }
166 31151 : }
167 :
168 29500 : bool _compute(const E* from, const E* to, const V* const vehicle, SUMOTime msTime, std::vector<const E*>& into, bool silent, bool avoidUnsafeBackTracking) {
169 : // 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)
170 : std::vector<double> backLengths;
171 29500 : double backDist = vehicle->getLength() - from->getLength();
172 : const E* start = from;
173 30275 : while (backDist > 0) {
174 1215 : const E* prev = getStraightPredecessor(start, into, (int)backLengths.size());
175 1215 : if (prev == nullptr) {
176 : #ifdef RailwayRouter_DEBUG_ROUTES
177 : std::cout << " Could not determine back edge for vehicle '" << vehicle->getID() << "' when routing from edge '" << from->getID() << "' at time=" << time2string(msTime) << "\n";
178 : #endif
179 : //WRITE_WARNING("Could not determine back edge for vehicle '" + vehicle->getID() + "' when routing from edge '" + from->getID() + "' at time=" + time2string(msTime));
180 : break;
181 : }
182 798 : backDist -= prev->getLength();
183 798 : if (avoidUnsafeBackTracking && prev->getSuccessors().size() > 1) {
184 : bool foundSwitch = false;
185 41 : for (const E* succ : prev->getSuccessors()) {
186 41 : if (succ != start && succ != prev->getBidiEdge()) {
187 : foundSwitch = true;
188 : break;
189 : }
190 : }
191 23 : if (foundSwitch) {
192 : break;
193 : }
194 : }
195 775 : backLengths.push_back(prev->getLength() + (backLengths.empty()
196 775 : ? MIN2(vehicle->getLength(), from->getLength())
197 : : backLengths.back()));
198 : start = prev;
199 : }
200 :
201 : std::vector<const _RailEdge*> intoTmp;
202 29500 : bool success = myInternalRouter->compute(start->getRailwayRoutingEdge(), to->getRailwayRoutingEdge(), vehicle, msTime, intoTmp, silent);
203 : #ifdef RailwayRouter_DEBUG_ROUTES
204 : std::cout << "RailRouter veh=" << vehicle->getID() << " from=" << from->getID() << " to=" << to->getID() << " t=" << time2string(msTime)
205 : << " safe=" << avoidUnsafeBackTracking << " success=" << success << " into=" << toString(into) << "\n";
206 : #endif
207 29500 : if (success) {
208 : const size_t intoSize = into.size();
209 28842 : int backIndex = (int)backLengths.size();
210 420340 : for (const _RailEdge* railEdge : intoTmp) {
211 391498 : if (railEdge->getOriginal() != nullptr) {
212 383811 : backIndex--;
213 : }
214 : // prevent premature reversal on back edge (extend train length)
215 391498 : const double length = backIndex >= 0 ? backLengths[backIndex] : vehicle->getLength();
216 391498 : railEdge->insertOriginalEdges(length, into);
217 : }
218 : #ifdef RailwayRouter_DEBUG_ROUTES
219 : std::cout << "RailRouter: internal result=" << toString(intoTmp) << "\n";
220 : std::cout << "RailRouter: expanded result=" << toString(into) << "\n";
221 : #endif
222 28842 : if (backLengths.size() > 0) {
223 : // skip the virtual back-edges
224 : into.erase(into.begin() + intoSize, into.begin() + intoSize + backLengths.size());
225 : #ifdef RailwayRouter_DEBUG_ROUTES
226 : std::cout << "RailRouter: backLengths=" << toString(backLengths) << " intoSize=" << intoSize << " final result=" << toString(into) << "\n";
227 : #endif
228 583 : if (*(into.begin() + intoSize) != from) {
229 23 : if (!avoidUnsafeBackTracking) {
230 : // try again, this time with more safety (but unable to
231 : // make use of turn-arounds on short edge)
232 : into.erase(into.begin() + intoSize, into.end());
233 23 : return _compute(from, to, vehicle, msTime, into, silent, true);
234 : } else {
235 0 : WRITE_WARNING("Railway routing failure due to turn-around on short edge '" + from->getID()
236 : + "' for vehicle '" + vehicle->getID() + "' time=" + time2string(msTime) + ".");
237 : }
238 : }
239 : }
240 28819 : if (this->myProhibited.size() > 0) {
241 : // make sure that turnarounds don't use prohibited edges
242 2728 : for (const E* e : into) {
243 2298 : if (std::find(this->myProhibited.begin(), this->myProhibited.end(), e) != this->myProhibited.end()) {
244 : into.clear();
245 : success = false;
246 : break;
247 : }
248 : }
249 : }
250 : }
251 : return success;
252 :
253 29500 : }
254 :
255 684 : const std::vector<_RailEdge*>& getRailEdges() {
256 684 : if (myOriginal != nullptr) {
257 110 : return myOriginal->getRailEdges();
258 : }
259 : #ifdef HAVE_FOX
260 574 : FXMutexLock locker(myLock);
261 : #endif
262 574 : if (myRailEdges.empty()) {
263 464 : myRailEdges = myInitialEdges;
264 464 : int numericalID = myInitialEdges.back()->getNumericalID() + 1;
265 34840 : for (_RailEdge* railEdge : myInitialEdges) {
266 34376 : railEdge->init(myRailEdges, numericalID, myMaxTrainLength);
267 : }
268 : }
269 574 : return myRailEdges;
270 : }
271 :
272 1254864 : static inline double getTravelTimeStatic(const RailEdge<E, V>* const edge, const V* const veh, double time) {
273 1254864 : if (edge->getOriginal() != nullptr) {
274 1178466 : return (*myStaticOperation)(edge->getOriginal(), veh, time);
275 : } else {
276 : // turnaround edge
277 76398 : if (edge->isVirtual()) {
278 : // add up time for replacement edges
279 : std::vector<const E*> repl;
280 56410 : edge->insertOriginalEdges(veh->getLength(), repl);
281 : assert(repl.size() > 0);
282 : double seenDist = 0;
283 : double result = 0;
284 : repl.pop_back(); // last edge must not be used fully
285 216708 : for (const E* e : repl) {
286 160298 : result += (*myStaticOperation)(e, veh, time + result);
287 160298 : seenDist += e->getLength();
288 : }
289 56410 : const double lengthOnLastEdge = MAX2(0.0, veh->getLength() - seenDist);
290 56410 : return result + myReversalPenalty + lengthOnLastEdge * myReversalPenaltyFactor;
291 56410 : } else {
292 : // if the edge from which this turnaround starts is longer
293 : // than the vehicle then we are overstimating the cost
294 : // (because the turnaround may happen before driving to the end)
295 : // However, unless the vehicle starts on this edge, we should be taking a
296 : // virtual turnaround at the end of the previous edge. Otherwise, the exaggerated cost doesn't
297 19988 : return myReversalPenalty;
298 : }
299 : }
300 : }
301 :
302 :
303 1215 : static const E* getStraightPredecessor(const E* edge, std::vector<const E*>& prevRoute, int backIndex) {
304 : const E* result = nullptr;
305 : #ifdef RailwayRouter_DEBUG_ROUTES
306 : std::cout << " getStraightPredecessor edge=" << edge->getID() << " prevRouteSize=" << prevRoute.size() << " backIndex=" << backIndex << "\n";
307 : #endif
308 1215 : if ((int)prevRoute.size() > backIndex) {
309 138 : return prevRoute[(int)prevRoute.size() - 1 - backIndex];
310 : }
311 2919 : for (const E* cand : edge->getPredecessors()) {
312 1992 : if (!cand->isInternal() && cand->getBidiEdge() != edge) {
313 : //std::cout << " cand=" << cand->getID() << "\n";
314 960 : if (result == nullptr) {
315 : result = cand;
316 : } else {
317 : // predecessor not unique. Better abort with a warning
318 : return nullptr;
319 : }
320 : }
321 : }
322 : return result;
323 : }
324 :
325 : private:
326 : _InternalRouter* myInternalRouter;
327 : RailwayRouter<E, V>* const myOriginal;
328 : /// @brief a RailEdge for every existing edge, filled on construction (but not in clones)
329 : std::vector<_RailEdge*> myInitialEdges;
330 : /// @brief complete rail network filled on demand (but not in clones)
331 : std::vector<_RailEdge*> myRailEdges;
332 :
333 : /// @brief whether to suppress warning/error if no route was found
334 : const bool mySilent;
335 :
336 : const double myMaxTrainLength;
337 :
338 : #ifdef HAVE_FOX
339 : /// The mutex used to avoid concurrent updates of myRailEdges
340 : mutable FXMutex myLock;
341 : #endif
342 :
343 : /// @brief The object's operation to perform. (hack)
344 : static typename SUMOAbstractRouter<E, V>::Operation myStaticOperation;
345 :
346 : static double myReversalPenalty;
347 : static double myReversalPenaltyFactor;
348 :
349 : private:
350 : /// @brief Invalidated assignment operator
351 : RailwayRouter& operator=(const RailwayRouter& s);
352 :
353 : };
354 :
355 : template<class E, class V>
356 : typename SUMOAbstractRouter<E, V>::Operation RailwayRouter<E, V>::myStaticOperation(nullptr);
357 : template<class E, class V>
358 : double RailwayRouter<E, V>::myReversalPenalty(60);
359 : template<class E, class V>
360 : double RailwayRouter<E, V>::myReversalPenaltyFactor(0.2); // 1/v
|
