An algorithm for optimizing a trade route?

Question

There are several s stores that offer articles at different prices. The store may not offer a specific product. Shops can be connected to each other (streets).

The task is to find the optimal route (cycle) from (and vice versa) some home location, so that the total price is minimal. Total prices are the sum of the prices of articles and the sum of the distances between stores.

Product prices are known for each store. You do not need to visit the store for this information.

Limitations:

• The buyer / traveler wants to purchase a list of articles, possibly all articles
• Each article is available in at least one store.
• Distances between stores are expressed as cost, so you can simply add it to the cost of purchased goods when calculating the total cost of the route.
• Shops can be visited more than once, but this will increase the number of trips and, consequently, the total cost of the route.

---

I did the initial simulation with networkx , simulating the stores (and houses) in an oriented graph (with distance / cost as weight), where each node (store) contains a list of all prices for the offered products.

My first attempt was to create a brute force solution, and I was able to iterate through all the simple loops . Then, for each cycle, travel and item costs are calculated (i.e., Minimum prices, as they appear in the stores in the cycle).

Now it works, but does not scale: the time complexity for listing all O((n+e)(c+1)) cycles for n nodes, e edges, and c elementary circuits ( Finding all elementary circuits of a directed graph. DB Johnson, SIAM Journal on Computing 4, No. 1, 77-84, 1975). And the number of cycles (circuits) is growing quite quickly:

 # random 'streetlike' shop-graphs number of shops: 3, cycles: 2 number of shops: 4, cycles: 11 number of shops: 5, cycles: 11 number of shops: 6, cycles: 60 number of shops: 7, cycles: 229 number of shops: 8, cycles: 868 number of shops: 9, cycles: 1399 number of shops: 10, cycles: 61139 number of shops: 11, cycles: 60066 number of shops: 12, cycles: 1246579 number of shops: 13, cycles: 7993420 

Any suggestions for a more scalable description of the problem? I think of dynamic or linear software solutions, but I would like to hear ideas.

---

update: a whole candidate dissertation was found on the topic: ftp://tesis.bbtk.ull.es/ccppytec/cp181.pdf

Answer 1

There was a comment here a minute ago that was related to a Wikipedia article about what this exact problem looks like: http://en.wikipedia.org/wiki/Traveling_purchaser_problem

There are links to documents describing various solution methods from this page:

Dynamic programming: http://www.di.unipi.it/optimize/Events/proceedings/T/C/4/TC4-1.pdf

http://infos2008.fci.cu.edu.eg/infos/DSS_04_P024-030.pdf (This can only find a "pretty good" solution, not necessarily absolute, but can be much faster)

Edit: Thanks, @soulcheck - your comment has disappeared for a while, but it has returned.

Answer 2

I think we need additional information - if the total "cost" is the distance traveled plus the amount spent, we fight because they are not the same units, therefore, if the distance is cheap, this becomes an example of the traveling salesman problem - to determine the lowest cost of goods each time, and then calculate the route to get them all, if the distance is expensive compared to the cost of the item, then we have another problem.

Summary. I think this problem will be complete if you add constaint - every mile spent on $ R $ units of money, then we can start building solutions ...