This paper introduces the Latency Location-Routing Problem (LLRP) whose goal is to minimize waiting time of recipients by optimally determining both the locations of depots and the routes of vehicles. The LLRP is customer oriented by pursuing minimization of the latency instead of minimization of the length of routes. One of the main applications of this problem is the distribution of supplies to affected areas in post-disaster relief activities. It is also relevant in customer-oriented supply chain where latency at demand locations plays a significant role in the satisfaction of the customers. The problem is formulated mathematically and two heuristics, the Memetic Algorithm (MA) and the Recursive Granular Algorithm (RGA), are proposed. An extensive experimental study shows that both algorithms are able to produce promising results in reasonable time. (C) 2016 Elsevier B.V. All rights reserved.