The Traveling Purchaser Problem (TPP):

The travelling purchaser travels from marketplace to marketplace searching for goods on his list. The travelling purchaser always returns to his "home" marketplace with all the goods on his list and having spent as little money as possible. Given a list of marketplaces, the cost of travelling between different marketplaces, and a list of available goods together with the price of each such good at each marketplace, the task is to find for a given "shopping list" of goods the purchasing route with the minimum combined cost of purchases and traveling.

The purchasing route solution will indicate both the order the marketplaces are visited and the goods that are purchased at each marketplace. The purchaser must start and finish at the same marketplace and visit each other marketplace at most once (it is not required that all marketplaces be visited). The decision version of TPP-D would ask if there exists a route for a set of marketplaces, travel costs, list of goods, and costs of goods such that the total cost of purchases and travelling is at most k.

Formally TPP-D = { (G, C, L, A, P, k) : where G=(V,E) where the vertices are marketplaces, E is the set of edges which represent the road between the marketplaces, C(u,v) is the cost of travelling from marketplace u to v, L is the shopping list of goods that the purchaser wants to buy, A(v) is the list of goods available at marketplace v and P(x,v) is the price of the good x at marketplace v. G has a TPP route with total cost at most k }.

Prove that TPP-D is NP-Complete.