home/Publications/HPS10

Abstract: In a dynamic dial-a-ride (DARP) problem the task is to provide a transportation service in a given area by dynamically routing a set of vehicles in response to passengers' trip requests. Passengers share vehicles similarly as with buses, while the schedule and routes are chosen ad hoc. We assume that each trip is defined by the origin-destination pair in plane augmented with a latest feasible delivery time, (r1,r2,tc). Optimal control of such a system is a complicated task in general and outside the scope of this paper. Instead, we consider a set of well-defined heuristic control policies that can be evaluated by means of simulations. The main contribution of this paper is two-fold: firstly, we demonstrate that a phenomenon known as congestive collapse, i.e., a dramatic performance drop, occurs in this system when the rate of trip requests increases beyond a capacity threshold of the given control policy (the value of which itself is unknown a priori); and secondly, we also describe a robust and computationally lightweight countermeasure to avoid the congestive collapse in such a way that the system's performance still improves after the capacity threshold has been passed. Despite its appealing simplicity, the method manages to reject customers detrimental for the common good.

Links:

BibTeX entry:

@inproceedings{hyytia-asmta-2010,
  author = {Esa Hyyti{\"a} and Aleksi Penttinen and Reijo Sulonen},
  title = {Congestive Collapse and Its Avoidance in a Dynamic Dial-a-Ride System with Time Windows},
  booktitle = {Analytical and Stochastic Modeling Techniques and Applications},
  publisher = {Springer Berlin, LNCS 6148},
  address = {Cardiff, Wales, United Kingdom},
  pages = {397-408},
  year = {2010},
  month = {Jun.},
  doiopt = {10.1007/978-3-642-13568-2_28},
}