The modeling and solution of a class of dial-a-ride problems using simulated annealing

A new mixed integer linear programming mathematical model of the dial-a-ride problem (DAP) which facilitates incorporation of multiple criteria and accommodates various forms of the basic DAP model is presented. This new mathematical model encapsulates in a single formulation various instances of the DAP previously available only in separate models. A simulated annealing based solution heuristic is developed for the model. Extensive analysis of the effects of the annealing parameters on the efficiency and accuracy of results is performed. The robustness of the algorithm is explored through solution of various instances of the problem. The intent is to explore the applicability of simulated annealing as a solution methodology for the DAP, and to examine the design issues associated with implementation of same. The results obtained in this paper are encouraging for small to medium sized instances of the DAP with efficiencies (with respect to objective value) exceeding 95%.