<commit_before>\documentclass[notitlepage, 12pt]{article}
% package includes
% ---------------------

\usepackage{graphicx} % for include images

\usepackage{url}
% \usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{subcaption}
\usepackage{float}
\restylefloat{table}
\restylefloat{figure}
\usepackage{setspace}
% \usepackage{minted}
% \usemintedstyle{colorful}
\graphicspath{{./Pictures/}}

\pagestyle{fancy}
\lhead{Team 4552}
\chead{Problem A}
\rhead{\thepage}

\renewcommand{\headrulewidth}{.8pt}
%\renewcommand{\footrulewidth}{.8pt}

\title{\textbf{Emergency Service Location Optimization in a Multi-Zone County based on Population Distribution}}
\author{Team 4552}

\date{November 15, 2013}

\begin{document}
\maketitle

\tableofcontents

\section{Problem Restatement}
Given a county made up of six separate zones and average travel times between zones, create a model to optimize the placement of $n$ ambulances in order to maximize the number of civilians reached in an eight minute period. Consider the scenarios where $n = 3$, $n = 2$, and $n = 1$, respectively, and for each scenario, keep track of how many people are not being reached with each possible solution.

Then, consider a scenario in which a large scale disaster affects a single location (e.g. the September 11th attacks), and discuss how an Emergency Service Coordinator would cover the situation. Examine how a real-world city or county would prepare for such a disaster. Finally, write a two page memo detailing the model and its analysis for the Emergency Service Coordinator.


\section{Assumptions and Justifications}
\begin{description}
    \item[TODO(drew): Add these assumptions] \hfill \\
    	* Each zone is not a point, but rather a distribution. We experimented with...
        * Route frequency is correlated with population frequency (two random variables?)
    \item[1. Naming] \hfill \\
    	A county is another name for a county. ... TODO(drew)
        Travel...
        Travel times...
    \item[2. Zone to Zone Travel] \hfill \\
    	The travel times given are considered to be optimal routes from the center of one zone to
        the center of the another, regardless of any other zones that may lie in between.
    \item[3. Travel Inside Each Zone] \hfill \\
    	The travel times given for travel from any zone to itself is the average
        of all the travel times of the different routes within that zone.
    \item[4. Directional Travel Inside Each Zone] \hfill \\
    	The ratio between the time it takes inside a zone to travel toward a second zone,
        to the time it takes inside a zone to return from a second, is equal to the ratio
        between the travel time from the first zone to the second, and the travel time from the
        second to the first.
    \item[5. Ambulance Placement] \hfill \\
        Ambulances can only be placed in the very center of a zone. Because we do not know the
        spacial position of the zones relative to each other, we cannot consider the ambulances
        being closer to one zone or another.
    \item[6. Partial Coverage] \hfill \\
        Partial ambulance coverage of a zone will be treated as incomplete even coverage over the entire
        zone. Because ambulances of ideal placement are unlikely to overlap in partial coverage, we assume
        that multiple ambulances will cover different areas of the zones, thus evening out coverage.
        (If partial coverages from multiple ambulances sum to above the total population of a zone,
        we assume that zone is completely covered by the ambulances.)
\end{description}

\section{The Model}

\subsection{Model Approach}

Given that a county has $n$ zones, $k$ ambulances need to be placed to maximize the number of people who can be reached in eight minutes or fewer. This system can be represented as a graph of $n$ nodes and $n^2$ vertices. By analyzing all possible configurations, we can identify the ideal nodes to place the ambulances. This algorithm can be made more efficient---albeit less optimal---by employing a greedy heuristic that only focuses on the nodes that provide the most added coverage.

Each zone is a region, and therefore the population is not concentrated on one point. As a result, ambulances will often be able to cover only a fraction of a zone's total population. In order to find these fractions, we developed a model of population density for each zone by extrapolating from the provided average travel times between zones.

Travel time from a zone A to another zone B is not necessarily the same as the travel time in the opposite direction. This inconsistency could be due to a variety of factors, including differences in traffic, roads, and conditions. As a result, these two cases for each pair of zones must be handled separately.

\subsection{Zone-to-Zone Population Dynamics}
The population that an ambulance can cover in a second zone, B, from a first zone, A, will be referred to as zone-to-zone coverage. Zone-to-zone coverage also applies if A and B are the same zone, and represents the coverage of an ambulance in the zone it is stationed in.

