OR and the holidays (2)

This blog post contributes to the INFORMS monthly blogging theme. Look for the INFORMS blog to summarize the blogs at the end of the month.

A Christmas tradition in the U.K. is the office Christmas party, when everyone in the company gets together for some kind of celebration. This year, the economic situation has meant that some companies have cut back on the expense of these events. However, my wife Tina's company held one on Friday evening, and the director invited spouses and partners to attend. More importantly, as an O.R. problem, he arranges taxis for everyone to and from the event. To save money, each one is shared by several people, collected on the way from the most distant employee.

So here is the O.R. problem. How many taxis should be ordered, and which routes should they take? It should be recognisable as a "Vehicle routing problem" for which there are numerous soilution approaches. The constraints and interesting features include:
1) some calls have one pick-up, others two; a route which is feasible for one size of taxi may not be feasible for a smaller one;
2) the supply of large taxis in Exeter is limited;
3) there is heavy demand from other users on a Friday evening, so a supplier may not have enough vehicles; should you order taxis from several taxi companies;

It was a good party, though I ate too much. And the Christmas ale ("Raisins to be Cheerful" from St Austell Brewery) was very good.