Improvements in the collection and treatment of sewage are critical to reduce health and environmental hazards in rapidly urbanising informal settlements. Where sewerage infrastructure is not available, road-based faecal sludge management options are often the only alternative. However, the costs of faecal sludge transportation are often a barrier to its implementation and operation and thus it is desirable to optimise travel time from source to treatment to reduce costs. This paper presents a novel technique, employing spatial network analysis, to optimise the spatio-topological configuration of a road-based faecal sludge transportation network on the basis of travel time. Using crowd-sourced spatial data for the Kibera settlement and the surrounding city, Nairobi, a proof-of-concept network model was created simulating the transport of waste from the 158 public toilets within Kibera. The toilets are serviced by vacuum pump trucks which move faecal sludge to a transfer station, and from there a tanker transports waste to a treatment plant. The model was used to evaluate the efficiency of different network configurations, based on transportation time. The results show that the location of the transfer station is a critical factor in network optimisation, demonstrating the utility of network analysis as part of the sanitation planning process.