Shortest path problem with multiple goals on a grid

In summary, the conversation discusses the shortest path problem in graph theory and its application in solving a variation of a picking problem in a warehouse. The person is looking for an algorithm that takes a single source with multiple goals and finds the shortest path that goes through all the goals. It is suggested to consider the Travelling Salesman Problem as a possible approach for this problem.
  • #1
hddd123456789
92
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
  • #3
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.
 

1. What is the shortest path problem with multiple goals on a grid?

The shortest path problem with multiple goals on a grid is a type of graph optimization problem where the goal is to find the shortest path from a starting point to multiple destination points on a grid. This problem is often encountered in various fields such as transportation, logistics, and robotics.

2. What is the difference between this problem and the traditional shortest path problem?

The traditional shortest path problem only has one goal point, while the shortest path problem with multiple goals on a grid has multiple destination points. This adds complexity to the problem as the shortest path needs to be calculated for each goal point, and the overall shortest path may not necessarily pass through all the goals.

3. How is this problem solved?

This problem can be solved using various algorithms such as Dijkstra's algorithm, A* search algorithm, and the Bellman-Ford algorithm. These algorithms use different techniques to find the shortest path from the starting point to each goal point, and then combine these paths to determine the overall shortest path.

4. Can this problem be applied to real-world scenarios?

Yes, this problem can be applied to real-world scenarios. For example, in transportation, this problem can be used to find the shortest path for a delivery truck to reach multiple destinations efficiently. In robotics, it can be used to plan the path for a robot to navigate through a grid-based environment to reach different objectives.

5. What are the main challenges in solving this problem?

The main challenges in solving this problem include determining an efficient algorithm that can handle multiple goals, dealing with obstacles or restrictions in the grid, and optimizing the overall path to minimize the time or cost of reaching all the goals. Additionally, the size of the grid and the number of goals can also impact the complexity and difficulty of solving this problem.

Similar threads

I The answer is 15! What is the problem?
    • General Math
Replies
1
Views
1K
Optimal Path from source to multiple destinations
    • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
    • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
MHB Question about Dynamic programming-Shortest Path Problem
    • General Math
Replies
12
Views
3K
MHB Counting shortest paths in a non-directed graph using BFS
    • Programming and Computer Science
Replies
1
Views
1K
Studying I have some epic math goals and creating a study plan
    • STEM Academic Advising
Replies
11
Views
1K
C data structures and algorithms - graph problem
    • Engineering and Comp Sci Homework Help
Replies
2
Views
2K
Shortest path between two points on a paraboloid
    • Calculus and Beyond Homework Help
Replies
11
Views
2K
I Can chatgpt accurately calculate expected lengths in Pascal's triangle?
    • General Math
2
Replies
66
Views
4K
A Orthogonality of variations in Faddev-Popov method for path integral
    • Quantum Physics
Replies
1
Views
632

Hot Threads

Recent Insights

Back
Top