Shortest path problem with multiple goals on a grid

Click For Summary
SUMMARY

The discussion centers on the shortest path problem in graph theory, specifically addressing the need for an algorithm that calculates the shortest path from a single source to multiple goals within a grid structure, such as a warehouse. The user references the Travelling Salesman Problem (TSP) as a potential framework, suggesting that a solution may be more manageable than the general TSP due to the grid's constraints. The conversation highlights the importance of considering intermediate nodes that can be visited en route to optimize the path.

PREREQUISITES
  • Understanding of graph theory concepts, particularly shortest path algorithms.
  • Familiarity with the Travelling Salesman Problem (TSP) and its variations.
  • Knowledge of grid-based data structures and their representation in algorithms.
  • Experience with algorithm optimization techniques.
NEXT STEPS
  • Research Dijkstra's algorithm for single-source shortest paths.
  • Explore A* search algorithm for pathfinding in grid environments.
  • Study heuristics for solving the Travelling Salesman Problem efficiently.
  • Investigate dynamic programming approaches to optimize multi-goal pathfinding.
USEFUL FOR

This discussion is beneficial for algorithm developers, operations researchers, and logistics professionals seeking to optimize routing in warehouse environments or similar grid-based systems.

hddd123456789
Messages
92
Reaction score
0
Hi, I've been reading up a bit on the shortest path problem in graph theory and was wondering if the problem I'm trying to solve is a variation of the same graph theory problem.

Say you have a grid of vertices and edges representing aisles and cross-aisles in a warehouse. In a standard picking problem, you will have to go and pick items up in various locations throughout the warehouse.

The algorithm that I found is for single pair shortest path meaning that there is one source and one goal. Am I right in thinking that what I need is an algorithm that takes a single source with multiple goals (pick locations) and then finds the shortest path from the source that goes through all the goals? Is there such an algorithm?
 
Mathematics news on Phys.org
It might be much more tractable than the general TSP. E.g. if a candidate solution has a step from node A to node B, and there is a node C within the rectangle with corners A. B, then you might as well visit C on the way from A to B.
 

Similar threads

Undergrad Hamilton path and circuit rounded path problem
  • · Replies 10 ·
Replies
10
Views
3K
Optimal Path from source to multiple destinations
  • · Replies 3 ·
Replies
3
Views
2K
MHB Question about Dynamic programming-Shortest Path Problem
  • · Replies 12 ·
Replies
12
Views
3K
Undergrad What is the Cheapest Route to Visit 6 Destinations in Tokyo?
  • · Replies 17 ·
Replies
17
Views
2K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad The answer is 15! What is the problem?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Counting shortest paths in a non-directed graph using BFS
  • · Replies 1 ·
Replies
1
Views
2K
C data structures and algorithms - graph problem
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad QED/Quantum Mechanics: Probability or Spatial Function?
  • · Replies 8 ·
Replies
8
Views
2K
Shortest path between two points on a paraboloid
  • · Replies 11 ·
Replies
11
Views
3K