Travel Optimization

I’m trying to reduce a real world problem to something that might be solvable by folks who know more about strange maths than I do.

Workers A, B, C, D, E, and F are based out of a central office. They need to schedule meetings in a time period with customers around the country, to which they will most likely fly. They want to optimize their travel.

This sounds like a Traveling Salesman Problem (TSP), but it gets weird:

Because they are a flying, not all paths between nodes are available.
Paths are also restricted temporally, as flights availability is limited, more or less so depending on the airport.
To make matters worse, due to differing expertise among the workers, different combinations of workers are required at different meetings. E.g., the meeting in LA may require workers A and B, but the meeting in Chicago requires workers A, C, and F.
Finally, the customers have limited availability.

Is there an established way of solving this sort of problem? Does this problem have a name? Are there commercial products that help with this? Searching for “travel optimization software” brings up many hits, IBM being a prominent one, but they don’t quite seem to address this scenario.

Note that I said the workers want to “optimize” their travel. That’s a bit intangible. They first need to fit all the meetings into their schedule. Then they want to minimize travel time. But then they probably want to avoid any variety of travel headaches, e.g. wrong-coast meetings on Monday and Friday, travel to Fairbanks in January vs March (as if that’s much better), flights at uncomfortable times, etc.

I’d say that it actually is a travelling salesman problem, with additional constraints being added. I’m not an expert on this, but it seems fair to me to assume that there is graph theory software (some of which open source) around that lets you draw the graph and add the constraints and that can run a number of problem-solving algorithms on it to find a solution.

It looks like this would actually be much faster to solve than a traditional TSP, since so many possible routes drop out due to the constraints. It thus may be possible to just brute-force it.

Your requirements are specific enough that there probably isn’t an off-the-shelf solution. If you wanted a computer program to do this, you’d probably have to hire a consultant to make it for you. It’s probably cheaper to just hire a full-time office worker to do this, instead of a program.

Oh we have folks in-house, but they are busy and get a lot of “I NEED A PROGRAM THAT DOES A THING,” so I like to poke around a bit before talking to them.

I’m not 100% convinced it’s worth pursuing, but we’ll see.

I worked for a while at a large company with offices in various parts of the UK. My bosses secretary (hint - always suck up to your bosses secretary) used to do all the travel arrangements.

She told me this story. They arranged a big meeting for managers in Paris. Not because it’s a nice place to go in the spring, but because it is convenient and has good air connections. There were people flying from the North, and from London and as a matter of course she made sure that they were booked on different flights.

We had some unseasonal snow, so all flights were delayed and re-routed. When the guys in London boarded their flight, they found all the others were sitting on the plane, which had been diverted.