A method comprising: identifying, by a backhaul optimization engine executing on a computer, from infrastructure information about a cellular communication system, a cluster of stranded sites in the cellular communication system, wherein the stranded sites are sites that are not connected to a backhaul connection for transportation of cellular data; identifying, by the backhaul optimization engine from the infrastructure information, relay sites with existing backhaul connections to alternative access vendor, AAV, sites; creating, by the backhaul optimization engine, a mesh network graph representing the cluster of stranded sites, the relay sites, and the AAV sites as vertices of the mesh network graph and possible connections between adjacent ones of the cluster of stranded sites, the relay sites, or the AAV sites as edges of the mesh network graph; updating (1806, 1808), by the backhaul optimization engine, weights for each vertex and edge of the mesh network graph for which there is an associated bid cost for a fiber connection or a microwave connection to a first state of the mesh network graph; selecting, by the backhaul optimization engine, potential starting points in the mesh network graph, wherein vertices representing stranded sites that have existing vendor bids for fiber connections or vertices representing AAV sites linked to relay sites are candidates for the potential starting points; identifying (1816, 1818, 1820, 1822, 1824), by the backhaul optimization engine, a plurality of minimum weight spanning tree solutions for different ones of the potential starting points, wherein, for the different ones of the potential starting points, the mesh network graph is updated from the first state by removing weights of vertices representing other potential starting points, and the plurality of minimum weight spanning tree solutions meet aggregated site capacity and minimum backhaul availability thresholds; and selecting (1826, 1828), by the backhaul optimization engine, one of the plurality of minimum weight spanning tree solutions that is associated with a minimum average cost per stranded site. identifying, by a backhaul optimization engine executing on a computer, from infrastructure information about a cellular communication system, a cluster of stranded sites in the cellular communication system, wherein the stranded sites are sites that are not connected to a backhaul connection for transportation of cellular data; identifying, by the backhaul optimization engine from the infrastructure information, relay sites with existing backhaul connections to alternative access vendor, AAV, sites; creating, by the backhaul optimization engine, a mesh network graph representing the cluster of stranded sites, the relay sites, and the AAV sites as vertices of the mesh network graph and possible connections between adjacent ones of the cluster of stranded sites, the relay sites, or the AAV sites as edges of the mesh network graph; updating (1806, 1808), by the backhaul optimization engine, weights for each vertex and edge of the mesh network graph for which there is an associated bid cost for a fiber connection or a microwave connection to a first state of the mesh network graph; selecting, by the backhaul optimization engine, potential starting points in the mesh network graph, wherein vertices representing stranded sites that have existing vendor bids for fiber connections or vertices representing AAV sites linked to relay sites are candidates for the potential starting points; identifying (1816, 1818, 1820, 1822, 1824), by the backhaul optimization engine, a plurality of minimum weight spanning tree solutions for different ones of the potential starting points, wherein, for the different ones of the potential starting points, the mesh network graph is updated from the first state by removing weights of vertices representing other potential starting points, and the plurality of minimum weight spanning tree solutions meet aggregated site capacity and minimum backhaul availability thresholds; and selecting (1826, 1828), by the backhaul optimization engine, one of the plurality of minimum weight spanning tree solutions that is associated with a minimum average cost per stranded site.