Locating ballot drop boxes is NP-hard

The state of Michigan passed Proposition 2 on November 8, 2022, a bill that introduces several voting rights including access to drop boxes. Proposition 2 will lead to the widespread use and location of drop boxes in the state of Michigan, since it requires at least one ballot drop box per 15,000 registered voters with at least one drop box per municipality. There will be questions about where to locate the drop boxes, since “the boxes would have to be distributed in an equitable way.”

Operations research can help inform these important election decisions. Dr. Adam Schmidt and I studied issues surrounding the location of drop boxes in our recent paper entitled “Locating ballot drop boxes” (Read the preprint here). Our paper studies how to locate ballot drop boxes when considering multiple criteria such as cost, voter access, and equity. The paper abstract is as follows:

For decades, voting-by-mail and the use of ballot drop boxes has substantially grown, and in response, many election officials have added new drop boxes to their voting infrastructure. However, existing guidance for locating drop boxes is limited. In this paper, we introduce an integer programming model, the drop box location problem (DBLP), to locate drop boxes. The DBLP considers criteria of cost, voter access, and risk. The cost of the drop box system is determined by the fixed cost of adding drop boxes and the operational cost of a collection tour by a bipartisan team who regularly collects ballots from selected locations. The DBLP utilizes covering sets to ensure each voter is in close proximity to a drop box and incorporates a novel measure of access to measure the ability to use multiple voting pathways to vote. The DBLP is shown to be NP-Hard, and we introduce a heuristic to generate a large number of feasible solutions for policy makers to select from a posteriori. Using a real-world case study of Milwaukee, WI, we study the benefit of the DBLP. The results demonstrate that the proposed optimization model identifies drop box locations that perform well across multiple criteria. The results also demonstrate that the trade-off between cost, access, and risk is non-trivial, which supports the use of the proposed optimization-based approach to select drop box locations.

We published an op-ed in The Hill summarizing some of the key findings from this paper.

While I am thrilled to see Michigan introduce a legal requirement for ballot drop boxes in future elections, our research indicates that this requirement is not straightforward for election officials to implement, since decisions involving the location of drop boxes are hard from theoretical and computational perspectives. Tools such as our integer programming model can help election officials make informed decisions.

Dr. Adam Schmidt recently defended his dissertation entitled “Optimization and Simulation Models for the Design of Resilient Election Voting Systems” about election resilience, and his paper about drop boxes is part of his dissertation. He also studied the impact of the COVID-19 pandemic on in-person voting and how to decide how to locate/consolidate polling locations.

I am exciting to see some states expanding the use of ballot drop boxes. Drop boxes have a place in our elections. The US states that are weighing legislation will define how and when drop boxes can be used. With research backed by proven scientific methods using operations research, we can truly make informed decisions about drop boxes and our voting systems.