Fair Carpooling Algorithm
April 21, 2011
When I first started work with my long-time employer, I would
carpool with a friend who lived quite close and worked at the same place. Our carpooling scheme was that we would each drive on alternate days. We soon discovered some problems with our supposedly simple
scheduling scheme. I would be away at conferences for a week at a time; and my carpool buddy expectedly needed to work late some days, so he needed to drive himself. How do you determine who should drive after such an interruption?
My carpool buddy, who was also a
scientist, thought that if one of us missed a turn at driving, he owed one driving chore. My idea was that our objective was to equalize our driving when we were actually together in a car; that is, I would drive him to work as often as he drove me. Here we have two scientists working with the same
dataset but disagreeing on the interpretation. Now you can see why there's still a
controversy about
global warming.
Soon after, The US had its
second energy crisis, and our employer started an employee van pool program. I became a member of one of about twenty such vans, and the contingent of each van had to decide how to handle the driving chores. Fortunately in our case, there was one person who enjoyed driving, so it was decided he would get a free ride for handling the driving chores. The rest of us would cover our (at first, nominal) fee, and also his. Some of the other vans rotated the driving chore, often among fifteen people.
About that same time, two
mathematicians/
computer scientists from
IBM published a paper on carpool scheduling. This was "A Fair Carpool Scheduling Algorithm" by
Ronald Fagin and John H. Williams that appeared in the IBM Journal of Research and Development (Volume 27, Number 2, March, 1983).[1] The IBM researchers adopted the same idea that I had about carpooling; namely, there should be no penalty to a member who doesn't ride on a given day.
Fagin and Williams examined other carpool scheduling algorithms before settling on their "fair carpool scheduling algorithm."
Simple Rotation - In this case, if a driver misses his turn at driving, he swaps this chore with another person. The problem is keeping track of who owes whom a driving chore.
Simple Tokens - Each time a person rides in a carpool they pay the driver one "ride token." The tokens need not be physical objects. A system can be worked out that a person without any ride tokens in his account must drive. Of course, you can envision quite a few procedural difficulties with this scheme.
Subsets - Only a mathematician would consider this particular approach, which you can read about in Ref. 1.
Fagin and Williams analyzed these three cases, and they find that all are "fair," except for the simple token approach, which was my approach to carpooling. However, it seems as if a two-person token carpool is equivalent to their fair carpool algorithm, so I feel justified. In any case, except for the token approach, these algorithms involved too much
bookkeeping for a large number of participants, so Fagin and Williams proposed their alternative.
The Fagin and Williams algorithm is actually quite straightforward, since it involves a
balance sheet between receipts and expenditures. If the "cost" of driving is considered to be
U, then each rider in a carpool "pays" the driver
U/n, where
n is the number of riders. The problem reduces to one of managing your personal finances, but you would need to ensure that none of your carpool buddies gets too much into debt.
IBM has had a continued interest in
commuting, since this can turn into an important profit center. IBM has a web site devoted to commuter traffic that includes many reports.[2] One of these describes a survey of 8,192 motorists in 20 cities on six continents.[3] With an emergent
middle class in many of these cities, most drivers have reported that traffic had increased horrendously in the three years prior to the survey (June, 2010).
US cities fared better in the survey than others, since their infrastructure was developed slowly over the course of many decades.
Beijing seemed to have the most problems, since 95% of respondents said that roadway traffic had "negatively affected their health," and 84% said that traffic had "negatively affected work or school performance."[3]
On average, sixteen percent of respondents to an IBM survey said they would work more if their commuting time could be significantly reduced. This bubble graph shows the percentage of such responses across many cities. (Via Flickr)
With today's ubiquity of
mobile computing devices, any fair carpooling algorithm can be implemented by a simple application. Our presently increasing cost of motor fuel, and the always persistent
rush hour traffic, should encourage someone to write this "App." If you do, please write it for
Android, and not a proprietary platform.
References:
- Ronald Fagin and John H. Williams, "A Fair Carpool Scheduling Algorithm," IBM Journal of Research and Development, vol. 27, no 2 (March 1983), pp. 133-139.
- "IBM Traffic Congestion - Ideas - United States," IBM Web Site
- John Buscemi, "IBM Global Commuter Pain Study Reveals Traffic Crisis in Key International Cities," IBM Press Release, June 30, 2010.
- Moni Naor, "On Fairness in the Carpool Problem," Weizmann Institute of
Science, May 4, 2004
- XJoao Pedro Boavida, Vikram Kamat, Darshana Nakum, Ryan Nong, Xinyi Zhang and Chai WahWu (mentor), "Algorithms For The Carpool Problem," IMA Preprint Series # 2133-6, Institute For Mathematics And Its Applications, University Of Minnesota, September, 2006.
Permanent Link to this article
Linked Keywords: Carpool; scheduling; scientist; dataset; global warming controversy; global warming; energy crisis; mathematician; computer scientist; IBM; Ronald Fagin; token; bookkeeping; balance sheet; commuting; middle class; Beijing; Flickr; mobile computing device; rush hour; Android.