Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-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 MSDispatch.cpp
15 : /// @author Jakob Erdmann
16 : /// @date 16.12.2019
17 : ///
18 : // An algorithm that performs dispatch for the taxi device
19 : /****************************************************************************/
20 : #include <config.h>
21 :
22 : #include <limits>
23 : #include <utils/xml/SUMOSAXAttributes.h>
24 : #include <microsim/MSNet.h>
25 : #include <microsim/MSEdge.h>
26 : #include <microsim/MSGlobals.h>
27 : #include <microsim/transportables/MSTransportable.h>
28 : #include "MSRoutingEngine.h"
29 : #include "MSDispatch.h"
30 :
31 : //#define DEBUG_RESERVATION
32 : //#define DEBUG_DETOUR
33 : //#define DEBUG_COND2(obj) (obj->getID() == "p0")
34 : #define DEBUG_COND2(obj) (true)
35 :
36 :
37 : // ===========================================================================
38 : // Reservation methods
39 : // ===========================================================================
40 :
41 : // ===========================================================================
42 : // MSDispatch methods
43 : // ===========================================================================
44 :
45 907 : MSDispatch::MSDispatch(const Parameterised::Map& params) :
46 : Parameterised(params),
47 907 : myOutput(nullptr),
48 907 : myReservationCount(0),
49 1814 : myRoutingMode(StringUtils::toInt(getParameter("routingMode", "1"))) {
50 907 : const std::string opt = "device.taxi.dispatch-algorithm.output";
51 907 : if (OptionsCont::getOptions().isSet(opt)) {
52 398 : OutputDevice::createDeviceByOption(opt, "DispatchInfo");
53 199 : myOutput = &OutputDevice::getDeviceByOption(opt);
54 : }
55 1814 : myKeepUnreachableResTime = string2time(OptionsCont::getOptions().getString("device.taxi.dispatch-keep-unreachable"));
56 907 : }
57 :
58 907 : MSDispatch::~MSDispatch() {
59 1298 : for (auto item : myGroupReservations) {
60 782 : for (Reservation* res : item.second) {
61 391 : delete res;
62 : }
63 : }
64 : myGroupReservations.clear();
65 907 : }
66 :
67 :
68 : Reservation*
69 3248 : MSDispatch::addReservation(MSTransportable* person,
70 : SUMOTime reservationTime,
71 : SUMOTime pickupTime,
72 : SUMOTime earliestPickupTime,
73 : const MSEdge* from, double fromPos,
74 : const MSStoppingPlace* fromStop,
75 : const MSEdge* to, double toPos,
76 : const MSStoppingPlace* toStop,
77 : std::string group,
78 : const std::string& line,
79 : int maxCapacity,
80 : int maxContainerCapacity) {
81 : std::string resID;
82 3248 : if (myLoadedReservations.size() > 0) {
83 76 : auto itL = myLoadedReservations.find(person->getID());
84 76 : if (itL != myLoadedReservations.end()) {
85 76 : resID = itL->second;
86 : myLoadedReservations.erase(itL);
87 : }
88 : }
89 : // no new reservation nedded if the person can be added to an existing group
90 3248 : if (group == "") {
91 : // the default empty group implies, no grouping is wanted (and
92 : // transportable ids are unique)
93 2842 : group = person->getID();
94 : } else {
95 : auto it2 = myRunningReservations.find(group);
96 406 : if (it2 != myRunningReservations.end()) {
97 256 : for (auto item : it2->second) {
98 : Reservation* res = const_cast<Reservation*>(item.first);
99 182 : if (res->from == from
100 70 : && res->to == to
101 70 : && (res->fromPos == fromPos || res->fromStop == fromStop)
102 70 : && (res->toPos == toPos || res->toStop == toStop)) {
103 : MSDevice_Taxi* taxi = item.second;
104 : if ((taxi->getState() == taxi->PICKUP
105 60 : && remainingCapacity(taxi, res) > 0
106 60 : && taxi->compatibleLine(taxi->getHolder().getParameter().line, line))
107 70 : || resID == res->id) {
108 : //std::cout << SIMTIME << " addPerson=" << person->getID() << " extendRes=" << toString(res->persons) << " taxi=" << taxi->getHolder().getID() << " state=" << taxi->getState() << "\n";
109 : res->persons.insert(person);
110 60 : taxi->addCustomer(person, res);
111 : #ifdef DEBUG_RESERVATION
112 : if (DEBUG_COND2(person)) std::cout << SIMTIME << " extendedReservation p=" << person->getID() << " resID=" << res->getID() << " taxi=" << taxi->getID() << "\n";
113 : #endif
114 : return res;
115 : }
116 : }
117 : }
118 : }
119 : }
120 : Reservation* result = nullptr;
121 : bool added = false;
122 : auto it = myGroupReservations.find(group);
123 3188 : if (it != myGroupReservations.end()) {
124 : // try to add to existing reservation
125 561 : for (Reservation* res : it->second) {
126 : if (res->persons.count(person) == 0
127 501 : && res->from == from
128 223 : && res->to == to
129 209 : && (res->fromPos == fromPos || res->fromStop == fromStop)
130 209 : && (res->toPos == toPos || res->toStop == toStop)
131 209 : && (resID.empty() || res->id == resID)) {
132 209 : if (res->persons.size() > 0 && (*res->persons.begin())->isPerson() != person->isPerson()) {
133 0 : WRITE_WARNINGF(TL("Mixing reservations of persons and containers with the same group is not supported for % and %"),
134 : (*res->persons.begin())->getID(), person->getID());
135 : }
136 400 : if ((person->isPerson() && (int)res->persons.size() >= maxCapacity) ||
137 209 : (!person->isPerson() && (int)res->persons.size() >= maxContainerCapacity)) {
138 : // split group to ensure that at least one taxi is capable of delivering group size.
139 24 : continue;
140 : }
141 : res->persons.insert(person);
142 : result = res;
143 : added = true;
144 185 : break;
145 : }
146 : }
147 : }
148 3188 : if (!added) {
149 3003 : if (resID.empty()) {
150 5854 : resID = toString(myReservationCount++);
151 : }
152 3003 : Reservation* newRes = new Reservation(resID, {person}, reservationTime, pickupTime, earliestPickupTime, from, fromPos, fromStop, to, toPos, toStop, group, line);
153 3003 : myGroupReservations[group].push_back(newRes);
154 : result = newRes;
155 : }
156 3188 : myHasServableReservations = true;
157 : #ifdef DEBUG_RESERVATION
158 : if (DEBUG_COND2(person)) std::cout << SIMTIME
159 : << " addReservation p=" << person->getID()
160 : << " addID=" << result->getID()
161 : << " rT=" << time2string(reservationTime)
162 : << " pT=" << time2string(pickupTime)
163 : << " from=" << from->getID() << " fromPos=" << fromPos
164 : << " to=" << to->getID() << " toPos=" << toPos
165 : << " group=" << group
166 : << " added=" << added
167 : << "\n";
168 : #endif
169 3188 : return result;
170 : }
171 :
172 :
173 : std::string
174 87 : MSDispatch::removeReservation(MSTransportable* person,
175 : const MSEdge* from, double fromPos,
176 : const MSEdge* to, double toPos,
177 : std::string group) {
178 87 : if (group == "") {
179 : // the default empty group implies, no grouping is wanted (and
180 : // transportable ids are unique)
181 77 : group = person->getID();
182 : }
183 87 : std::string removedID = "";
184 : auto it = myGroupReservations.find(group);
185 87 : if (it != myGroupReservations.end()) {
186 77 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
187 77 : Reservation* res = *itRes;
188 : if (res->persons.count(person) != 0
189 77 : && res->from == from
190 77 : && res->to == to
191 77 : && res->fromPos == fromPos
192 77 : && res->toPos == toPos) {
193 : res->persons.erase(person);
194 77 : if (res->persons.empty()) {
195 77 : removedID = res->id;
196 77 : it->second.erase(itRes);
197 : // cleans up MSDispatch_Greedy
198 77 : fulfilledReservation(res);
199 77 : if (it->second.empty()) {
200 : myGroupReservations.erase(it);
201 : }
202 : }
203 : break;
204 : }
205 : }
206 : } else {
207 : auto it2 = myRunningReservations.find(group);
208 10 : if (it2 != myRunningReservations.end()) {
209 10 : for (auto item : it2->second) {
210 : const Reservation* const res = item.first;
211 : if (res->persons.count(person) != 0
212 10 : && res->from == from
213 10 : && res->to == to
214 10 : && res->fromPos == fromPos
215 10 : && res->toPos == toPos) {
216 10 : if (res->persons.size() == 1) {
217 10 : removedID = res->id;
218 : }
219 10 : item.second->cancelCustomer(person); // will delete res via fulfilledReservation if necessary
220 : break;
221 : }
222 : }
223 : }
224 : }
225 87 : myHasServableReservations = myGroupReservations.size() > 0;
226 : #ifdef DEBUG_RESERVATION
227 : if (DEBUG_COND2(person)) std::cout << SIMTIME
228 : << " removeReservation p=" << person->getID()
229 : << " from=" << from->getID() << " fromPos=" << fromPos
230 : << " to=" << to->getID() << " toPos=" << toPos
231 : << " group=" << group
232 : << " removedID=" << removedID
233 : << " hasServable=" << myHasServableReservations
234 : << "\n";
235 : #endif
236 87 : return removedID;
237 : }
238 :
239 :
240 : Reservation*
241 150 : MSDispatch::updateReservationFromPos(MSTransportable* person,
242 : const MSEdge* from, double fromPos,
243 : const MSEdge* to, double toPos,
244 : std::string group, double newFromPos) {
245 150 : if (group == "") {
246 : // the default empty group implies, no grouping is wanted (and
247 : // transportable ids are unique)
248 150 : group = person->getID();
249 : }
250 : Reservation* result = nullptr;
251 150 : std::string updatedID = "";
252 : auto it = myGroupReservations.find(group);
253 150 : if (it != myGroupReservations.end()) {
254 66 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
255 66 : Reservation* res = *itRes;
256 : // TODO: if there is already a reservation with the newFromPos, add to this reservation
257 : // TODO: if there are other persons in this reservation, create a new reservation for the updated one
258 : if (res->persons.count(person) != 0
259 66 : && res->from == from
260 66 : && res->to == to
261 66 : && res->fromPos == fromPos
262 66 : && res->toPos == toPos) {
263 : // update fromPos
264 66 : res->fromPos = newFromPos;
265 : result = res;
266 66 : updatedID = res->id;
267 : break;
268 : }
269 : }
270 : }
271 : #ifdef DEBUG_RESERVATION
272 : if (DEBUG_COND2(person)) std::cout << SIMTIME
273 : << " updateReservationFromPos p=" << person->getID()
274 : << " from=" << from->getID() << " fromPos=" << fromPos
275 : << " to=" << to->getID() << " toPos=" << toPos
276 : << " group=" << group
277 : << " newFromPos=" << newFromPos
278 : << " updatedID=" << updatedID
279 : << "\n";
280 : #endif
281 150 : return result;
282 : }
283 :
284 :
285 : std::vector<Reservation*>
286 20215 : MSDispatch::getReservations() {
287 : std::vector<Reservation*> reservations;
288 41835 : for (const auto& it : myGroupReservations) {
289 21620 : reservations.insert(reservations.end(), it.second.begin(), it.second.end());
290 : }
291 20215 : return reservations;
292 0 : }
293 :
294 :
295 : std::vector<const Reservation*>
296 4106 : MSDispatch::getRunningReservations() {
297 : std::vector<const Reservation*> result;
298 9493 : for (auto item : myRunningReservations) {
299 10774 : for (auto item2 : item.second) {
300 5387 : result.push_back(item2.first);
301 : }
302 : }
303 4106 : return result;
304 0 : }
305 :
306 :
307 : void
308 2664 : MSDispatch::servedReservation(const Reservation* res, MSDevice_Taxi* taxi) {
309 2664 : auto itR = myRunningReservations.find(res->group);
310 2664 : if (itR != myRunningReservations.end() && itR->second.count(res) != 0) {
311 : #ifdef DEBUG_RESERVATION
312 : std::cout << SIMTIME << " servedReservation res=" << res->id << " taxi=" << taxi->getID() << " (running)\n";
313 : #endif
314 : return; // was redispatch
315 : }
316 : #ifdef DEBUG_RESERVATION
317 : std::cout << SIMTIME << " servedReservation res=" << res->id << " taxi=" << taxi->getID() << "\n";
318 : #endif
319 2540 : auto it = myGroupReservations.find(res->group);
320 2540 : if (it == myGroupReservations.end()) {
321 0 : throw ProcessError(TL("Inconsistent group reservations."));
322 : }
323 2540 : auto it2 = std::find(it->second.begin(), it->second.end(), res);
324 2540 : if (it2 == it->second.end()) {
325 0 : throw ProcessError(TL("Inconsistent group reservations (2)."));
326 : }
327 2540 : myRunningReservations[res->group][res] = taxi;
328 2540 : const_cast<Reservation*>(*it2)->state = Reservation::ASSIGNED;
329 2540 : it->second.erase(it2);
330 2540 : if (it->second.empty()) {
331 : myGroupReservations.erase(it);
332 : }
333 : }
334 :
335 :
336 : void
337 4 : MSDispatch::swappedRunning(const Reservation* res, MSDevice_Taxi* taxi) {
338 : #ifdef DEBUG_RESERVATION
339 : std::cout << SIMTIME << " swapped res=" << res->id << " old=" << myRunningReservations[res->group][res]->getID() << " new=" << taxi->getID() << "\n";
340 : #endif
341 4 : myRunningReservations[res->group][res] = taxi;
342 4 : }
343 :
344 :
345 : void
346 2578 : MSDispatch::fulfilledReservation(const Reservation* res) {
347 : #ifdef DEBUG_RESERVATION
348 : std::cout << SIMTIME << " fullfilled res=" << res->id << "\n";
349 : #endif
350 2578 : myRunningReservations[res->group].erase(res);
351 2578 : if (myRunningReservations[res->group].empty()) {
352 : myRunningReservations.erase(res->group);
353 : }
354 2578 : delete res;
355 2578 : }
356 :
357 :
358 : SUMOAbstractRouter<MSEdge, SUMOVehicle>&
359 15118 : MSDispatch::getRouter() const {
360 30236 : return myRoutingMode == 1 ? MSRoutingEngine::getRouterTT(0, SVC_TAXI) : MSNet::getInstance()->getRouterTT(0);
361 : }
362 :
363 :
364 : SUMOTime
365 3822 : MSDispatch::computePickupTime(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
366 : ConstMSEdgeVector edges;
367 3822 : double fromPos = taxi->getHolder().getPositionOnLane() - NUMERICAL_EPS;
368 3822 : const MSEdge* from = *taxi->getHolder().getRerouteOrigin();
369 3822 : const bool originDiffers = from != taxi->getHolder().getEdge();
370 7615 : router.compute(from, originDiffers ? 0 : fromPos, res.from, res.fromPos, &taxi->getHolder(), t, edges, true);
371 3822 : if (edges.empty()) {
372 : return SUMOTime_MAX;
373 : } else {
374 2913 : if (originDiffers) {
375 : assert(from == *(taxi->getHolder().getCurrentRouteEdge() + 1));
376 29 : edges.insert(edges.begin(), taxi->getHolder().getEdge());
377 : }
378 2913 : return TIME2STEPS(router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, res.fromPos, t));
379 : }
380 3822 : }
381 :
382 :
383 : bool
384 3426 : MSDispatch::isReachable(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
385 : ConstMSEdgeVector edges;
386 3426 : router.compute(res.from, res.fromPos, res.to, res.toPos, &taxi->getHolder(), t, edges, true);
387 3426 : return !edges.empty();
388 3426 : }
389 :
390 :
391 : double
392 438 : MSDispatch::computeDetourTime(SUMOTime t, SUMOTime viaTime, const MSDevice_Taxi* taxi,
393 : const MSEdge* from, double fromPos,
394 : const MSEdge* via, double viaPos,
395 : const MSEdge* to, double toPos,
396 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router,
397 : double& timeDirect) {
398 : ConstMSEdgeVector edges;
399 438 : if (timeDirect < 0) {
400 372 : router.compute(from, fromPos, to, toPos, &taxi->getHolder(), t, edges, true);
401 372 : timeDirect = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, toPos, t);
402 : edges.clear();
403 : }
404 :
405 438 : router.compute(from, fromPos, via, viaPos, &taxi->getHolder(), t, edges, true);
406 438 : const double start = STEPS2TIME(t);
407 438 : const double leg1 = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, viaPos, t);
408 : #ifdef DEBUG_DETOUR
409 : std::cout << " leg1=" << toString(edges) << " startPos=" << fromPos << " toPos=" << viaPos << " time=" << leg1 << "\n";
410 : #endif
411 438 : const double wait = MAX2(0.0, STEPS2TIME(viaTime) - (start + leg1));
412 : edges.clear();
413 438 : const SUMOTime timeContinue = TIME2STEPS(start + leg1 + wait);
414 438 : router.compute(via, viaPos, to, toPos, &taxi->getHolder(), timeContinue, edges, true);
415 438 : const double leg2 = router.recomputeCostsPos(edges, &taxi->getHolder(), viaPos, toPos, timeContinue);
416 438 : const double timeDetour = leg1 + wait + leg2;
417 : #ifdef DEBUG_DETOUR
418 : std::cout << " leg2=" << toString(edges) << " startPos=" << viaPos << " toPos=" << toPos << " time=" << leg2 << "\n";
419 : std::cout << " t=" << STEPS2TIME(t) << " vt=" << STEPS2TIME(viaTime)
420 : << " from=" << from->getID() << " to=" << to->getID() << " via=" << via->getID()
421 : << " direct=" << timeDirect << " detour=" << timeDetour << " wait=" << wait << "\n";
422 : #endif
423 438 : return timeDetour;
424 438 : }
425 :
426 :
427 : int
428 4329 : MSDispatch::remainingCapacity(const MSDevice_Taxi* taxi, const Reservation* res) {
429 : assert(res->persons.size() > 0);
430 4329 : return ((*res->persons.begin())->isPerson()
431 4329 : ? taxi->getHolder().getVehicleType().getPersonCapacity()
432 192 : : taxi->getHolder().getVehicleType().getContainerCapacity()) - (int)res->persons.size();
433 : }
434 :
435 :
436 : void
437 16 : MSDispatch::saveState(OutputDevice& out, SUMOTime nextDispatch) const {
438 16 : out.openTag(SUMO_TAG_DISPATCHER);
439 16 : out.writeAttr(SUMO_ATTR_NEXT, nextDispatch);
440 16 : out.writeAttr(SUMO_ATTR_COUNT, myReservationCount);
441 :
442 16 : std::ostringstream internals;
443 34 : for (const auto& it : myRunningReservations) {
444 38 : for (const auto& item : it.second) {
445 48 : for (const MSTransportable* t : item.first->persons) {
446 28 : internals << t->getID() << " " << item.first->id << " ";
447 : }
448 : }
449 : }
450 61 : for (const auto& it : myGroupReservations) {
451 94 : for (const Reservation* res : it.second) {
452 98 : for (const MSTransportable* t : res->persons) {
453 49 : internals << t->getID() << " " << res->id << " ";
454 : }
455 : }
456 : }
457 16 : out.writeAttr(SUMO_ATTR_CUSTOMERS, internals.str());
458 16 : out.closeTag();
459 16 : }
460 :
461 :
462 : void
463 16 : MSDispatch::loadState(const SUMOSAXAttributes& attrs) {
464 16 : bool ok = true;
465 16 : myReservationCount = attrs.get<int>(SUMO_ATTR_COUNT, "dispatcher", ok);
466 32 : std::istringstream bis(attrs.getString(SUMO_ATTR_CUSTOMERS));
467 : std::string tID, rID;
468 93 : while (bis >> tID && bis >> rID) {
469 77 : myLoadedReservations[tID] = rID;
470 : }
471 16 : }
472 :
473 :
474 :
475 : /****************************************************************************/
|
