Generalizations of the TSP

Here's my first post in a row of posts detailing what I'm doing in my thesis - and for what it's good. Typically, math students don't necessarily know whether the contents of their thesis can be applied to anything in the real world at all (I'm exaggerating - but for most of them, it's more difficult to find the connection). In my case, however, it's pretty straight forward:

Imagine you're working for UPS and you pick up your truck at 7am in the morning to start your delivery tour. Now, if you're a clever driver, you might want to take a moment and consider how to best approach today's deliveries: what's the shortest (or cheapest or fastest or ...) route to take through town delivering all the packages and, after the last delivery, returning to your depot. That's the Traveling Salesman Problem (TSP) - a very classic example of a problem that's hard to solve to optimality.

Now UPS offers clients to dispatch packages with high or normal priority. High priority packages will be treated with a higher urgency and will typically be delivered before a normal priority package is delivered. In addition to that, a realistic constraint for the delivery of packages is to impose a latest time for delivery, say you have to finish the delivery of all packages by 5pm (receptionists leave rather early, I hear). Trying to come up with a tour for the driver that takes both extensions into consideration (prioritization of deliveries and maximum time allowed for delivery on a single day) is a generalization of the TSP - the Orienteering Problem (OP).

There are a lot more variations of the original TSP. The OP, however, should give you an idea of what such a variation / generalization can look like. In my thesis I'm having a look at these kind of generalizations and trying to come up with algorithms that will solve them to optimality (ie. we find the best tour possible, guaranteed!) but take a lot of computation time or algorithms which only come close to the best tour (which we cannot guarantee, however :-( ) but are fairly quick.

That's enough for a first post - I don't want to scare anybody away before the real fun starts. In the next post I'll try to give a low-math overview of how one can tackle these problems. Let's see whether that's possible!

PS: For the nit-pickers out there: the OP is not really a generalization in the sense that you can solve the TSP by means of an OP. I still like to call it a generalization so bear with me.