Eclipse SUMO - Simulation of Urban MObility
MSDispatch_Greedy.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"
28 
29 //#define DEBUG_DISPATCH
30 //#define DEBUG_SERVABLE
31 //#define DEBUG_TRAVELTIME
32 //#define DEBUG_COND2(obj) (obj->getID() == "p0")
33 #define DEBUG_COND2(obj) (true)
34 
35 // ===========================================================================
36 // MSDispatch_Greedy methods
37 // ===========================================================================
38 
39 void
40 MSDispatch_Greedy::computeDispatch(SUMOTime now, const std::vector<MSDevice_Taxi*>& fleet) {
41  int numDispatched = 0;
42  int numPostponed = 0;
43  // find available vehicles
44  std::set<MSDevice_Taxi*, MSVehicleDevice::ComparatorNumericalVehicleIdLess> available;
45  for (auto* taxi : fleet) {
46  if (taxi->isEmpty()) {
47  available.insert(taxi);
48  }
49  }
50  // greedy assign closest vehicle in reservation order
52  std::vector<Reservation*> reservations = getReservations();
53  std::sort(reservations.begin(), reservations.end(), time_sorter());
54 #ifdef DEBUG_DISPATCH
55  std::cout << SIMTIME << " computeDispatch fleet=" << fleet.size() << " available=" << available.size() << " reservations=" << toString(reservations) << "\n";
56 #endif
57  for (auto it = reservations.begin(); it != reservations.end();) {
58  if (available.size() == 0) {
59  break;
60  }
61  Reservation* res = *it;
62  if (res->recheck > now) {
63  it++;
64  numPostponed++;
65  continue;
66  }
67  //Position pos = res.from->getLanes().front()->geometryPositionAtOffset(res.fromPos);
68  MSDevice_Taxi* closest = nullptr;
69  SUMOTime closestTime = SUMOTime_MAX;
70  bool tooEarly = false;
71  for (auto* taxi : available) {
72  if (remainingCapacity(taxi, res) < 0 || !taxi->compatibleLine(res)) {
73  continue;
74  }
75  SUMOTime travelTime = computePickupTime(now, taxi, *res, router);
76 #ifdef DEBUG_TRAVELTIME
77  if (DEBUG_COND2(person)) {
78  std::cout << SIMTIME << " taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons) << " traveltime=" << time2string(travelTime) << "\n";
79  }
80 #endif
81  if (travelTime < closestTime) {
82  closestTime = travelTime;
83  closest = taxi;
84  SUMOTime taxiWait = res->pickupTime - (now + closestTime);
85  if (taxiWait > myMaximumWaitingTime) {
86  // no need to service this customer now
87  tooEarly = true;
88  res->recheck += MAX2(now + myRecheckTime, res->pickupTime - closestTime - myRecheckSafety);
89  break;
90  }
91  }
92  }
93  if (tooEarly || closest == nullptr) {
94  // too early or all taxis are too small
95  it++;
96  numPostponed++;
97  } else {
98  numDispatched += dispatch(closest, it, router, reservations);
99  available.erase(closest);
100  }
101  }
102  // check if any taxis are able to service the remaining requests
103  myHasServableReservations = reservations.size() > 0 && (available.size() < fleet.size() || numPostponed > 0 || numDispatched > 0);
104 #ifdef DEBUG_SERVABLE
105  std::cout << SIMTIME << " reservations=" << reservations.size() << " avail=" << available.size()
106  << " fleet=" << fleet.size() << " postponed=" << numPostponed << " dispatched=" << numDispatched << "\n";
107 #endif
108 }
109 
110 
111 int
112 MSDispatch_Greedy::dispatch(MSDevice_Taxi* taxi, std::vector<Reservation*>::iterator& resIt, SUMOAbstractRouter<MSEdge, SUMOVehicle>& /*router*/, std::vector<Reservation*>& reservations) {
113 #ifdef DEBUG_DISPATCH
114  if (DEBUG_COND2(person)) {
115  std::cout << SIMTIME << " dispatch taxi=" << taxi->getHolder().getID() << " person=" << toString((*resIt)->persons) << "\n";
116  }
117 #endif
118  taxi->dispatch(**resIt);
119  servedReservation(*resIt); // deleting res
120  resIt = reservations.erase(resIt);
121  return 1;
122 }
123 
124 
125 // ===========================================================================
126 // MSDispatch_GreedyClosest methods
127 // ===========================================================================
128 
129 void
130 MSDispatch_GreedyClosest::computeDispatch(SUMOTime now, const std::vector<MSDevice_Taxi*>& fleet) {
131  bool havePostponed = false;
132  int numDispatched = 0;
133  // find available vehicles
134  std::set<MSDevice_Taxi*, MSVehicleDevice::ComparatorNumericalVehicleIdLess> available;
135  for (auto* taxi : fleet) {
136  if (taxi->isEmpty()) {
137  available.insert(taxi);
138  }
139  }
140 #ifdef DEBUG_DISPATCH
141  std::cout << SIMTIME << " computeDispatch fleet=" << fleet.size() << " available=" << available.size() << "\n";
142 #endif
143  // greedy assign closest vehicle
145  std::vector<Reservation*> activeReservations;
146  for (Reservation* res : getReservations()) {
147  if (res->recheck <= now) {
148  activeReservations.push_back(res);
149  }
150  }
151  while (available.size() > 0 && activeReservations.size() > 0) {
152  Reservation* closest = nullptr;
153  MSDevice_Taxi* closestTaxi = nullptr;
154  SUMOTime closestTime = SUMOTime_MAX;
155  for (Reservation* res : activeReservations) {
156  SUMOTime recheck = SUMOTime_MAX;
157  for (auto* taxi : available) {
158  if (remainingCapacity(taxi, res) < 0 || !taxi->compatibleLine(res)) {
159  continue;
160  }
161  SUMOTime travelTime = computePickupTime(now, taxi, *res, router);
162  SUMOTime taxiWait = res->pickupTime - (now + travelTime);
163 #ifdef DEBUG_TRAVELTIME
164  if (DEBUG_COND2(person)) std::cout << SIMTIME << " taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons)
165  << " traveltime=" << time2string(travelTime)
166  << " pickupTime=" << time2string(res->pickupTime)
167  << " taxiWait=" << time2string(taxiWait) << "\n";
168 #endif
169  if (travelTime < closestTime) {
170  if (taxiWait < myMaximumWaitingTime) {
171  closestTime = travelTime;
172  closest = res;
173  closestTaxi = taxi;
174  } else {
175  recheck = MIN2(recheck,
176  MAX2(now + myRecheckTime, res->pickupTime - closestTime - myRecheckSafety));
177  }
178  }
179  }
180  /*
181  if (closestTaxi == nullptr) {
182  // all taxis would arrive to early. postpone recheck
183  res.recheck = recheck;
184  }
185  */
186  }
187  if (closestTaxi != nullptr) {
188  auto closeIt = std::find(activeReservations.begin(), activeReservations.end(), closest);
189  numDispatched += dispatch(closestTaxi, closeIt, router, activeReservations);
190  available.erase(closestTaxi);
191  } else {
192  // all current reservations are too early or too big
193  havePostponed = true;
194  break;
195  }
196  }
197  // check if any taxis are able to service the remaining requests
198  myHasServableReservations = getReservations().size() > 0 && (available.size() < fleet.size() || havePostponed || numDispatched > 0);
199 #ifdef DEBUG_SERVABLE
200  std::cout << SIMTIME << " reservations=" << getReservations().size() << " avail=" << available.size()
201  << " fleet=" << fleet.size() << " postponed=" << havePostponed << " dispatched=" << numDispatched << "\n";
202 #endif
203 }
204 
205 
206 /****************************************************************************/
#define DEBUG_COND2(obj)
std::string time2string(SUMOTime t)
convert SUMOTime to string
Definition: SUMOTime.cpp:68
#define SUMOTime_MAX
Definition: SUMOTime.h:33
#define SIMTIME
Definition: SUMOTime.h:60
long long int SUMOTime
Definition: SUMOTime.h:32
@ SVC_TAXI
vehicle is a taxi
T MIN2(T a, T b)
Definition: StdDefs.h:74
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
void dispatch(const Reservation &res)
service the given reservation
sorts reservations by time
Definition: MSDispatch.h:106
void computeDispatch(SUMOTime now, const std::vector< MSDevice_Taxi * > &fleet)
computes dispatch and updates reservations
const SUMOTime myRecheckTime
recheck interval for early reservations
virtual void computeDispatch(SUMOTime now, const std::vector< MSDevice_Taxi * > &fleet)
computes dispatch and updates reservations
const int myRoutingMode
which router/edge weights to use
virtual int dispatch(MSDevice_Taxi *taxi, std::vector< Reservation * >::iterator &resIt, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router, std::vector< Reservation * > &reservations)
trigger taxi dispatch.
const SUMOTime myRecheckSafety
const SUMOTime myMaximumWaitingTime
maximum time to arrive earlier at customer
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
bool myHasServableReservations
whether the last call to computeDispatch has left servable reservations
Definition: MSDispatch.h:170
std::vector< Reservation * > getReservations()
retrieve all reservations
Definition: MSDispatch.cpp:169
void servedReservation(const Reservation *res)
Definition: MSDispatch.cpp:185
static MSNet * getInstance()
Returns the pointer to the unique instance of MSNet (singleton).
Definition: MSNet.cpp:174
SUMOAbstractRouter< MSEdge, SUMOVehicle > & getRouterTT(const int rngIndex, const MSEdgeVector &prohibited=MSEdgeVector()) const
Definition: MSNet.cpp:1352
static SUMOAbstractRouter< MSEdge, SUMOVehicle > & getRouterTT(const int rngIndex, SUMOVehicleClass svc, const MSEdgeVector &prohibited=MSEdgeVector())
return the router instance
SUMOVehicle & getHolder() const
Returns the vehicle that holds this device.
const std::string & getID() const
Returns the id.
Definition: Named.h:74
SUMOTime pickupTime
Definition: MSDispatch.h:72
SUMOTime recheck
Definition: MSDispatch.h:79
std::set< MSTransportable * > persons
Definition: MSDispatch.h:70