Line data Source code
1 : /****************************************************************************/
2 : // Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.dev/sumo
3 : // Copyright (C) 2007-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 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 <microsim/MSNet.h>
24 : #include <microsim/MSEdge.h>
25 : #include <microsim/transportables/MSTransportable.h>
26 : #include "MSRoutingEngine.h"
27 : #include "MSDispatch.h"
28 :
29 : //#define DEBUG_RESERVATION
30 : //#define DEBUG_DETOUR
31 : //#define DEBUG_COND2(obj) (obj->getID() == "p0")
32 : #define DEBUG_COND2(obj) (true)
33 :
34 :
35 : // ===========================================================================
36 : // Reservation methods
37 : // ===========================================================================
38 :
39 : std::string
40 348 : Reservation::getID() const {
41 348 : return toString(persons);
42 : }
43 :
44 : // ===========================================================================
45 : // MSDispatch methods
46 : // ===========================================================================
47 :
48 773 : MSDispatch::MSDispatch(const Parameterised::Map& params) :
49 : Parameterised(params),
50 773 : myOutput(nullptr),
51 773 : myReservationCount(0) {
52 773 : const std::string opt = "device.taxi.dispatch-algorithm.output";
53 773 : if (OptionsCont::getOptions().isSet(opt)) {
54 336 : OutputDevice::createDeviceByOption(opt, "DispatchInfo");
55 168 : myOutput = &OutputDevice::getDeviceByOption(opt);
56 : }
57 1546 : myKeepUnreachableResTime = string2time(OptionsCont::getOptions().getString("device.taxi.dispatch-keep-unreachable"));
58 773 : }
59 :
60 773 : MSDispatch::~MSDispatch() {
61 1138 : for (auto item : myGroupReservations) {
62 730 : for (Reservation* res : item.second) {
63 365 : delete res;
64 : }
65 : }
66 : myGroupReservations.clear();
67 773 : }
68 :
69 :
70 : Reservation*
71 2609 : MSDispatch::addReservation(MSTransportable* person,
72 : SUMOTime reservationTime,
73 : SUMOTime pickupTime,
74 : SUMOTime earliestPickupTime,
75 : const MSEdge* from, double fromPos,
76 : const MSStoppingPlace* fromStop,
77 : const MSEdge* to, double toPos,
78 : const MSStoppingPlace* toStop,
79 : std::string group,
80 : const std::string& line,
81 : int maxCapacity,
82 : int maxContainerCapacity) {
83 : // no new reservation nedded if the person can be added to an existing group
84 2609 : if (group == "") {
85 : // the default empty group implies, no grouping is wanted (and
86 : // transportable ids are unique)
87 2407 : group = person->getID();
88 : }
89 : Reservation* result = nullptr;
90 : bool added = false;
91 : auto it = myGroupReservations.find(group);
92 2609 : if (it != myGroupReservations.end()) {
93 : // try to add to existing reservation
94 139 : for (Reservation* res : it->second) {
95 : if (res->persons.count(person) == 0
96 127 : && res->from == from
97 127 : && res->to == to
98 127 : && res->fromPos == fromPos
99 127 : && res->toPos == toPos) {
100 127 : if (res->persons.size() > 0 && (*res->persons.begin())->isPerson() != person->isPerson()) {
101 0 : WRITE_WARNINGF(TL("Mixing reservations of persons and containers with the same group is not supported for % and %"),
102 : (*res->persons.begin())->getID(), person->getID());
103 : }
104 248 : if ((person->isPerson() && (int)res->persons.size() >= maxCapacity) ||
105 139 : (!person->isPerson() && (int)res->persons.size() >= maxContainerCapacity)) {
106 : // split group to ensure that at least one taxi is capable of delivering group size.
107 12 : continue;
108 : }
109 : res->persons.insert(person);
110 : result = res;
111 : added = true;
112 115 : break;
113 : }
114 : }
115 : }
116 2609 : if (!added) {
117 2494 : Reservation* newRes = new Reservation(toString(myReservationCount++), {person}, reservationTime, pickupTime, earliestPickupTime, from, fromPos, fromStop, to, toPos, toStop, group, line);
118 2494 : myGroupReservations[group].push_back(newRes);
119 : result = newRes;
120 : }
121 2609 : myHasServableReservations = true;
122 : #ifdef DEBUG_RESERVATION
123 : if (DEBUG_COND2(person)) std::cout << SIMTIME
124 : << " addReservation p=" << person->getID()
125 : << " rT=" << time2string(reservationTime)
126 : << " pT=" << time2string(pickupTime)
127 : << " from=" << from->getID() << " fromPos=" << fromPos
128 : << " to=" << to->getID() << " toPos=" << toPos
129 : << " group=" << group
130 : << " added=" << added
131 : << "\n";
132 : #endif
133 2609 : return result;
134 : }
135 :
136 :
137 : std::string
138 87 : MSDispatch::removeReservation(MSTransportable* person,
139 : const MSEdge* from, double fromPos,
140 : const MSEdge* to, double toPos,
141 : std::string group) {
142 87 : if (group == "") {
143 : // the default empty group implies, no grouping is wanted (and
144 : // transportable ids are unique)
145 77 : group = person->getID();
146 : }
147 87 : std::string removedID = "";
148 : auto it = myGroupReservations.find(group);
149 87 : if (it != myGroupReservations.end()) {
150 77 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
151 77 : Reservation* res = *itRes;
152 : if (res->persons.count(person) != 0
153 77 : && res->from == from
154 77 : && res->to == to
155 77 : && res->fromPos == fromPos
156 77 : && res->toPos == toPos) {
157 : res->persons.erase(person);
158 77 : if (res->persons.empty()) {
159 77 : removedID = res->id;
160 77 : it->second.erase(itRes);
161 : // cleans up MSDispatch_Greedy
162 77 : fulfilledReservation(res);
163 77 : if (it->second.empty()) {
164 : myGroupReservations.erase(it);
165 : }
166 : }
167 : break;
168 : }
169 : }
170 : } else {
171 : auto it2 = myRunningReservations.find(group);
172 10 : if (it2 != myRunningReservations.end()) {
173 10 : for (auto item : it2->second) {
174 : const Reservation* res = item.first;
175 : if (res->persons.count(person) != 0
176 10 : && res->from == from
177 10 : && res->to == to
178 10 : && res->fromPos == fromPos
179 10 : && res->toPos == toPos) {
180 : MSDevice_Taxi* taxi = item.second;
181 10 : taxi->cancelCustomer(person);
182 10 : if (res->persons.empty()) {
183 0 : removedID = res->id;
184 : }
185 : break;
186 : }
187 : }
188 : }
189 : }
190 87 : myHasServableReservations = myGroupReservations.size() > 0;
191 : #ifdef DEBUG_RESERVATION
192 : if (DEBUG_COND2(person)) std::cout << SIMTIME
193 : << " removeReservation p=" << person->getID()
194 : << " from=" << from->getID() << " fromPos=" << fromPos
195 : << " to=" << to->getID() << " toPos=" << toPos
196 : << " group=" << group
197 : << " removedID=" << removedID
198 : << " hasServable=" << myHasServableReservations
199 : << "\n";
200 : #endif
201 87 : return removedID;
202 : }
203 :
204 :
205 : Reservation*
206 150 : MSDispatch::updateReservationFromPos(MSTransportable* person,
207 : const MSEdge* from, double fromPos,
208 : const MSEdge* to, double toPos,
209 : std::string group, double newFromPos) {
210 150 : if (group == "") {
211 : // the default empty group implies, no grouping is wanted (and
212 : // transportable ids are unique)
213 : group = person->getID();
214 : }
215 : Reservation* result = nullptr;
216 150 : std::string updatedID = "";
217 : auto it = myGroupReservations.find(group);
218 150 : if (it != myGroupReservations.end()) {
219 66 : for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
220 66 : Reservation* res = *itRes;
221 : // TODO: if there is already a reservation with the newFromPos, add to this reservation
222 : // TODO: if there are other persons in this reservation, create a new reservation for the updated one
223 : if (res->persons.count(person) != 0
224 66 : && res->from == from
225 66 : && res->to == to
226 66 : && res->fromPos == fromPos
227 66 : && res->toPos == toPos) {
228 : // update fromPos
229 66 : res->fromPos = newFromPos;
230 : result = res;
231 66 : updatedID = res->id;
232 : break;
233 : }
234 : }
235 : }
236 : #ifdef DEBUG_RESERVATION
237 : if (DEBUG_COND2(person)) std::cout << SIMTIME
238 : << " updateReservationFromPos p=" << person->getID()
239 : << " from=" << from->getID() << " fromPos=" << fromPos
240 : << " to=" << to->getID() << " toPos=" << toPos
241 : << " group=" << group
242 : << " newFromPos=" << newFromPos
243 : << " updatedID=" << updatedID
244 : << "\n";
245 : #endif
246 150 : return result;
247 : }
248 :
249 :
250 : std::vector<Reservation*>
251 17359 : MSDispatch::getReservations() {
252 : std::vector<Reservation*> reservations;
253 36489 : for (const auto& it : myGroupReservations) {
254 19130 : reservations.insert(reservations.end(), it.second.begin(), it.second.end());
255 : }
256 17359 : return reservations;
257 0 : }
258 :
259 :
260 : std::vector<const Reservation*>
261 4214 : MSDispatch::getRunningReservations() {
262 : std::vector<const Reservation*> result;
263 9551 : for (auto item : myRunningReservations) {
264 10674 : for (auto item2 : item.second) {
265 5337 : result.push_back(item2.first);
266 : }
267 : }
268 4214 : return result;
269 0 : }
270 :
271 :
272 : void
273 2181 : MSDispatch::servedReservation(const Reservation* res, MSDevice_Taxi* taxi) {
274 2181 : auto itR = myRunningReservations.find(res->group);
275 2181 : if (itR != myRunningReservations.end() && itR->second.count(res) != 0) {
276 : return; // was redispatch
277 : }
278 : auto it = myGroupReservations.find(res->group);
279 2057 : if (it == myGroupReservations.end()) {
280 0 : throw ProcessError(TL("Inconsistent group reservations."));
281 : }
282 2057 : auto it2 = std::find(it->second.begin(), it->second.end(), res);
283 2057 : if (it2 == it->second.end()) {
284 0 : throw ProcessError(TL("Inconsistent group reservations (2)."));
285 : }
286 2057 : myRunningReservations[res->group][res] = taxi;
287 2057 : const_cast<Reservation*>(*it2)->state = Reservation::ASSIGNED;
288 2057 : it->second.erase(it2);
289 2057 : if (it->second.empty()) {
290 : myGroupReservations.erase(it);
291 : }
292 : }
293 :
294 :
295 : void
296 2111 : MSDispatch::fulfilledReservation(const Reservation* res) {
297 2111 : myRunningReservations[res->group].erase(res);
298 2111 : if (myRunningReservations[res->group].empty()) {
299 : myRunningReservations.erase(res->group);
300 : }
301 2111 : delete res;
302 2111 : }
303 :
304 :
305 : SUMOTime
306 2733 : MSDispatch::computePickupTime(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
307 : ConstMSEdgeVector edges;
308 2733 : router.compute(taxi->getHolder().getEdge(), taxi->getHolder().getPositionOnLane() - NUMERICAL_EPS,
309 2733 : res.from, res.fromPos, &taxi->getHolder(), t, edges, true);
310 2733 : if (edges.empty()) {
311 : return SUMOTime_MAX;
312 : } else {
313 1825 : return TIME2STEPS(router.recomputeCosts(edges, &taxi->getHolder(), t));
314 : }
315 2733 : }
316 :
317 :
318 : bool
319 2373 : MSDispatch::isReachable(SUMOTime t, const MSDevice_Taxi* taxi, const Reservation& res, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router) {
320 : ConstMSEdgeVector edges;
321 2373 : router.compute(res.from, res.fromPos, res.to, res.toPos, &taxi->getHolder(), t, edges, true);
322 2373 : return !edges.empty();
323 2373 : }
324 :
325 :
326 : double
327 440 : MSDispatch::computeDetourTime(SUMOTime t, SUMOTime viaTime, const MSDevice_Taxi* taxi,
328 : const MSEdge* from, double fromPos,
329 : const MSEdge* via, double viaPos,
330 : const MSEdge* to, double toPos,
331 : SUMOAbstractRouter<MSEdge, SUMOVehicle>& router,
332 : double& timeDirect) {
333 : ConstMSEdgeVector edges;
334 440 : if (timeDirect < 0) {
335 384 : router.compute(from, fromPos, to, toPos, &taxi->getHolder(), t, edges, true);
336 384 : timeDirect = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, toPos, t);
337 : edges.clear();
338 : }
339 :
340 440 : router.compute(from, fromPos, via, viaPos, &taxi->getHolder(), t, edges, true);
341 440 : const double start = STEPS2TIME(t);
342 440 : const double leg1 = router.recomputeCostsPos(edges, &taxi->getHolder(), fromPos, viaPos, t);
343 : #ifdef DEBUG_DETOUR
344 : std::cout << " leg1=" << toString(edges) << " startPos=" << fromPos << " toPos=" << viaPos << " time=" << leg1 << "\n";
345 : #endif
346 440 : const double wait = MAX2(0.0, STEPS2TIME(viaTime) - (start + leg1));
347 : edges.clear();
348 440 : const SUMOTime timeContinue = TIME2STEPS(start + leg1 + wait);
349 440 : router.compute(via, viaPos, to, toPos, &taxi->getHolder(), timeContinue, edges, true);
350 440 : const double leg2 = router.recomputeCostsPos(edges, &taxi->getHolder(), viaPos, toPos, timeContinue);
351 440 : const double timeDetour = leg1 + wait + leg2;
352 : #ifdef DEBUG_DETOUR
353 : std::cout << " leg2=" << toString(edges) << " startPos=" << viaPos << " toPos=" << toPos << " time=" << leg2 << "\n";
354 : std::cout << " t=" << STEPS2TIME(t) << " vt=" << STEPS2TIME(viaTime)
355 : << " from=" << from->getID() << " to=" << to->getID() << " via=" << via->getID()
356 : << " direct=" << timeDirect << " detour=" << timeDetour << " wait=" << wait << "\n";
357 : #endif
358 440 : return timeDetour;
359 440 : }
360 :
361 :
362 : int
363 3182 : MSDispatch::remainingCapacity(const MSDevice_Taxi* taxi, const Reservation* res) {
364 : assert(res->persons.size() > 0);
365 3182 : return ((*res->persons.begin())->isPerson()
366 3182 : ? taxi->getHolder().getVehicleType().getPersonCapacity()
367 192 : : taxi->getHolder().getVehicleType().getContainerCapacity()) - (int)res->persons.size();
368 : }
369 :
370 :
371 : /****************************************************************************/
|
