Two Phase Algorithm for Dynamic Dial-A-Ride Problem

Public transportation planning is one of the basic factors in economic and social development modern societies. Dial-a-ride problem is a topic in the area of public transportation planning which helps to plan a more convenience passenger transportation and also to improve traffic systems. In the dynamic DARP, requests are received throughout the planning horizon and the primary objective is to accept as many requests as possible while satisfying operational constraints. In this research, we developed a two-step algorithm based on dynamic dial-a-ride problem. In the first step a new request is accepted, while in the second step the optimum route is found by creating a feasible neighborhood of the current route. The results showed that the proposed algorithm obtains a near optimum solution in a short period of time (in few minutes) with the rate of acceptance above 85 percent of new requests.