{ "cells": [ { "cell_type": "markdown", "id": "d59e293a", "metadata": {}, "source": [ "# Siting Restaurants with MCLP in San Francisco\n", "\n", "*Authors:* [Timothy Ellersiek](https://github.com/TimMcCauley), [James Gaboardi](https://github.com/jGaboardi)\n", "\n", "This notebook implements the maximize covering location problem (MCLP) to site 2 of 10 possible locations for restaurants in San Francisco's Mission District & Bernal Heights. The objective is to maximize the demand of randomly created households able to reach the restaurants within 3 minutes afoot. \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", "- [routing-py](https://github.com/gis-ops/routing-py)\n", "- [shapely](https://github.com/shapely/shapely)" ] }, { "cell_type": "code", "execution_count": 1, "id": "b56e0345", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:27.207756Z", "start_time": "2022-12-29T02:20:27.167577Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:07.114730Z", "iopub.status.busy": "2023-12-10T18:58:07.114271Z", "iopub.status.idle": "2023-12-10T18:58:07.155592Z", "shell.execute_reply": "2023-12-10T18:58:07.154865Z", "shell.execute_reply.started": "2023-12-10T18:58:07.114687Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Last updated: 2023-12-10T13:58:07.138829-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": "0565cc82", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:29.198743Z", "start_time": "2022-12-29T02:20:27.210914Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:07.158130Z", "iopub.status.busy": "2023-12-10T18:58:07.157843Z", "iopub.status.idle": "2023-12-10T18:58:09.283956Z", "shell.execute_reply": "2023-12-10T18:58:09.282997Z", "shell.execute_reply.started": "2023-12-10T18:58:07.158108Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Watermark: 2.4.3\n", "\n", "pulp : 2.7.0\n", "spopt : 0.5.1.dev59+g343ef27\n", "shapely : 2.0.2\n", "routingpy: 1.2.1\n", "folium : 0.15.0\n", "json : 2.0.9\n", "geopandas: 0.14.1\n", "numpy : 1.26.2\n", "\n" ] } ], "source": [ "import geopandas\n", "import folium\n", "import json\n", "import numpy\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 MCLP, simulated_geo_points \n", "\n", "%watermark -w\n", "%watermark -iv" ] }, { "cell_type": "markdown", "id": "9b96fba3", "metadata": {}, "source": [ "-------------------------------\n", "\n", "San Francisco's Mission District and Bernal Heights merged polygon" ] }, { "cell_type": "code", "execution_count": 3, "id": "f07586c6", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:29.218234Z", "start_time": "2022-12-29T02:20:29.203551Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:09.285760Z", "iopub.status.busy": "2023-12-10T18:58:09.285126Z", "iopub.status.idle": "2023-12-10T18:58:09.300696Z", "shell.execute_reply": "2023-12-10T18:58:09.300121Z", "shell.execute_reply.started": "2023-12-10T18:58:09.285729Z" } }, "outputs": [ { "data": { "text/plain": [ "'{\"type\": \"Polygon\", \"coordinates\": [[[-122.405115, 37.764635], [-122.405212, 37.763469], [-122.405832, 37.762199], [-122.405859, 37.761815], [-122.40604, 37.761865], [-122.406365, 37.761199], [-122.40645, 37.760114], [-122.406167, 37.759315], [-122.406015, 37.759409], [-122.405604, 37.758851], [-122.40405, 37.757619], [-122.403428, 37.756871], [-122.403585, 37.756818], [-122.403328, 37.756082], [-122.40315, 37.754488], [-122.403524, 37.754463], [-122.403437, 37.753199], [-122.403364, 37.752366], [-122.403022, 37.752336], [-122.403052, 37.752048], [-122.405091, 37.745281], [-122.405614, 37.7442], [-122.405493, 37.744084], [-122.404865, 37.744385], [-122.404524, 37.744285], [-122.406652, 37.741241], [-122.406936, 37.740554], [-122.407045, 37.739587], [-122.408136, 37.73964], [-122.408009, 37.737734], [-122.408218, 37.73765], [-122.408284, 37.736846], [-122.408613, 37.736074], [-122.409287, 37.735258], [-122.410052, 37.734675], [-122.411978, 37.733732], [-122.412695, 37.733197], [-122.414554, 37.732371], [-122.416255, 37.732034], [-122.419881, 37.732016], [-122.423718, 37.73155], [-122.425944, 37.731698], [-122.425256, 37.732125], [-122.422274, 37.732383], [-122.421889, 37.732533], [-122.421787, 37.732774], [-122.422472, 37.733967], [-122.422901, 37.734388], [-122.422243, 37.734846], [-122.422133, 37.735162], [-122.426983, 37.735455], [-122.427849, 37.734718], [-122.428578, 37.735082], [-122.42801, 37.735441], [-122.428454, 37.735882], [-122.42551, 37.737774], [-122.42452, 37.739868], [-122.42427, 37.739867], [-122.424394, 37.740405], [-122.424168, 37.740805], [-122.426453, 37.764634], [-122.421885, 37.764908], [-122.42173, 37.763304], [-122.421031, 37.76335], [-122.421248, 37.764947], [-122.407553, 37.765798], [-122.407431, 37.764497], [-122.405115, 37.764635]]]}'" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "SF_MISSION_BERNAL = {\n", " \"type\": \"Polygon\",\n", " \"coordinates\": [\n", " [\n", " [-122.405115, 37.764635],\n", " [-122.405212, 37.763469],\n", " [-122.405832, 37.762199],\n", " [-122.405859, 37.761815],\n", " [-122.40604, 37.761865],\n", " [-122.406365, 37.761199],\n", " [-122.40645, 37.760114],\n", " [-122.406167, 37.759315],\n", " [-122.406015, 37.759409],\n", " [-122.405604, 37.758851],\n", " [-122.40405, 37.757619],\n", " [-122.403428, 37.756871],\n", " [-122.403585, 37.756818],\n", " [-122.403328, 37.756082],\n", " [-122.40315, 37.754488],\n", " [-122.403524, 37.754463],\n", " [-122.403437, 37.753199],\n", " [-122.403364, 37.752366],\n", " [-122.403022, 37.752336],\n", " [-122.403052, 37.752048],\n", " [-122.405091, 37.745281],\n", " [-122.405614, 37.7442],\n", " [-122.405493, 37.744084],\n", " [-122.404865, 37.744385],\n", " [-122.404524, 37.744285],\n", " [-122.406652, 37.741241],\n", " [-122.406936, 37.740554],\n", " [-122.407045, 37.739587],\n", " [-122.408136, 37.73964],\n", " [-122.408009, 37.737734],\n", " [-122.408218, 37.73765],\n", " [-122.408284, 37.736846],\n", " [-122.408613, 37.736074],\n", " [-122.409287, 37.735258],\n", " [-122.410052, 37.734675],\n", " [-122.411978, 37.733732],\n", " [-122.412695, 37.733197],\n", " [-122.414554, 37.732371],\n", " [-122.416255, 37.732034],\n", " [-122.419881, 37.732016],\n", " [-122.423718, 37.73155],\n", " [-122.425944, 37.731698],\n", " [-122.425256, 37.732125],\n", " [-122.422274, 37.732383],\n", " [-122.421889, 37.732533],\n", " [-122.421787, 37.732774],\n", " [-122.422472, 37.733967],\n", " [-122.422901, 37.734388],\n", " [-122.422243, 37.734846],\n", " [-122.422133, 37.735162],\n", " [-122.426983, 37.735455],\n", " [-122.427849, 37.734718],\n", " [-122.428578, 37.735082],\n", " [-122.42801, 37.735441],\n", " [-122.428454, 37.735882],\n", " [-122.42551, 37.737774],\n", " [-122.42452, 37.739868],\n", " [-122.42427, 37.739867],\n", " [-122.424394, 37.740405],\n", " [-122.424168, 37.740805],\n", " [-122.426453, 37.764634],\n", " [-122.421885, 37.764908],\n", " [-122.42173, 37.763304],\n", " [-122.421031, 37.76335],\n", " [-122.421248, 37.764947],\n", " [-122.407553, 37.765798],\n", " [-122.407431, 37.764497],\n", " [-122.405115, 37.764635],\n", " ]\n", " ],\n", "}\n", "\n", "SF_MISSION_BERNAL = str(SF_MISSION_BERNAL).replace(\"'\", '\"')\n", "SF_MISSION_BERNAL" ] }, { "cell_type": "markdown", "id": "d4cdc9b7", "metadata": {}, "source": [ "Convert `SF_MISSION_BERNAL` to a `shapely.Polygon` then a `geopandas.GeoDataFrame`" ] }, { "cell_type": "code", "execution_count": 4, "id": "9f6b3238", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:29.226387Z", "start_time": "2022-12-29T02:20:29.220792Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:09.301636Z", "iopub.status.busy": "2023-12-10T18:58:09.301446Z", "iopub.status.idle": "2023-12-10T18:58:09.307769Z", "shell.execute_reply": "2023-12-10T18:58:09.307213Z", "shell.execute_reply.started": "2023-12-10T18:58:09.301619Z" } }, "outputs": [ { "data": { "image/svg+xml": [ "" ], "text/plain": [ "" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "misson_bernal = shape(json.loads(SF_MISSION_BERNAL))\n", "misson_bernal" ] }, { "cell_type": "code", "execution_count": 5, "id": "6dae6ff8", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:29.242296Z", "start_time": "2022-12-29T02:20:29.229147Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:09.308605Z", "iopub.status.busy": "2023-12-10T18:58:09.308427Z", "iopub.status.idle": "2023-12-10T18:58:09.321184Z", "shell.execute_reply": "2023-12-10T18:58:09.320570Z", "shell.execute_reply.started": "2023-12-10T18:58:09.308588Z" } }, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
geometry
0POLYGON ((-122.40511 37.76463, -122.40521 37.7...
\n", "
" ], "text/plain": [ " geometry\n", "0 POLYGON ((-122.40511 37.76463, -122.40521 37.7..." ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "misson_bernal = geopandas.GeoDataFrame(geometry=[misson_bernal])\n", "misson_bernal" ] }, { "cell_type": "markdown", "id": "0fa9bcca", "metadata": {}, "source": [ "Generate 200 artificial households within `misson_bernal`" ] }, { "cell_type": "code", "execution_count": 6, "id": "ff17dc8e", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:29.266809Z", "start_time": "2022-12-29T02:20:29.244591Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:09.322778Z", "iopub.status.busy": "2023-12-10T18:58:09.322490Z", "iopub.status.idle": "2023-12-10T18:58:09.342555Z", "shell.execute_reply": "2023-12-10T18:58:09.342005Z", "shell.execute_reply.started": "2023-12-10T18:58:09.322755Z" } }, "outputs": [ { "data": { "text/plain": [ "[[-122.41455252209364, 37.75604380541952],\n", " [-122.41317377916111, 37.75021115925127],\n", " [-122.4177510779481, 37.7536705815843],\n", " [-122.41739502122897, 37.76209144173078],\n", " [-122.40834467492677, 37.74966359321169]]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "NUM_HOUSEHOLDS = 200\n", "households = simulated_geo_points(misson_bernal, needed=NUM_HOUSEHOLDS, seed=0)\n", "households = households.geometry.map(lambda pt: [pt.x, pt.y]).to_list()\n", "households[:5]" ] }, { "cell_type": "markdown", "id": "2aaf739e", "metadata": {}, "source": [ "## Adding a Leaflet Map for Visualisation via Folium\n", "\n", "In the following we are using [folium](https://python-visualization.github.io/folium/) to visualize the data on the map. After creating the base map, we will load the merged polygon of Mission District and Bernal Heights boundary onto it and finally the artificial househoulds we created earlier. In the subsequent step we will add some fixed positions for our possible restaurants which are depicted as red circles." ] }, { "cell_type": "code", "execution_count": 7, "id": "9cce5603", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:29.443789Z", "start_time": "2022-12-29T02:20:29.270011Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:09.345378Z", "iopub.status.busy": "2023-12-10T18:58:09.345124Z", "iopub.status.idle": "2023-12-10T18:58:09.529832Z", "shell.execute_reply": "2023-12-10T18:58:09.529161Z", "shell.execute_reply.started": "2023-12-10T18:58:09.345361Z" }, "scrolled": true }, "outputs": [ { "data": { "text/html": [ "
Make this Notebook Trusted to load map: File -> Trust Notebook
" ], "text/plain": [ "" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = folium.Map(\n", " location=[37.748273, -122.410558], tiles=\"cartodbpositron\", zoom_start=15\n", ")\n", "\n", "folium.GeoJson(\n", " data=SF_MISSION_BERNAL,\n", " name=\"Mission District & Bernal Heights\",\n", " style_function=lambda x: {\"color\": \"darksalmon\", \"fillColor\": \"darksalmon\"},\n", ").add_to(m)\n", "\n", "households_fg = folium.FeatureGroup(\"Households\").add_to(m)\n", "for coord in households:\n", " folium.CircleMarker(\n", " location=[coord[1], coord[0]],\n", " radius=3,\n", " fill=True,\n", " fill_opacity=1,\n", " popup=folium.Popup(\"Random Household\", show=False),\n", " color=\"cornflowerblue\",\n", " ).add_to(households_fg)\n", "m" ] }, { "cell_type": "markdown", "id": "0e9664e1", "metadata": {}, "source": [ "Define 10 restaurant locations" ] }, { "cell_type": "code", "execution_count": 8, "id": "f5020f6b", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:29.449710Z", "start_time": "2022-12-29T02:20:29.445421Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:09.530937Z", "iopub.status.busy": "2023-12-10T18:58:09.530600Z", "iopub.status.idle": "2023-12-10T18:58:09.534720Z", "shell.execute_reply": "2023-12-10T18:58:09.533870Z", "shell.execute_reply.started": "2023-12-10T18:58:09.530918Z" } }, "outputs": [], "source": [ "restaurants = [\n", " [-122.41957, 37.76032],\n", " [-122.40789, 37.75781],\n", " [-122.41525, 37.74622],\n", " [-122.42265, 37.75189],\n", " [-122.41890, 37.74224],\n", " [-122.41365, 37.73596],\n", " [-122.40846, 37.76454],\n", " [-122.41489, 37.75905],\n", " [-122.42365, 37.74082],\n", " [-122.40667, 37.74899],\n", "]\n", "n_rests = len(restaurants)" ] }, { "cell_type": "markdown", "id": "250619f2", "metadata": {}, "source": [ "Add them to the map" ] }, { "cell_type": "code", "execution_count": 9, "id": "da9e9d63", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:29.628221Z", "start_time": "2022-12-29T02:20:29.452355Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:09.536281Z", "iopub.status.busy": "2023-12-10T18:58:09.535873Z", "iopub.status.idle": "2023-12-10T18:58:09.715056Z", "shell.execute_reply": "2023-12-10T18:58:09.714556Z", "shell.execute_reply.started": "2023-12-10T18:58:09.536248Z" } }, "outputs": [ { "data": { "text/html": [ "
Make this Notebook Trusted to load map: File -> Trust Notebook
" ], "text/plain": [ "" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "restaurants_fg = folium.FeatureGroup(\"Restaurants\").add_to(m)\n", "for i, coord in enumerate(restaurants):\n", " folium.CircleMarker(\n", " location=[coord[1], coord[0]],\n", " radius=5,\n", " fill=True,\n", " fill_opacity=1,\n", " popup=folium.Popup(f\"Potential Restaurant ({i})\", show=False),\n", " color=\"crimson\",\n", " ).add_to(restaurants_fg)\n", "m" ] }, { "cell_type": "markdown", "id": "4fc0985b", "metadata": {}, "source": [ "## Computing the Distance (Routing) Matrix\n", "\n", "Given our 10 restaurants and 200 artificial households we want to compute our distance matrix. Instead of using simple euclidean distance we can make use of proper routes following roads which will yield more realistic travel times. The [routing-py library](https://github.com/gis-ops/routing-py) helps us achieve this which features the ability to use different open source frameworks such as OSRM or Valhalla as well as 3rd party API's such as Google Maps or HERE." ] }, { "cell_type": "code", "execution_count": 10, "id": "0063b6c1", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:29.633481Z", "start_time": "2022-12-29T02:20:29.630307Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:09.716323Z", "iopub.status.busy": "2023-12-10T18:58:09.716066Z", "iopub.status.idle": "2023-12-10T18:58:09.730749Z", "shell.execute_reply": "2023-12-10T18:58:09.724814Z", "shell.execute_reply.started": "2023-12-10T18:58:09.716302Z" } }, "outputs": [], "source": [ "all_locations = households + restaurants\n", "source_indices = [i for i in range(NUM_HOUSEHOLDS)]\n", "target_indices = [i for i in range(NUM_HOUSEHOLDS, len(all_locations))]" ] }, { "cell_type": "code", "execution_count": 11, "id": "7f13139e", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:30.369316Z", "start_time": "2022-12-29T02:20:29.640338Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:09.734069Z", "iopub.status.busy": "2023-12-10T18:58:09.733404Z", "iopub.status.idle": "2023-12-10T18:58:10.433768Z", "shell.execute_reply": "2023-12-10T18:58:10.433315Z", "shell.execute_reply.started": "2023-12-10T18:58:09.734030Z" }, "scrolled": true }, "outputs": [], "source": [ "client = OSRM(base_url=\"https://router.project-osrm.org\")\n", "osrm_routing_matrix = client.matrix(\n", " dry_run=False,\n", " locations=all_locations,\n", " sources=source_indices,\n", " destinations=target_indices,\n", " profile=\"pedestrian\",\n", ")\n", "cost_matrix = numpy.array(osrm_routing_matrix.durations)" ] }, { "cell_type": "markdown", "id": "a69b120b", "metadata": {}, "source": [ "## Solving the MCLP\n", "\n", "Last but not least we want to run the solver. We choose the `pulp.COIN_CMD` solver and set a maximium coverage to 3 minutes. Our weights of the households we set to 1 and treat them equally. Finally we loop over the solution and add the sited restaurants and the corresponding allocated households to the map with different radiuses. " ] }, { "cell_type": "code", "execution_count": 12, "id": "456380f7", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:30.378157Z", "start_time": "2022-12-29T02:20:30.372350Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:10.434664Z", "iopub.status.busy": "2023-12-10T18:58:10.434505Z", "iopub.status.idle": "2023-12-10T18:58:10.439521Z", "shell.execute_reply": "2023-12-10T18:58:10.438753Z", "shell.execute_reply.started": "2023-12-10T18:58:10.434649Z" } }, "outputs": [], "source": [ "# maximum acceptable service duration, 3\n", "SERVICE_RADIUS = 180\n", "\n", "# weights, all set to 1 for demos sake\n", "ai = numpy.ones((1, NUM_HOUSEHOLDS), dtype=int)\n", "\n", "# the number of restaurants to site\n", "P_FACILITIES = 2\n", "\n", "# set the solver (for available solvers run ``pulp.listSolvers(onlyAvailable=True)``)\n", "solver = pulp.COIN_CMD(msg=False)" ] }, { "cell_type": "code", "execution_count": 13, "id": "d4c053b7", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:30.462272Z", "start_time": "2022-12-29T02:20:30.381862Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:10.440400Z", "iopub.status.busy": "2023-12-10T18:58:10.440224Z", "iopub.status.idle": "2023-12-10T18:58:10.523174Z", "shell.execute_reply": "2023-12-10T18:58:10.522073Z", "shell.execute_reply.started": "2023-12-10T18:58:10.440386Z" } }, "outputs": [], "source": [ "mclp = MCLP.from_cost_matrix(cost_matrix, ai, SERVICE_RADIUS, p_facilities=P_FACILITIES)\n", "mclp = mclp.solve(solver)" ] }, { "cell_type": "markdown", "id": "6ee0f18f", "metadata": {}, "source": [ "How did the model perform?" ] }, { "cell_type": "code", "execution_count": 14, "id": "2b377c3b", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:30.470402Z", "start_time": "2022-12-29T02:20:30.466167Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:10.526071Z", "iopub.status.busy": "2023-12-10T18:58:10.525215Z", "iopub.status.idle": "2023-12-10T18:58:10.531454Z", "shell.execute_reply": "2023-12-10T18:58:10.530437Z", "shell.execute_reply.started": "2023-12-10T18:58:10.526027Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Of the 200 households, 154 have access to at least 1 restaurant within a 3-minute walk along the street network when siting 2 restaurants. This accounts for 77.0% coverage.\n" ] } ], "source": [ "obj_val = int(mclp.problem.objective.value())\n", "minutes = int(SERVICE_RADIUS/60)\n", "obj_perc = mclp.perc_cov\n", "print(\n", " f\"Of the {NUM_HOUSEHOLDS} households, {obj_val} have access to at least 1 \"\n", " f\"restaurant within a {minutes}-minute walk along the street network when \"\n", " f\"siting {P_FACILITIES} restaurants. This accounts for {obj_perc}% coverage.\"\n", ")" ] }, { "cell_type": "markdown", "id": "e993fc21", "metadata": {}, "source": [ "Add the results to the map" ] }, { "cell_type": "code", "execution_count": 15, "id": "5323e10c", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:30.804469Z", "start_time": "2022-12-29T02:20:30.474181Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:10.532835Z", "iopub.status.busy": "2023-12-10T18:58:10.532502Z", "iopub.status.idle": "2023-12-10T18:58:10.866222Z", "shell.execute_reply": "2023-12-10T18:58:10.865617Z", "shell.execute_reply.started": "2023-12-10T18:58:10.532798Z" } }, "outputs": [ { "data": { "text/html": [ "
Make this Notebook Trusted to load map: File -> Trust Notebook
" ], "text/plain": [ "" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "sited_restaurants_fg = folium.FeatureGroup(\"Sited Restaurants\").add_to(m)\n", "allocated_households_demand_fg = folium.FeatureGroup(\"Allocated Households\").add_to(m)\n", "solution = {}\n", "colors = [\n", " \"darkcyan\",\n", " \"saddlebrown\",\n", " \"lavender\",\n", " \"lightskyblue\",\n", " \"mediumseagreen\",\n", " \"coral\",\n", " \"blueviolet\",\n", " \"darkgoldenrod\",\n", " \"mediumvioletred\",\n", " \"mediumorchid\"\n", "]\n", "for i in range(n_rests):\n", " if mclp.fac2cli[i]:\n", " folium.CircleMarker(\n", " location=[restaurants[i][1], restaurants[i][0]],\n", " radius=30,\n", " fill=True,\n", " popup=folium.Popup(f\"Sited Restaurant ({i})\", show=True),\n", " color=colors[i],\n", " ).add_to(sited_restaurants_fg)\n", " solution[i] = []\n", " for j in mclp.fac2cli[i]:\n", " solution[i].append(households[j])\n", " folium.CircleMarker(\n", " location=[households[j][1], households[j][0]],\n", " radius=10,\n", " fill=True,\n", " popup=\"Household\",\n", " color=colors[i],\n", " ).add_to(allocated_households_demand_fg)\n", "folium.LayerControl().add_to(m)\n", "m" ] }, { "cell_type": "markdown", "id": "d463f868", "metadata": {}, "source": [ "Inspect the solution set" ] }, { "cell_type": "code", "execution_count": 16, "id": "25869602", "metadata": { "ExecuteTime": { "end_time": "2022-12-29T02:20:30.816179Z", "start_time": "2022-12-29T02:20:30.806663Z" }, "execution": { "iopub.execute_input": "2023-12-10T18:58:10.867723Z", "iopub.status.busy": "2023-12-10T18:58:10.867310Z", "iopub.status.idle": "2023-12-10T18:58:10.875153Z", "shell.execute_reply": "2023-12-10T18:58:10.874408Z", "shell.execute_reply.started": "2023-12-10T18:58:10.867701Z" } }, "outputs": [ { "data": { "text/plain": [ "{4: [[-122.41524164428937, 37.74575134212079],\n", " [-122.41939041609294, 37.746517470353716],\n", " [-122.4232014632692, 37.735965467842085],\n", " [-122.42051691306378, 37.74400636648324],\n", " [-122.4140060513352, 37.74657122463306],\n", " [-122.42323994562125, 37.737074528368524],\n", " [-122.41188716363442, 37.74022473080378],\n", " [-122.4166609618889, 37.73992108767487],\n", " [-122.42451537332036, 37.735330127834594],\n", " [-122.42355414116491, 37.74417809964479],\n", " [-122.4213505852644, 37.735666491828425],\n", " [-122.42100984111212, 37.73561618691874],\n", " [-122.42045162186741, 37.74573767903614],\n", " [-122.4140979332363, 37.74063905928569],\n", " [-122.41520587274562, 37.73476727461245],\n", " [-122.42118193788865, 37.73782393776602],\n", " [-122.41125572058564, 37.740797233065884],\n", " [-122.41070210763999, 37.74173662069288],\n", " [-122.41170660507584, 37.74148457789174],\n", " [-122.41401197674212, 37.751786210327225],\n", " [-122.41382634618964, 37.73969735334643],\n", " [-122.40991900141367, 37.74223349220518],\n", " [-122.41840106253402, 37.7387367287149],\n", " [-122.42276619176752, 37.74026120078767],\n", " [-122.41892417399505, 37.73770106674906],\n", " [-122.41163237344158, 37.740568264758494],\n", " [-122.42039964169358, 37.744682871447594],\n", " [-122.41100854960864, 37.738930706925785],\n", " [-122.42208826738184, 37.73885550860088],\n", " [-122.42327589475202, 37.7460946279338],\n", " [-122.41901571198258, 37.74742653113364],\n", " [-122.41535585953757, 37.73607306850611],\n", " [-122.41025793398745, 37.74511425270174],\n", " [-122.41412809295414, 37.73782696783066],\n", " [-122.41970410021572, 37.736623528205754],\n", " [-122.41915845180576, 37.73623856050469],\n", " [-122.41551073208204, 37.73923240960833],\n", " [-122.42006414249477, 37.73432756040431],\n", " [-122.41817054462335, 37.73950355490107],\n", " [-122.41140314623527, 37.73995333620304],\n", " [-122.42166950005372, 37.73605302291012],\n", " [-122.42187930857803, 37.74717190213178],\n", " [-122.42133239235675, 37.74456173838566],\n", " [-122.42194819694559, 37.74435235234791],\n", " [-122.41356130372293, 37.740893604514234],\n", " [-122.4191004858632, 37.7382987149878],\n", " [-122.41531864893646, 37.742057632289225],\n", " [-122.42148375412637, 37.73596321664609],\n", " [-122.41468049513983, 37.747198302368524],\n", " [-122.41007117187876, 37.745215819217684],\n", " [-122.41069845878158, 37.742773768312524],\n", " [-122.42244404189351, 37.737048133592474],\n", " [-122.41949619370845, 37.743766497582506],\n", " [-122.42022883226554, 37.73952102093955],\n", " [-122.42292601164742, 37.740221292002616],\n", " [-122.41812421353865, 37.73713086318324],\n", " [-122.41225380452875, 37.7483419775086],\n", " [-122.41535766353438, 37.746074199675945],\n", " [-122.41440239836186, 37.741380940454206],\n", " [-122.4105207768065, 37.74575801806093],\n", " [-122.42263298457125, 37.74348609136638],\n", " [-122.42220382143077, 37.7351770739924],\n", " [-122.42161560269948, 37.744531940576856],\n", " [-122.42250059810968, 37.73743562493618],\n", " [-122.41709590262614, 37.74197743401586],\n", " [-122.41446908756086, 37.74085356398497],\n", " [-122.41693866931666, 37.745307885159676],\n", " [-122.42222954548635, 37.74887491191325],\n", " [-122.42064590761126, 37.74432569801819],\n", " [-122.42209591165009, 37.74682924903755],\n", " [-122.42334097025606, 37.743252477037885],\n", " [-122.41468376365637, 37.741231897645584],\n", " [-122.41267626306029, 37.74110751909093],\n", " [-122.4232176302866, 37.735512604334986]],\n", " 7: [[-122.41455252209364, 37.75604380541952],\n", " [-122.41317377916111, 37.75021115925127],\n", " [-122.4177510779481, 37.7536705815843],\n", " [-122.41739502122897, 37.76209144173078],\n", " [-122.40834467492677, 37.74966359321169],\n", " [-122.41406105319669, 37.76324983366825],\n", " [-122.40869142607274, 37.76134617605315],\n", " [-122.41678443341827, 37.75828156322945],\n", " [-122.41692062210988, 37.75101772588085],\n", " [-122.4129352817101, 37.75267875552496],\n", " [-122.41153810982007, 37.75451800575868],\n", " [-122.4140060513352, 37.74657122463306],\n", " [-122.41385911135957, 37.76337653617459],\n", " [-122.42043665185116, 37.754407470692996],\n", " [-122.40978938157065, 37.76450303329318],\n", " [-122.41344777640442, 37.751148483269525],\n", " [-122.42287692579625, 37.76417974814643],\n", " [-122.41715126382405, 37.760537804214785],\n", " [-122.41004340162493, 37.74871935743222],\n", " [-122.41774596037905, 37.75231775479745],\n", " [-122.41401197674212, 37.751786210327225],\n", " [-122.4139005439404, 37.75392082167846],\n", " [-122.41743903596992, 37.76209659106257],\n", " [-122.40797490641594, 37.755656776209086],\n", " [-122.42601660166785, 37.76304044055552],\n", " [-122.42475869912616, 37.76128158121274],\n", " [-122.4254136565183, 37.76059258583783],\n", " [-122.40794615669083, 37.75104056209607],\n", " [-122.41075451027352, 37.747082929796356],\n", " [-122.41012514709995, 37.7612218618984],\n", " [-122.41975219244812, 37.763334928138605],\n", " [-122.4148893680859, 37.75175323687019],\n", " [-122.42381965154172, 37.76389286561216],\n", " [-122.42060974443976, 37.75539837180495],\n", " [-122.41486518168091, 37.76225919844404],\n", " [-122.41354296784603, 37.76001174749493],\n", " [-122.41250374000519, 37.76143653964776],\n", " [-122.42383388780732, 37.76418120866797],\n", " [-122.41948996087152, 37.76375791326102],\n", " [-122.40901934781371, 37.757190231652636],\n", " [-122.41446616923866, 37.7515671364096],\n", " [-122.41145761273533, 37.75843991693097],\n", " [-122.41993600982686, 37.764481854652736],\n", " [-122.4226566332339, 37.76406227103009],\n", " [-122.41246627252544, 37.76149261428097],\n", " [-122.42108957360912, 37.76062461888235],\n", " [-122.41586666626333, 37.75345065474162],\n", " [-122.42607748635427, 37.761078335088655],\n", " [-122.41783069338953, 37.750638766365256],\n", " [-122.40658575420164, 37.756449811909334],\n", " [-122.41111606218875, 37.75537378026224],\n", " [-122.42394850602186, 37.75855610670547],\n", " [-122.40867766046134, 37.75817465417819],\n", " [-122.41381831239967, 37.76440867305686],\n", " [-122.41757863525594, 37.74901705715819],\n", " [-122.41487544794536, 37.75488633070316],\n", " [-122.41854278041016, 37.764304983194315],\n", " [-122.42379568293042, 37.76250964248838],\n", " [-122.41468049513983, 37.747198302368524],\n", " [-122.40923776500622, 37.75333381902695],\n", " [-122.40822541947725, 37.76439953782074],\n", " [-122.41686980413054, 37.751790025694],\n", " [-122.40760247546336, 37.762676079668196],\n", " [-122.42196706998658, 37.760627863987054],\n", " [-122.41832341219747, 37.76337637245978],\n", " [-122.42603224084327, 37.763924686918585],\n", " [-122.41225380452875, 37.7483419775086],\n", " [-122.42240830574532, 37.75423945656585],\n", " [-122.42228960924437, 37.75435434305817],\n", " [-122.41936389765623, 37.759929842009704],\n", " [-122.40775071665323, 37.76530111041392],\n", " [-122.4099039982627, 37.761747153832005],\n", " [-122.41901248673905, 37.75719450024423],\n", " [-122.41573893502441, 37.763831603122455],\n", " [-122.41237555483644, 37.761252927558274],\n", " [-122.40455000117886, 37.75726219498988],\n", " [-122.41069965976091, 37.76470088472506],\n", " [-122.41879495724017, 37.7622151757651],\n", " [-122.41516185537776, 37.75725637834527],\n", " [-122.42005488320424, 37.76320058943922],\n", " [-122.40966406763532, 37.754856259950174],\n", " [-122.41267234354358, 37.75588417673643],\n", " [-122.41129594712292, 37.761662032164296],\n", " [-122.41501959094464, 37.7631304733426]]}" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "solution" ] } ], "metadata": { "interpreter": { "hash": "31b88bb145573cdebdaa7fd72fef7949ecb3dda26d5e10d4ccc660a5d07787a7" }, "kernelspec": { "display_name": "Python [conda env:py311_spopt]", "language": "python", "name": "conda-env-py311_spopt-py" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.6" } }, "nbformat": 4, "nbformat_minor": 5 }