Public Services
Schools · Fire Stations · Transit · Emergency
Operations research carries special moral weight when applied to public services — every misallocated fire truck or poorly routed bus affects lives directly. From the landmark RAND Corporation fire station models that reshaped New York City's emergency response in the 1970s, to transit scheduling algorithms that determine whether a shift worker can reach their job on time, these are problems where mathematical rigour meets civic responsibility.
The Maximal Covering Location Problem (MCLP) asks where to place p facilities so that the maximum number of demand points fall within a specified service distance. In fire protection, this translates to siting stations so that the greatest proportion of the population can receive a response within 4–6 minutes. The RAND Corporation's pioneering work for New York City in the early 1970s showed that relocating just a handful of fire companies could dramatically reduce response time disparities across boroughs — a finding that reshaped urban emergency planning worldwide.
Problem type: Maximal Covering Location Problem (MCLP). Select p station sites from candidate locations to maximise the population covered within a response-time radius, subject to a fixed number of stations.
s.t. y_i ≤ Σj∈N_i x_j ∀ i // covered only if station nearby
Σj x_j = p // exactly p stations
x_j, y_i ∈ {0,1}
// N_i = {j : d(i,j) ≤ R} coverage neighbourhood
Fire Station Solver
- Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations Research, 19(6), 1363–1373. Published
- Walker, W., Chaiken, J., & Ignall, E. (1974). Fire department deployment analysis: A public policy analysis case study. RAND Corporation, R-1566-NYC. Operational
- Church, R. & ReVelle, C. (1974). The maximal covering location problem. Papers of the Regional Science Association, 32, 101–118. Published
Transit network design determines which routes a bus or rail system should operate and at what frequencies to satisfy origin–destination demand while minimising passenger travel time and operator cost. The problem is notoriously hard — even small networks produce a combinatorial explosion of possible route sets. Mandl's benchmark (1979) with 15 nodes and 21 links has been studied for decades, while Ceder & Wilson (1986) decomposed the problem into route generation, frequency setting, and timetabling sub-problems that remain the standard framework today.
Problem type: Transit route network design. Select a set of routes on a graph and assign frequencies to minimise total passenger travel time (in-vehicle + waiting + transfer) subject to fleet size and route-length constraints.
s.t. Σr f_r · len_r / speed ≤ Fleet // fleet constraint
f_r ≥ f_min ∀ r // minimum frequency
len_r ≤ L_max // max route length
// d_od = demand from o to d
Transit Network Solver
- Mandl, C.E. (1979). Applied network optimization. Academic Press. Benchmark instance with 15 nodes, 21 edges. Published
- Ceder, A. & Wilson, N.H.M. (1986). Bus network design. Transportation Research Part B, 20(4), 331–344. Published
- Baaj, M.H. & Mahmassani, H.S. (1995). Hybrid route generation heuristic algorithm for the design of transit networks. Transportation Research Part C, 3(1), 31–50. Published
Municipal garbage collection is a classic arc routing problem: every street segment (arc) that requires service must be traversed by a collection vehicle. The Chinese Postman Problem finds the minimum-cost traversal of all edges in a graph, while the Capacitated Arc Routing Problem (CARP) adds vehicle capacity constraints and a depot. Edmonds & Johnson (1973) provided the foundational polynomial-time algorithm for the undirected Chinese Postman, and Golden & Wong (1981) proved CARP is NP-hard, motivating the route-first cluster-second heuristic that remains widely used in municipal fleet planning.
Problem type: Capacitated Arc Routing Problem (CARP). Partition required arcs among vehicles of limited capacity and find minimum-cost tours from a depot, traversing every required arc at least once.
s.t. Σa∈tour_k demand_a ≤ Q ∀ k // vehicle capacity
each required arc in exactly one tour_k
each tour_k starts and ends at depot
// deadheading = traversal without collection
Garbage Collection Solver
- Edmonds, J. & Johnson, E.L. (1973). Matching, Euler tours and the Chinese postman. Mathematical Programming, 5, 88–124. Published
- Golden, B.L. & Wong, R.T. (1981). Capacitated arc routing problems. Networks, 11(3), 305–315. Published
- Belenguer, J.M. & Benavent, E. (2003). A cutting plane algorithm for the capacitated arc routing problem. Computers & Operations Research, 30(5), 705–728. Published
All Public Services Applications
Browse the complete collection