Computational Complexity of Solutions of the Traveling Purchaser Problem on a Small Data Set
First, it is good to observe that the problem is very difficult to approximate (see e.g., my earlier answer on it here). 

Second, there is very recent survey on the traveling purchaser problem and its variants by Manerba et al. [1]. Essentially, you will find discussion on relevant methods that have been applied to solve the problem in practical settings. If you want theoretical time bounds for heuristics, see Section 6.1.1. on page 13.



[1] Manerba, Daniele, Renata Mansini, and Jorge Riera-Ledesma. "The traveling purchaser problem and its variants." European Journal of Operational Research 259.1 (2017): 1-18.