From 679044dadde06e7bfee642d6c1aac517dd4eee03 Mon Sep 17 00:00:00 2001 From: itsGarrin Date: Tue, 7 Nov 2023 18:15:55 -0500 Subject: Made the algorithm work for n bike teams --- ZestySalesman.ipynb | 452 ++++++++++++++++++++++++++++++++++++++++++---------- utils.py | 253 ++++++++++------------------- 2 files changed, 451 insertions(+), 254 deletions(-) diff --git a/ZestySalesman.ipynb b/ZestySalesman.ipynb index 57593d2..4e14da2 100644 --- a/ZestySalesman.ipynb +++ b/ZestySalesman.ipynb @@ -7,8 +7,8 @@ "metadata": { "collapsed": true, "ExecuteTime": { - "end_time": "2023-11-07T18:15:48.594817Z", - "start_time": "2023-11-07T18:15:47.605833Z" + "end_time": "2023-11-07T23:05:35.179983Z", + "start_time": "2023-11-07T23:05:34.039783Z" } }, "outputs": [], @@ -32,8 +32,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:15:48.604219Z", - "start_time": "2023-11-07T18:15:48.596141Z" + "end_time": "2023-11-07T23:05:35.194166Z", + "start_time": "2023-11-07T23:05:35.181233Z" } }, "id": "73b780e762c9de37" @@ -43,16 +43,16 @@ "execution_count": 3, "outputs": [], "source": [ - "# 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", + "# Create two centroids, one in the North End and one in the Seaport District\n", + "centroids = [[42.365, -71.054], [42.351, -71.045]]\n", "\n", "northeastern_coordinate = \"-71.09033,42.33976\"" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:15:48.608755Z", - "start_time": "2023-11-07T18:15:48.604788Z" + "end_time": "2023-11-07T23:05:35.195314Z", + "start_time": "2023-11-07T23:05:35.193156Z" } }, "id": "be4c8c1d77842ef7" @@ -73,8 +73,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:15:48.613233Z", - "start_time": "2023-11-07T18:15:48.607380Z" + "end_time": "2023-11-07T23:05:35.201800Z", + "start_time": "2023-11-07T23:05:35.197747Z" } }, "id": "ffe4025e97a6c6b9" @@ -90,8 +90,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:15:48.613309Z", - "start_time": "2023-11-07T18:15:48.611827Z" + "end_time": "2023-11-07T23:05:35.215762Z", + "start_time": "2023-11-07T23:05:35.200811Z" } }, "id": "72657779b4484aae" @@ -108,8 +108,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:15:48.617922Z", - "start_time": "2023-11-07T18:15:48.614428Z" + "end_time": "2023-11-07T23:05:35.215916Z", + "start_time": "2023-11-07T23:05:35.204173Z" } }, "id": "a157ffaec020a29a" @@ -120,23 +120,21 @@ "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.. ... ... ... \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
" + "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[169 rows x 3 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
namegpslist
0521 Commercial Street #525[42.3688272, -71.0553792]A
1Acorn St[42.3576234, -71.0688746]A
2Arlington's Great Meadows[42.4299758, -71.2038948]A
3Arthur Fiedler Statue[42.3565057, -71.0754527]A
4BU Beach[42.3511927, -71.1060828]A
............
33The Quiet Few[42.3670906, -71.0359889]D
34The Tall Ship Boston[42.3649544, -71.0414523]D
35Toasted Flats[42.3711266, -71.0371343]D
36Vega Market[42.3891835, -71.033703]D
37Winthrop High School[42.3803348, -70.9799864]D
\n

169 rows × 3 columns

\n
" }, "metadata": {}, "output_type": "display_data" } ], "source": [ - "# Create a new column with normalized gps coordinates and centroids\n", - "TotalList['normalized_gps'], norm_centroids = utils.normalize_gps(TotalList['gps'].values.tolist(), centroids)\n", "display(TotalList)" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:15:48.627782Z", - "start_time": "2023-11-07T18:15:48.618140Z" + "end_time": "2023-11-07T23:05:35.216384Z", + "start_time": "2023-11-07T23:05:35.206794Z" } }, "id": "a03ebde91b87fa3b" @@ -178,15 +176,17 @@ ], "source": [ "# Cluster and minimize the data\n", - "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)" + "_, routes = utils.cluster_and_optimize(TotalList, centroids, northeastern_coordinate,\n", + " time_diff=0.25, max_time=24)\n", + "\n", + "route_1_coordinates = routes[0]\n", + "route_2_coordinates = routes[1]" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:16:41.294672Z", - "start_time": "2023-11-07T18:15:48.624793Z" + "end_time": "2023-11-07T23:06:04.963804Z", + "start_time": "2023-11-07T23:05:35.213646Z" } }, "id": "ee9b3c1ecb360976" @@ -218,8 +218,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:16:41.298495Z", - "start_time": "2023-11-07T18:16:41.293559Z" + "end_time": "2023-11-07T23:06:04.981278Z", + "start_time": "2023-11-07T23:06:04.967948Z" } }, "id": "aa618161182b5b07" @@ -236,8 +236,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:16:43.656626Z", - "start_time": "2023-11-07T18:16:41.303093Z" + "end_time": "2023-11-07T23:06:07.185941Z", + "start_time": "2023-11-07T23:06:04.976840Z" } }, "id": "32c485788eedd94" @@ -257,8 +257,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:16:43.676130Z", - "start_time": "2023-11-07T18:16:43.661970Z" + "end_time": "2023-11-07T23:06:07.206851Z", + "start_time": "2023-11-07T23:06:07.193514Z" } }, "id": "49dba1f17ca8337e" @@ -269,8 +269,8 @@ "outputs": [ { "data": { - "text/plain": " waypoint_index trips_index \\\n0 0 0 \n1 1 0 \n2 2 0 \n3 3 0 \n4 4 0 \n.. ... ... \n151 62 0 \n152 63 0 \n153 64 0 \n154 65 0 \n155 66 0 \n\n hint distance \\\n0 t4YsgAGHLIAAAAAAVQEAAAAAAAAwAAAAAAAAAHV0F0IAAA... 19.432511 \n1 IzYEgGw1BIASAAAArwAAADMAAACUAwAAynkIQGUkmkEXlL... 6.024489 \n2 5IgsgAqJLID7AAAAHgAAAAwAAAAIAAAAz5ffQcMBVEDFYK... 5.871835 \n3 G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8... 2.602121 \n4 gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR... 15.458439 \n.. ... ... \n151 lhgDgIkYA4BkAAAAIgEAAFoBAAAaAAAAJyAzQWNrAEI8Ax... 7.134933 \n152 MQwigFwMIoAoAAAANQAAABwAAAB-AAAAoidqQSAYl0GvUh... 11.504463 \n153 bwwigH0MIoAFAAAAEAAAAFUAAAArAAAAag0xP3921D-BFx... 8.340476 \n154 k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e... 36.240351 \n155 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.055582, 42.365251] -71.055582 42.365251 \n3 [-71.056164, 42.366918] -71.056164 42.366918 \n4 [-71.055561, 42.368861] -71.055561 42.368861 \n.. ... ... ... ... \n151 [-71.083465, 42.34194] -71.083465 42.341940 \n152 [-71.094327, 42.341231] -71.094327 42.341231 \n153 [-71.095003, 42.342001] -71.095003 42.342001 \n154 [-71.093834, 42.339096] -71.093834 42.339096 \n155 Northeastern (Inbound) [-71.090331, 42.339762] -71.090331 42.339762 \n\n route \n0 1 \n1 1 \n2 1 \n3 1 \n4 1 \n.. ... \n151 2 \n152 2 \n153 2 \n154 2 \n155 2 \n\n[156 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
2205IgsgAqJLID7AAAAHgAAAAwAAAAIAAAAz5ffQcMBVEDFYK...5.871835[-71.055582, 42.365251]-71.05558242.3652511
330G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8...2.602121[-71.056164, 42.366918]-71.05616442.3669181
440gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR...15.458439[-71.055561, 42.368861]-71.05556142.3688611
..............................
151620lhgDgIkYA4BkAAAAIgEAAFoBAAAaAAAAJyAzQWNrAEI8Ax...7.134933[-71.083465, 42.34194]-71.08346542.3419402
152630MQwigFwMIoAoAAAANQAAABwAAAB-AAAAoidqQSAYl0GvUh...11.504463[-71.094327, 42.341231]-71.09432742.3412312
153640bwwigH0MIoAFAAAAEAAAAFUAAAArAAAAag0xP3921D-BFx...8.340476[-71.095003, 42.342001]-71.09500342.3420012
154650k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e...36.240351[-71.093834, 42.339096]-71.09383442.3390962
155660DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397622
\n

156 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 61 0 \n169 62 0 \n170 63 0 \n171 64 0 \n172 65 0 \n\n hint distance \\\n0 1IwsgDuNLIBFAAAAWgEAAA8AAAAAAAAAFQP1QGa9GUI7qN... 8.262982 \n1 G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8... 2.602121 \n2 gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR... 15.458439 \n3 HpwsgCKcLIAAAAAAEgAAAAAAAAAAAAAAAAAAACg870AAAA... 39.201677 \n4 qn8sgKt_LIAfAAAAAAAAAAAAAAAAAAAA2ElcQAAAAAAAAA... 39.331841 \n.. ... ... \n168 7hAigPYQIoA2AgAAYwEAAAAAAAAAAAAAnsd7Qq9XHUIAAA... 7.478611 \n169 bwwigH0MIoAFAAAAEAAAAFUAAAArAAAAag0xP3921D-BFx... 8.340476 \n170 MQwigFwMIoAoAAAANQAAABwAAAB-AAAAoidqQSAYl0GvUh... 11.504463 \n171 k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e... 36.240351 \n172 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat lon \\\n0 [-71.053931, 42.365054] -71.053931 42.365054 \n1 [-71.056164, 42.366918] -71.056164 42.366918 \n2 [-71.055561, 42.368861] -71.055561 42.368861 \n3 [-71.062507, 42.365968] -71.062507 42.365968 \n4 [-71.064277, 42.358851] -71.064277 42.358851 \n.. ... ... ... ... \n168 [-71.096959, 42.344689] -71.096959 42.344689 \n169 [-71.095003, 42.342001] -71.095003 42.342001 \n170 [-71.094327, 42.341231] -71.094327 42.341231 \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
0001IwsgDuNLIBFAAAAWgEAAA8AAAAAAAAAFQP1QGa9GUI7qN...8.262982[-71.053931, 42.365054]-71.05393142.3650541
110G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8...2.602121[-71.056164, 42.366918]-71.05616442.3669181
220gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR...15.458439[-71.055561, 42.368861]-71.05556142.3688611
330HpwsgCKcLIAAAAAAEgAAAAAAAAAAAAAAAAAAACg870AAAA...39.201677[-71.062507, 42.365968]-71.06250742.3659681
440qn8sgKt_LIAfAAAAAAAAAAAAAAAAAAAA2ElcQAAAAAAAAA...39.331841[-71.064277, 42.358851]-71.06427742.3588511
..............................
1686107hAigPYQIoA2AgAAYwEAAAAAAAAAAAAAnsd7Qq9XHUIAAA...7.478611[-71.096959, 42.344689]-71.09695942.3446892
169620bwwigH0MIoAFAAAAEAAAAFUAAAArAAAAag0xP3921D-BFx...8.340476[-71.095003, 42.342001]-71.09500342.3420012
170630MQwigFwMIoAoAAAANQAAABwAAAB-AAAAoidqQSAYl0GvUh...11.504463[-71.094327, 42.341231]-71.09432742.3412312
171640k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e...36.240351[-71.093834, 42.339096]-71.09383442.3390962
172650DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397622
\n

173 rows × 9 columns

\n
" }, "metadata": {}, "output_type": "display_data" @@ -282,8 +282,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:16:43.691423Z", - "start_time": "2023-11-07T18:16:43.681109Z" + "end_time": "2023-11-07T23:06:07.219423Z", + "start_time": "2023-11-07T23:06:07.214064Z" } }, "id": "f231d9a35358988c" @@ -304,8 +304,8 @@ "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": 13, "metadata": {}, @@ -332,8 +332,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:16:43.877482Z", - "start_time": "2023-11-07T18:16:43.683653Z" + "end_time": "2023-11-07T23:06:07.316817Z", + "start_time": "2023-11-07T23:06:07.221200Z" } }, "id": "80fd847da2833913" @@ -356,8 +356,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "Route 1 has 87 waypoints\n", - "Route 2 has 65 waypoints\n" + "Route 1 has 105 waypoints\n", + "Route 2 has 64 waypoints\n" ] } ], @@ -371,8 +371,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:16:43.895169Z", - "start_time": "2023-11-07T18:16:43.807251Z" + "end_time": "2023-11-07T23:06:07.318988Z", + "start_time": "2023-11-07T23:06:07.297230Z" } }, "id": "f53c97acec1c2fc4" @@ -385,8 +385,8 @@ "name": "stdout", "output_type": "stream", "text": [ - "The trip will take 9.916944444444445 hours\n", - "The trip will take 9.295277777777779 hours\n" + "The trip will take 13.1925 hours\n", + "The trip will take 13.017777777777777 hours\n" ] } ], @@ -401,8 +401,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:16:46.273794Z", - "start_time": "2023-11-07T18:16:43.813481Z" + "end_time": "2023-11-07T23:06:09.735945Z", + "start_time": "2023-11-07T23:06:07.299647Z" } }, "id": "a3ec09dfb5cbb5b3" @@ -434,16 +434,19 @@ ], "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)" + "# Add a third centroid in the Financial District\n", + "centroids.append([42.356, -71.055])\n", + "_, routes = utils.cluster_and_optimize(TotalList, centroids, northeastern_coordinate, time_diff=0.3, max_time=24)\n", + "\n", + "route_1_coordinates = routes[0]\n", + "route_2_coordinates = routes[1]\n", + "route_3_coordinates = routes[2]" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:17:05.599874Z", - "start_time": "2023-11-07T18:16:46.275388Z" + "end_time": "2023-11-07T23:07:36.195528Z", + "start_time": "2023-11-07T23:06:09.732162Z" } }, "id": "bb6e00857e8175c0" @@ -472,8 +475,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:17:05.600430Z", - "start_time": "2023-11-07T18:17:05.595893Z" + "end_time": "2023-11-07T23:07:36.198703Z", + "start_time": "2023-11-07T23:07:36.194798Z" } }, "id": "e886e061f86a2118" @@ -491,8 +494,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:17:09.536438Z", - "start_time": "2023-11-07T18:17:05.601412Z" + "end_time": "2023-11-07T23:07:38.315154Z", + "start_time": "2023-11-07T23:07:36.199174Z" } }, "id": "23e4682fe9e30631" @@ -513,8 +516,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:17:09.555728Z", - "start_time": "2023-11-07T18:17:09.541352Z" + "end_time": "2023-11-07T23:07:38.325567Z", + "start_time": "2023-11-07T23:07:38.320173Z" } }, "id": "c3a5c5d6f3ac46c0" @@ -525,8 +528,8 @@ "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 31 0 \n171 32 0 \n172 33 0 \n173 34 0 \n174 35 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 e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA... 6.310267 \n171 g38hgI1_IYBOAAAAfwAAAAAAAAAAAAAAZ4ECQsbEUkIAAA... 12.789906 \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 Carmel Street [-71.100092, 42.332401] -71.100092 42.332401 \n171 Tremont Street [-71.098267, 42.332009] -71.098267 42.332009 \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
..............................
170310e38hgIUAA4C6AgAAGQAAAAAAAAAAAAAA_DybQoNdJUEAAA...6.310267Carmel Street[-71.100092, 42.332401]-71.10009242.3324013
171320g38hgI1_IYBOAAAAfwAAAAAAAAAAAAAAZ4ECQsbEUkIAAA...12.789906Tremont Street[-71.098267, 42.332009]-71.09826742.3320093
172330cX8hgJF_IYA1AAAAMAAAAGcAAABOAAAATyWxQQ77nUEHMC...22.776295Alleghany Street[-71.099348, 42.33047]-71.09934842.3304703
173340s9QhgLbUIYAwAAAAkAAAAAAAAAAAAAAA2XmpQNgrgEEAAA...4.111715[-71.09454, 42.325354]-71.09454042.3253543
174350DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397623
\n

