Eclipse SUMO - Simulation of Urban MObility
MSDispatch_RouteExtension.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-2020 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_COND2(obj) (obj->getID() == "p0")
31 #define DEBUG_COND2(obj) (true)
32 
33 
34 // ===========================================================================
35 // method definitions
36 // ===========================================================================
37 void
38 MSDispatch_RouteExtension::findInsertionPoint(std::vector<const Reservation*>::iterator& resIt, EdgePosVector::iterator& edgeIt,
39  const EdgePosVector::iterator& edgeEnd, ConstMSEdgeVector& route,
40  const MSEdge* newEdge, const double newPos) const {
41  for (const MSEdge* edge : route) {
42  while (edgeIt != edgeEnd && edge == edgeIt->first) {
43  if (edge == newEdge && edgeIt->second > newPos) {
44  break;
45  }
46  resIt++;
47  edgeIt++;
48  }
49  if (edge == newEdge) {
50  break;
51  }
52  }
53 }
54 
55 
56 int
57 MSDispatch_RouteExtension::dispatch(MSDevice_Taxi* taxi, std::vector<Reservation*>::iterator& resIt, SUMOAbstractRouter<MSEdge, SUMOVehicle>& router, std::vector<Reservation*>& reservations) {
58  const Reservation* const res = *resIt;
59 #ifdef DEBUG_DISPATCH
60  if (DEBUG_COND2(person)) {
61  std::cout << SIMTIME << " dispatch taxi=" << taxi->getHolder().getID() << " person=" << toString(res->persons) << "\n";
62  }
63 #endif
65  int capacityLeft = taxi->getHolder().getVehicleType().getPersonCapacity() - (int)res->persons.size();
66  std::vector<const Reservation*> sequence{ res, res };
67  std::vector<const Reservation*> toRemove{ res };
68  EdgePosVector posSequence({ std::make_pair(res->from, res->fromPos), std::make_pair(res->to, res->toPos) });
69  const Reservation* first = sequence.front();
70  const Reservation* last = sequence.back();
71  ConstMSEdgeVector route;
72  router.compute(first->from, first->fromPos, last->to, last->toPos, &taxi->getHolder(), MAX2(now, first->pickupTime), route);
73  // check whether the ride can be shared
74  for (auto it2 = resIt + 1; it2 != reservations.end();) {
75  Reservation* const res2 = *it2;
76  if (capacityLeft < (int)res2->persons.size()) {
77  it2++;
78  continue;
79  }
80  // check whether res2 picks up or gets picked up on the way
81  ConstMSEdgeVector route2;
82  // TODO It may be more efficient to check first whether from and to are already in the route
83  router.compute(res2->from, res2->fromPos, res2->to, res2->toPos, &taxi->getHolder(), MAX2(now, res2->pickupTime), route2);
84  const bool pickup = std::find(route.begin(), route.end(), res2->from) != route.end();
85  const bool dropoff = std::find(route.begin(), route.end(), res2->to) != route.end();
86 #ifdef DEBUG_DISPATCH
87  if (DEBUG_COND2(person)) std::cout << " consider sharing ride with " << toString(res2->persons)
88  << " pickup=" << pickup << " startFirst=" << (std::find(route2.begin(), route2.end(), first->from) != route2.end())
89  << " dropoff=" << dropoff << " endLast=" << (std::find(route2.begin(), route2.end(), last->to) != route2.end())
90  << "\n";
91 #endif
92  if ((pickup || std::find(route2.begin(), route2.end(), first->from) != route2.end()) &&
93  (dropoff || std::find(route2.begin(), route2.end(), last->to) != route2.end())) {
94  std::vector<const Reservation*>::iterator resSeqIt = sequence.begin();
95  EdgePosVector::iterator edgeIt = posSequence.begin();
96  if (pickup) {
97  // new reservation gets picked up
98  findInsertionPoint(resSeqIt, edgeIt, posSequence.end(), route, res2->from, res2->fromPos);
99  }
100  resSeqIt = sequence.insert(resSeqIt, res2) + 1;
101  edgeIt = posSequence.insert(edgeIt, std::make_pair(res2->from, res2->fromPos)) + 1;
102  if (dropoff) {
103  // new reservation drops off and route continues
104  findInsertionPoint(resSeqIt, edgeIt, posSequence.end(), route, res2->to, res2->toPos);
105  sequence.insert(resSeqIt, res2);
106  posSequence.insert(edgeIt, std::make_pair(res2->from, res2->fromPos));
107  } else {
108  // new reservation ends last
109  sequence.push_back(res2);
110  posSequence.push_back(std::make_pair(res2->to, res2->toPos));
111  }
112  toRemove.push_back(res2);
113  it2 = reservations.erase(it2); // (resIt before it2) stays valid
114  // TODO we have more capacity if some pickup is after an earlier dropoff
115  capacityLeft -= (int)res2->persons.size();
116  if (capacityLeft == 0) {
117  break;
118  }
119  route.clear();
120  first = sequence.front();
121  last = sequence.back();
122  // TODO this is wrong for non linear networks! should be reusing the route snippets from above
123  router.compute(first->from, first->fromPos, last->to, last->toPos, &taxi->getHolder(), MAX2(now, first->pickupTime), route);
124  } else {
125  it2++;
126  }
127  }
128  if (sequence.size() > 2) {
129  taxi->dispatchShared(sequence);
130  if (myOutput != nullptr) {
131  myOutput->writeXMLHeader("DispatchInfo_RouteExtension", "");
132  myOutput->openTag("dispatchShared");
133  myOutput->writeAttr("time", time2string(now));
134  myOutput->writeAttr("id", taxi->getHolder().getID());
135  myOutput->writeAttr("persons", toString(res->persons));
136  myOutput->writeAttr("sharingPersons", toString(sequence));
137  myOutput->writeAttr("type", "routeExtension");
138  myOutput->closeTag();
139  }
140 #ifdef DEBUG_DISPATCH
141  if (DEBUG_COND2(person)) std::cout << " sharing ride with " << toString(sequence)
142  << "\n";
143 #endif
144  } else {
145  taxi->dispatch(*res);
146  }
147  for (const Reservation* r : toRemove) {
148  servedReservation(r); // deleting r
149  }
150  resIt = reservations.erase(resIt);
151  return (int)toRemove.size();
152 }
153 
154 
155 /****************************************************************************/
#define DEBUG_COND2(obj)
std::vector< const MSEdge * > ConstMSEdgeVector
Definition: MSEdge.h:74
std::string time2string(SUMOTime t)
convert SUMOTime to string
Definition: SUMOTime.cpp:68
#define SIMTIME
Definition: SUMOTime.h:60
long long int SUMOTime
Definition: SUMOTime.h:31
T MAX2(T a, T b)
Definition: StdDefs.h:79
std::string toString(const T &t, std::streamsize accuracy=gPrecision)
Definition: ToString.h:44
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
void dispatchShared(const std::vector< const Reservation * > &reservations)
service the given reservations
void findInsertionPoint(std::vector< const Reservation * >::iterator &resIt, EdgePosVector::iterator &edgeIt, const EdgePosVector::iterator &edgeEnd, ConstMSEdgeVector &route, const MSEdge *newEdge, const double newPos) const
virtual int dispatch(MSDevice_Taxi *taxi, std::vector< Reservation * >::iterator &resIt, SUMOAbstractRouter< MSEdge, SUMOVehicle > &router, std::vector< Reservation * > &reservations)
trigger taxi dispatch.
std::vector< std::pair< const MSEdge *, double > > EdgePosVector
OutputDevice * myOutput
optional file output for dispatch information
Definition: MSDispatch.h:145
void servedReservation(const Reservation *res)
Definition: MSDispatch.cpp:121
A road/street connecting two junctions.
Definition: MSEdge.h:77
static MSNet * getInstance()
Returns the pointer to the unique instance of MSNet (singleton).
Definition: MSNet.cpp:171
SUMOTime getCurrentTimeStep() const
Returns the current simulation step.
Definition: MSNet.h:313
SUMOVehicle & getHolder() const
Returns the vehicle that holds this device.
int getPersonCapacity() const
Get this vehicle type's person capacity.
const std::string & getID() const
Returns the id.
Definition: Named.h:73
bool writeXMLHeader(const std::string &rootElement, const std::string &schemaFile, std::map< SumoXMLAttr, std::string > attrs=std::map< SumoXMLAttr, std::string >())
Writes an XML header with optional configuration.
OutputDevice & openTag(const std::string &xmlElement)
Opens an XML tag.
OutputDevice & writeAttr(const SumoXMLAttr attr, const T &val)
writes a named attribute
Definition: OutputDevice.h:239
bool closeTag(const std::string &comment="")
Closes the most recently opened tag and optionally adds a comment.
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.
SUMOTime pickupTime
Definition: MSDispatch.h:58
const MSEdge * to
Definition: MSDispatch.h:61
double fromPos
Definition: MSDispatch.h:60
const MSEdge * from
Definition: MSDispatch.h:59
std::set< MSTransportable * > persons
Definition: MSDispatch.h:56
double toPos
Definition: MSDispatch.h:62