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 240406 : TripItem(const std::string& _line = "") :
70 480812 : 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 14210 : 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 14210 : myAmClone(false), myInternalRouter(nullptr), myIntermodalNet(nullptr),
91 14210 : myCallback(callback), myCarWalkTransfer(carWalkTransfer), myTaxiWait(taxiWait),
92 14210 : myRoutingAlgorithm(routingAlgorithm),
93 28420 : myRoutingMode(routingMode), myExternalEffort(calc) {
94 14210 : }
95 :
96 : /// Destructor
97 33958 : virtual ~IntermodalRouter() {
98 8224 : delete myInternalRouter;
99 16979 : if (!myAmClone) {
100 14207 : delete myIntermodalNet;
101 : }
102 50937 : }
103 :
104 2772 : SUMOAbstractRouter<E, _IntermodalTrip>* clone() {
105 2772 : createNet();
106 2772 : return new IntermodalRouter<E, L, N, V>(myIntermodalNet, myCarWalkTransfer, myTaxiWait, myRoutingAlgorithm, myRoutingMode, myExternalEffort);
107 : }
108 :
109 : int getCarWalkTransfer() const {
110 5454 : 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 212284 : 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 212284 : createNet();
123 212284 : _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 212284 : const _IntermodalEdge* iFrom = originStopID != "" ? myIntermodalNet->getStopEdge(originStopID) : myIntermodalNet->getDepartEdge(from, trip.departPos);
127 212284 : const _IntermodalEdge* iTo = stopID != "" ? myIntermodalNet->getStopEdge(stopID) : myIntermodalNet->getArrivalEdge(to, trip.arrivalPos);
128 212284 : const bool success = myInternalRouter->compute(iFrom, iTo, &trip, msTime, intoEdges, true);
129 212284 : if (success) {
130 212147 : std::string lastLine = "";
131 : const _IntermodalEdge* lastLineEdge = nullptr;
132 212147 : double lastLineTime = STEPS2TIME(msTime);
133 212147 : double time = STEPS2TIME(msTime);
134 212147 : double effort = 0.;
135 212147 : double length = 0.;
136 : const _IntermodalEdge* prev = nullptr;
137 2163369 : for (const _IntermodalEdge* iEdge : intoEdges) {
138 : bool addedEdge = false;
139 1951222 : if (iEdge->includeInRoute(false)) {
140 1121635 : if (iEdge->getLine() == "!stop") {
141 59354 : if (into.size() > 0) {
142 : // previous stage ends at stop
143 39701 : into.back().destStop = iEdge->getID();
144 39701 : if (myExternalEffort != nullptr) {
145 0 : into.back().description = myExternalEffort->output(iEdge->getNumericalID());
146 : }
147 39701 : if (lastLine == "!ped") {
148 : lastLine = ""; // a stop always starts a new trip item
149 : }
150 : } else {
151 : // trip starts at stop
152 : lastLine = "";
153 58959 : into.push_back(TripItem("!stop"));
154 19653 : into.back().destStop = iEdge->getID();
155 : }
156 : } else {
157 1062281 : if (iEdge->getLine() != lastLine || loopedLineTransfer(lastLineEdge, iEdge, lastLineTime, time)) {
158 : lastLine = iEdge->getLine();
159 : lastLineEdge = iEdge;
160 220753 : lastLineTime = time;
161 220753 : if (lastLine == "!car") {
162 4402 : into.push_back(TripItem(vehicle->getID()));
163 2201 : into.back().vType = vehicle->getParameter().vtypeid;
164 218552 : } else if (lastLine == "!ped") {
165 643323 : into.push_back(TripItem());
166 : } else {
167 8222 : into.push_back(TripItem(lastLine));
168 4111 : into.back().depart = iEdge->getIntended(time, into.back().intended);
169 : }
170 220753 : into.back().departPos = iEdge->getStartPos();
171 : }
172 1062281 : if (into.back().edges.empty() || into.back().edges.back() != iEdge->getEdge()) {
173 573191 : into.back().edges.push_back(iEdge->getEdge());
174 573191 : into.back().arrivalPos = iEdge->getEndPos();
175 : addedEdge = true;
176 : }
177 : }
178 : }
179 1951222 : const double prevTime = time;
180 1951222 : const double prevEffort = effort;
181 1951222 : const double prevLength = length;
182 1951222 : myInternalRouter->updateViaCost(prev, iEdge, &trip, time, effort, length);
183 : // correct intermodal length:
184 1951222 : length += iEdge->getPartialLength(&trip) - iEdge->getLength();
185 : prev = iEdge;
186 1951222 : if (!into.empty()) {
187 1757031 : into.back().traveltime += time - prevTime;
188 1757031 : into.back().cost += effort - prevEffort;
189 1757031 : into.back().length += length - prevLength;
190 1757031 : if (into.back().depart < 0) {
191 236299 : into.back().depart = prevTime;
192 : }
193 1757031 : if (addedEdge) {
194 573191 : into.back().exitTimes.push_back(time);
195 : }
196 : }
197 : }
198 : } else {
199 259 : const std::string oType = originStopID != "" ? "stop" : "edge";
200 137 : const std::string oID = originStopID != "" ? originStopID : from->getID();
201 251 : const std::string dType = stopID != "" ? "stop" : "edge";
202 137 : const std::string dID = stopID != "" ? stopID : to->getID();
203 411 : this->myErrorMsgHandler->informf(TL("No connection between % '%' and % '%' found."), oType, oID, dType, dID);
204 : }
205 212284 : if (into.size() > 0) {
206 212147 : into.back().arrivalPos = arrivalPos;
207 : }
208 : #ifdef IntermodalRouter_DEBUG_ROUTES
209 : double time = STEPS2TIME(msTime);
210 : for (const _IntermodalEdge* iEdge : intoEdges) {
211 : const double edgeEffort = myInternalRouter->getEffort(iEdge, &trip, time);
212 : time += edgeEffort;
213 : std::cout << iEdge->getID() << "(" << iEdge->getLine() << "): " << edgeEffort << " l=" << iEdge->getLength() << " pL=" << iEdge->getPartialLength(&trip) << "\n";
214 : }
215 : std::cout << TIME2STEPS(msTime) << " trip from " << from->getID() << " to " << (to != nullptr ? to->getID() : stopID)
216 : << " departPos=" << trip.departPos
217 : << " arrivalPos=" << trip.arrivalPos
218 : << " modes=" << getVehicleClassNames(modeSet)
219 : << " edges=" << toString(intoEdges)
220 : // << " resultEdges=" << toString(into)
221 : << " time=" << time
222 : << "\n";
223 : #endif
224 212284 : return success;
225 212284 : }
226 :
227 : /** @brief Builds the route between the given edges using the minimum effort at the given time
228 : The definition of the effort depends on the wished routing scheme */
229 0 : bool compute(const E*, const E*, const _IntermodalTrip* const,
230 : SUMOTime, std::vector<const E*>&, bool) {
231 0 : throw ProcessError(TL("Do not use this method"));
232 : }
233 :
234 504 : inline void setBulkMode(const bool mode) {
235 : SUMOAbstractRouter<E, _IntermodalTrip>::setBulkMode(mode);
236 504 : if (myInternalRouter != nullptr) {
237 24 : myInternalRouter->setBulkMode(mode);
238 : }
239 504 : }
240 :
241 208805 : void prohibit(const _Prohibitions& toProhibit) {
242 208805 : createNet();
243 : typename _InternalRouter::Prohibitions toProhibitPE;
244 208805 : for (auto item : toProhibit) {
245 0 : toProhibitPE[myIntermodalNet->getBothDirections(item.first).first] = item.second;
246 0 : toProhibitPE[myIntermodalNet->getBothDirections(item.first).second] = item.second;
247 0 : toProhibitPE[myIntermodalNet->getCarEdge(item.first)] = item.second;
248 : }
249 208805 : myInternalRouter->prohibit(toProhibitPE);
250 208805 : }
251 :
252 16 : void writeNetwork(OutputDevice& dev) {
253 16 : createNet();
254 1988 : for (_IntermodalEdge* e : myIntermodalNet->getAllEdges()) {
255 1972 : dev.openTag(SUMO_TAG_EDGE);
256 1972 : dev.writeAttr(SUMO_ATTR_ID, e->getID());
257 1972 : dev.writeAttr(SUMO_ATTR_LINE, e->getLine());
258 1972 : dev.writeAttr(SUMO_ATTR_LENGTH, e->getLength());
259 5916 : dev.writeAttr("successors", toString(e->getSuccessors(SVC_IGNORING)));
260 3944 : dev.closeTag();
261 : }
262 16 : }
263 :
264 8 : void writeWeights(OutputDevice& dev) {
265 8 : createNet();
266 8 : SUMOVTypeParameter dummyVT(DEFAULT_PEDTYPE_ID, SVC_PEDESTRIAN);
267 8 : _IntermodalTrip trip(nullptr, nullptr, 0., 0., DEFAULT_PEDESTRIAN_SPEED, 0, nullptr,
268 : dummyVT, nullptr, SVC_PASSENGER | SVC_BICYCLE | SVC_BUS);
269 1040 : for (_IntermodalEdge* e : myIntermodalNet->getAllEdges()) {
270 1032 : dev.openTag(SUMO_TAG_EDGE);
271 1032 : dev.writeAttr(SUMO_ATTR_ID, e->getID());
272 1032 : dev.writeAttr("traveltime", e->getTravelTime(&trip, 0.));
273 1032 : dev.writeAttr("effort", e->getEffort(&trip, 0.));
274 2064 : dev.closeTag();
275 : }
276 8 : }
277 :
278 : Network* getNetwork() const {
279 77060 : return myIntermodalNet;
280 : }
281 :
282 : EffortCalculator* getExternalEffort() const {
283 4857 : return myExternalEffort;
284 : }
285 :
286 : private:
287 2772 : IntermodalRouter(Network* net, const int carWalkTransfer, double taxiWait, const std::string& routingAlgorithm,
288 : const int routingMode, EffortCalculator* calc) :
289 : SUMOAbstractRouter<E, _IntermodalTrip>("IntermodalRouterClone", true, nullptr, nullptr, false, false),
290 2772 : myAmClone(true), myInternalRouter(nullptr), myIntermodalNet(net),
291 2772 : myCarWalkTransfer(carWalkTransfer),
292 2772 : myTaxiWait(taxiWait),
293 5544 : myRoutingAlgorithm(routingAlgorithm), myRoutingMode(routingMode), myExternalEffort(calc) {
294 2772 : createNet();
295 2772 : }
296 :
297 0 : static inline double getCombined(const _IntermodalEdge* const edge, const _IntermodalTrip* const trip, double time) {
298 0 : return edge->getTravelTime(trip, time) + trip->externalFactor * trip->calc->getEffort(edge->getNumericalID());
299 : }
300 :
301 426657 : inline void createNet() {
302 426657 : if (myIntermodalNet == nullptr) {
303 5454 : myIntermodalNet = new Network(E::getAllEdges(), false, myCarWalkTransfer);
304 5454 : myIntermodalNet->addCarEdges(E::getAllEdges(), myTaxiWait);
305 5454 : myCallback(*this);
306 : }
307 426657 : if (myInternalRouter == nullptr) {
308 8226 : switch (myRoutingMode) {
309 8214 : case 0:
310 8214 : if (myRoutingAlgorithm == "astar") {
311 702 : myInternalRouter = new _InternalAStar(myIntermodalNet->getAllEdges(), true,
312 351 : gWeightsRandomFactor > 1 ? &_IntermodalEdge::getTravelTimeStaticRandomized : &_IntermodalEdge::getTravelTimeStatic, nullptr, true);
313 : } else {
314 15726 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true,
315 7863 : gWeightsRandomFactor > 1 ? &_IntermodalEdge::getTravelTimeStaticRandomized : &_IntermodalEdge::getTravelTimeStatic, nullptr, false, nullptr, true);
316 : }
317 : break;
318 12 : case 1:
319 12 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &_IntermodalEdge::getTravelTimeAggregated, nullptr, false, nullptr, true);
320 12 : break;
321 0 : case 2:
322 0 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &_IntermodalEdge::getEffortStatic, &_IntermodalEdge::getTravelTimeStatic, false, nullptr, true);
323 0 : break;
324 0 : case 3:
325 0 : if (myExternalEffort != nullptr) {
326 0 : std::vector<std::string> edgeLines;
327 0 : for (const auto e : myIntermodalNet->getAllEdges()) {
328 0 : edgeLines.push_back(e->getLine());
329 : }
330 0 : myExternalEffort->init(edgeLines);
331 0 : }
332 0 : myInternalRouter = new _InternalDijkstra(myIntermodalNet->getAllEdges(), true, &getCombined, &_IntermodalEdge::getTravelTimeStatic, false, myExternalEffort, true);
333 0 : break;
334 : }
335 : }
336 426657 : }
337 :
338 :
339 841543 : bool loopedLineTransfer(const _IntermodalEdge* prev, const _IntermodalEdge* cur, double prevTime, double time) {
340 : assert(prev != nullptr);
341 1683086 : if (myIntermodalNet->isLooped(cur->getLine())) {
342 : // check if the last two edges are served by different vehicles
343 : std::string intended1;
344 : std::string intended2;
345 30 : prev->getIntended(prevTime, intended1);
346 30 : cur->getIntended(time, intended2);
347 0 : return intended1 != intended2;
348 : }
349 : return false;
350 : }
351 :
352 : private:
353 : const bool myAmClone;
354 : _InternalRouter* myInternalRouter;
355 : Network* myIntermodalNet;
356 : CreateNetCallback myCallback;
357 : const int myCarWalkTransfer;
358 : const double myTaxiWait;
359 : const std::string myRoutingAlgorithm;
360 : const int myRoutingMode;
361 : EffortCalculator* const myExternalEffort;
362 :
363 :
364 : private:
365 : /// @brief Invalidated assignment operator
366 : IntermodalRouter& operator=(const IntermodalRouter& s);
367 :
368 : };
|
