Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics

Dashboard
Notifications
Mark all as read
Q&A

How do I find the order that yields the shortest path?

+7
−0

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

  1. 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.
  2. 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.
  3. 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

  1. Does anyone know of a name for this problem, or something analogous to it, that I could research more information on?
  2. 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?
Why does this post require moderator attention?
You might want to add some details to your flag.
Why should this post be closed?

5 comments

There might be some heuristics available based on the actual application. For example, if this is a carousel of tools for a CNC machine, then you probably want to cluster course tools together for the initial rough cuts, and fine tools together for the finishing passes. (Of course, the tool change time is unlikely to be significant in a CNC machine, so that probably isn't your application.) Martin Bonner‭ about 1 month ago

@Martin Bonner - actually, that is my application. I tried to generalize it, since I expect there might be applications in robotics and other related fields as well. We think we can shave several seconds off the cycle time, and when you're working on an automated cell that runs 24 hours a day with a sub-10 minute cycle, saving those seconds could add up to a couple "free" parts every day. matthewb‭ about 1 month ago

This particular CNC program switches back and forth a lot between otherwise "earlier" and "later" tools to remove burrs, hence the inefficiency and interest in an algorithm. Once we have it, we'll probably apply it to other jobs as well. matthewb‭ about 1 month ago

Sounds like you can perhaps use some modified version of Prim's algorithm for the most efficient way to connect all nodes to a graph. Or some other manner of "greedy algorithm". Lundin‭ about 1 month ago

@Lundin - I think applying greedy principles to my third idea above might be decent. I hope to code something up and try it out soon. matthewb‭ about 1 month ago

1 answer

+6
−0

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.

Why does this post require moderator attention?
You might want to add some details to your flag.

1 comment

Thanks! Those look helpful. I'll look into it more in the morning. The force-based method could be promising, though I'll have to think about how best to adapt it to my discrete situation. matthewb‭ about 1 month ago

Sign up to answer this question »