Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
How do I find the order that yields the shortest path?
The Problem
I have a path optimization problem that in some ways reminds me of the Traveling Salesman Problem, but differs in some key respects. I have a group of items that need to be used by a machine in a certain sequence; for example, if I have (physical) objects A, B, C, and D, the machine might need them in this order: A, B, D, B, C, A. Note that some will be repeated.
These objects are stored in a sort of carousel. In a machine with six positions, they would be arranged like this:
4
5 3
6 2
1
To switch from one item to another takes an amount of time proportional to the distance between the two. So if I'm currently using an item stored in position 1 and I need the item in position 2, switching to the item in 2 takes 1 unit of time. If I currently have the item in position 1 and I need to switch to the item in position 5, it will take 2 units of time.
I would like to place the items in the carousel in an order that will minimize the amount of time needed to work my way through the given sequence. If I take the list of items from above and put them in order so that A is in 1, B in 2, C in 3, and D in 4, then the sequence I gave will have a time cost of 1+2+2+1+2=8. However, if I put B in position 3 and C in position 2 instead, then I will have a cost of 2+1+1+1+1=6. How can I programmatically go about finding the placement that will minimize cost?
Potential Solutions
- Brute force: I could always try every possible position for each item and then simply pick the ordering that yields the lowest cost for the needed sequence. However, the application I'm working on has over 20 positions and as many items, so trying every possible combination would be impractically time-consuming. If there's some heuristic that would allow me to eliminate most possible combinations in large swaths, that might help, but I haven't thought of anything that good yet.
- Another approach would be to start with some sort of default order (like the A->1, B->2, etc. above), try swapping different pairs of items, keep the swap that results in the greatest cost reduction, and repeat until I reach a minimum. There's no guarantee, though, that this would be the absolute minimum or even very close to it, so I would probably have to start from a number of randomly chosen orders to do very well. Even then I would have no way of knowing for sure whether or not the result was particularly good.
- The final method I thought of would be to find the item with the most changes into and out of it and put it somewhere, then take the item with the most connections to that one and place it next to the first, and so on. However, I'm concerned that items further down from the most "popular" one might become split across the gathering cluster of items in an inefficient way.
My Questions
- Does anyone know of a name for this problem, or something analogous to it, that I could research more information on?
- Does anyone have any ideas for a heuristic (or, better yet, exact) algorithm that would take a reasonable amount of time and find close to the best order?
1 answer
This looks like it's a slightly restricted version of the circular dilation minimization problem in the theory of graph drawing. See, for example, https://doi.org/10.1080/00207168808803629.
Specifically, your problem can be expressed as finding a vertex numbering with minimal circular dilation for the graph formed from a vertex for each of your items and an undirected edge for every adjacent pair in your item use order (there can be multiple edges between two vertices, as in the case of B and D in your example).
I'm not familiar with a good heuristic for solving this problem, but I think circular graph layout engines sometimes use force-based physical simulations to cut the NP knot. You might try that if researching the literature doesn't come up with anything useful.
1 comment thread