Construction of a high fidelity travel duration matrix for a real-time scheduling problem

Spring 2010

Atikhun Unahalekhaka
Stephen Smith
Project description

ACCESS is the para-transit organization that services Allegheny County. Customers call in a day ahead with requests of pickup location, drop-off location, and time. ACCESS is then responsible for getting vehicles to various pickup locations the next day within a window of specified pickup times. We are interested in solving the real-time scheduling problem as unexpected events occur (e.g., driver does a pickup out of order, customer cancels a travel request). The goal is a system that will dynamically reschedule as appropriate to re-task and consolidate vehicle trips while maintaining customer service level constraints.

The first step to achieving this goal is to develop a mechanism for generating a high-fidelity, point-to-point travel duration matrix from the historical data provided by onboard ACCESS vehicle sensors. This initial problem will serve as the focus of the independent study project. There are several challenges to producing a travel duration matrix from this data:

(1) travel durations vary according to time of day and this needs to be accounted for, (2) there are likely too many pickup and drop off locations (latitude/longitude points) to consider each individually, so data must somehow be aggregated, and (3) we would like a procedure for building the duration matrix that is more sensitive to recent samples, so that we have hope of accounting for dynamics phenomena like bridge closings for construction.

The work will require applying and evaluating various clustering techniques on ACCESS supplied travel data, exploiting such techniques as kernel density estimation if data proves to be sparse, developing a procedure that utilizes the techniques identified by this analysis to generate the duration matrix, and verifying the accuracy and efficiency of the matrix in answering shortest path queries. The duration matrix will eventually be configured for use within the dynamic scheduling algorithm.

Return to project list