175 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.. ... ... \n170 49 0 \n171 50 0 \n172 51 0 \n173 52 0 \n174 53 0 \n\n hint distance \\\n0 1IwsgDuNLIBFAAAAWgEAAA8AAAAAAAAAFQP1QGa9GUI7qN... 8.262982 \n1 G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8... 2.602121 \n2 gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR... 15.458439 \n3 HpwsgCKcLIAAAAAAEgAAAAAAAAAAAAAAAAAAACg870AAAA... 39.201677 \n4 LRUugHAVLoA1AAAA7wEAAKAAAADqAAAAYZa9QBEBXEIOWo... 1.865658 \n.. ... ... \n170 7hAigPYQIoA2AgAAYwEAAAAAAAAAAAAAnsd7Qq9XHUIAAA... 7.478611 \n171 bwwigH0MIoAFAAAAEAAAAFUAAAArAAAAag0xP3921D-BFx... 8.340476 \n172 MQwigFwMIoAoAAAANQAAABwAAAB-AAAAoidqQSAYl0GvUh... 11.504463 \n173 k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e... 36.240351 \n174 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat lon \\\n0 [-71.053931, 42.365054] -71.053931 42.365054 \n1 [-71.056164, 42.366918] -71.056164 42.366918 \n2 [-71.055561, 42.368861] -71.055561 42.368861 \n3 [-71.062507, 42.365968] -71.062507 42.365968 \n4 [-71.061735, 42.369195] -71.061735 42.369195 \n.. ... ... ... ... \n170 [-71.096959, 42.344689] -71.096959 42.344689 \n171 [-71.095003, 42.342001] -71.095003 42.342001 \n172 [-71.094327, 42.341231] -71.094327 42.341231 \n173 [-71.093834, 42.339096] -71.093834 42.339096 \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
0001IwsgDuNLIBFAAAAWgEAAA8AAAAAAAAAFQP1QGa9GUI7qN...8.262982[-71.053931, 42.365054]-71.05393142.3650541
110G4gsgDiILICSAwAA5gAAAOkAAAAAAAAAQljLQnyXy0Fhy8...2.602121[-71.056164, 42.366918]-71.05616442.3669181
220gIosgLaKLIDOAAAArgAAAFwBAAAAAAAAp3O3QafxmUEQiR...15.458439[-71.055561, 42.368861]-71.05556142.3688611
330HpwsgCKcLIAAAAAAEgAAAAAAAAAAAAAAAAAAACg870AAAA...39.201677[-71.062507, 42.365968]-71.06250742.3659681
440LRUugHAVLoA1AAAA7wEAAKAAAADqAAAAYZa9QBEBXEIOWo...1.865658[-71.061735, 42.369195]-71.06173542.3691951
..............................
1704907hAigPYQIoA2AgAAYwEAAAAAAAAAAAAAnsd7Qq9XHUIAAA...7.478611[-71.096959, 42.344689]-71.09695942.3446893
171500bwwigH0MIoAFAAAAEAAAAFUAAAArAAAAag0xP3921D-BFx...8.340476[-71.095003, 42.342001]-71.09500342.3420013
172510MQwigFwMIoAoAAAANQAAABwAAAB-AAAAoidqQSAYl0GvUh...11.504463[-71.094327, 42.341231]-71.09432742.3412313
173520k4chgBiIIYAKAAAAFwAAAPQDAAB_AgAAHn2aP-biHUBi6e...36.240351[-71.093834, 42.339096]-71.09383442.3390963
174530DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397623
\n

