Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2001-2026 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 IntermodalRouter.h
15 : /// @author Jakob Erdmann
16 : /// @author Michael Behrisch
17 : /// @date Mon, 03 March 2014
18 : ///
19 : // The IntermodalRouter builds a special network and (delegates to a SUMOAbstractRouter)
20 : /****************************************************************************/
21 : #pragma once
22 : #include <config.h>
23 :
24 : #include <string>
25 : #include <vector>
26 : #include <algorithm>
27 : #include <assert.h>
28 : #include <utils/common/MsgHandler.h>
29 : #include <utils/common/SUMOTime.h>
30 : #include <utils/common/ToString.h>
31 : #include <utils/vehicle/SUMOVehicle.h>
32 : #include <utils/iodevices/OutputDevice.h>
33 : #include "SUMOAbstractRouter.h"
34 : #include "DijkstraRouter.h"
35 : #include "AStarRouter.h"
36 : #include "IntermodalNetwork.h"
37 : #include "EffortCalculator.h"
38 : #include "CarEdge.h"
39 : #include "StopEdge.h"
40 : #include "PedestrianRouter.h"
41 :
42 : //#define IntermodalRouter_DEBUG_ROUTES
43 :
44 :
45 : // ===========================================================================
46 : // class definitions
47 : // ===========================================================================
48 : /**
49 : * @class IntermodalRouter
50 : * The router for pedestrians (on a bidirectional network of sidewalks and crossings)
51 : */
52 : template<class E, class L, class N, class V>
53 : class IntermodalRouter : public SUMOAbstractRouter<E, IntermodalTrip<E, N, V> > {
54 : public:
55 : typedef IntermodalNetwork<E, L, N, V> Network;
56 : typedef typename SUMOAbstractRouter<E, SUMOVehicle>::Prohibitions _Prohibitions;
57 :
58 : private:
59 : typedef void(*CreateNetCallback)(IntermodalRouter <E, L, N, V>&);
60 : typedef IntermodalEdge<E, L, N, V> _IntermodalEdge;
61 : typedef IntermodalTrip<E, N, V> _IntermodalTrip;
62 : typedef SUMOAbstractRouter<_IntermodalEdge, _IntermodalTrip> _InternalRouter;
63 : typedef MapMatcher<E, L, N> _MapMatcher;
64 : typedef DijkstraRouter<_IntermodalEdge, _IntermodalTrip> _InternalDijkstra;
65 : typedef AStarRouter<_IntermodalEdge, _IntermodalTrip, _MapMatcher> _InternalAStar;
66 :
67 : public:
68 : struct TripItem {
69 200697 : TripItem(const std::string& _line = "") :
70 401394 : line(_line), intended(_line) {}
71 : std::string line;
72 : std::string vType = "";
73 : std::string destStop = "";
74 : std::string intended; // intended public transport vehicle id
75 : double depart = -1.; // intended public transport departure
76 : std::vector<const E*> edges;
77 : double traveltime = 0.;
78 : double cost = 0.;
79 : double length = 0.;
80 : double departPos = INVALID_DOUBLE;
81 : double arrivalPos = INVALID_DOUBLE;
82 : std::string description = "";
83 : std::vector<double> exitTimes;
84 : };
85 :
86 : /// Constructor
87 14362 : IntermodalRouter(CreateNetCallback callback, const int carWalkTransfer, double taxiWait, const std::string& routingAlgorithm,
88 : const int routingMode = 0, EffortCalculator* calc = nullptr) :
89 : SUMOAbstractRouter<E, _IntermodalTrip>("IntermodalRouter", true, nullptr, nullptr, false, false),
90 14362 : myAmClone(false), myInternalRouter(nullptr), myIntermodalNet(nullptr),
91 14362 : myCallback(callback), myCarWalkTransfer(carWalkTransfer), myTaxiWait(taxiWait),
92 14362 : myRoutingAlgorithm(routingAlgorithm),
93 28724 : myRoutingMode(routingMode), myExternalEffort(calc) {
94 14362 : }
95 :
96 : /// Destructor
97 34360 : virtual ~IntermodalRouter() {
98 8314 : delete myInternalRouter;
99 17180 : if (!myAmClone) {
100 14360 : delete myIntermodalNet;
101 : }
102 51540 : }
103 :
104 2820 : SUMOAbstractRouter<E, _IntermodalTrip>* clone() {
105 2820 : createNet();
106 2820 : return new IntermodalRouter<E, L, N, V>(myIntermodalNet, myCarWalkTransfer, myTaxiWait, myRoutingAlgorithm, myRoutingMode, myExternalEffort);
107 : }
108 :
109 : int getCarWalkTransfer() const {
110 5495 : return myCarWalkTransfer;
111 : }
112 :
113 : /** @brief Builds the route between the given edges using the minimum effort at the given time
114 : The definition of the effort depends on the wished routing scheme */
115 172686 : bool compute(const E* from, const E* to,
116 : const double departPos, const std::string& originStopID,
117 : const double arrivalPos, const std::string& stopID,
118 : const double speed, const V* const vehicle,
119 : const SUMOVTypeParameter& pars,
120 : const SVCPermissions modeSet, const SUMOTime msTime,
121 : std::vector<TripItem>& into, const double externalFactor = 0.) {
122 172686 : createNet();
123 172686 : _IntermodalTrip trip(from, to, departPos, arrivalPos, speed, msTime, nullptr, pars, vehicle, modeSet, myExternalEffort, externalFactor);
124 0 : std::vector<const _IntermodalEdge*> intoEdges;
125 : //std::cout << "compute from=" << from->getID() << " to=" << to->getID() << " dPos=" << departPos << " aPos=" << arrivalPos << " stopID=" << stopID << " speed=" << speed << " veh=" << Named::getIDSecure(vehicle) << " modeSet=" << modeSet << " t=" << msTime << " iFrom=" << myIntermodalNet->getDepartEdge(from, trip.departPos)->getID() << " iTo=" << (stopID != "" ? myIntermodalNet->getStopEdge(stopID) : myIntermodalNet->getArrivalEdge(to, trip.arrivalPos))->getID() << "\n";
126 172686 : const _IntermodalEdge* iFrom = originStopID != "" ? myIntermodalNet->getStopEdge(originStopID) : myIntermodalNet->getDepartEdge(from, trip.departPos);
127 172686 : const _IntermodalEdge* iTo = stopID != "" ? myIntermodalNet->getStopEdge(stopID) : myIntermodalNet->getArrivalEdge(to, trip.arrivalPos);
128 172686 : const bool success = myInternalRouter->compute(iFrom, iTo, &trip, msTime, intoEdges, true);
129 172686 : if (success) {
130 172529 : std::string lastLine = "";
131 : const _IntermodalEdge* lastLineEdge = nullptr;
132 172529 : double lastLineTime = STEPS2TIME(msTime);
133 172529 : double time = STEPS2TIME(msTime);
134 172529 : double effort = 0.;
135 172529 : double length = 0.;
136 : const _IntermodalEdge* prev = nullptr;
137 1817734 : for (const _IntermodalEdge* iEdge : intoEdges) {
138 : bool addedEdge = false;
139 1645205 : if (iEdge->includeInRoute(false)) {
140 933462 : if (iEdge->getLine() == "!stop") {
141 59243 : if (into.size() > 0) {
142 : // previous stage ends at stop
143 39565 : into.back().destStop = iEdge->getID();
144 39565 : if (myExternalEffort != nullptr) {
145 0 : into.back().description = myExternalEffort->output(iEdge->getNumericalID());
146 : }
147 39565 : if (lastLine == "!ped") {
148 : lastLine = ""; // a stop always starts a new trip item
149 : }
150 : } else {
151 : // trip starts at stop
152 : lastLine = "";
153 59034 : into.push_back(TripItem("!stop"));
154 19678 : into.back().destStop = iEdge->getID();
155 : }
156 : } else {
157 874219 : if (iEdge->getLine() != lastLine || loopedLineTransfer(lastLineEdge, iEdge, lastLineTime, time)) {
158 : lastLine = iEdge->getLine();
159 : lastLineEdge = iEdge;
160 181019 : lastLineTime = time;
161 181019 : if (lastLine == "!car") {
162 4488 : into.push_back(TripItem(vehicle->getID()));
163 2244 : into.back().vType = vehicle->getParameter().vtypeid;
164 178775 : } else if (lastLine == "!ped") {
165 524178 : into.push_back(TripItem());
166 : } else {
167 8098 : into.push_back(TripItem(lastLine));
168 4049 : into.back().depart = iEdge->getIntended(time, into.back().intended);
169 : }
170 181019 : into.back().departPos = iEdge->getStartPos();
171 : }
172 874219 : if (into.back().edges.empty() || into.back().edges.back() != iEdge->getEdge()) {
173 493762 : into.back().edges.push_back(iEdge->getEdge());
174 493762 : into.back().arrivalPos = iEdge->getEndPos();
175 : addedEdge = true;
176 : }
177 : }
178 : }
179 1645205 : const double prevTime = time;
180 1645205 : const double prevEffort = effort;
181 1645205 : const double prevLength = length;
182 1645205 : myInternalRouter->updateViaCost(prev, iEdge, &trip, time, effort, length);
183 : // correct intermodal length:
184 1645205 : length += iEdge->getPartialLength(&trip) - iEdge->getLength();
185 : prev = iEdge;
186 1645205 : if (!into.empty()) {
187 1490682 : into.back().traveltime += time - prevTime;
188 1490682 : into.back().cost += effort - prevEffort;
189 1490682 : into.back().length += length - prevLength;
190 1490682 : if (into.back().depart < 0) {
191 196652 : into.back().depart = prevTime;
192 : }
193 1490682 : if (addedEdge) {
194 493762 : into.back().exitTimes.push_back(time);
195 : }
196 : }
197 : }
198 : } else {
199 287 : const std::string oType = originStopID != "" ? "stop" : "edge";
200 157 : const std::string oID = originStopID != "" ? originStopID : from->getID();
201 279 : const std::string dType = stopID != "" ? "stop" : "edge";
202 157 : const std::string dID = stopID != "" ? stopID : to->getID();
203 187 : const std::string vClass = vehicle == nullptr ? "" : (" with vClass " + getVehicleClassNames(vehicle->getVClass()));
204 471 : this->myErrorMsgHandler->informf(TL("No connection between % '%' and % '%' found%."), oType, oID, dType, dID, vClass);
205 : }
206 172686 : if (into.size() > 0) {
207 172529 : into.back().arrivalPos = arrivalPos;
208 : }
209 : #ifdef IntermodalRouter_DEBUG_ROUTES
210 : double time = STEPS2TIME(msTime);
211 : for (const _IntermodalEdge* iEdge : intoEdges) {
212 : const double edgeEffort = myInternalRouter->getEffort(iEdge, &trip, time);
213 : time += edgeEffort;
214 : std::cout << iEdge->getID() << "(" << iEdge->getLine() << "): " << edgeEffort << " l=" << iEdge->getLength() << " pL=" << iEdge->getPartialLength(&trip) << "\n";
215 : }
216 : std::cout << TIME2STEPS(msTime) << " trip from " << from->getID() << " to " << (to != nullptr ? to->getID() : stopID)
217 : << " departPos=" << trip.departPos
218 : << " arrivalPos=" << trip.arrivalPos
219 : << " modes=" << getVehicleClassNames(modeSet)
220 : << " vehType=" << (vehicle == nullptr ? "NULL" : vehicle->getVTypeParameter().id)
221 : << " edges=" << toString(intoEdges)
222 : // << " resultEdges=" << toString(into)
223 : << " time=" << time
224 : << "\n";
225 : #endif
226 172686 : return success;
227 172686 : }
228 :
229 : /** @brief Builds the route between the given edges using the minimum effort at the given time
230 : The definition of the effort depends on the wished routing scheme */
231 0 : bool compute(const E*, const E*, const _IntermodalTrip* const,
232 : SUMOTime, std::vector<const E*>&, bool) {
233 0 : throw ProcessError(TL("Do not use this method"));
234 : }
235 :
236 710 : inline void setBulkMode(const bool mode) {
237 : SUMOAbstractRouter<E, _IntermodalTrip>::setBulkMode(mode);
238 710 : if (myInternalRouter != nullptr) {
239 24 : myInternalRouter->setBulkMode(mode);
240 : }
241 710 : }
242 :
243 169161 : void prohibit(const _Prohibitions& toProhibit) {
244 169161 : createNet();
245 : typename _InternalRouter::Prohibitions toProhibitPE;
246 169161 : for (auto item : toProhibit) {
247 0 : toProhibitPE[myIntermodalNet->getBothDirections(item.first).first] = item.second;
248 0 : toProhibitPE[myIntermodalNet->getBothDirections(item.first).second] = item.second;
249 0 : toProhibitPE[myIntermodalNet->getCarEdge(item.first)] = item.second;
250 : }
251 169161 : myInternalRouter->prohibit(toProhibitPE);
252 169161 : }
253 :
254 16 : void writeNetwork(OutputDevice& dev) {
255 16 : createNet();
256 1988 : for (_IntermodalEdge* e : myIntermodalNet->getAllEdges()) {
257 1972 : dev.openTag(SUMO_TAG_EDGE);
258 1972 : dev.writeAttr(SUMO_ATTR_ID, e->getID());
259 1972 : dev.writeAttr(SUMO_ATTR_LINE, e->getLine());
260 1972 : dev.writeAttr(SUMO_ATTR_LENGTH, e->getLength());
261 3944 : dev.writeAttr("successors", toString(e->getSuccessors(SVC_IGNORING)));
262 3944 : dev.closeTag();
263 : }
264 16 : }
265 :
266 8 : void writeWeights(OutputDevice& dev) {
267 8 : createNet();
268 8 : SUMOVTypeParameter dummyVT(DEFAULT_PEDTYPE_ID, SVC_PEDESTRIAN);
269 8 : _IntermodalTrip trip(nullptr, nullptr, 0., 0., DEFAULT_PEDESTRIAN_SPEED, 0, nullptr,
270 : dummyVT, nullptr, SVC_PASSENGER | SVC_BICYCLE | SVC_BUS);
271 1040 : for (_IntermodalEdge* e : myIntermodalNet->getAllEdges()) {
272 1032 : dev.openTag(SUMO_TAG_EDGE);
273 1032 : dev.writeAttr(SUMO_ATTR_ID, e->getID());
274 1032 : dev.writeAttr("traveltime", e->getTravelTime(&trip, 0.));
275 1032 : dev.writeAttr("effort", e->getEffort(&trip, 0.));
276 2064 : dev.closeTag();
277 : }
278 8 : }
279 :
280 : Network* getNetwork() const {
281 77020 : return myIntermodalNet;
282 : }
283 :
284 : EffortCalculator* getExternalEffort() const {
285 4898 : return myExternalEffort;
286 : }
287 :
288 : private:
289 2820 : IntermodalRouter(Network* net, const int carWalkTransfer, double taxiWait, const std::string& routingAlgorithm,
290 : const int routingMode, EffortCalculator* calc) :
291 : SUMOAbstractRouter<E, _IntermodalTrip>("IntermodalRouterClone", true, nullptr, nullptr, false, false),
292 2820 : myAmClone(true), myInternalRouter(nullptr), myIntermodalNet(net),
293 2820 : myCarWalkTransfer(carWalkTransfer),
294 2820 : myTaxiWait(taxiWait),
295 5640 : myRoutingAlgorithm(routingAlgorithm), myRoutingMode(routingMode), myExternalEffort(calc) {
296 2820 : createNet();
297 2820 : }
298 :
299 0 : static inline double getCombined(const _IntermodalEdge* const edge, const _IntermodalTrip* const trip, double time) {
300 0 : return edge->getTravelTime(trip, time) + trip->externalFactor * trip->calc->getEffort(edge->getNumericalID());
301 : }
302 :
303 347511 : inline void createNet() {
304 347511 : if (myIntermodalNet == nullptr) {
305 5495 : myIntermodalNet = new Network(E::getAllEdges(), false, myCarWalkTransfer);
306 5495 : myIntermodalNet->addCarEdges(E::getAllEdges(), myTaxiWait);
307 5495 : myCallback(*this);
308 : }
309 347511 : if (myInternalRouter == nullptr) {
310 8315 : switch (myRoutingMode) {
311 8303 : case 0:
312 8303 : if (myRoutingAlgorithm == "astar") {
313 702 : myInternalRouter = new _InternalAStar(myIntermodalNet->getAllEdges(), true,
314 351 : gWeightsRandomFactor > 1 ? &_IntermodalEdge::getTravelTimeStaticRandomized : &_IntermodalEdge::getTravelTimeStatic, nullptr, true);
315 : } else {
316 15904 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true,
317 7952 : gWeightsRandomFactor > 1 ? &_IntermodalEdge::getTravelTimeStaticRandomized : &_IntermodalEdge::getTravelTimeStatic, nullptr, false, nullptr, true);
318 : }
319 : break;
320 12 : case 1:
321 12 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &_IntermodalEdge::getTravelTimeAggregated, nullptr, false, nullptr, true);
322 12 : break;
323 0 : case 2:
324 0 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &_IntermodalEdge::getEffortStatic, &_IntermodalEdge::getTravelTimeStatic, false, nullptr, true);
325 0 : break;
326 0 : case 3:
327 0 : if (myExternalEffort != nullptr) {
328 0 : std::vector<std::string> edgeLines;
329 0 : for (const auto e : myIntermodalNet->getAllEdges()) {
330 0 : edgeLines.push_back(e->getLine());
331 : }
332 0 : myExternalEffort->init(edgeLines);
333 0 : }
334 0 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &getCombined, &_IntermodalEdge::getTravelTimeStatic, false, myExternalEffort, true);
335 0 : break;
336 : }
337 : }
338 347511 : }
339 :
340 :
341 693215 : bool loopedLineTransfer(const _IntermodalEdge* prev, const _IntermodalEdge* cur, double prevTime, double time) {
342 : assert(prev != nullptr);
343 1386430 : if (myIntermodalNet->isLooped(cur->getLine())) {
344 : // check if the last two edges are served by different vehicles
345 : std::string intended1;
346 : std::string intended2;
347 30 : prev->getIntended(prevTime, intended1);
348 30 : cur->getIntended(time, intended2);
349 0 : return intended1 != intended2;
350 : }
351 : return false;
352 : }
353 :
354 : private:
355 : const bool myAmClone;
356 : _InternalRouter* myInternalRouter;
357 : Network* myIntermodalNet;
358 : CreateNetCallback myCallback;
359 : const int myCarWalkTransfer;
360 : const double myTaxiWait;
361 : const std::string myRoutingAlgorithm;
362 : const int myRoutingMode;
363 : EffortCalculator* const myExternalEffort;
364 :
365 :
366 : private:
367 : /// @brief Invalidated assignment operator
368 : IntermodalRouter& operator=(const IntermodalRouter& s);
369 :
370 : };
|
