This paper describes a Multi-Trip Heterogeneous Fixed Fleet Vehicle Routing Problem (MTHFFVRP) arising at one of the major retail chain in Turkey. The paper presents a GIS-based optimization method, based on a tabu search algorithm, that can be used to store, analyze and visualize all data as well as model solutions in geographic format. The solution method is applied on a real dataset of the supermarket store chain operates in Turkey. The paper presents computational and managerial results by analyzing the trade-offs between various parameters such as demand, number of vehicles, vehicle speed and capacity, and also a single-trip version of the problem. According to the one of the results, the total en-route time is increased by 5.18%, 4.25% and 1.82%, when the capacity of each vehicle type is decreased by 30%, 20% and 10%, respectively.