The Northfield Community (Car)Pool
Advisor: David Liben-Nowell
I. Background
Around ten years ago,
a feasibility
study for a commuter-rail line estimated that thousands of
automobiles trips between Northfield and the Twin Cities occur daily.
Due to the vagaries of local and state politics, the plans for the
commuter-rail line have been put on hold—but those automobile
trips are still happening. (Hilariously, the state legislature has
even passed a ban on the discussion of this rail line.) But,
okay, fine. Let's assume that rail is off the table for the
foreseeable future, and see what we can do right now with to
improve the efficiency of car travel between Northfield and the
Cities.
Every day, people at Carleton or elsewhere in Northfield hop in their
cars for a solo drive to the Cities. Pairs of individuals starting
from nearly identical locations at nearly identical times drive to
nearby locations, and then drive back at similar times. Others
without cars beg friends to borrow something driveable or abandon
trips that they wish to make. The goal of this project is to build a
system to connect these people together, so that they can carpool.
II. The Project
Your team will build an iPhone app (and perhaps other platforms?) that
allows drivers and riders to be matched up. While the precise details
of your system are up to you, there are two fundamental operations
that users of the system must be able to complete:
- Request a ride. A request will consist of a departure
time/location, an arrival location, and some measure of flexibility in
location and timing. For example, I might say that I want to arrive
at Target Field at 7:05p, but I'm willing to be as much as an hour
early. Or I want to be at the University of Minnesota computer
science department at 11:00a, but I'm willing to be dropped off
anywhere on
the #2
bus line (as long as I'm early enough to get to the U by bus
before 11:00a).
- Offer a ride. An offer will also consist of a departure
time/location, an arrival location, some measure of flexibility in
location and timing, and some type of demanded price. (Perhaps the
request will instead, or also, include some kind of payment offer.)
For example, I might say that I'm leaving Northfield at 10:00a to go
Lake Calhoun, and I'm willing to go up to 15 minutes out of my way to
drop a rider (or riders) off, and I ask for $10 plus $0.50 for every
extra minute of driving that the rider causes me.
The tasks that you will have to complete include:
- designing the architecture of the system. (Presumably there will
be a server with a database that does the matching-type computation?)
- designing the mobile application by which users interact with the
server. The user experience/interface will be crucial to your
project's success.
- designing the matching algorithm. There are many choices here (do
drivers list their availability, and riders agree to drivers' terms?
vice versa? do drivers get the offer from the "best available" rider,
and then take it or leave it? does the system collect both kinds of
requests and compute an optimal matching?)
- testing the system with actual users, and improving the design in
response to their responses.
III. References
A sampling of existing ride-sharing systems:
On the algorithmic side: