Algorithm for dial-a-ride vehicles routing problem

Problem Description and solution:

1. Passengers (disables and old people) call the service centre a day before for the ride request. The important input for each request include
1. Pick up time
2. Pick up address
3. Drop off time
4. Drop off address
   

2. There may be 100s of request per day. We form a schedule for each vehicles so that
1. The overall distances traveled is minimized
2. The dwell time (the time for which passenger is in vehicles) for each passenger is minimized so that quality of service is increased.
3. Let nth request is denoted by q_n with pick up and drop off time by P_n and D_n respectively.
4. Let N be total number of requests per day. Then since this is combinatorial problem, if we consider R request at a time for forming a route, the total possible routes are N!/(R!(N-R)!). However, all these combinations are not valid routes
5. Now the problem is to eliminating invalid routes. All the combination that are not sorted with respect to pick up time are invalids. Eliminate them.
6. For each valid route, elaborate route in terms of P_n and D_n where the result is time sorted with increasing order.
7. Now Check whether the route satisfy the following constraints.
1. Route shouldn’t overflow vehicle’s maximum capacity. Starting from the initial position, each time P_n is encountered, decrease C by 1 and when D_n is encountered, increase C by 1. At each P_n and D_n, also check whether C<0,>
2. Route should satisfy every Pick up and drop up timing constraint. Let the starting location of the vehicle be at Main Depot Z. Then for each P or D, selected from the starting of the route, following condition must be true.

t(Z,P/D)<=(t_p/d- t_z) i.e. time taken to reach at P/D should be less than or equal to Pick up or drop off time of that pick up or drop off location. We continue comparing similarly until the end of the route or up to which the timing constraint is satisfied. We save optimal solution until more appropriate solution is discovered.

8. After finding the optimal route solution for one vehicle, we remove the requests that are going to be served by this vehicle and with remaining requests, we start the same process for next vehicle.

P.S. Here the total number of requests considered can be either whole requests for the day or a partition of the whole request such that solving partition by partition can reduce the complexity combinatorial problem.