4
$\begingroup$

Background: I have a set of ZIP codes (e.g., all of the state of Wisconsin), and am trying to figure out an optimization-based approach to identify a subset of these ZIP codes for a logistics service area. Whether or not to include each ZIP code is a binary decision variable, Xi, i=1...N. Each ZIP code has a cost and benefit to its inclusion in the service area; these will be used in the objective function and some constraints (objective function will be linear, and the costs & benefits constraints will be linear)

What I'm having trouble with is the requirement that the selected ZIPs need to be contiguous, i.e., you need to be able to travel from any selected ZIP, to any other selected ZIP, by traveling through selected ZIPs. I have a rough idea how to formulate this using nonlinear constraints and concepts from graph theory, but I would like to understand if there are any papers or references that might already suggest how to approach it.

Thanks in advance.

$\endgroup$
1
  • $\begingroup$ It looks like you need a connected component with minimum cost $\endgroup$ – Kuifje Dec 26 '20 at 9:22
7
$\begingroup$

These are called contiguity constraints. See this paper for models and references.

$\endgroup$
1
  • $\begingroup$ Thanks, this is really helpful. Never thought that there would be a parallel between logistics service areas, and fighting gerrymandering, but now I get it! $\endgroup$ – Ralph Asher Dec 28 '20 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.