## Friday, September 20, 2013

### Finding an Optimal Meeting Location

I encountered a neat version of this problem last week at work, while folks were trying to schedule a meeting with a client.

Decisions, Decisions. Location, Location, Location. Where do we meet?

Problem Statement
There are Wij project team members located at office O(i), i = 1, ..., M, that have skill sets j = 1, .., N. Each office location is staffed by a workers having different skill-sets and job responsibilities, such as research, software development, pre-sales, analytical services, etc. It is preferable that everybody attends, but to achieve a quorum and a productive meeting, at least Q(i) persons from O(i), and at least S(j) persons of skill-set j must be present. Assume that the unit travel expense T is roughly the cost of a round-trip air-ticket between O(i) to the airport nearest the meeting location, and that we incur a fixed, location-specific setup cost C. There are additional requirements that limit the number of feasible location choices: safety, conference-friendliness, etc.

Objective: optimally locate the meeting to minimize total cost.

Let A* be the airport associated with the optimal location.
Let x(ij) be the number of people of skill set j attending from O(i)

The problem formulation looks like this:
Minimize Sum(i, j) x(ij) T(O(i), A*) + C(A*)
sum(j) x(ij)  Q(i), i = 1, ..., M
sum(i) x(ij)  S(j), j = 1, ..., N
x(ij)  Wij, x integer.
A*  {commercial airports associated with feasible locations}

This resembles a capacitated location-allocation problem. If the x-variables are fixed, the formulation reduces to a pure A* location search. Similarly, if A* is fixed, the problem turns into a capacitated supply-demand problem.  If every location had exactly one skill set, then we can allocate no more than min(W, max(Q, S)) from each office, leaving us with a pure location problem. Let's assume this is indeed the case, and proceed.

If there are K feasible airports, we can compute the M travel costs, plus the setup-cost C per candidate to determine the total cost associated with a choice. After O(MK) computations in an exhaustive search, we can determine A*. But what if K is very large? We could look at this as a Weber problem and find the centroid, or, suppose we restrict our candidates to coincide with one of the office locations. This is not a terrible idea, since we can avoid paying for an external conference hall (C~0). This requires only O(M2) computations, and all team members at the optimal office location can attend.  Will the best choice from this restricted set of "extreme points" yield an optimal cost solution? In general, it is not guaranteed. If air fares to/from a particular airport (e.g. Las Vegas) is relatively low, then it may be optimal for the selected team members from every location to fly there, even if it is lies outside the convex hull of the office (airport) locations. However, if the traveling cost is a 'nice' function of distance traveled, then results from the literature can be employed to provide decision support:

Literature: Finding An Optimal Meeting Point on Road Networks
Stackoverflow discussion: "Shortest distance travel - common meeting point"

A wonderful reference book is the classic ol' textbook by R. L. Francis, et al., on Facility Layout and Location Analysis.