Overview of a Mail Transportation Vehicle Routing Problem (VRP)

Way back in my first blog post, I talked about how there are several areas where operations research would likely be useful within the State of Wisconsin, and one of the areas I highlighted was the State’s interdepartmental mail transportation system. Over the last few months, I’ve been working to model this system with Professor Linderoth, and I figured it’d be worth discussing here since it’s technically a public sector OR problem.

To provide some context for this problem, here’s the basic setup. There are 57 locations in Madison that require mail deliveries each day, and five trucks are available to make these deliveries. Each truck is assigned a total of four routes (one for each time period), and these routes all start and end at the “depot” where the mail is sorted and prepared for the next delivery. Some locations require multiple stops throughout the day, but otherwise there are very few additional complexities. As a result, this problem can be represented using a set-covering model where the objective is to choose a set of routes that minimizes the total distance the trucks have to travel each day.

This model can be seen below:

Mail Transportation VRP model (Full)

Unfortunately, despite the simple mathematical formulation, developing a reasonable solution to this problem is quite challenging because of how many possible routes there are. Even when the number of locations on each route is restricted to 15, there are still more than 2.88e+25 routes that could be taken [1]. That’s a lot of routes, so generating and including all of them in the model simply isn’t practical.

Instead, a more reasonable approach is to create a small set of “good” routes that could be used to find a heuristic solution. While there are a number of sophisticated techniques that exist for this purpose, I originally started with an extremely simple approach and added additional complexity over time. At first, this consisted of randomly generating a large number of routes and throwing out any that exceeded a “high cost” threshold. Building off of this basic structure, I then improved the process by creating routes using location “clusters” to increase the likelihood of generating a good route each time. These routes then served as a starting point for the iterative, column-generation scheme that I’ve been working on most recently, which is something I’ll probably describe in more detail in a future blog post. Although these are fairly crude approaches to route generation, they’ve already resulted in a 15-20% reduction in total travel time when compared to the current state, and that number can only improve as further refinements are made.

[1] Expressed mathematically, this is 57!/(57-15)! since there are 57 locations, the order of stops along a route matters, and each location can only be visited once per route.

Advertisements

4 thoughts on “Overview of a Mail Transportation Vehicle Routing Problem (VRP)

  1. Integer programming rulez! This has been my favorite post so far. 🙂
    But I would argue that 57!/(15!)(42!) is probably the number of routes that have exactly 15 customers — since in this instance you would only consider one of the 15! routes with the same customers that has the smallest cost.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s