There are number of shops s which offer articles a for different prices. It is possible for a shop to not offer a specific product. Shops can be connected to each other (streets).
The task is to find an optimal route (cycle) from (and back to) some home location, so that the total price is minimal. The total prices is the sum of prices of the articles and the sum of the distances between the shops.
The prices of articles are known for each shop. A shop does not need to be visited for this information.
The constraits are:
- The buyer/traveller wants to purchase a list of articles, potentially all articles
- Every article is available at least in one shop
- The distances between shops are expressed as cost, so it may be simply added to the cost of the purchased articles, when calculating the total cost of a route
- Shops can be visited more than once, but that would increase the travelling an therefore the total cost of a route
I did the initial modeling with networkx, modeling the shops (and the home) as a directed graph (with the distance/cost as weight), where each node (shop) holds a list of all prices for the products it offers.
My first attempt was to create a brute-force solution, and I succeeded by iterating over all simple cycles. Then, for each cycle I calculate the travelling costs and the costs of the articles (that is, the minimum prices, as they appear in the shops of the cycle).
Now the above works, but doesn't scale: The time complexity for enumerating all cycles is O((n+e)(c+1)) for n nodes, e edges and c elementary circuits (Finding all the elementary circuits of a directed graph. D. B. Johnson, SIAM Journal on Computing 4, no. 1, 77-84, 1975). And the number of cycles (circuits) grows quite rapidly:
# 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 problem description? I'm thinking about dynamic or linear programming solutions, but I'd love to hear ideas.
update: Found a whole PhD thesis on the topic: ftp://tesis.bbtk.ull.es/ccppytec/cp181.pdf
I think we need more information - if the total 'cost' is the distance traveled plus the amount of money spent then we struggle because they arn't the same units - so if distance is cheap then this becomes an instance of the traveling salesman problem - identify the lowest cost item of each time and then compute the route to get them all, if distance is expensive compared to the cost of the item, then we have different problem.
Summary - I think this problem will be complete if you add the constaint - each mile traveled costs $R$ units of money, then we can start building solutions...