Inter-route optimization procedures for the dial-a-ride problem in Paratransit.

The Dial-A-Ride Problem with Time Windows (DAEIPTW) is concerned about the satisfaction of a set of customer requests serviced by a fleet of vehicles starting at and returning to a central depot. Each request has a pickup and a dropoff stop. Time windows, precedence and vehicle capacity constraints must be satisfied. The DARPTW in paratransit is a special case of the DARPTW where the load of transportation is seniors and/or handicapped people and related paratransit constraints must be also satisfied. Since the DARPTW is NP-hard, heuristic solutions are mainly considered for the problem. In the thesis, the heuristic solutions for the DARPTW in paratransit include route construction and post-optimization. Insertion heuristics is used to construct initial routes. The post-optimization includes intra-route and inter-route optimization. The intra-route optimization is performed with an Or-interchange algorithm. For the inter-route optimization, four selection horizon heuristic algorithms are proposed and developed. A comparison of the Or-opt intra-route heuristic algorithm with the four inter-route heuristic algorithms and a comparison among the four interroute optimization methods are presented from 8 test problems. The results show that the inter-route post-optimization is a useful tool for improvement of the quality of the initial routes.