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 
39 std::string
41  return toString(persons);
42 }
43 
44 // ===========================================================================
45 // MSDispatch methods
46 // ===========================================================================
47 
48 MSDispatch::MSDispatch(const std::map<std::string, std::string>& params) :
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("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 
124 std::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 
168 std::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 
178 std::vector<const Reservation*>
180  return std::vector<const Reservation*>(myRunningReservations.begin(), myRunningReservations.end());
181 }
182 
183 
184 void
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 
206 void
208  myRunningReservations.erase(res);
209  delete res;
210 }
211 
212 
213 SUMOTime
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 
222 double
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 
258 int
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 /****************************************************************************/
#define DEBUG_COND2(obj)
Definition: MSDispatch.cpp:32
std::vector< const MSEdge * > ConstMSEdgeVector
Definition: MSEdge.h:74
#define WRITE_WARNINGF(...)
Definition: MsgHandler.h:281
std::string time2string(SUMOTime t)
convert SUMOTime to string
Definition: SUMOTime.cpp:68
#define STEPS2TIME(x)
Definition: SUMOTime.h:53
#define SIMTIME
Definition: SUMOTime.h:60
#define TIME2STEPS(x)
Definition: SUMOTime.h:55
long long int SUMOTime
Definition: SUMOTime.h:32
T MAX2(T a, T b)
Definition: StdDefs.h:80
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:48
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
MSDispatch(const std::map< std::string, std::string > &params)
Constructor;.
Definition: MSDispatch.cpp:48
virtual void fulfilledReservation(const Reservation *res)
erase reservation from storage
Definition: MSDispatch.cpp:207
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:58
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
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