Project Number:
09-19
Research Project:
Using Auctions to Allocate Transportation Requests for Demand Responsive Transit Systems
P.I. Name & Address:
Sven Koenig
University of Southern California
Department of Computer Science
Henry Salvatori Computer Science Center, Room 300
Los Angeles, CA 90089-0781
Email: skoenig@usc.edu
Website: http://idm-lab.org/
Phone: (213) 740-6491
Fax: (213) 740-7285
Project Objective:
There is a need for a transit system that provides flexible service at a cost efficient price. Fixed-route bus transit systems are much more cost efficient than Demand Responsive Transit (DRT) systems, with an average cost per passenger trip of $2.19 and about $17.00 respectively. However, as an alternative to private automobiles, fixed-route bus transit systems have a major deficiency. The general public considers the service to be inconvenient. Also, the total time for a trip is perceived as being greater than that of a private auto and trips covering more than 10 miles require transfers between vehicles. This may explain the small number of people who use some form of public transit system to work. DRT systems provide great flexibility but are largely limited to specialized operations such as dial-a-ride service mandated under the Americans with Disabilities Act (paratransit DRT) since they tend to be much more costly to deploy as a general transit service than fixed-route bus transit systems. Thus, their deployment and operating costs need to be reduced to make them viable as a general transit service. This project advocates the use of modern technologies to create DRT systems that are cost-efficient, distributed and adaptive, by exploiting the fact that buses are starting to be equipped with multi-way communication devices, on-board computers, sensors and data centers.
Task Descriptions
The P.I. proposes to build a DRT system based on SSI (Sequential Single-Item) auctions, which requires the extension of ideas from task-allocation problems in the context of multi-agent routing to the ones in the context of DRT systems. We expect this task to take about nine months. We have already consulted with transportation researchers from the ISE department of USC to gather expertise on the topic.
We propose to then implement the system and test it in simple simulations. We expect this task to take about three months. While we will start to work on it in parallel with the task above, we intend to concentrate on it during the last three months of the project. We will evaluate the auction-based DRT system with respect to the metrics mentioned earlier: real time performance, solution quality and robustness towards failures. The technical and experimental results will be presented in technical reports and publications at conferences.
A first implementation of the DRT system based on auctions together with its experimental evaluation is the main deliverable, together with publications on the topic.
Milestones, Dates:
August 15, 2008 – September 14, 2009
Total Budget:
$90,000
Student Involvement:
One graduate student at 50% effort, 11.5 months
One graduate student at 50% effort, 2.5 months
Relationship to Other Research Projects:
Related to 00-08; part of the mobility focus area
Technology Transfer Activities:
Project report will be posted soon
Potential Benefits of the Project:
The proposed research has the potential to spur the transit industry's migration towards real-time coordination to meet the future demands of modern urban transit networks
TRB Keywords:
Demand Responsive Transit (DRT), paratransit, fixed route, Americans with Disabilities Act (ADA)
