On-line dial-a-ride problems under a restricted information model
In on-line dial-a-ride problems servers are travelling in some metric space to serve requests for rides which are presented over time. Each ride is characterized by two points in the metric space, a source, the starting point of the ride, and a destination, the endpoint of the ride. Usually it is assumed that at the release of a request, complete information about the ride is known. We diverge from this by assuming that at the release of a ride, only information about the source is given. At visiting the source, the information about the destination will be made available to the servers. For many practical problems, our model is closer to reality. However, we feel that the lack of information is often a choice, rather than inherent to the problem: additional information can be obtained, but this requires investments in information systems. In this paper we give mathematical evidence that for the problem under study it pays to invest.
dial-a-ride on-line optimization competitive analysis