As I briefly described during the Zoom call on This week I worked on Friday 3/27/2020, I worked on designing the algorithm this week. The following is a more detailed report:

• I first researched more about traveling salesman problem. After research, I feel like it might not be the most accurate representation of the problem at hand. One thing that TSP does not allow is visiting a node more than once, but my algorithm can visit any node any number of times as long as the total distance remains the shortest. Another thing TSP makes sure is that all nodes are visited, which is highly likely not the case for my algorithm. A user is very unlikely to have to visit every stop of every aisle. To address this problem, I first thought about building a sub-graph consist of only the nodes I need to visit. It is easy to figure out which nodes to keep, but when it comes to which edges to keep, it is unclear to me how that can be done easily. Also, intermediate nodes might need to be included in order to keep the graph connected. After thinking for a while, I feel like constructing a sub-graph than guarantees to still contain the optimal route is just as computationally complex as finding out the optimal route directly.
• I then arrived at this algorithm that uses A* followed by a greedy approach. I currently think this algorithm has run time O(N^3). This algorithm looks better to me as it has a better time complexity than the best approach for traveling salesman problem. I did not try to formally prove the correctness, as in whether the solution is guaranteed to be optimal, but the completeness should be obvious.
• First step of the algorithm, I use A* to find the shortest path between any two nodes. I save this data in a dictionary as it will also be useful if I would need to re-plan using A*. Then I use a greedy approach. Every time I try to figure out which node to visit next, I pick the one that can be inserted into the current route with the least cost and update the current route to include the new node. For example, at the very beginning, I start at A. I see that C is closest to A, so I update the current route to be A->C->A. I always make sure I come back to starting point. Then for explanation purposes, let’s assume at some point my current route becomes A->C->B->A->D->A. Then for all node_i left that I still need to visit, I figure out which of the following is the smallest: 1. A->i + i->C; 2. C->i + i->B; 3. B->i + i->A; 4. A->i + i->D; 5. A->i + i->A; 6. B->i + i->B; 7. C->i + i->C; 8. D->i + i->D. If node E has the shortest distance in segment 2 and the shortest path from B to E is B->E and the shortest path from C to E is C->Z->E, the updated route becomes A->C->Z->E->B->A->D->A. If node F has the shortest distance in segment 7 with the shortest path from C to F being C->X->F, then the updated route becomes A->C->X->F->X->C->B->A->D->A. If node G has the shortest distance in segment 5 and the shortest path from A to G is A->G, then the updated route becomes A->C->B->A->D->A->F->A.
• I tested this algorithm with hand on small and relatively sparse maps, it looks correct.
• Next week, I will work on implementing this algorithm in Python. I should be able to have the functional algorithm (given the store map and a list of nodes that i need to visit, output an optimal path through those nodes) for midway demo.