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.
The problem addressed by this thesis is whether globally consistent mapping can be practically achieved for the underground mining industry with little to no infrastructure and no a priori knowledge of the environment. This thesis has specific application to an underground global positioning system (UGPS) research project that is currently underway at MDA Space Missions of Brampton, ON. Using developed methods and algorithms from the mobile robotics literature, a tailored mapping algorithm was constructed for the effective and accurate mapping of large scale passageway environments. Following the use of a simulated environment for both feasibility tests and algorithm validation, the developed algorithms were applied to three real data sets, each having unique characteristics. Two of the data sets were obtained from underground mines courtesy of Atlas Copco Rock Drills AB of Orebro, Sweden. A quantitative and qualitative analysis of the produced pose estimates and maps provided clear indications about where the developed algorithms perform well, and also identified possible areas of future research. Finally, the successful integration of the generated maps into MDA's localization research was achieved.
