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

Creator: 

Chen, Hongling

Date: 

1998

Abstract: 

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.

Subject: 

Heuristic Programming.
Algorithms.
Mathematical Optimization.
Paratransit Services -- Automation.

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Master of Computer Science: 
M.C.S.

Thesis Degree Level: 

Master's

Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).