A lack of spatial understanding of the county entails the use of a different type of population density. Rather than expressing population as a function of area or distance, we chose to express population density in terms of travel time from a reference point. This is analogous to plotting the number of people a vehicle is likely to meet at each time as it drives along a one-dimensional path. See Figure \ref{B(t)}.

\begin{figure}
\centering
\begin{subfigure}{.45\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{B(t).png}
  \caption{An example of a zone's population density as a function of travel time from another zone.}
  \label{B(t)}
\end{subfigure}%
\hfill
\begin{subfigure}{.45\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{A(t)B(t).png}
  \caption{The width of A and B are shown. $T_{AB} $ is the travel time between the centers (i.e. the provided average).}
  \label{A(t)B(t)}
\end{subfigure}
\caption{Examples of population density as a function of travel time}
\label{examples}
\end{figure}

\newpage

%TODO: We are trying to find zone-to-zone coverage...

\begin{description}
    \item[$\mathbf{Z_{AB}(t)}$] \hfill \\
    	The zone-to-zone coverage function of B from A
    \item[$\mathbf{A(t), B(t)}$] \hfill \\
    	Probability density functions with respect to travel time from the center of A
    \item[$\mathbf{v}$] \hfill \\
    	Required ambulance response time
    \item[$\mathbf{T_{AB}}$] \hfill \\
    	Travel time from A to B, given
    \item[$\mathbf{T_{BA}}$] \hfill \\
    	Travel time from B to A, given
    \item[$\mathbf{P_B}$] \hfill \\
    	Total population of B
    \item[$\mathbf{F_B(s)}$] \hfill \\
    	The probability curve for differences in travel time within B
   \item[$\mathbf{T_A}$] \hfill \\
    	Average travel time inside of A
    \item[$\mathbf{T_{A+}}$] \hfill \\
    	Average travel time in the direction of B to A inside of A
    \item[$\mathbf{T_{A-}}$] \hfill \\
    	Average travel time in the direction of A to B inside of A
   \item[$\mathbf{T_B}$] \hfill \\
    	Average travel time inside of B
    \item[$\mathbf{T_{B+}}$] \hfill \\
    	Average travel time in the direction of A to B inside of B
    \item[$\mathbf{T_{B-}}$] \hfill \\
    	Average travel time in the direction of B to A inside of B
    \item[$\mathbf{a, b}$] \hfill \\
    	Width of A and B respectively
    \item[$\mathbf{g}$] \hfill \\
    	Width of the gap between A and B
\end{description}

%TODO: Graphical representation of origin and setup
% Zones A and B are two zones separated by a gap. Each zone has a width and a population distribution

The function for zone-to-zone coverage in respect to travel time can be written as the product of the population of B with the percent of the population that is covered from A in less than $v$ minutes. The percent is the area under the probability curve, $B(t)$. As shown in Figure \ref{A(t)B(t)}, the bounds begin at $T_{AB} - \frac{b}{2}$ and end at $v$. If $v$ is less than $T_{AB} - \frac{b}{2}$, the coverage of B is 0.

$$Z_{AB}(t) = P_B \int^v_{T_{AB} - \frac{b}{2}} B(t) dt$$

$B(t)$ is a population density function with a zone-specific constant $b$, which is the width of zone B. Every zone has a different $b$ and, as a result, a different $B(t)$. In order to find this specific $B(t)$, we must obtain $b$. Until then, we cannot directly evaluate $B(t)$.

Using the average travel time within B that is provided to us, we can calculate the value for $b$. However, since we are provided with a general average travel time within each zone---which does not account for the direction of travel---we must extrapolate both the average travel time within B towards A and within B away from A.

The average travel time in the direction of A to B inside of B, $T_{B+}$, and the average travel time in the direction of B to A
inside of B, $T_{B-}$, have a total average travel time of $T_B$. We can also write the ratio of $T_{B+}$ and $T_{B-}$,
which is equivalent to the ratio of $T_{AB}$ and $T_{BA}$.
$$T_B = \frac{T_{B+} + T_{B-}}{2}$$
$$\frac{T_{B+}}{T_{B-}} = \frac{T_{AB}}{T_{BA}}$$

This allows us to solve for $T_{B+}$.<commit_msg>Edits<commit_after>\documentclass[notitlepage, 12pt]{article}
% package includes
% ---------------------

\usepackage{graphicx} % for include images

\usepackage{url}
% \usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{subcaption}
\usepackage{float}
\restylefloat{table}
\restylefloat{figure}
\usepackage{setspace}
% \usepackage{minted}
% \usemintedstyle{colorful}
\graphicspath{{./Pictures/}}

\pagestyle{fancy}
\lhead{Team 4552}
\chead{Problem A}
\rhead{\thepage}

\renewcommand{\headrulewidth}{.8pt}
%\renewcommand{\footrulewidth}{.8pt}

\title{\textbf{Emergency Service Location Optimization in a Multi-Zone County based on Population Distribution}}
\author{Team 4552}

\date{November 15, 2013}

\begin{document}
\maketitle

\tableofcontents

\section{Problem Restatement}
Given a county made up of six separate zones and average travel times between zones, create a model to optimize the placement of $n$ ambulances in order to maximize the number of civilians reached in an eight minute period. Consider the scenarios where $n = 3$, $n = 2$, and $n = 1$, respectively, and for each scenario, keep track of how many people are not being reached with each possible solution.

Then, consider a scenario in which a large scale disaster affects a single location (e.g. the September 11th attacks), and discuss how an Emergency Service Coordinator would cover the situation. Examine how a real-world city or county would prepare for such a disaster. Finally, write a two page memo detailing the model and its analysis for the Emergency Service Coordinator.


\section{Assumptions and Justifications}
\begin{description}
    \item[TODO(drew): Add these assumptions] \hfill \\
    	* Each zone is not a point, but rather a distribution. We experimented with...
        * Route frequency is correlated with population frequency (two random variables?)
    \item[1. Naming] \hfill \\
    	A county is another name for a county. ... TODO(drew)
        Travel...
        Travel times...
    \item[2. Zone to Zone Travel] \hfill \\
    	The travel times given are considered to be optimal routes from the center of one zone to
        the center of the another, regardless of any other zones that may lie in between.
    \item[3. Travel Inside Each Zone] \hfill \\
    	The travel times given for travel from any zone to itself is the average
        of all the travel times of the different routes within that zone.
    \item[4. Directional Travel Inside Each Zone] \hfill \\
    	The ratio between the time it takes inside a zone to travel toward a second zone,
        to the time it takes inside a zone to return from a second, is equal to the ratio
        between the travel time from the first zone to the second, and the travel time from the
        second to the first.
    \item[5. Ambulance Placement] \hfill \\
        Ambulances can only be placed in the very center of a zone. Because we do not know the
        spacial position of the zones relative to each other, we cannot consider the ambulances
        being closer to one zone or another.
    \item[6. Partial Coverage] \hfill \\
        Partial ambulance coverage of a zone will be treated as incomplete even coverage over the entire
        zone. Because ambulances of ideal placement are unlikely to overlap in partial coverage, we assume
        that multiple ambulances will cover different areas of the zones, thus evening out coverage.
        (If partial coverages from multiple ambulances sum to above the total population of a zone,
        we assume that zone is completely covered by the ambulances.)
\end{description}

\section{The Model}

\subsection{Model Approach}

Given that a county has $n$ zones, $k$ ambulances need to be placed to maximize the number of people who can be reached in eight minutes or fewer. This system can be represented as a graph of $n$ nodes and $n^2$ vertices. By analyzing all possible configurations, we can identify the ideal nodes to place the ambulances. This algorithm can be made more efficient---albeit less optimal---by employing a greedy heuristic that only focuses on the nodes that provide the most added coverage.

Each zone is a region, and therefore the population is not concentrated on one point. As a result, ambulances will often be able to cover only a fraction of a zone's total population. In order to find these fractions, we developed a model of population density for each zone by extrapolating from the provided average travel times between zones.

Travel time from a zone A to another zone B is not necessarily the same as the travel time in the opposite direction. This inconsistency could be due to a variety of factors, including differences in traffic, roads, and conditions. As a result, these two cases for each pair of zones must be handled separately.

\subsection{Zone-to-Zone Population Dynamics}

\begin{figure}
\centering
\begin{subfigure}{.45\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{B(t).png}
  \caption{An example of a zone's population density as a function of travel time from another zone.}
  \label{B(t)}
\end{subfigure}%
\hfill
\begin{subfigure}{.45\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{A(t)B(t).png}
  \caption{The width of A and B are shown. $T_{AB} $ is the travel time between the centers (i.e. the provided average).}
  \label{A(t)B(t)}
\end{subfigure}
\caption{Examples of population density as a function of travel time}
\label{examples}
\end{figure}

\newpage

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=3.5in]{6point.pdf}
\caption{A graph of the nodes (zones) and edges (travel times).}
\label{satan1}
\end{center}
\end{figure}

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=3.5in]{greedy6point.pdf}
\caption{A graph of the nodes (zones) with all edges (travel times) greater than 8 removed.}
\label{satan2}
\end{center}
\end{figure}

The population that an ambulance can cover in a second zone, B, from a first zone, A, will be referred to as zone-to-zone coverage. Zone-to-zone coverage also applies if A and B are the same zone, and represents the coverage of an ambulance in the zone it is stationed in.

A lack of spatial understanding of the county entails the use of a different type of population density. Rather than expressing population as a function of area or distance, we chose to express population density in terms of travel time from a reference point. This is analogous to plotting the number of people a vehicle is likely to meet at each time as it drives along a one-dimensional path. See Figure \ref{B(t)}.

Because we have more than four different zones, it is not possible for every zone to be adjacent with all the other zones. Therefore, the ambulance may travel through another zone C in an optimal route between zones A and B. However, we are only calculating the zone-to-zone population coverage of B from A, we can consider any time spent in zone C as a gap (i.e. containing a population density of 0). The zone-to-zone coverage of C from A is already accounted for in a separate calculation of A to C. 

The following calculations are used to find the coverage function for any pair of zones. Separate calculations must be done for every pair, as we as for both directions for each pair. We will be using the following variables, equations, and constants:

\begin{description}
    \item[$\mathbf{Z_{AB}(t)}$] \hfill \\
    	The zone-to-zone coverage function of B from A; to be solved
    \item[$\mathbf{B(t)}$] \hfill \\
    	Probability density function of zone B with respect to travel time (from the center of A)
   \item[$\mathbf{a, b}$] \hfill \\
    	Width of A and B respectively
    \item[$\mathbf{v}$] \hfill \\
    	Required ambulance response time; given (8 minutes)
    \item[$\mathbf{T_{AB}, T_{BA}}$] \hfill \\
    	Travel time from A to B and travel time from B to A; given
    \item[$\mathbf{P_B}$] \hfill \\
    	Total population of B; given
   \item[$\mathbf{T_B}$] \hfill \\
    	Average travel time inside of B; given
    \item[$\mathbf{T_{B+}, T_{B-}}$] \hfill \\
    	Average travel time inside of B in the direction of A to B\\Average travel time inside of B in the direction of B to A
    \item[$\mathbf{F_B(s)}$] \hfill \\
	  Frequency distribution of travel times from one random point in zone B to another point in B
\end{description}

The function for zone-to-zone coverage in respect to travel time can be written as the product of the population of B with the percent of the population that is covered from A in less than $v$ minutes. The percent is the area under the probability curve, $B(t)$. As shown in Figure \ref{A(t)B(t)}, the bounds begin at $T_{AB} - \frac{b}{2}$ and end at $v$. If $v$ is less than $T_{AB} - \frac{b}{2}$, the coverage of B is 0.

$$Z_{AB}(t) = P_B \int^v_{T_{AB} - \frac{b}{2}} B(t) dt$$

$B(t)$ is a population density function with a zone-specific constant $b$, which is the width of zone B. Every zone has a different $b$ and, as a result, a different $B(t)$. In order to find this specific $B(t)$, we must obtain $b$. Until then, we cannot directly evaluate $B(t)$.

Using the average travel time within B that is provided to us, we can calculate the value for $b$. However, since we are provided with a general average travel time within each zone---which does not account for the direction of travel---we must extrapolate both the average travel time within B towards A and within B away from A.

The average travel time in the direction of A to B inside of B, $T_{B+}$, and the average travel time in the direction of B to A
inside of B, $T_{B-}$, have a total average travel time of $T_B$. We can also write the ratio of $T_{B+}$ and $T_{B-}$,
which is equivalent to the ratio of $T_{AB}$ and $T_{BA}$.
$$T_B = \frac{T_{B+} + T_{B-}}{2}$$
$$\frac{T_{B+}}{T_{B-}} = \frac{T_{AB}}{T_{BA}}$$

This allows us to solve for $T_{B+}$.
{'fraction_non_alphanumeric': 0.0874120406567631, 'fraction_numerical': 0.005056033359395361, 'mean_word_length': 3.653407712830463, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '603098', 'n_tokens_mistral': 5430, 'n_tokens_neox': 5226, 'n_words': 2749}