Eclipse SUMO - Simulation of Urban MObility
MSDispatch.cpp
Go to the documentation of this file.
1/****************************************************************************/
2// Eclipse SUMO, Simulation of Urban MObility; see https://eclipse.org/sumo
3// Copyright (C) 2007-2022 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/****************************************************************************/
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>
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
39std::string
41 return toString(persons);
42}
43
44// ===========================================================================
45// MSDispatch methods
46// ===========================================================================
47
49 Parameterised(params),
50 myOutput(nullptr),
51 myReservationCount(0) {
52 const std::string opt = "device.taxi.dispatch-algorithm.output";
53 if (OptionsCont::getOptions().isSet(opt)) {
54 OutputDevice::createDeviceByOption(opt, "DispatchInfo");
56 }
57}
58
59
62 SUMOTime reservationTime,
63 SUMOTime pickupTime,
64 const MSEdge* from, double fromPos,
65 const MSEdge* to, double toPos,
66 std::string group,
67 const std::string& line,
68 int maxCapacity,
69 int maxContainerCapacity) {
70 // no new reservation nedded if the person can be added to an existing group
71 if (group == "") {
72 // the default empty group implies, no grouping is wanted (and
73 // transportable ids are unique)
74 group = person->getID();
75 }
76 Reservation* result = nullptr;
77 bool added = false;
78 auto it = myGroupReservations.find(group);
79 if (it != myGroupReservations.end()) {
80 // try to add to existing reservation
81 for (Reservation* res : it->second) {
82 if (res->persons.count(person) == 0
83 && res->from == from
84 && res->to == to
85 && res->fromPos == fromPos
86 && res->toPos == toPos) {
87 if (res->persons.size() > 0 && (*res->persons.begin())->isPerson() != person->isPerson()) {
88 WRITE_WARNINGF(TL("Mixing reservations of persons and containers with the same group is not supported for % and %"),
89 (*res->persons.begin())->getID(), person->getID());
90 }
91 if ((person->isPerson() && (int)res->persons.size() >= maxCapacity) ||
92 (!person->isPerson() && (int)res->persons.size() >= maxContainerCapacity)) {
93 // split group to ensure that at least one taxi is capable of delivering group size.
94 continue;
95 }
96 res->persons.insert(person);
97 result = res;
98 added = true;
99 break;
100 }
101 }
102 }
103 if (!added) {
104 Reservation* newRes = new Reservation(toString(myReservationCount++), {person}, reservationTime, pickupTime, from, fromPos, to, toPos, group, line);
105 myGroupReservations[group].push_back(newRes);
106 result = newRes;
107 }
109#ifdef DEBUG_RESERVATION
110 if (DEBUG_COND2(person)) std::cout << SIMTIME
111 << " addReservation p=" << person->getID()
112 << " rT=" << time2string(reservationTime)
113 << " pT=" << time2string(pickupTime)
114 << " from=" << from->getID() << " fromPos=" << fromPos
115 << " to=" << to->getID() << " toPos=" << toPos
116 << " group=" << group
117 << " added=" << added
118 << "\n";
119#endif
120 return result;
121}
122
123
124std::string
126 const MSEdge* from, double fromPos,
127 const MSEdge* to, double toPos,
128 std::string group) {
129 if (group == "") {
130 // the default empty group implies, no grouping is wanted (and
131 // transportable ids are unique)
132 group = person->getID();
133 }
134 std::string removedID = "";
135 auto it = myGroupReservations.find(group);
136 if (it != myGroupReservations.end()) {
137 // try to add to existing reservation
138 for (auto itRes = it->second.begin(); itRes != it->second.end(); itRes++) {
139 Reservation* res = *itRes;
140 if (res->persons.count(person) != 0
141 && res->from == from
142 && res->to == to
143 && res->fromPos == fromPos
144 && res->toPos == toPos) {
145 res->persons.erase(person);
146 if (res->persons.empty()) {
147 removedID = res->id;
149 it->second.erase(itRes);
150 }
151 break;
152 }
153 }
154 }
155#ifdef DEBUG_RESERVATION
156 if (DEBUG_COND2(person)) std::cout << SIMTIME
157 << " removeReservation p=" << person->getID()
158 << " from=" << from->getID() << " fromPos=" << fromPos
159 << " to=" << to->getID() << " toPos=" << toPos
160 << " group=" << group
161 << " removedID=" << removedID
162 << "\n";
163#endif
164 return removedID;
165}
166
167
168std::vector<Reservation*>
170 std::vector<Reservation*> reservations;
171 for (const auto& it : myGroupReservations) {
172 reservations.insert(reservations.end(), it.second.begin(), it.second.end());
173 }
174 return reservations;
175}
176
177
178std::vector<const Reservation*>
180 return std::vector<const Reservation*>(myRunningReservations.begin(), myRunningReservations.end());
181}
182
183
184void
186 if (myRunningReservations.count(res)) {
187 return; // was redispatch
188 }
189 auto it = myGroupReservations.find(res->group);
190 if (it == myGroupReservations.end()) {
191 throw ProcessError("Inconsistent group reservations.");
192 }
193 auto it2 = std::find(it->second.begin(), it->second.end(), res);
194 if (it2 == it->second.end()) {
195 throw ProcessError("Inconsistent group reservations (2).");
196 }
197 myRunningReservations.insert(*it2);
198 const_cast<Reservation*>(*it2)->state = Reservation::ASSIGNED;
199 it->second.erase(it2);
200 if (it->second.empty()) {
201 myGroupReservations.erase(it);
202 }
203}
204
205
206void
208 myRunningReservations.erase(res);
209 delete res;
210}
211
212
215 ConstMSEdgeVector edges;
216 router.compute(taxi->getHolder().getEdge(), taxi->getHolder().getPositionOnLane() - NUMERICAL_EPS,
217 res.from, res.fromPos, &taxi->getHolder(), t, edges, true);
218 return TIME2STEPS(router.recomputeCosts(edges, &taxi->getHolder(), t));
219}
220
221
222double
224 const MSEdge* from, double fromPos,
225 const MSEdge* via, double viaPos,
226 const MSEdge* to, double toPos,
228 double& timeDirect) {
229 ConstMSEdgeVector edges;
230 if (timeDirect < 0) {
231 router.compute(from, fromPos, to, toPos, &taxi->getHolder(), t, edges, true);
232 timeDirect = router.recomputeCosts(edges, &taxi->getHolder(), fromPos, toPos, t);
233 edges.clear();
234 }
235
236 router.compute(from, fromPos, via, viaPos, &taxi->getHolder(), t, edges, true);
237 const double start = STEPS2TIME(t);
238 const double leg1 = router.recomputeCosts(edges, &taxi->getHolder(), fromPos, viaPos, t);
239#ifdef DEBUG_DETOUR
240 std::cout << " leg1=" << toString(edges) << " startPos=" << fromPos << " toPos=" << viaPos << " time=" << leg1 << "\n";
241#endif
242 const double wait = MAX2(0.0, STEPS2TIME(viaTime) - (start + leg1));
243 edges.clear();
244 const SUMOTime timeContinue = TIME2STEPS(start + leg1 + wait);
245 router.compute(via, viaPos, to, toPos, &taxi->getHolder(), timeContinue, edges, true);
246 const double leg2 = router.recomputeCosts(edges, &taxi->getHolder(), viaPos, toPos, timeContinue);
247 const double timeDetour = leg1 + wait + leg2;
248#ifdef DEBUG_DETOUR
249 std::cout << " leg2=" << toString(edges) << " startPos=" << viaPos << " toPos=" << toPos << " time=" << leg2 << "\n";
250 std::cout << " t=" << STEPS2TIME(t) << " vt=" << STEPS2TIME(viaTime)
251 << " from=" << from->getID() << " to=" << to->getID() << " via=" << via->getID()
252 << " direct=" << timeDirect << " detour=" << timeDetour << " wait=" << wait << "\n";
253#endif
254 return timeDetour;
255}
256
257
258int
260 assert(res->persons.size() > 0);
261 return ((*res->persons.begin())->isPerson()
263 : taxi->getHolder().getVehicleType().getContainerCapacity()) - (int)res->persons.size();
264}
265
266
267/****************************************************************************/
long long int SUMOTime
Definition: GUI.h:36
#define DEBUG_COND2(obj)
Definition: MSDispatch.cpp:32
std::vector< const MSEdge * > ConstMSEdgeVector
Definition: MSEdge.h:74
#define WRITE_WARNINGF(...)
Definition: MsgHandler.h:266
#define TL(string)
Definition: MsgHandler.h:282
std::string time2string(SUMOTime t)
convert SUMOTime to string
Definition: SUMOTime.cpp:68
#define STEPS2TIME(x)
Definition: SUMOTime.h:54
#define SIMTIME
Definition: SUMOTime.h:61
#define TIME2STEPS(x)
Definition: SUMOTime.h:56
T MAX2(T a, T b)
Definition: StdDefs.h:77
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:46
A device which collects info on the vehicle trip (mainly on departure and arrival)
Definition: MSDevice_Taxi.h:49
OutputDevice * myOutput
optional file output for dispatch information
Definition: MSDispatch.h:182
int remainingCapacity(const MSDevice_Taxi *taxi, const Reservation *res)
whether the given taxi has sufficient capacity to serve the reservation
Definition: MSDispatch.cpp:259
static SUMOTime computePickupTime(SUMOTime t, const MSDevice_Taxi *taxi, const Reservation &res, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router)
compute time to pick up the given reservation
Definition: MSDispatch.cpp:214
virtual std::string removeReservation(MSTransportable *person, const MSEdge *from, double fromPos, const MSEdge *to, double toPos, std::string group)
remove person from reservation. If the whole reservation is removed, return it's id
Definition: MSDispatch.cpp:125
bool myHasServableReservations
whether the last call to computeDispatch has left servable reservations
Definition: MSDispatch.h:170
std::map< std::string, std::vector< Reservation * > > myGroupReservations
Definition: MSDispatch.h:185
std::vector< Reservation * > getReservations()
retrieve all reservations
Definition: MSDispatch.cpp:169
virtual std::vector< const Reservation * > getRunningReservations()
retrieve all reservations that were already dispatched and are still active
Definition: MSDispatch.cpp:179
static double computeDetourTime(SUMOTime t, SUMOTime viaTime, const MSDevice_Taxi *taxi, const MSEdge *from, double fromPos, const MSEdge *via, double viaPos, const MSEdge *to, double toPos, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router, double &timeDirect)
compute directTime and detourTime
Definition: MSDispatch.cpp:223
virtual Reservation * addReservation(MSTransportable *person, SUMOTime reservationTime, SUMOTime pickupTime, const MSEdge *from, double fromPos, const MSEdge *to, double toPos, std::string group, const std::string &line, int maxCapacity, int maxContainerCapacity)
add a new reservation
Definition: MSDispatch.cpp:61
int myReservationCount
Definition: MSDispatch.h:184
virtual void fulfilledReservation(const Reservation *res)
erase reservation from storage
Definition: MSDispatch.cpp:207
MSDispatch(const Parameterised::Map &params)
Constructor;.
Definition: MSDispatch.cpp:48
void servedReservation(const Reservation *res)
Definition: MSDispatch.cpp:185
std::set< const Reservation * > myRunningReservations
Definition: MSDispatch.h:179
A road/street connecting two junctions.
Definition: MSEdge.h:77
bool isPerson() const
Whether it is a person.
SUMOVehicle & getHolder() const
Returns the vehicle that holds this device.
int getPersonCapacity() const
Get this vehicle type's person capacity.
int getContainerCapacity() const
Get this vehicle type's container capacity.
const std::string & getID() const
Returns the id.
Definition: Named.h:74
static OptionsCont & getOptions()
Retrieves the options.
Definition: OptionsCont.cpp:59
static bool createDeviceByOption(const std::string &optionName, const std::string &rootElement="", const std::string &schemaFile="")
Creates the device using the output definition stored in the named option.
static OutputDevice & getDeviceByOption(const std::string &name)
Returns the device described by the option.
An upper class for objects with additional parameters.
Definition: Parameterised.h:41
std::map< std::string, std::string > Map
parameters map
Definition: Parameterised.h:45
double recomputeCosts(const std::vector< const E * > &edges, const V *const v, SUMOTime msTime, double *lengthp=nullptr) const
virtual bool compute(const E *from, const E *to, const V *const vehicle, SUMOTime msTime, std::vector< const E * > &into, bool silent=false)=0
Builds the route between the given edges using the minimum effort at the given time The definition of...
virtual const MSVehicleType & getVehicleType() const =0
Returns the object's "vehicle" type.
virtual const MSEdge * getEdge() const =0
Returns the edge the object is currently at.
virtual double getPositionOnLane() const =0
Get the object's position along the lane.
std::string id
Definition: MSDispatch.h:69
const MSEdge * to
Definition: MSDispatch.h:75
std::string getID() const
debug identification
Definition: MSDispatch.cpp:40
double fromPos
Definition: MSDispatch.h:74
const MSEdge * from
Definition: MSDispatch.h:73
std::string group
Definition: MSDispatch.h:77
ReservationState state
Definition: MSDispatch.h:80
std::set< MSTransportable * > persons
Definition: MSDispatch.h:70
double toPos
Definition: MSDispatch.h:76