Distribution of non-medical products is a very interesting problem in healthcare supply chain logistics. It has a considerable impact on profit, especially when products have to be transported firstly from the manufacturing centres to intermediate healthcare facilities then to the final healthcare establishments. This transportation is ensured at two levels by selecting the best intermediate facilities and the best trips. In this paper, we address the two-echelon location-distribution problem and we develop a multi-objective mathematical formulation for minimising two objective functions. The first is the total distribution cost which is the sum of transportation costs, the opening cost of intermediate healthcare facilities and the usage cost of vehicles. The second is the total horizon time of the distribution of products. For solving this new problem, we propose two solution approaches, the multi-objective particle swarm optimisation algorithm improved by variable neighbourhood search heuristics and the non-dominated sorting genetic algorithm combined also with the same heuristics. They are tested on thirty problems and compared with different related works. Moreover, a real case study of non-medical products distribution is studied. The validation and efficiency of the algorithms are based on several performance metrics which are presented later.