175 rows × 9 columns

\n
" }, "metadata": {}, "output_type": "display_data" @@ -538,8 +541,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:17:09.566860Z", - "start_time": "2023-11-07T18:17:09.558481Z" + "end_time": "2023-11-07T23:07:38.333653Z", + "start_time": "2023-11-07T23:07:38.322616Z" } }, "id": "17a8cc8fed5450a6" @@ -560,8 +563,8 @@ "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": 21, "metadata": {}, @@ -581,15 +584,15 @@ " 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", + "\n", "# Display the map\n", "m" ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:17:09.664747Z", - "start_time": "2023-11-07T18:17:09.566588Z" + "end_time": "2023-11-07T23:07:38.444061Z", + "start_time": "2023-11-07T23:07:38.336503Z" } }, "id": "702adaec008a6ec8" @@ -612,9 +615,9 @@ "name": "stdout", "output_type": "stream", "text": [ - "Route 1 has 57 waypoints\n", - "Route 2 has 78 waypoints\n", - "Route 3 has 34 waypoints\n" + "Route 1 has 61 waypoints\n", + "Route 2 has 56 waypoints\n", + "Route 3 has 52 waypoints\n" ] } ], @@ -630,8 +633,8 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:17:09.666099Z", - "start_time": "2023-11-07T18:17:09.634214Z" + "end_time": "2023-11-07T23:07:38.445284Z", + "start_time": "2023-11-07T23:07:38.401884Z" } }, "id": "4106acf2adad01d7" @@ -644,9 +647,9 @@ "name": "stdout", "output_type": "stream", "text": [ - "The trip will take 9.175 hours\n", - "The trip will take 8.926111111111112 hours\n", - "The trip will take 9.533333333333333 hours\n" + "The trip will take 9.394444444444444 hours\n", + "The trip will take 8.852777777777778 hours\n", + "The trip will take 9.325555555555555 hours\n" ] } ], @@ -665,25 +668,308 @@ "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:17:15.097884Z", - "start_time": "2023-11-07T18:17:09.637760Z" + "end_time": "2023-11-07T23:07:40.521741Z", + "start_time": "2023-11-07T23:07:38.405889Z" } }, "id": "c58106faf0fc7f4e" }, + { + "cell_type": "markdown", + "source": [ + "# 10 ROUTES (because I can)" + ], + "metadata": { + "collapsed": false + }, + "id": "4068a0b6460f19ab" + }, { "cell_type": "code", - "execution_count": 23, + "execution_count": 24, + "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", + "# Add seven more centroids around Boston with different latitudes and longitudes\n", + "for i in range(7):\n", + " centroids.append([42.365 + i * 0.01, -71.054 + i * 0.01])\n", + "\n", + "_, routes = utils.cluster_and_optimize(TotalList, centroids, northeastern_coordinate, time_diff=0.5, max_time=24)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T23:09:18.376367Z", + "start_time": "2023-11-07T23:07:40.529888Z" + } + }, + "id": "5995d6556f940e67" + }, + { + "cell_type": "markdown", + "source": [ + "## Create JSON" + ], + "metadata": { + "collapsed": false + }, + "id": "8c6f5aeb5e6c2832" + }, + { + "cell_type": "code", + "execution_count": 25, "outputs": [], - "source": [], + "source": [ + "# Create a JSON request for the API\n", + "# This is the data we want to get from the API\n", + "route_strings = []\n", + "for route in routes:\n", + " route_strings.append(utils.list_to_string(route))" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T23:09:18.395941Z", + "start_time": "2023-11-07T23:09:18.378652Z" + } + }, + "id": "375b090921cab03e" + }, + { + "cell_type": "code", + "execution_count": 26, + "outputs": [], + "source": [ + "# Create a dataframe from the JSON\n", + "dfs = []\n", + "for i in range(len(routes)):\n", + " dfs.append(utils.create_json_df(route_strings[i], utils.list_to_string([centroids[i]]), northeastern_coordinate))\n", + " \n", + "# Concatenate the dataframes\n", + "df = pd.concat(dfs, ignore_index=True)" + ], "metadata": { "collapsed": false, "ExecuteTime": { - "end_time": "2023-11-07T18:17:15.098169Z", - "start_time": "2023-11-07T18:17:15.094392Z" + "end_time": "2023-11-07T23:09:21.149586Z", + "start_time": "2023-11-07T23:09:18.384347Z" } }, - "id": "a2f10e3152b95a69" + "id": "74f619c6df3bd6c4" + }, + { + "cell_type": "code", + "execution_count": 30, + "outputs": [ + { + "name": "stderr", + "output_type": "stream", + "text": [ + "/var/folders/8b/9mzlkxlx3zx9nmpy8prjpmm80000gn/T/ipykernel_42497/2886398449.py:3: SettingWithCopyWarning: \n", + "A value is trying to be set on a copy of a slice from a DataFrame\n", + "\n", + "See the caveats in the documentation: https://pandas.pydata.org/pandas-docs/stable/user_guide/indexing.html#returning-a-view-versus-a-copy\n", + " df['route'].iloc[i * len(routes[i]):(i + 1) * len(routes[i])] = i + 1\n" + ] + } + ], + "source": [ + "# Add columns for the route number\n", + "for i in range(len(routes)):\n", + " df['route'].iloc[i * len(routes[i]):(i + 1) * len(routes[i])] = i + 1" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T23:10:17.312994Z", + "start_time": "2023-11-07T23:10:17.307208Z" + } + }, + "id": "488924ebe78c61aa" + }, + { + "cell_type": "code", + "execution_count": 31, + "outputs": [ + { + "data": { + "text/plain": " waypoint_index trips_index \\\n0 0 0 \n1 1 0 \n2 2 0 \n3 3 0 \n4 4 0 \n.. ... ... \n184 11 0 \n185 12 0 \n186 13 0 \n187 14 0 \n188 15 0 \n\n hint distance \\\n0 1IwsgDuNLIBFAAAAWgEAAA8AAAAAAAAAFQP1QGa9GUI7qN... 8.262982 \n1 LRUugHAVLoA1AAAA7wEAAKAAAADqAAAAYZa9QBEBXEIOWo... 1.865658 \n2 lM4AgM3LAIAEAAAAHAAAAJEAAAC_AgAAyLv6PxJ7NEGyPn... 2.242639 \n3 ZQ0fgPINH4AgAAAAEQAAAFEAAAAqAAAArYRYQRHu20BfWQ... 48.627645 \n4 HR8ugIJiBICVAQAARwAAAAAAAACLAAAAQ1M0Qu3l-EAAAA... 0.645763 \n.. ... ... \n184 -2EugABiLoCcAQAAigAAAAAAAAAAAAAAMQI3QqZ0dUEAAA... 7.363621 \n185 VSIfgAYjH4AUAAAAAAAAACUBAADDAAAAaIcPQAAAAADYBw... 18.888832 \n186 0OEhgPvhIYADAAAABgAAAA8AAAA0AAAA2lq-PipQFD-Y-N... 2.009578 \n187 C-AhgGbgIYBZAAAAMQAAAAAAAABqAAAAj5QfQS1zq0AAAA... 4.887502 \n188 DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA... 0.236958 \n\n name location lat \\\n0 [-71.053931, 42.365054] -71.053931 \n1 [-71.061735, 42.369195] -71.061735 \n2 Miller's River Littoral Way [-71.065634, 42.371832] -71.065634 \n3 [-71.06828, 42.369868] -71.068280 \n4 [-71.094764, 42.377355] -71.094764 \n.. ... ... ... \n184 [-71.102659, 42.382131] -71.102659 \n185 [-71.110851, 42.374259] -71.110851 \n186 [-71.085166, 42.349997] -71.085166 \n187 [-71.091358, 42.348977] -71.091358 \n188 Northeastern (Inbound) [-71.090331, 42.339762] -71.090331 \n\n lon route \n0 42.365054 1 \n1 42.369195 1 \n2 42.371832 1 \n3 42.369868 4 \n4 42.377355 1 \n.. ... ... \n184 42.382131 10 \n185 42.374259 6 \n186 42.349997 6 \n187 42.348977 6 \n188 42.339762 6 \n\n[189 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
0001IwsgDuNLIBFAAAAWgEAAA8AAAAAAAAAFQP1QGa9GUI7qN...8.262982[-71.053931, 42.365054]-71.05393142.3650541
110LRUugHAVLoA1AAAA7wEAAKAAAADqAAAAYZa9QBEBXEIOWo...1.865658[-71.061735, 42.369195]-71.06173542.3691951
220lM4AgM3LAIAEAAAAHAAAAJEAAAC_AgAAyLv6PxJ7NEGyPn...2.242639Miller's River Littoral Way[-71.065634, 42.371832]-71.06563442.3718321
330ZQ0fgPINH4AgAAAAEQAAAFEAAAAqAAAArYRYQRHu20BfWQ...48.627645[-71.06828, 42.369868]-71.06828042.3698684
440HR8ugIJiBICVAQAARwAAAAAAAACLAAAAQ1M0Qu3l-EAAAA...0.645763[-71.094764, 42.377355]-71.09476442.3773551
..............................
184110-2EugABiLoCcAQAAigAAAAAAAAAAAAAAMQI3QqZ0dUEAAA...7.363621[-71.102659, 42.382131]-71.10265942.38213110
185120VSIfgAYjH4AUAAAAAAAAACUBAADDAAAAaIcPQAAAAADYBw...18.888832[-71.110851, 42.374259]-71.11085142.3742596
1861300OEhgPvhIYADAAAABgAAAA8AAAA0AAAA2lq-PipQFD-Y-N...2.009578[-71.085166, 42.349997]-71.08516642.3499976
187140C-AhgGbgIYBZAAAAMQAAAAAAAABqAAAAj5QfQS1zq0AAAA...4.887502[-71.091358, 42.348977]-71.09135842.3489776
188150DoUhgBeFIYCcAAAAJgAAAAAAAAARAAAAm0CKQdkZiEAAAA...0.236958Northeastern (Inbound)[-71.090331, 42.339762]-71.09033142.3397626
\n

189 rows × 9 columns

\n
" + }, + "metadata": {}, + "output_type": "display_data" + } + ], + "source": [ + "# Display the dataframe\n", + "display(df)" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T23:10:19.393773Z", + "start_time": "2023-11-07T23:10:19.390813Z" + } + }, + "id": "8e436ba5d3949420" + }, + { + "cell_type": "markdown", + "source": [ + "## Map" + ], + "metadata": { + "collapsed": false + }, + "id": "1552586cb84a48c5" + }, + { + "cell_type": "code", + "execution_count": 37, + "outputs": [ + { + "data": { + "text/plain": "", + "text/html": "
Make this Notebook Trusted to load map: File -> Trust Notebook
" + }, + "execution_count": 37, + "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', 'orange', 'purple', 'pink', 'black', 'gray', 'brown', 'yellow']\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-07T23:13:22.619199Z", + "start_time": "2023-11-07T23:13:22.527566Z" + } + }, + "id": "4305c6981e48e87f" + }, + { + "cell_type": "markdown", + "source": [ + "## Results" + ], + "metadata": { + "collapsed": false + }, + "id": "4723f2f26efe49d3" + }, + { + "cell_type": "code", + "execution_count": 36, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "Route 1 has 20 waypoints\n", + "Route 2 has 10 waypoints\n", + "Route 3 has 28 waypoints\n", + "Route 4 has 1 waypoints\n", + "Route 5 has 15 waypoints\n", + "Route 6 has 37 waypoints\n", + "Route 7 has 18 waypoints\n", + "Route 8 has 16 waypoints\n", + "Route 9 has 10 waypoints\n", + "Route 10 has 14 waypoints\n" + ] + } + ], + "source": [ + "# Get the number of waypoints for each route\n", + "route_waypoints = []\n", + "for route in routes:\n", + " route_waypoints.append(len(route))\n", + "for i in range(len(route_waypoints)):\n", + " print(\"Route {} has {} waypoints\".format(i + 1, route_waypoints[i]))" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T23:12:32.990935Z", + "start_time": "2023-11-07T23:12:32.987254Z" + } + }, + "id": "5887f93dd890bc77" + }, + { + "cell_type": "code", + "execution_count": 34, + "outputs": [ + { + "name": "stdout", + "output_type": "stream", + "text": [ + "The trip will take 3.1816666666666666 hours\n", + "The trip will take 3.8113888888888887 hours\n", + "The trip will take 3.9852777777777777 hours\n", + "The trip will take 3.8975 hours\n", + "The trip will take 4.088611111111111 hours\n", + "The trip will take 4.039444444444444 hours\n", + "The trip will take 3.17 hours\n", + "The trip will take 3.209722222222222 hours\n", + "The trip will take 4.1275 hours\n", + "The trip will take 3.2069444444444444 hours\n" + ] + } + ], + "source": [ + "# Get the trip time for each route\n", + "trip_hrs = []\n", + "for i in range(len(routes)):\n", + " trip_hrs.append(utils.get_trip_time(route_strings[i], route_waypoints[i], utils.list_to_string([centroids[i]]),\n", + " northeastern_coordinate))\n", + "for i in range(len(trip_hrs)):\n", + " print(\"The trip will take {} hours\".format(trip_hrs[i]))" + ], + "metadata": { + "collapsed": false, + "ExecuteTime": { + "end_time": "2023-11-07T23:11:11.477373Z", + "start_time": "2023-11-07T23:11:08.172393Z" + } + }, + "id": "3a4b529fc3f2b336" + }, + { + "cell_type": "code", + "execution_count": null, + "outputs": [], + "source": [], + "metadata": { + "collapsed": false + }, + "id": "a4cf5509f890423a" } ], "metadata": { diff --git a/utils.py b/utils.py index a4b789d..aeaf7ab 100644 --- a/utils.py +++ b/utils.py @@ -5,161 +5,30 @@ import requests from sklearn.cluster import KMeans -def cluster_and_minimize_2(df, centroids, norm_centroids, end, time_diff, max_time=24, n=2): - # Cluster the coordinates - kmeans = KMeans(n_clusters=len(norm_centroids), init=norm_centroids) - kmeans.fit(df['normalized_gps'].values.tolist()) - - df['cluster'] = kmeans.labels_ - centroid_1 = list_to_string([centroids[0]]) - centroid_2 = list_to_string([centroids[1]]) - - # Return the list of locations in each cluster - route_1 = df[df['cluster'] == 0] - route_2 = df[df['cluster'] == 1] - - 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) - - # Remove waypoints from the longest route until the trip time is less than the max time - route_1_coordinates = __remove_longest_waypoints__(route_1_coordinates, centroid_1, end, max_time) - route_2_coordinates = __remove_longest_waypoints__(route_2_coordinates, centroid_2, end, max_time) - - # 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 - - return df, route_1_coordinates, route_2_coordinates - +def cluster_and_optimize(df, centroids, end, time_diff=0.25, max_time=24, n=2): + # Create a new column with normalized gps coordinates and centroids + df['normalized_gps'], norm_centroids = __normalize_gps(df['gps'].values.tolist(), centroids) -def minimize_route_time_diff(route_1_coordinates, route_2_coordinates, route_1_start, route_2_start, end, - 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 - """ - # 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) - - # Find the average trip time - average_time = (route_1_time + route_2_time) / 2 - - # Define a list of all times and route coordinates - times = [route_1_time, route_2_time] - routes = [route_1_coordinates, route_2_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[1]] - 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[1]], routes[sorted_indices[0]]) - routes[sorted_indices[1]].remove(closest_coordinate) - routes[sorted_indices[0]].append(closest_coordinate) - - # Recursively call the function - return minimize_route_time_diff(routes[0], routes[1], route_1_start, route_2_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] - - -# Create a function to minimize the time difference between three routes -def cluster_and_minimize_3(df, centroids, norm_centroids, end, time_diff, max_time=24, 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]]) + routes = [] + starts = [] + for i in range(len(centroids)): + routes.append(df[df['cluster'] == i]['gps'].values.tolist()) + starts.append(list_to_string([centroids[i]])) - # Return the list of locations in each cluster - route_1 = df[df['cluster'] == 0] - route_2 = df[df['cluster'] == 1] - route_3 = df[df['cluster'] == 2] - - # Minimize the time difference between the routes - 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) + routes = __minimize_route_time_diff(routes, starts, end, time_diff, n) # Remove waypoints from the longest route until the trip time is less than the max time - route_1_coordinates = __remove_longest_waypoints__(route_1_coordinates, centroid_1, end, max_time) - route_2_coordinates = __remove_longest_waypoints__(route_2_coordinates, centroid_2, end, max_time) - route_3_coordinates = __remove_longest_waypoints__(route_3_coordinates, centroid_3, end, max_time) - - # 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 __remove_longest_waypoints__(route_coordinates, start, end, max_time): - """ - Takes a list of lists of coordinates and returns a list of lists of coordinates that is the same length as the - original list but has a trip time less than the max time - """ - # Find the trip time for the route - route_time = get_trip_time(list_to_string(route_coordinates), len(route_coordinates), start, end) - - # If the trip time is greater than the max time, remove the waypoint with the longest distance from the mean - if route_time > max_time: - route_mean = __mean_center__(route_coordinates) - furthest_coordinate = __find_farthest_coordinate__(route_coordinates, route_mean) - route_coordinates.remove(furthest_coordinate) + for i in range(len(routes)): + routes[i] = __remove_longest_waypoints(routes[i], starts[i], end, max_time) + df.loc[df['gps'].astype(str).isin(map(str, routes[i])), 'cluster'] = i - return __remove_longest_waypoints__(route_coordinates, start, end, max_time) - - return route_coordinates + return df, routes def list_to_string(list_of_lists): @@ -193,7 +62,7 @@ def create_json_df(coordinate_string, start, end): return df -def get_trip_time(coordinate_string, num_waypoints, start, end): +def get_trip_time(coordinate_string, num_waypoints, start, end, time_per_waypoint=90): """ Takes a list of lists of coordinates and returns the time of the trip in hours """ @@ -202,14 +71,67 @@ 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 * 90 + waypoint_time_seconds = num_waypoints * time_per_waypoint total_time_hours = (travel_time_seconds + waypoint_time_seconds) / 3600 return total_time_hours -def normalize_gps(coordinates, centroids): +def __minimize_route_time_diff(routes, starts, end, + time_diff, n): + """ + Takes two routes and a time difference and returns routes that have time differences less than the time difference + """ + times = [] + + for i, route in enumerate(routes): + times.append(get_trip_time(list_to_string(route), len(route), starts[i], end)) + + # Find the average trip time + average_time = np.mean(times) + + # Sort the trip times + sorted_indices = np.argsort(times) + + # Find the difference between the longest trip time and the average trip time + time_difference = times[sorted_indices[-1]] - average_time + + # If the difference is greater than the time difference, move a coordinate from the longest route to the shortest route + if time_difference > time_diff: + # Move a coordinate from the longest route to the shortest route + closest_coordinate = __find_closest_coordinate(routes[sorted_indices[-1]], + __mean_center(routes[sorted_indices[0]])) + routes[sorted_indices[0]].append(closest_coordinate) + routes[sorted_indices[-1]].remove(closest_coordinate) + + # Recursively minimize the time difference between the routes + return __minimize_route_time_diff(routes, starts, 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 + + +def __remove_longest_waypoints(route_coordinates, start, end, max_time): + """ + Takes a list of lists of coordinates and returns a list of lists of coordinates that is the same length as the + original list but has a trip time less than the max time + """ + # Find the trip time for the route + route_time = get_trip_time(list_to_string(route_coordinates), len(route_coordinates), start, end) + + # If the trip time is greater than the max time, remove the waypoint with the longest distance from the mean + if route_time > max_time: + route_mean = __mean_center(route_coordinates) + furthest_coordinate = __find_farthest_coordinate(route_coordinates, route_mean) + route_coordinates.remove(furthest_coordinate) + + return __remove_longest_waypoints(route_coordinates, start, end, max_time) + + return route_coordinates + + +def __normalize_gps(coordinates, centroids): """ Takes a list of lists of coordinates and centroids and returns a list of lists of normalized coordinates and centroids """ @@ -230,70 +152,59 @@ def normalize_gps(coordinates, centroids): for i in coordinates: normalized_coordinates.append( - [__min_max_normalize__(i[0], min_lat, max_lat), __min_max_normalize__(i[1], min_lon, max_lon)]) + [__min_max_normalize(i[0], min_lat, max_lat), __min_max_normalize(i[1], min_lon, max_lon)]) for i in centroids: normalized_centroids.append( - [__min_max_normalize__(i[0], min_lat, max_lat), __min_max_normalize__(i[1], min_lon, max_lon)]) + [__min_max_normalize(i[0], min_lat, max_lat), __min_max_normalize(i[1], min_lon, max_lon)]) return normalized_coordinates, normalized_centroids -def __min_max_normalize__(value, min_value, max_value): +def __min_max_normalize(value, min_value, max_value): """ Takes a value, min value, and max value and returns the normalized value """ return (value - min_value) / (max_value - min_value) -# Given two clusters and their respective lists of coordinates, move one coordinate from the larger centroid to the smaller centroid -def __move_coordinate__(larger_centroid_coordinates, smaller_centroid_coordinates): - # Calculate the centroid of the smaller cluster - smaller_centroid = __mean_center__(smaller_centroid_coordinates) - - # Find the coordinate in the larger cluster that is closest to the centroid of the smaller cluster - closest_coordinate = __find_closest_coordinate__(larger_centroid_coordinates, smaller_centroid) - - return closest_coordinate - - -def __find_closest_coordinate__(coordinates, centroid): +def __find_closest_coordinate(coordinates, centroid): """ Takes a list of coordinates and a centroid and returns the coordinate in the list that is closest to the centroid """ closest_coordinate = coordinates[0] - closest_coordinate_distance = __distance__(closest_coordinate, centroid) + closest_coordinate_distance = __distance(closest_coordinate, centroid) for coordinate in coordinates: - if __distance__(coordinate, centroid) < closest_coordinate_distance: + if __distance(coordinate, centroid) < closest_coordinate_distance: closest_coordinate = coordinate - closest_coordinate_distance = __distance__(coordinate, centroid) + closest_coordinate_distance = __distance(coordinate, centroid) return closest_coordinate -def __find_farthest_coordinate__(coordinates, centroid): +def __find_farthest_coordinate(coordinates, centroid): """ Takes a list of coordinates and a centroid and returns the coordinate in the list that is furthest from the centroid """ farthest_coordinate = coordinates[0] - farthest_coordinate_distance = __distance__(farthest_coordinate, centroid) + farthest_coordinate_distance = __distance(farthest_coordinate, centroid) for coordinate in coordinates: - if __distance__(coordinate, centroid) > farthest_coordinate_distance: + if __distance(coordinate, centroid) > farthest_coordinate_distance: farthest_coordinate = coordinate - farthest_coordinate_distance = __distance__(coordinate, centroid) + farthest_coordinate_distance = __distance(coordinate, centroid) return farthest_coordinate -def __mean_center__(coordinates): +def __mean_center(coordinates): """ Takes a list of coordinates and returns the mean center of the coordinates """ return [sum([i[0] for i in coordinates]) / len(coordinates), sum([i[1] for i in coordinates]) / len(coordinates)] -def __distance__(coordinate1, coordinate2): +def __distance(coordinate1, coordinate2): """ Takes two coordinates and returns the distance between them """ -- cgit v1.2.3