A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> The static dial-a-ride problem <s> A number of papers have been proposed for the approximate solution of the dial-a-ride routing problem. The object of this paper is to examine some of these heuristics, to introdllce some new heuristics, and to compare these approximate algorithms. <s> BIB001 </s> A survey on pickup and delivery problems: Part i: Transportation between customers and depot <s> The static dial-a-ride problem <s> Real-time decision problems are playing an increasingly important role in the economy due to advances in communication and information technologies that now allow realtime information to be quickly obtained and processed (Seguin et al., 1997). Among these, dynamic vehicle routing and dispatching problems have emerged as an intense area of research in the operations research community. Numerous examples may be found in Haines and Wolfe (1982), Powell, Jaillet and Odoni (1995) and Psaraftis (1995). In these problems, a set of vehicles is routed over a particular time horizon (typically, a day) while new service requests are occuring in real-time. With each new request, the current solution may be reconfigured to better service the new request, as well as those already assigned to a route. <s> BIB002
The dial-a-ride problem class has received considerable attention in the literature. The first publications in this area date back to the late 1960s and early 1970s (cf.     . Surveys on solution methods can be found in (Cordeau and Laporte, 2003a BIB002 . BIB001 compare different local search based heuristic methods for the SDARP.