Intractability of the dial-a-ride problem and a multiobjective solution using simulated annealing

Numerous techniques for generating approximate solutions have been proposed in the last decade for routing and scheduling in multi-vehicle dial-a-ride problems. While some of these techniques have mathematical foundations, it is often difficult to assess the global optimality of the generated solution due to the use of pure local improvement methods. In addition, most of these methods are based on a single objective, such as minimization of the number of vehicles used, and cannot account for different or competing objectives that characterize the problem. This paper proves the intractability of the dial-a-ride problem, and then describes a new approximate method based on simulated annealing that is used to solve these problems in the presence of multiple objectives.