From 65021e67cd575df51e31857ff7559fcaad9f588e Mon Sep 17 00:00:00 2001 From: itsGarrin Date: Mon, 6 Nov 2023 20:28:53 -0500 Subject: Finished 3 route algorithm --- ZestySalesman.ipynb | 441 ++++++++++++++++++++++++++++++++++++++++++++-------- utils.py | 151 +++++++++++++++--- 2 files changed, 505 insertions(+), 87 deletions(-) diff --git a/ZestySalesman.ipynb b/ZestySalesman.ipynb index f39f5bc..1d1fd59 100644 --- a/ZestySalesman.ipynb +++ b/ZestySalesman.ipynb @@ -2,13 +2,13 @@ "cells": [ { "cell_type": "code", - "execution_count": 16, + "execution_count": 24, "id": "initial_id", "metadata": { "collapsed": true, "ExecuteTime": { - "end_time": "2023-11-07T00:07:54.400654Z", - "start_time": "2023-11-07T00:07:54.375821Z" + "end_time": "2023-11-07T01:17:52.608101Z", + "start_time": "2023-11-07T01:17:52.539921Z" } }, "outputs": [], @@ -20,7 +20,7 @@ }, { "cell_type": "code", - "execution_count": 17, + "execution_count": 25, "outputs": [], "source": [ "# Load the data\n", @@ -32,34 +32,34 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:07:54.430515Z", - "start_time": "2023-11-07T00:07:54.381537Z" + "end_time": "2023-11-07T01:17:52.672617Z", + "start_time": "2023-11-07T01:17:52.544450Z" } }, "id": "73b780e762c9de37" }, { "cell_type": "code", - "execution_count": 18, + "execution_count": 26, "outputs": [], "source": [ - "# Create two centroids, one in the North End and one in the Financial District\n", - "centroids = [[42.364506, -71.054733], [42.358894, -71.056742]]\n", + "# Create three centroids, one in the North End, one in the Financial District, and one in the Back Bay\n", + "centroids = [[42.364506, -71.054733], [42.358894, -71.056742], [42.3505, -71.0760]]\n", "\n", "northeastern_coordinate = \"-71.09033,42.33976\"" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:07:54.431407Z", - "start_time": "2023-11-07T00:07:54.392677Z" + "end_time": "2023-11-07T01:17:52.673868Z", + "start_time": "2023-11-07T01:17:52.558087Z" } }, - "id": "65e208650eb43b4" + "id": "be4c8c1d77842ef7" }, { "cell_type": "code", - "execution_count": 19, + "execution_count": 27, "outputs": [], "source": [ "# Combine the two lists and add a column to indicate the list\n", @@ -68,20 +68,20 @@ "ListC['list'] = 'C'\n", "ListD['list'] = 'D'\n", "\n", - "TotalList = pd.concat([ListA, ListB, ListC])" + "TotalList = pd.concat([ListA, ListB, ListC, ListD])" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:07:54.431829Z", - "start_time": "2023-11-07T00:07:54.397279Z" + "end_time": "2023-11-07T01:17:52.702176Z", + "start_time": "2023-11-07T01:17:52.568817Z" } }, "id": "ffe4025e97a6c6b9" }, { "cell_type": "code", - "execution_count": 20, + "execution_count": 28, "outputs": [], "source": [ "# Remove all columns but name and gps\n", @@ -90,15 +90,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:07:54.432180Z", - "start_time": "2023-11-07T00:07:54.401907Z" + "end_time": "2023-11-07T01:17:52.706405Z", + "start_time": "2023-11-07T01:17:52.577745Z" } }, "id": "72657779b4484aae" }, { "cell_type": "code", - "execution_count": 21, + "execution_count": 29, "outputs": [], "source": [ "# Convert the gps column to a list of lists for k-means\n", @@ -108,20 +108,20 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:07:54.432238Z", - "start_time": "2023-11-07T00:07:54.405216Z" + "end_time": "2023-11-07T01:17:52.706689Z", + "start_time": "2023-11-07T01:17:52.581919Z" } }, "id": "a157ffaec020a29a" }, { "cell_type": "code", - "execution_count": 22, + "execution_count": 30, "outputs": [ { "data": { - "text/plain": " name gps list \\\n0 521 Commercial Street #525 [42.3688272, -71.0553792] A \n1 Acorn St [42.3576234, -71.0688746] A \n2 Arlington's Great Meadows [42.4299758, -71.2038948] A \n3 Arthur Fiedler Statue [42.3565057, -71.0754527] A \n4 BU Beach [42.3511927, -71.1060828] A \n.. ... ... ... \n28 The Clam Box [42.2763168, -71.0092883] C \n29 The Partisans [42.3478375, -71.0404428] C \n30 Union Oyster House [42.361288, -71.056908] C \n31 Victoria's Diner [42.3270498, -71.0667744] C \n32 Wollaston Beach [42.2806539, -71.0119933] C \n\n normalized_gps \n0 [0.7251058917247415, 0.8141430878559053] \n1 [0.6747391031099019, 0.778052752104061] \n2 [1.0, 0.41697235794883575] \n3 [0.6697144722136962, 0.7604611403245493] \n4 [0.6458298305822171, 0.6785480000609988] \n.. ... \n28 [0.30922451563130937, 0.9374025730216268] \n29 [0.6307464973238023, 0.8540870458656248] \n30 [0.6912133469876947, 0.8100546647415456] \n31 [0.5372951958288665, 0.7836692527743693] \n32 [0.32872198960456106, 0.9301686741961767] \n\n[131 rows x 4 columns]", - "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
namegpslistnormalized_gps
0521 Commercial Street #525[42.3688272, -71.0553792]A[0.7251058917247415, 0.8141430878559053]
1Acorn St[42.3576234, -71.0688746]A[0.6747391031099019, 0.778052752104061]
2Arlington's Great Meadows[42.4299758, -71.2038948]A[1.0, 0.41697235794883575]
3Arthur Fiedler Statue[42.3565057, -71.0754527]A[0.6697144722136962, 0.7604611403245493]
4BU Beach[42.3511927, -71.1060828]A[0.6458298305822171, 0.6785480000609988]
...............
28The Clam Box[42.2763168, -71.0092883]C[0.30922451563130937, 0.9374025730216268]
29The Partisans[42.3478375, -71.0404428]C[0.6307464973238023, 0.8540870458656248]
30Union Oyster House[42.361288, -71.056908]C[0.6912133469876947, 0.8100546647415456]
31Victoria's Diner[42.3270498, -71.0667744]C[0.5372951958288665, 0.7836692527743693]
32Wollaston Beach[42.2806539, -71.0119933]C[0.32872198960456106, 0.9301686741961767]
\n

131 rows × 4 columns

\n
" + "text/plain": " name gps list \\\n0 521 Commercial Street #525 [42.3688272, -71.0553792] A \n1 Acorn St [42.3576234, -71.0688746] A \n2 Arlington's Great Meadows [42.4299758, -71.2038948] A \n3 Arthur Fiedler Statue [42.3565057, -71.0754527] A \n4 BU Beach [42.3511927, -71.1060828] A \n.. ... ... ... \n33 The Quiet Few [42.3670906, -71.0359889] D \n34 The Tall Ship Boston [42.3649544, -71.0414523] D \n35 Toasted Flats [42.3711266, -71.0371343] D \n36 Vega Market [42.3891835, -71.033703] D \n37 Winthrop High School [42.3803348, -70.9799864] D \n\n normalized_gps \n0 [0.7251058917247415, 0.7797482353989729] \n1 [0.6747391031099019, 0.7451825969538083] \n2 [1.0, 0.3993566550776867] \n3 [0.6697144722136962, 0.7283341725828262] \n4 [0.6458298305822171, 0.6498815915448888] \n.. ... \n33 [0.717298990038831, 0.8294124246148072] \n34 [0.7076956827824702, 0.8154190706511427] \n35 [0.7354428661210094, 0.8264787225922622] \n36 [0.8166178304491644, 0.8352672783369615] \n37 [0.7768384161061446, 0.972851090162032] \n\n[169 rows x 4 columns]", + "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
namegpslistnormalized_gps
0521 Commercial Street #525[42.3688272, -71.0553792]A[0.7251058917247415, 0.7797482353989729]
1Acorn St[42.3576234, -71.0688746]A[0.6747391031099019, 0.7451825969538083]
2Arlington's Great Meadows[42.4299758, -71.2038948]A[1.0, 0.3993566550776867]
3Arthur Fiedler Statue[42.3565057, -71.0754527]A[0.6697144722136962, 0.7283341725828262]
4BU Beach[42.3511927, -71.1060828]A[0.6458298305822171, 0.6498815915448888]
...............
33The Quiet Few[42.3670906, -71.0359889]D[0.717298990038831, 0.8294124246148072]
34The Tall Ship Boston[42.3649544, -71.0414523]D[0.7076956827824702, 0.8154190706511427]
35Toasted Flats[42.3711266, -71.0371343]D[0.7354428661210094, 0.8264787225922622]
36Vega Market[42.3891835, -71.033703]D[0.8166178304491644, 0.8352672783369615]
37Winthrop High School[42.3803348, -70.9799864]D[0.7768384161061446, 0.972851090162032]
\n

169 rows × 4 columns

\n
" }, "metadata": {}, "output_type": "display_data" @@ -135,8 +135,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:07:54.432731Z", - "start_time": "2023-11-07T00:07:54.412279Z" + "end_time": "2023-11-07T01:17:52.707232Z", + "start_time": "2023-11-07T01:17:52.597329Z" } }, "id": "a03ebde91b87fa3b" @@ -144,16 +144,26 @@ { "cell_type": "markdown", "source": [ - "# Cluster and Minimize" + "# 2 Routes" ], "metadata": { "collapsed": false }, "id": "4bd41be9aca5094b" }, + { + "cell_type": "markdown", + "source": [ + "## Cluster and Minimize" + ], + "metadata": { + "collapsed": false + }, + "id": "90d1d2f1a931597f" + }, { "cell_type": "code", - "execution_count": 23, + "execution_count": 31, "outputs": [ { "name": "stderr", @@ -168,21 +178,32 @@ ], "source": [ "# Cluster and minimize the data\n", - "df, route_1_coordinates, route_2_coordinates = utils.cluster_and_minimize(TotalList, centroids, norm_centroids,\n", - " northeastern_coordinate, 0.5)" + "norm_centroids_2 = norm_centroids[:2]\n", + "_, route_1_coordinates, route_2_coordinates = utils.cluster_and_minimize_2(TotalList, centroids, norm_centroids_2,\n", + " northeastern_coordinate, 0.5, minimize=True)" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:08:20.577006Z", - "start_time": "2023-11-07T00:07:54.416349Z" + "end_time": "2023-11-07T01:18:19.800168Z", + "start_time": "2023-11-07T01:17:52.606044Z" } }, "id": "ee9b3c1ecb360976" }, + { + "cell_type": "markdown", + "source": [ + "## Create JSON" + ], + "metadata": { + "collapsed": false + }, + "id": "c85b8ef869e35006" + }, { "cell_type": "code", - "execution_count": 24, + "execution_count": 32, "outputs": [], "source": [ "# Create a JSON request for the API\n", @@ -193,15 +214,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:08:20.591584Z", - "start_time": "2023-11-07T00:08:20.577492Z" + "end_time": "2023-11-07T01:18:19.807296Z", + "start_time": "2023-11-07T01:18:19.799849Z" } }, "id": "aa618161182b5b07" }, { "cell_type": "code", - "execution_count": 25, + "execution_count": 33, "outputs": [], "source": [ "# Create a dataframe from the JSON\n", @@ -211,15 +232,15 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:08:22.409355Z", - "start_time": "2023-11-07T00:08:20.579890Z" + "end_time": "2023-11-07T01:18:22.014184Z", + "start_time": "2023-11-07T01:18:19.803262Z" } }, "id": "32c485788eedd94" }, { "cell_type": "code", - "execution_count": 26, + "execution_count": 34, "outputs": [], "source": [ "# Add columns for the route number\n", @@ -232,47 +253,57 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:08:22.425179Z", - "start_time": "2023-11-07T00:08:22.412707Z" + "end_time": "2023-11-07T01:18:22.024878Z", + "start_time": "2023-11-07T01:18:22.017438Z" } }, "id": "49dba1f17ca8337e" }, { "cell_type": "code", - "execution_count": 27, + "execution_count": 35, "outputs": [ { "data": { - "text/plain": " waypoint_index trips_index \\\n0 0 0 \n13 1 0 \n68 2 0 \n40 3 0 \n22 4 0 \n.. ... ... \n14 67 0 \n11 68 0 \n69 69 0 \n19 70 0 \n71 71 0 \n\n hint distance \\\n0 dMQAgDTDAIAuAAAAEgAAAAAAAAAAAAAAiaamQKk960AAAA... 1.113855 \n13 oLwsgCS9LIBHAAAA2AAAAAAAAABgAQAAkQwAQdo1v0EAAA... 2.532529 \n68 CL0sgBS9LIAhAAAAagAAAAAAAAAAAAAAfoF0QPCwOkEAAA... 7.608103 \n40 YbwsgEO9LIBbAAAAEgAAAAAAAAAPAAAA5ua1QcswjkAAAA... 0.468602 \n22 UkAEgFxABIB8AAAAAAAAAAAAAAAYAgAAVjBdQQAAAAAAAA... 6.397300 \n.. ... ... \n14 -mUsgHZmLIATAAAAYgEAAL0AAADpAAAALf8HQHZ8HUK-9a... 55.355565 \n11 43YhgPN2IYA1AAAAJAAAAAAAAAA5AAAAEha0QWgpbEEAAA... 18.896385 \n69 CdQhgB0OA4AYAAAAHgAAADkAAAAAAAAALdMlQdSMQ0Fd0r... 10.970598 \n19 XAAigHIAIoBKAAAASwAAAFUAAABDAQAARGUEQURlBEG2ZR... 11.054154 \n71 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat lon \\\n0 State Street [-71.056741, 42.358884] -71.056741 42.358884 \n13 [-71.056995, 42.36049] -71.056995 42.360490 \n68 [-71.056994, 42.361263] -71.056994 42.361263 \n40 Creek Square [-71.056819, 42.361534] -71.056819 42.361534 \n22 [-71.059255, 42.359295] -71.059255 42.359295 \n.. ... ... ... ... \n14 [-71.049204, 42.325624] -71.049204 42.325624 \n11 Lucy Street [-71.06221, 42.324934] -71.062210 42.324934 \n69 [-71.066844, 42.327134] -71.066844 42.327134 \n19 [-71.071196, 42.34085] -71.071196 42.340850 \n71 Northeastern (Inbound) [-71.090331, 42.339762] -71.090331 42.339762 \n\n route \n0 2 \n13 2 \n68 2 \n40 2 \n22 2 \n.. ... \n14 2 \n11 2 \n69 2 \n19 2 \n71 2 \n\n[72 rows x 9 columns]", - "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
waypoint_indextrips_indexhintdistancenamelocationlatlonroute
000dMQAgDTDAIAuAAAAEgAAAAAAAAAAAAAAiaamQKk960AAAA...1.113855State Street[-71.056741, 42.358884]-71.05674142.3588842
1310oLwsgCS9LIBHAAAA2AAAAAAAAABgAQAAkQwAQdo1v0EAAA...2.532529[-71.056995, 42.36049]-71.05699542.3604902
6820CL0sgBS9LIAhAAAAagAAAAAAAAAAAAAAfoF0QPCwOkEAAA...7.608103[-71.056994, 42.361263]-71.05699442.3612632
4030YbwsgEO9LIBbAAAAEgAAAAAAAAAPAAAA5ua1QcswjkAAAA...0.468602Creek Square[-71.056819, 42.361534]-71.05681942.3615342
2240UkAEgFxABIB8AAAAAAAAAAAAAAAYAgAAVjBdQQAAAAAAAA...6.397300[-71.059255, 42.359295]-71.05925542.3592952
..............................
14670-mUsgHZmLIATAAAAYgEAAL0AAADpAAAALf8HQHZ8HUK-9a...55.355565[-71.049204, 42.325624]-71.04920442.3256242
1168043YhgPN2IYA1AAAAJAAAAAAAAAA5AAAAEha0QWgpbEEAAA...18.896385Lucy Street[-71.06221, 42.324934]-71.06221042.3249342
69690CdQhgB0OA4AYAAAAHgAAADkAAAAAAAAALdMlQdSMQ0Fd0r...10.970598[-71.066844, 42.327134]-71.06684442.3271342
19700XAAigHIAIoBKAAAASwAAAFUAAABDAQAARGUEQURlBEG2ZR...11.054154[-71.071196, 42.34085]-71.07119642.3408502
71710DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397622
\n

72 rows × 9 columns

\n
" + "text/plain": " waypoint_index trips_index \\\n0 0 0 \n1 1 0 \n2 2 0 \n3 3 0 \n4 4 0 \n.. ... ... \n168 64 0 \n169 65 0 \n170 66 0 \n171 67 0 \n172 68 0 \n\n hint distance \\\n0 t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA... 19.432511 \n1 IzYEgGw1BIASAAAArwAAADMAAACUAwAAynkIQGUkmkEXlL... 6.024489 \n2 G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8... 2.602121 \n3 gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR... 15.458439 \n4 HpwsgCKcLIAAAAAAEgAAAAAAAAAAAAAAAAAAACg870AAAA... 39.201677 \n.. ... ... \n168 cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC... 22.776295 \n169 g38hgI1_IYBOAAAAfwAAAAAAAAAAAAAAZ4ECQsbEUkIAAA... 12.789906 \n170 e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA... 6.310267 \n171 k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e... 36.240351 \n172 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat lon \\\n0 [-71.054865, 42.364361] -71.054865 42.364361 \n1 [-71.055569, 42.364032] -71.055569 42.364032 \n2 [-71.056164, 42.366918] -71.056164 42.366918 \n3 [-71.055561, 42.368861] -71.055561 42.368861 \n4 [-71.062507, 42.365968] -71.062507 42.365968 \n.. ... ... ... ... \n168 Alleghany Street [-71.099348, 42.33047] -71.099348 42.330470 \n169 Tremont Street [-71.098267, 42.332009] -71.098267 42.332009 \n170 Carmel Street [-71.100092, 42.332401] -71.100092 42.332401 \n171 [-71.093834, 42.339096] -71.093834 42.339096 \n172 Northeastern (Inbound) [-71.090331, 42.339762] -71.090331 42.339762 \n\n route \n0 1 \n1 1 \n2 1 \n3 1 \n4 1 \n.. ... \n168 2 \n169 2 \n170 2 \n171 2 \n172 2 \n\n[173 rows x 9 columns]", + "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
waypoint_indextrips_indexhintdistancenamelocationlatlonroute
000t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA...19.432511[-71.054865, 42.364361]-71.05486542.3643611
110IzYEgGw1BIASAAAArwAAADMAAACUAwAAynkIQGUkmkEXlL...6.024489[-71.055569, 42.364032]-71.05556942.3640321
220G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8...2.602121[-71.056164, 42.366918]-71.05616442.3669181
330gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR...15.458439[-71.055561, 42.368861]-71.05556142.3688611
440HpwsgCKcLIAAAAAAEgAAAAAAAAAAAAAAAAAAACg870AAAA...39.201677[-71.062507, 42.365968]-71.06250742.3659681
..............................
168640cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC...22.776295Alleghany Street[-71.099348, 42.33047]-71.09934842.3304702
169650g38hgI1_IYBOAAAAfwAAAAAAAAAAAAAAZ4ECQsbEUkIAAA...12.789906Tremont Street[-71.098267, 42.332009]-71.09826742.3320092
170660e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA...6.310267Carmel Street[-71.100092, 42.332401]-71.10009242.3324012
171670k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e...36.240351[-71.093834, 42.339096]-71.09383442.3390962
172680DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397622
\n

173 rows × 9 columns

\n
" }, "metadata": {}, "output_type": "display_data" } ], "source": [ - "display(df2)" + "display(df)" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:08:22.440853Z", - "start_time": "2023-11-07T00:08:22.424158Z" + "end_time": "2023-11-07T01:18:22.033944Z", + "start_time": "2023-11-07T01:18:22.026906Z" } }, "id": "f231d9a35358988c" }, + { + "cell_type": "markdown", + "source": [ + "## Map" + ], + "metadata": { + "collapsed": false + }, + "id": "75be92e34a36147f" + }, { "cell_type": "code", - "execution_count": 28, + "execution_count": 36, "outputs": [ { "data": { - "text/plain": "", - "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" + "text/plain": "", + "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" }, - "execution_count": 28, + "execution_count": 36, "metadata": {}, "output_type": "execute_result" } @@ -297,22 +328,32 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:08:22.513542Z", - "start_time": "2023-11-07T00:08:22.430363Z" + "end_time": "2023-11-07T01:18:22.118478Z", + "start_time": "2023-11-07T01:18:22.036338Z" } }, "id": "80fd847da2833913" }, + { + "cell_type": "markdown", + "source": [ + "## Results" + ], + "metadata": { + "collapsed": false + }, + "id": "a7b562f75f7e0813" + }, { "cell_type": "code", - "execution_count": 29, + "execution_count": 37, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "Route 1 has 61 waypoints\n", - "Route 2 has 70 waypoints\n" + "Route 1 has 102 waypoints\n", + "Route 2 has 67 waypoints\n" ] } ], @@ -326,22 +367,22 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:08:22.513689Z", - "start_time": "2023-11-07T00:08:22.488854Z" + "end_time": "2023-11-07T01:18:22.120347Z", + "start_time": "2023-11-07T01:18:22.104950Z" } }, "id": "f53c97acec1c2fc4" }, { "cell_type": "code", - "execution_count": 30, + "execution_count": 38, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ - "The trip will take 10.36111111111111 hours\n", - "The trip will take 10.586666666666666 hours\n" + "The trip will take 12.788333333333334 hours\n", + "The trip will take 13.1675 hours\n" ] } ], @@ -356,25 +397,289 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:08:24.460727Z", - "start_time": "2023-11-07T00:08:22.491469Z" + "end_time": "2023-11-07T01:18:24.705352Z", + "start_time": "2023-11-07T01:18:22.107540Z" } }, "id": "a3ec09dfb5cbb5b3" }, + { + "cell_type": "markdown", + "source": [ + "# 3 Routes" + ], + "metadata": { + "collapsed": false + }, + "id": "de7b5856172d213c" + }, { "cell_type": "code", - "execution_count": 30, + "execution_count": 47, + "outputs": [ + { + "name": "stderr", + "output_type": "stream", + "text": [ + "/Users/garrinshieh/anaconda3/lib/python3.11/site-packages/sklearn/cluster/_kmeans.py:1412: FutureWarning: The default value of `n_init` will change from 10 to 'auto' in 1.4. Set the value of `n_init` explicitly to suppress the warning\n", + " super()._check_params_vs_input(X, default_n_init=10)\n", + "/Users/garrinshieh/anaconda3/lib/python3.11/site-packages/sklearn/cluster/_kmeans.py:1412: RuntimeWarning: Explicit initial center position passed: performing only one init in KMeans instead of n_init=10.\n", + " super()._check_params_vs_input(X, default_n_init=10)\n" + ] + } + ], + "source": [ + "# Cluster and minimize the data\n", + "_, route_1_coordinates, route_2_coordinates, route_3_coordinates = utils.cluster_and_minimize_3(TotalList, centroids,\n", + " norm_centroids,\n", + " northeastern_coordinate,\n", + " 0.2, minimize=True)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T01:22:14.864605Z", + "start_time": "2023-11-07T01:21:59.518900Z" + } + }, + "id": "bb6e00857e8175c0" + }, + { + "cell_type": "markdown", + "source": [ + "## Create JSON" + ], + "metadata": { + "collapsed": false + }, + "id": "19afb4f687b37383" + }, + { + "cell_type": "code", + "execution_count": 48, + "outputs": [], + "source": [ + "# Create a JSON request for the API\n", + "# This is the data we want to get from the API\n", + "route_1 = utils.list_to_string(route_1_coordinates)\n", + "route_2 = utils.list_to_string(route_2_coordinates)\n", + "route_3 = utils.list_to_string(route_3_coordinates)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T01:22:16.725390Z", + "start_time": "2023-11-07T01:22:16.722334Z" + } + }, + "id": "e886e061f86a2118" + }, + { + "cell_type": "code", + "execution_count": 49, + "outputs": [], + "source": [ + "# Create a dataframe from the JSON\n", + "df1 = utils.create_json_df(route_1, utils.list_to_string([centroids[0]]), northeastern_coordinate)\n", + "df2 = utils.create_json_df(route_2, utils.list_to_string([centroids[1]]), northeastern_coordinate)\n", + "df3 = utils.create_json_df(route_3, utils.list_to_string([centroids[2]]), northeastern_coordinate)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T01:22:19.351381Z", + "start_time": "2023-11-07T01:22:17.034813Z" + } + }, + "id": "23e4682fe9e30631" + }, + { + "cell_type": "code", + "execution_count": 50, + "outputs": [], + "source": [ + "# Add columns for the route number\n", + "df1['route'] = 1\n", + "df2['route'] = 2\n", + "df3['route'] = 3\n", + "\n", + "# Concatenate the three dataframes\n", + "df = pd.concat([df1, df2, df3], ignore_index=True)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T01:22:19.360710Z", + "start_time": "2023-11-07T01:22:19.355746Z" + } + }, + "id": "c3a5c5d6f3ac46c0" + }, + { + "cell_type": "code", + "execution_count": 51, + "outputs": [ + { + "data": { + "text/plain": " waypoint_index trips_index \\\n0 0 0 \n1 1 0 \n2 2 0 \n3 3 0 \n4 4 0 \n.. ... ... \n170 29 0 \n171 30 0 \n172 31 0 \n173 32 0 \n174 33 0 \n\n hint distance \\\n0 t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA... 19.432511 \n1 e1kugJlZLoBmAAAA6QAAAAAAAAAAAAAAZ6M2QSewzkEAAA... 4.756158 \n2 tFkugHVaLoAOAAAAAAAAABgAAAAAAAAAwMG2QAAAAAB6ii... 4.525535 \n3 sJAugLOQLoBuAQAAlAEAAAAAAAAAAAAAHFcjQvEZM0IAAA... 7.844897 \n4 VREtgNlJBIBCAAAAYAAAAAAAAAARAAAAOOzeQU7vHkIAAA... 22.681980 \n.. ... ... \n170 gLshgIS7IYAAAAAAPAAAAAAAAAAAAAAAAAAAAPGU1UAAAA... 10.782119 \n171 e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA... 6.310267 \n172 cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC... 22.776295 \n173 s9QhgLbUIYAwAAAAkAAAAAAAAAAAAAAA2XmpQNgrgEEAAA... 4.111715 \n174 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat lon \\\n0 [-71.054865, 42.364361] -71.054865 42.364361 \n1 [-71.060933, 42.376178] -71.060933 42.376178 \n2 [-71.060753, 42.376391] -71.060753 42.376391 \n3 [-71.060948, 42.380436] -71.060948 42.380436 \n4 Factory Street [-71.061206, 42.398809] -71.061206 42.398809 \n.. ... ... ... ... \n170 [-71.10963, 42.336448] -71.109630 42.336448 \n171 Carmel Street [-71.100092, 42.332401] -71.100092 42.332401 \n172 Alleghany Street [-71.099348, 42.33047] -71.099348 42.330470 \n173 [-71.09454, 42.325354] -71.094540 42.325354 \n174 Northeastern (Inbound) [-71.090331, 42.339762] -71.090331 42.339762 \n\n route \n0 1 \n1 1 \n2 1 \n3 1 \n4 1 \n.. ... \n170 3 \n171 3 \n172 3 \n173 3 \n174 3 \n\n[175 rows x 9 columns]", + "text/html": "
\n\n\n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n \n
waypoint_indextrips_indexhintdistancenamelocationlatlonroute
000t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA...19.432511[-71.054865, 42.364361]-71.05486542.3643611
110e1kugJlZLoBmAAAA6QAAAAAAAAAAAAAAZ6M2QSewzkEAAA...4.756158[-71.060933, 42.376178]-71.06093342.3761781
220tFkugHVaLoAOAAAAAAAAABgAAAAAAAAAwMG2QAAAAAB6ii...4.525535[-71.060753, 42.376391]-71.06075342.3763911
330sJAugLOQLoBuAQAAlAEAAAAAAAAAAAAAHFcjQvEZM0IAAA...7.844897[-71.060948, 42.380436]-71.06094842.3804361
440VREtgNlJBIBCAAAAYAAAAAAAAAARAAAAOOzeQU7vHkIAAA...22.681980Factory Street[-71.061206, 42.398809]-71.06120642.3988091
..............................
170290gLshgIS7IYAAAAAAPAAAAAAAAAAAAAAAAAAAAPGU1UAAAA...10.782119[-71.10963, 42.336448]-71.10963042.3364483
171300e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA...6.310267Carmel Street[-71.100092, 42.332401]-71.10009242.3324013
172310cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC...22.776295Alleghany Street[-71.099348, 42.33047]-71.09934842.3304703
173320s9QhgLbUIYAwAAAAkAAAAAAAAAAAAAAA2XmpQNgrgEEAAA...4.111715[-71.09454, 42.325354]-71.09454042.3253543
174330DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397623
\n

175 rows × 9 columns

\n
" + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "display(df)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T01:22:19.375055Z", + "start_time": "2023-11-07T01:22:19.364517Z" + } + }, + "id": "17a8cc8fed5450a6" + }, + { + "cell_type": "markdown", + "source": [ + "## Map" + ], + "metadata": { + "collapsed": false + }, + "id": "b20a57aa09792c39" + }, + { + "cell_type": "code", + "execution_count": 52, + "outputs": [ + { + "data": { + "text/plain": "", + "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" + }, + "execution_count": 52, + "metadata": {}, + "output_type": "execute_result" + } + ], + "source": [ + "# Create a map\n", + "m = folium.Map(location=[df['lon'].mean(), df['lat'].mean()], zoom_start=11)\n", + "\n", + "# Add the points and lines for the three routes with different colors\n", + "colors = ['red', 'blue', 'green']\n", + "\n", + "for route in df['route'].unique():\n", + " df_route = df[df['route'] == route]\n", + " folium.PolyLine(df_route[['lon', 'lat']].values.tolist(), color=colors[route - 1]).add_to(m)\n", + " for i in range(len(df_route)):\n", + " folium.CircleMarker(df_route[['lon', 'lat']].iloc[i].values.tolist(), radius=3, color=colors[route - 1]).add_to(\n", + " m)\n", + " \n", + "# Display the map\n", + "m" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T01:22:20.246243Z", + "start_time": "2023-11-07T01:22:20.167900Z" + } + }, + "id": "702adaec008a6ec8" + }, + { + "cell_type": "markdown", + "source": [ + "## Results" + ], + "metadata": { + "collapsed": false + }, + "id": "a947e49e27c734e9" + }, + { + "cell_type": "code", + "execution_count": 53, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Route 1 has 57 waypoints\n", + "Route 2 has 80 waypoints\n", + "Route 3 has 32 waypoints\n" + ] + } + ], + "source": [ + "# Get the number of waypoints for each route\n", + "route_1_waypoints = len(route_1_coordinates)\n", + "route_2_waypoints = len(route_2_coordinates)\n", + "route_3_waypoints = len(route_3_coordinates)\n", + "print(\"Route 1 has {} waypoints\".format(route_1_waypoints))\n", + "print(\"Route 2 has {} waypoints\".format(route_2_waypoints))\n", + "print(\"Route 3 has {} waypoints\".format(route_3_waypoints))" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T01:22:21.994911Z", + "start_time": "2023-11-07T01:22:21.992304Z" + } + }, + "id": "4106acf2adad01d7" + }, + { + "cell_type": "code", + "execution_count": 54, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "The trip will take 9.175 hours\n", + "The trip will take 9.341111111111111 hours\n", + "The trip will take 9.398333333333333 hours\n" + ] + } + ], + "source": [ + "# Get the trip time for each route\n", + "trip_hrs_1 = utils.get_trip_time(route_1, route_1_waypoints, utils.list_to_string([centroids[0]]),\n", + " northeastern_coordinate)\n", + "print(\"The trip will take {} hours\".format(trip_hrs_1))\n", + "trip_hrs_2 = utils.get_trip_time(route_2, route_2_waypoints, utils.list_to_string([centroids[1]]),\n", + " northeastern_coordinate)\n", + "print(\"The trip will take {} hours\".format(trip_hrs_2))\n", + "trip_hrs_3 = utils.get_trip_time(route_3, route_3_waypoints, utils.list_to_string([centroids[2]]),\n", + " northeastern_coordinate)\n", + "print(\"The trip will take {} hours\".format(trip_hrs_3))" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T01:22:25.544575Z", + "start_time": "2023-11-07T01:22:23.206069Z" + } + }, + "id": "c58106faf0fc7f4e" + }, + { + "cell_type": "code", + "execution_count": 46, "outputs": [], "source": [], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T00:08:24.471189Z", - "start_time": "2023-11-07T00:08:24.460431Z" + "end_time": "2023-11-07T01:18:42.067793Z", + "start_time": "2023-11-07T01:18:42.056069Z" } }, - "id": "eafe5678c44e94fd" + "id": "a2f10e3152b95a69" } ], "metadata": { diff --git a/utils.py b/utils.py index e0cc295..2898b3d 100644 --- a/utils.py +++ b/utils.py @@ -1,11 +1,12 @@ import folium +import numpy as np import pandas as pd import requests from sklearn.cluster import KMeans # Given a dataframe of coordinates and centroids, cluster the coordinates, minimize the time difference, and return the routes -def cluster_and_minimize(df, centroids, norm_centroids, end, time_diff): +def cluster_and_minimize_2(df, centroids, norm_centroids, end, time_diff, minimize=True, n=2): # Cluster the coordinates kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids) @@ -32,11 +33,16 @@ def cluster_and_minimize(df, centroids, norm_centroids, end, time_diff): trip_hrs_1 = get_trip_time(route_1_str, route_1_stops, centroid_1, end) trip_hrs_2 = get_trip_time(route_2_str, route_2_stops, centroid_2, end) - # if the absolute value of the difference in trip times is greater than the time difference, minimize the time difference - if abs(trip_hrs_1 - trip_hrs_2) > time_diff: - route_1_coordinates, route_2_coordinates = minimize_route_time_diff(route_1['gps'].values.tolist(), - route_2['gps'].values.tolist(), - centroid_1, centroid_2, end, time_diff) + if minimize: + # if the absolute value of the difference in trip times is greater than the time difference, minimize the time difference + if abs(trip_hrs_1 - trip_hrs_2) > time_diff: + route_1_coordinates, route_2_coordinates = minimize_route_time_diff(route_1['gps'].values.tolist(), + route_2['gps'].values.tolist(), + centroid_1, centroid_2, end, time_diff, + n=n) + else: + route_1_coordinates = route_1['gps'].values.tolist() + route_2_coordinates = route_2['gps'].values.tolist() else: route_1_coordinates = route_1['gps'].values.tolist() route_2_coordinates = route_2['gps'].values.tolist() @@ -49,7 +55,7 @@ def cluster_and_minimize(df, centroids, norm_centroids, end, time_diff): def minimize_route_time_diff(route_1_coordinates, route_2_coordinates, route_1_start, route_2_start, end, - time_diff): + time_diff, n): """ Takes two routes and a time difference and returns a route that is the same length as the shorter route but has a time difference that is less than the time difference """ @@ -63,34 +69,141 @@ def minimize_route_time_diff(route_1_coordinates, route_2_coordinates, route_1_s # If the difference in time is greater than the time difference, move the closest coordinate from the longer route to the shorter route if route_time_diff > time_diff: # Find which route is longer - if len(route_1_coordinates) > len(route_2_coordinates): + if route_1_time > route_2_time: longer_route = route_1_coordinates shorter_route = route_2_coordinates - # Move the closest coordinate from the longer route to the shorter route - closest_coordinate = move_coordinate(longer_route, shorter_route) - longer_route.remove(closest_coordinate) - shorter_route.append(closest_coordinate) + for i in range(n): + # Move the closest coordinate from the longer route to the shorter route + closest_coordinate = move_coordinate(longer_route, shorter_route) + longer_route.remove(closest_coordinate) + shorter_route.append(closest_coordinate) # Recursively call the function - return minimize_route_time_diff(longer_route, shorter_route, route_1_start, route_2_start, end, time_diff) + return minimize_route_time_diff(longer_route, shorter_route, route_1_start, route_2_start, end, + time_diff, n) else: longer_route = route_2_coordinates shorter_route = route_1_coordinates - # Move the closest coordinate from the longer route to the shorter route - closest_coordinate = move_coordinate(longer_route, shorter_route) - longer_route.remove(closest_coordinate) - shorter_route.append(closest_coordinate) + for i in range(n): + # Move the closest coordinate from the longer route to the shorter route + closest_coordinate = move_coordinate(longer_route, shorter_route) + longer_route.remove(closest_coordinate) + shorter_route.append(closest_coordinate) # Recursively call the function - return minimize_route_time_diff(shorter_route, longer_route, route_1_start, route_2_start, end, time_diff) + return minimize_route_time_diff(shorter_route, longer_route, route_1_start, route_2_start, end, + time_diff, n) # If the difference in time is less than the time difference, return the routes return route_1_coordinates, route_2_coordinates +# Create a function to minimize the time difference between three routes +def cluster_and_minimize_3(df, centroids, norm_centroids, end, time_diff, minimize=True, n=2): + # Cluster the coordinates + kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids) + + # Fit the coordinates to the clusters + kmeans.fit(df['normalized_gps'].values.tolist()) + + # Add the cluster labels to the dataframe + df['cluster'] = kmeans.labels_ + + # Create centroid strings + centroid_1 = list_to_string([centroids[0]]) + centroid_2 = list_to_string([centroids[1]]) + centroid_3 = list_to_string([centroids[2]]) + + # Return the list of locations in each cluster + route_1 = df[df['cluster'] == 0] + route_1_stops = len(route_1['gps'].values.tolist()) + route_1_str = list_to_string(route_1['gps'].values.tolist()) + + route_2 = df[df['cluster'] == 1] + route_2_stops = len(route_2['gps'].values.tolist()) + route_2_str = list_to_string(route_2['gps'].values.tolist()) + + route_3 = df[df['cluster'] == 2] + route_3_stops = len(route_3['gps'].values.tolist()) + route_3_str = list_to_string(route_3['gps'].values.tolist()) + + # Get the trip time for each route + trip_hrs_1 = get_trip_time(route_1_str, route_1_stops, centroid_1, end) + trip_hrs_2 = get_trip_time(route_2_str, route_2_stops, centroid_2, end) + trip_hrs_3 = get_trip_time(route_3_str, route_3_stops, centroid_3, end) + + average_time = (trip_hrs_1 + trip_hrs_2 + trip_hrs_3) / 3 + + times = [trip_hrs_1, trip_hrs_2, trip_hrs_3] + routes = [route_1_str, route_2_str, route_3_str] + + sorted_indices = np.argsort(times) + + if minimize: + # if the absolute value of the difference in trip times is greater than the time difference, minimize the time difference + if times[sorted_indices[2]] - average_time > time_diff: + route_1_coordinates, route_2_coordinates, route_3_coordinates = minimize_route_time_diff_3( + route_1['gps'].values.tolist(), + route_2['gps'].values.tolist(), + route_3['gps'].values.tolist(), + centroid_1, centroid_2, centroid_3, end, time_diff, + n=n) + else: + route_1_coordinates = route_1['gps'].values.tolist() + route_2_coordinates = route_2['gps'].values.tolist() + route_3_coordinates = route_3['gps'].values.tolist() + else: + route_1_coordinates = route_1['gps'].values.tolist() + route_2_coordinates = route_2['gps'].values.tolist() + route_3_coordinates = route_3['gps'].values.tolist() + + # Edit the dataframe to reflect the new coordinate clusters + df.loc[df['gps'].astype(str).isin(map(str, route_1_coordinates)), 'cluster'] = 0 + df.loc[df['gps'].astype(str).isin(map(str, route_2_coordinates)), 'cluster'] = 1 + df.loc[df['gps'].astype(str).isin(map(str, route_3_coordinates)), 'cluster'] = 2 + + return df, route_1_coordinates, route_2_coordinates, route_3_coordinates + + +def minimize_route_time_diff_3(route_1_coordinates, route_2_coordinates, route_3_coordinates, + route_1_start, route_2_start, route_3_start, end, time_diff, n): + """ + Takes three routes and a time difference and returns routes that have time differences less than the time difference + """ + # Find the trip time for each route + route_1_time = get_trip_time(list_to_string(route_1_coordinates), len(route_1_coordinates), route_1_start, end) + route_2_time = get_trip_time(list_to_string(route_2_coordinates), len(route_2_coordinates), route_2_start, end) + route_3_time = get_trip_time(list_to_string(route_3_coordinates), len(route_3_coordinates), route_3_start, end) + + # Find the average trip time + average_time = (route_1_time + route_2_time + route_3_time) / 3 + + # Define a list of all times and route coordinates + times = [route_1_time, route_2_time, route_3_time] + routes = [route_1_coordinates, route_2_coordinates, route_3_coordinates] + + # Sort the routes by time + sorted_indices = np.argsort(times) + + # If the difference of the longest trip time from average is greater than the time difference + if times[sorted_indices[2]] - average_time > time_diff: + # Move the closest coordinate(s) from the longest route to the shortest route + for i in range(n): + closest_coordinate = move_coordinate(routes[sorted_indices[2]], routes[sorted_indices[0]]) + routes[sorted_indices[2]].remove(closest_coordinate) + routes[sorted_indices[0]].append(closest_coordinate) + + # Recursively call the function + return minimize_route_time_diff_3(routes[0], routes[1], routes[2], route_1_start, route_2_start, route_3_start, + end, time_diff, n) + + # If the difference of the longest trip time from average is less than the time difference, return the routes + return routes[0], routes[1], routes[2] + + def list_to_string(list_of_lists): """ Takes a list of lists of coordinates and returns a string of the coordinates @@ -131,7 +244,7 @@ def get_trip_time(coordinate_string, num_waypoints, start, end): coordinates = coordinates.json() travel_time_seconds = int(coordinates['trips'][0]['duration']) - waypoint_time_seconds = num_waypoints * 60 + waypoint_time_seconds = num_waypoints * 90 total_time_hours = (travel_time_seconds + waypoint_time_seconds) / 3600 -- cgit v1.2.3