{ "cells": [ { "cell_type": "markdown", "id": "d59e293a", "metadata": {}, "source": [ "# Siting First Aid Stations with LSCP on Toronto's University Campus\n", "\n", "*Authors:* [Timothy Ellersiek](https://github.com/TimMcCauley), [James Gaboardi](https://github.com/jGaboardi)\n", "\n", "This notebook implements the location set covering problem (LSCP) to site first aid stations for Toronto's University campus. LSCP determines locations such that as many demand points as possible are within the maximum service radius. By doing so, the number of locations required to cover all demand points is minimized. In contrast to the maximum covering location problem it does not require a maximum amount of locations as an input parameter. Hence, the use cases for LSCP are specific. One common scenario is finding suitable locations for hospitals in cities where the amount is governed by reachability preconditions to households in a certain amount of time. \n", "\n", "In this notebook demand is described as buildings within Toronto's University campus. Possible locations for the first aid stations are determined using [Overpass API](https://wiki.openstreetmap.org/wiki/Overpass_API) which fetches geometries directly from [OpenStreetMap.org](https://openstreetmap.org).\n", "\n", "The routing matrix is computed using [Open Source Routing Machine's demo server API](http://project-osrm.org).\n", "\n", "## Prerequisites\n", "\n", "To run this jupyter notebook locally, you will have to install the following additional libraries into your python environment.\n", "\n", "- [folium](https://python-visualization.github.io/folium)\n", "- [overpy](https://github.com/DinoTools/python-overpy)\n", "- [routing-py](https://github.com/gis-ops/routing-py)\n", "- [shapely](https://github.com/shapely/shapely)" ] }, { "cell_type": "code", "execution_count": 1, "id": "4a4648c9", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:18:56.099117Z", "start_time": "2022-12-29T02:18:56.053561Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:49:32.487851Z", "iopub.status.busy": "2023-12-10T18:49:32.487607Z", "iopub.status.idle": "2023-12-10T18:49:32.529797Z", "shell.execute_reply": "2023-12-10T18:49:32.529016Z", "shell.execute_reply.started": "2023-12-10T18:49:32.487827Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Last updated: 2023-12-10T13:49:32.513924-05:00\n", "\n", "Python implementation: CPython\n", "Python version : 3.11.6\n", "IPython version : 8.18.0\n", "\n", "Compiler : Clang 15.0.7 \n", "OS : Darwin\n", "Release : 23.1.0\n", "Machine : x86_64\n", "Processor : i386\n", "CPU cores : 8\n", "Architecture: 64bit\n", "\n" ] } ], "source": [ "%config InlineBackend.figure_format = \"retina\"\n", "%load_ext watermark\n", "%watermark" ] }, { "cell_type": "code", "execution_count": 2, "id": "367156e4", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:18:58.404656Z", "start_time": "2022-12-29T02:18:56.103546Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:49:32.532293Z", "iopub.status.busy": "2023-12-10T18:49:32.532052Z", "iopub.status.idle": "2023-12-10T18:49:34.670667Z", "shell.execute_reply": "2023-12-10T18:49:34.669612Z", "shell.execute_reply.started": "2023-12-10T18:49:32.532271Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Watermark: 2.4.3\n", "\n", "pulp : 2.7.0\n", "overpy : 0.6\n", "spopt : 0.5.1.dev59+g343ef27\n", "shapely : 2.0.2\n", "routingpy: 1.2.1\n", "json : 2.0.9\n", "folium : 0.15.0\n", "numpy : 1.26.2\n", "\n" ] } ], "source": [ "import folium\n", "import json\n", "import numpy\n", "import overpy\n", "import pulp\n", "import routingpy\n", "from routingpy import OSRM\n", "import shapely\n", "from shapely.geometry import shape, Point\n", "import spopt\n", "from spopt.locate import LSCP\n", "\n", "%watermark -w\n", "%watermark -iv" ] }, { "cell_type": "markdown", "id": "391b3990", "metadata": {}, "source": [ "--------------------------\n", "\n", "Create `overpy.Overpass()` instance in order to make queries" ] }, { "cell_type": "code", "execution_count": 3, "id": "9c1276e0", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:18:58.414149Z", "start_time": "2022-12-29T02:18:58.410492Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:49:34.672718Z", "iopub.status.busy": "2023-12-10T18:49:34.672026Z", "iopub.status.idle": "2023-12-10T18:49:34.675923Z", "shell.execute_reply": "2023-12-10T18:49:34.675337Z", "shell.execute_reply.started": "2023-12-10T18:49:34.672688Z" } }, "outputs": [], "source": [ "api = overpy.Overpass()" ] }, { "cell_type": "markdown", "id": "27413bd6", "metadata": { "ExecuteTime": { "end_time": "2022-10-19T13:06:22.437712Z", "start_time": "2022-10-19T13:06:18.752025Z" } }, "source": [ "First of all we want to fetch all buildings in the University of Toronto boundary" ] }, { "cell_type": "code", "execution_count": 4, "id": "f61a54fb", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:19:01.151129Z", "start_time": "2022-12-29T02:18:58.416996Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:49:34.677382Z", "iopub.status.busy": "2023-12-10T18:49:34.677096Z", "iopub.status.idle": "2023-12-10T18:49:35.949640Z", "shell.execute_reply": "2023-12-10T18:49:35.947881Z", "shell.execute_reply.started": "2023-12-10T18:49:34.677362Z" } }, "outputs": [], "source": [ "result = api.query(\n", " \"\"\"\n", " [out:json];\n", " \n", " area[name=\"Toronto\"]->.b;\n", " way(area.b)[name=\"University of Toronto\"];\n", " map_to_area -> .a;\n", " \n", " way[building=\"university\"](area.a);\n", " out center;\n", " \"\"\"\n", ")" ] }, { "cell_type": "markdown", "id": "582062c0", "metadata": {}, "source": [ "Create a `folium.Map()` instance to visualize the data" ] }, { "cell_type": "code", "execution_count": 5, "id": "9364e615", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:19:01.169561Z", "start_time": "2022-12-29T02:19:01.154897Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:49:35.952758Z", "iopub.status.busy": "2023-12-10T18:49:35.952137Z", "iopub.status.idle": "2023-12-10T18:49:35.967503Z", "shell.execute_reply": "2023-12-10T18:49:35.966475Z", "shell.execute_reply.started": "2023-12-10T18:49:35.952714Z" } }, "outputs": [], "source": [ "m = folium.Map(\n", " location=[43.6624674, -79.3988052], tiles=\"cartodbpositron\", zoom_start=15\n", ")" ] }, { "cell_type": "markdown", "id": "7561203b", "metadata": {}, "source": [ "Let's add our results to the map!" ] }, { "cell_type": "code", "execution_count": 6, "id": "20c9ff1c", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:19:01.178438Z", "start_time": "2022-12-29T02:19:01.172990Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:49:35.969460Z", "iopub.status.busy": "2023-12-10T18:49:35.968891Z", "iopub.status.idle": "2023-12-10T18:49:35.975396Z", "shell.execute_reply": "2023-12-10T18:49:35.974564Z", "shell.execute_reply.started": "2023-12-10T18:49:35.969408Z" } }, "outputs": [], "source": [ "def get_centroid(pnt_info, xy=True):\n", " \"\"\"Extract centroid from location information.\"\"\"\n", " if isinstance(pnt_info, overpy.Way):\n", " x, y = pnt_info.center_lon, pnt_info.center_lat\n", " if not xy:\n", " x, y = y, x\n", " else:\n", " x, y = pnt_info[\"center\"][1], pnt_info[\"center\"][0]\n", " return [x, y]" ] }, { "cell_type": "code", "execution_count": 7, "id": "16f5e4a8", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:19:01.184711Z", "start_time": "2022-12-29T02:19:01.181407Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:49:35.979398Z", "iopub.status.busy": "2023-12-10T18:49:35.979088Z", "iopub.status.idle": "2023-12-10T18:49:35.982977Z", "shell.execute_reply": "2023-12-10T18:49:35.982062Z", "shell.execute_reply.started": "2023-12-10T18:49:35.979374Z" } }, "outputs": [], "source": [ "get_tag = lambda w: w.tags.get(\"name\", \"n/a\")" ] }, { "cell_type": "code", "execution_count": 8, "id": "0de53198", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:19:01.296346Z", "start_time": "2022-12-29T02:19:01.187131Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:49:35.984647Z", "iopub.status.busy": "2023-12-10T18:49:35.984177Z", "iopub.status.idle": "2023-12-10T18:49:36.098337Z", "shell.execute_reply": "2023-12-10T18:49:36.097586Z", "shell.execute_reply.started": "2023-12-10T18:49:35.984623Z" } }, "outputs": [ { "data": { "text/html": [ "