Fast heuristics for a dynamic paratransit problem

In a previous paper we developed a non-standard two-stage recourse model for the dynamic day-ahead paratransit planning problem. Two heuristics, which are frequently applied in the recourse model, contain many details which leads to large CPU times to solve instances of relatively small size. In this paper we simplify both heuristics to decrease CPU time considerably while maintaining the quality of the obtained solutions as much as possible. Numerical experiments on (semi-)realistic instances, inspired by practice, show that our recourse model with fast heuristics provides acceptable solutions within reasonable time.