Introduction

In my final blog post, I’m going to once again be writing about the vehicle routing problem I’ve been working on over the past few months. For those of you checking in for the first time, I highly recommend reading “Part 1” in this two part series before continuing:

As I mentioned in Part 1, enumerating all possible routes in this model is not practical, so a column generation procedure was used to find a reasonable subset of “good” routes. Although the column generation procedure for this problem is not as advanced as what was used in the political districting model I presented in class, it’s still able to generate fairly substantial improvements.

Before diving into the column generation procedure, though, here’s a brief overview of the algorithm I implemented in Gurobi Python:

- Start with a feasible subset of routes
- Solve the linear relaxation of the problem
- While improvements to the optimal LP solution can be found:
- Perform the column generation procedure
- Add new columns (routes) to the subset
- Resolve LP

- Change decision variables to binary
- Solve IP

Column generation

Just like in the political districting model, the point of this column generation procedure is to find columns with negative reduced costs. This stems from the fact that all nonbasic variables should have positive reduced costs if the current LP solution is optimal. In this model, the reduced cost can be represented by the following expression:

Since we’re trying to minimize the reduced cost, the lambda and mu values associated with each location can therefore be treated as “prizes” when deciding what locations should be visited during the column/route generation procedure. If a location has a large “prize” and is only a short distance away, it’d likely be worth adding to the route.

When generating these routes, I originally started with a fairly simple greedy algorithm to make sure everything was working as intended. Each time the LP was resolved, the algorithm started at the “depot” and chose the next stop by looking for the location with the lowest “distance – prize” value. Then, when a new stop was added to the route, the algorithm checked whether or not the route’s overall reduced cost was negative. If it was, this route was added to the subset and the next stop was chosen based on the same criterion as before. This procedure ended when the “distance – prize” value became positive or when the maximum number of stops was reached, whichever came first.

Building off of this simple heuristic, I then added a “weighted coin flip” to the algorithm, which allowed many more routes to be generated during each iteration of the overall while loop. Weights were assigned to each location based on their “distance – prize” value so that the locations with the largest negative values were most likely to be added to the route. By including these weighted probabilities in the algorithm, I was able to generate a far greater number of routes each time the LP was resolved.

Once all of this had been implemented, the solution I found showed a 29% improvement in the overall travel time when compared to the routes that are currently being used. Additionally, the results also indicated that only four trucks would be needed to complete these routes in the future, which is one less than the current number of trucks. What this means in more practical terms is that one employee could probably be transitioned to more valuable work moving forward. Overall, these results seem very promising and could lead to substantial time and cost savings if implemented.