Appended all warehouse to all stores, Created Centroids for Store and Warehouse , then used the Distance tool to find the closest using a Summarize, Joined back to product table and used a formula to calculate the distance for each product then summarized the results.
