2

I am learning about graphs and algorithms and I am having a hard time even finding a name for this kind of problem, let alone coming up with a good solution.

If we just have an unweighted undirected graph, finding the shortest path from A to B is trivial (BFS).

It becomes harder if we have to visit certain nodes ("Go from A to B, while picking up item 1 on node C, item 2 on node D.. in any order, visiting a node more than once is allowed"), but this is still an easy to find problem.

Now, what if each item can be picked up from more than one node? It only needs to be picked up once, how to choose which node to use, so that the resulting path is the shortest possible?

Each item can be available on many nodes, each node can have none at min and all at max items available on it. Multiple nodes with a specific item can be visited, but only one is required for each item.

Think ~10000 nodes, ~10 items, each item available in up to ~10 nodes. Bruteforcing all possibilities for each item feels wrong, since the linked solution for a specific set of nodes already tries all their permutations, so this would be very complex.

I have found some resemblance to the picker routing problem, specifically the mixed-shelve warehouse variant. The problem is to find the shortest route to pickup each item from an order in a warehouse, where each item is stocked in multiple places in the warehouse. Contrary to my situation, papers solving these problems think of specific shaped graphs (rectangular warehouse, parralel aisles) and are satisfied with heuristic aproximations of the shortest path. Mixed-shelves picker routing turns out to be NP-hard.

DkMemu
  • 23
  • 4
  • If the easier version of the problem is NP-hard, this version clearly is as well. None of the papers give more general heuristics? – BlueRaja - Danny Pflughoeft Oct 08 '22 at 14:41
  • @BlueRaja-DannyPflughoeft for a non-rectangular warehouse maybe, but these heuristic approaches are very far from what I need (specific use case, approximation), I just mentioned that this is the only similar problem I found. I wasn't sure if this "warehouse" problem's hardness was relevant to my problem, but you are right. – DkMemu Oct 08 '22 at 15:51
  • You say, ~10, but what are the highest possible number of items and the highest possible number of nodes that contain one or more of them? With 10 and 10, we can try all combinations of less than 11 nodes and all their permutations, and the program would run in millions (not even tens of millions) of iterations. – גלעד ברקן Oct 09 '22 at 19:02

1 Answers1

0

A 'greedy' algorithm:

  • Identify L1 all the nodes that have one or more of the required items
  • Use travelling salesman ( TS ) algorithm to find shortest path from A to B that visits every node that has one or more of the required items.
  • Identify L2 all the nodes whose items could have been picked up at other nodes.
  • LOOP
    • Iterate N over L2
      • Set L3 to L1 without N
      • Solve TS on L3
      • If TS on L3 shorter than best found
        • Best = L3
      • ITERATE end
    • IF no improvement DONE
    • L1 = Best
    • LOOP end
ravenspoint
  • 19,093
  • 6
  • 57
  • 103
  • Could you please explain the loop a little bit more? I don't think I understand how exactly L3 is supposed to be built. – DkMemu Oct 08 '22 at 17:13
  • If L1 = 1,2,3 and N = 2 then L3 would be 1,3 – ravenspoint Oct 08 '22 at 21:13
  • Does that mean every time TS on L3 is run, size of L3 is constant |L1| - 1? I don't see how that would result in the shortest path, pardon my confusion, I must be getting something wrong. – DkMemu Oct 09 '22 at 08:52
  • There are two nested loops. "Iterate N..." has a const L3 length. Each pass throught "LOOP..." has a shorter L3 by one until no improvement found. – ravenspoint Oct 09 '22 at 14:02