Another way to find and use the most expensive node
In my previous post, I looked at how slack variables were used to determine the maximum cost value of a node on a route, and how that value could be assigned as a “cost” for the entire route. The program, vrp_node_max.py. was developed by Mizux and is really clever. However, as I mentioned in my previous post, the final note in the original forum thread from Guy was a note that the approach did not seem to work in practice. With this post, I want to explore what that means and how to fix it.
More fun with Slack: Understanding vrp_node_max.py
A few weeks ago while working on a project I came across a very interesting program in the OR-Tools code base. The origin of the code started from a question from Guy on the OR-Tools forum. When the question was originally posted last summer, I didn’t have the opportunity to dig into the proposed result, but now I do, and I discovered it is a very interesting (ab)use of the slack dimension. Since I haven’t written anything here in ages, it seemed like a good idea to write up a blog post on the code and my understanding of how it works.
Converting a TSP to a multi-day TSP and using Slack in OR Tools
Recently a question was asked on the OR Tools forum about how to convert a single-day TSP problem into a multi-day TSP problem. The original poster was thorough, and cross posted to Stack Overflow and posted his original code as a gist on GitHub. The problem is interesting in that it takes a away from an idealized lab problem toward integrating real-world constraints. So I responded to the question with my solution, and decided to write it up properly here.
Keeping with my pattern of posts based on OR Tools GitHub issues, (issue #968) asked how to model having multiple alternatives for pickup locations and dropoff locations.
FIFO Constraints in OR Tools
A question was posed recently on the Google OR Tools GitHub issues (issue #922) that asked whether it was possible to set up FIFO or LIFO constraints. I’d never done that before, but it seemed straightforward to implement. There were a few wrinkles though, so I thought I’d write them up for my future self.
Destination Time Windows
Generating random pickup and delivery pairs has been a pain point for me in the past. The problem comes with generating reasonable destination time windows. In my latest cycle of coding up a test environment for pickup and delivery problems with time windows (PDPTW), I had an insight that both makes generating random deliveries easier, and also improves the actual solution process of the PDPTW problem.
We’ve recently been doing a lot of work with Google’s OR Tools. One of our clients discovered a surprising result while setting disjunctions. As expected, with no disjunctions, all nodes are required. But if you set just one disjunction, most nodes are dropped. We didn’t have a good answer for what was going on, so I decided to explore the situation in this post.
Google’s OR Tools is incredibly useful, but can be tricky to use. I subscribe to the mailing list to keep up on other users’ questions and solutions, and usually I just read and learn. But yesterday a question popped up on the OR-Tools mailing list that I could answer: how to force some node to occur before another node.