library(tidyverse)
library(tidycensus)
library(sf)
library(knitr)
library(viridis)
library(bookdown)
library(MASS)
library(rmarkdown)
options(scipen = 999)
knitr::opts_chunk$set(echo = TRUE)
theme_update(plot.title = element_text(hjust = 0.5))

Introduction

Transportation planners often are challenged to balance accessibility through location stops versus maintaining or increasing efficiency to ensure the route is practical. We use ArcGIS Pro and CPLEX to solve problems involving the maximum covering location problem (MCLP). We will specifically use a sample bus line in Charlotte to analyse the sensitivity of the coverage model by varying the willingness of agents to commute to travel nodes. The main outcome is that that after a certain amount of placed stops, coverage will not increase as all demand will be satisfied.

Solving MCLP models via ArcGIS Pro offers powerful visual insights to urban transportation policy makers as this case study will demonstrate, and we believe that in future, it will rarely be the case that decisions on new transport lines will be taken without solving such models.

Methodology

The Maximum Location Coverage Problem (MLCP) is a NP-hard maximization problem in computational complexity theory that optimizes to cover a maximum of demand subject to constraints. A typical use for MLCP is the siting of public service facilities, as public funds should be deployed to their maximum efficiency. Mathematically speaking, the MLCP has the form

\[ \text{max} \sum_{i \in I} g_iY_i \\ \text{s.t.} \sum_{j \in N_i}x_j \geq Y_i \ \forall i \in I, \ (1)\\ \sum_{j \in J} x_j \leq p, \ (2) \\ x_j, Y_i \in \{0,1\}, \\ Y_i = \begin{cases} 1 & \text{if } i \text{ is covered by at least one facility} \\ 0 & \text{otherwise }\end{cases}. \] In this form, \(g_i\) is the demand at a location and \(Y_i\) is a decision variable that is constrained to be either zero or one. Thus, the objective functions aims to capture the most amount of demand possible given that we can place a maximum of \(p\) facilities (constraint (2), also called budget constraint in Game Theory)) and that a demand node can only be covered if at least one facility is covering it (constraint (1)).

It should be noted that the MCLP can he highly sensitive to the input variables, as we will see in our sample bus line analysis in Charlotte. This is to say that slight changes in the constraint can lead to utterly distinct optimization results, and that therefore, thorough prior research is required for a proper use of MCLP.

Case Study | Charlotte Area Transit System (CATS)

In our study we examined a sample bus line in the Charlotte metropolitan area. Our objective was to measure overlap and redundancy in coverage among bus stations contingent on a person’s willingness to travel to a specific bus stop. Our sample included 941 demand nodes, each of which was measured as equal weight and was assumed to travel to the closest bus stop for their final destination. Using various distances as the radius each stop covers, all distances managed to accommodate nearly every demand node after 12 bus stops, as shown in the graph below.

knitr::include_graphics("https://github.com/TrevorKap/Classes_MUSA/raw/c27c6a73146d91b8650bb14d71c8ba311181cab1/SpatialOptimization/SpatialOptHW2chart1New.png")

We notice in the graph that all measured distances end up ‘flatlining’ because the entire sample was covered after 12 stations were strategically placed. This also means every bus stop added after the 12th added zero value to the transit line and decreased its efficiency.

The weakness within the survey is the measured distance a person is assumed to travel. Majority of people are willing to walk for five to ten minutes, or approximately ¼- to ½-mile to a transit stop1. To better reflect a person’s travel distance we would need to measure each station using an 800 meter radius. Regardless of the flaw, the 46 total bus stops sampled is excessive for the single transit line.

knitr::include_graphics("https://github.com/TrevorKap/Classes_MUSA/raw/1a547eb4a4aa282760be961b8f770f284639c07c/SpatialOptimization/p10.png")

The map above displays the overlap among the chosen bus stops if 3,000 meters (blue) was the calculated willingness to travel. Despite the model only choosing 7 stations, there is already large areas of overlap among 2-3 other bus stations, with every demand node covered with multiple options. The area covered by stations with a 2,500 meter buffer (red) fulfill the same objective but do not cover the far reaching areas covered by the blue buffer.

knitr::include_graphics("https://github.com/TrevorKap/Classes_MUSA/raw/1a547eb4a4aa282760be961b8f770f284639c07c/SpatialOptimization/p15.png")

Despite the additional bus stops presented and the decrease distanced of assumed travel, there is overlap between bus stations along the road the bus line travels along. This overlap indicates the issue is the location of the existing bus stops, as they are too close together and cover the same populations.

knitr::include_graphics("https://github.com/TrevorKap/Classes_MUSA/raw/c27c6a73146d91b8650bb14d71c8ba311181cab1/SpatialOptimization/SpatialOptHW2chart2New.png")

In the graph we ran the model while considered population density for each demand node, measuring the differences between the city center’s demand compared to the suburbs. Even with population accounted for, both assumed willing travel distances only required a maximum of 8 bus stops along the sample in order to cover 100% of demand.

Conclusion

Despite the nuances and external factors not accounted for in the model and study, there is clear redundancy in the sampled transit line and there are multiple solution to improve the efficiency of the bus line. One way is to relocate existing bus stops that cover underserved or outreaching communities who do not have walkable access to a bus stop. Another is to skip existing bus stops that do not service a unique audience and are already overlapping cover with adjacent stations. Lastly, it is recommended to reconduct the study with more realistic walkable travel distances to better accurately measure each bus stop’s existing coverage.

  1. U.S. Department of Transportation. https://safety.fhwa.dot.gov/ped_bike/ped_transit/ped_transguide/ch4.cfm#↩︎