A heuristic repair method for dial-a-ride problem in intracity logistic based on neighborhood shrinking

The Dial-a-ride problem (DARP) is a challenging combinatorial optimization problem with lots of applications in the real world. It has so many applications in the smart city like bus intelligent scheduling and taxi intelligent scheduling. However, most of these works rarely address how to handle the infeasible initial solution. The infeasible solution is an unstable factor in the search framework which gives a negative influence on the quality of the final local optimal solution. In this paper, we present a heuristic repair method (HRM) for DARP. Based on a greedy strategy and proper evaluation function, the HRM will reduce the infeasibility of the most infeasible route by deleting several waypoints in the route and reinsert them into one feasible route. The result of experiments shows that HRM can raise about 50% of the fixing ability of a local search operator.