{ "info": { "author": "Suriyan Laohaprapanon, Gaurav Sood", "author_email": "suriyant@gmail.com, gsood07@gmail.com", "bugtrack_url": null, "classifiers": [ "Development Status :: 3 - Alpha", "Intended Audience :: Developers", "License :: OSI Approved :: MIT License", "Programming Language :: Python :: 2.7", "Programming Language :: Python :: 3.5", "Topic :: Scientific/Engineering :: Information Analysis", "Topic :: Software Development :: Libraries :: Python Modules", "Topic :: Utilities" ], "description": "allocator: Optimally Allocate Geographically Distributed Tasks\n==============================================================\n\n.. image:: https://travis-ci.org/soodoku/allocator.svg?branch=master\n :target: https://travis-ci.org/soodoku/allocator\n.. image:: https://ci.appveyor.com/api/projects/status/qfvbu8h99ymtw2ub?svg=true\n :target: https://ci.appveyor.com/project/soodoku/allocator\n.. image:: https://img.shields.io/pypi/v/allocator.svg\n :target: https://pypi.python.org/pypi/allocator\n\nHow can we efficiently collect data from geographically distributed locations? If the data \ncollection is being crowd-sourced, then we may want to exploit the fact that workers\nare geographically distributed. One simple heuristic to do so is to order the locations by \ndistance for each worker (with some task registration backend). If you have hired \nworkers (or rented drones) who you can send to different locations, then you must split the tasks \nacross workers (drones), and plan the 'shortest' routes for each, ala the Traveling Salesman \nProblem (TSP). This is a problem that companies like Fedex etc. solve all the time. Since there \nare no computationally feasible solutions for solving for the global minimum, one heuristic solution \nis to split the locations into clusters of points that are close to each other (ideally, \nwe want the clusters to be 'balanced'), and then to estimate a TSP solution for each cluster. \n\nThe package provides a simple way to implement these solutions. Broadly, it provides three kinds of functions:\n\n1. **Sort by Distance:** Produces an ordered list of workers for each point or an ordered list of points \n for each worker.\n\n2. **Cluster the Points:** Clusters the points into *n_worker* groups.\n\n3. **Shortest Path:** Order points within a cluster (or any small number of points) into a path or itinerary. \n\nThe package also provides access to three different kinds of distance functions for calculating the distance matrices\nthat underlie these functions: \n\n1. **Euclidean Distance:** use option ``-d euclidean``; similar to the Haversine distance within the same `UTM zone `__)\n\n2. **Haversine Distance:** use option ``-d haversine``. \n\n3. **OSRM Distance:** use option ``-d osrm``. Neither Haversine nor Euclidean distance take account of the actual road network or the traffic. To use actual travel time, use `Open Source Routing Machine API `__ A maximum number of 100 points can be passed to the function if we use the public server. However, you can set up your own private OSRM server with ``--max-table-size`` to specific the maximum number of points.\n\n4. **Google Distance Matrix API:**. use option ``-d google``. This option available in ``sort_by_distane`` and ``cluster_kahip`` only due to Google Distance Matrix API has very usage limits. Please look at the limitations `here. `__\n\nRelated Package\n^^^^^^^^^^^^^^^\nTo sample locations randomly on the streets, check out `geo_sampling `__.\n\nApplication\n^^^^^^^^^^^^^^^\nMissing Women on the streets of Delhi. See `women count `__\n\nInstall\n-------\n\n::\n\n pip install allocator\n\nFunctions\n---------\n\n1. `Sort By Distance `__\n \n2. **Cluster**\n \n Cluster data collection locations using k-means (clustering) or KaHIP (graph partitioning). To check which of the algorithms produces more cohesive, balanced clusters,\n run `Compare K-means to KaHIP `__\n \n a. `k-means `__\n\n **Examples:**\n\n ::\n\n python -m allocator.cluster_kmeans -n 10 allocator/examples/chonburi-roads-1k.csv --plot\n\n\n b. `KaHIP allocator `__\n\n\n3. **Shortest Path**\n\n These function can be used find the estimated shortest path across all the locations in a cluster. We expose three different ways of getting the 'shortest' path, a) via MST (Christofides algorithm), b) via Google OR-Tools, b) Google Maps Directions API.\n\n a. `Approximate TSP using MST `__\n\n b. `Google OR Tools TSP solver Shortest path `__\n\n c. `Google Maps Directions API Shortest path `__ \n\n d. `OSRM Trip API Shortest path `__ \n\n\nDocumentation\n-------------\n\nDocumentation available at: https://allocator.readthedocs.io/en/latest/\n\nAuthors\n-------\n\nSuriyan Laohaprapanon and Gaurav Sood\n\nContributor Code of Conduct\n---------------------------\n\nThe project welcomes contributions from everyone! In fact, it depends on\nit. To maintain this welcoming atmosphere, and to collaborate in a fun\nand productive way, we expect contributors to the project to abide by\nthe `Contributor Code of\nConduct `__.\n\nLicense\n-------\n\nThe package is released under the `MIT\nLicense `__.\n", "description_content_type": null, "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/soodoku/allocator", "keywords": "routing shortest path", "license": "MIT", "maintainer": "", "maintainer_email": "", "name": "allocator", "package_url": "https://pypi.org/project/allocator/", "platform": "", "project_url": "https://pypi.org/project/allocator/", "project_urls": { "Homepage": "https://github.com/soodoku/allocator" }, "release_url": "https://pypi.org/project/allocator/0.1.7/", "requires_dist": null, "requires_python": "", "summary": "Optimally Allocate Geographically Distributed Tasks", "version": "0.1.7" }, "last_serial": 3026165, "releases": { "0.1.6": [ { "comment_text": "", "digests": { "md5": "2bb12b73f821e7a629bde79ebf23f210", "sha256": "11bf7d622db9e23ccb29ba4548d938904fd02babf2a7746c9beaae657a2d0eb5" }, "downloads": -1, "filename": "allocator-0.1.6.tar.gz", "has_sig": false, "md5_digest": "2bb12b73f821e7a629bde79ebf23f210", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 25415352, "upload_time": "2017-07-16T01:01:52", "url": "https://files.pythonhosted.org/packages/67/19/0e5ee85d7a4d2302486d19b4b8bfa9efed2b0b79eca60c85bb6a02567040/allocator-0.1.6.tar.gz" } ], "0.1.7": [ { "comment_text": "", "digests": { "md5": "db5685b67b160695ef8791cd10314a3c", "sha256": "a0941ebd7dde324231d2204d1c53d556ce0c11cf026130bbf3f441b5dd39364d" }, "downloads": -1, "filename": "allocator-0.1.7.tar.gz", "has_sig": false, "md5_digest": "db5685b67b160695ef8791cd10314a3c", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 25418348, "upload_time": "2017-07-16T06:25:04", "url": "https://files.pythonhosted.org/packages/7a/4d/160163df199e40214f6f1939d38530c48384f9736320703896ca19aaf114/allocator-0.1.7.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "db5685b67b160695ef8791cd10314a3c", "sha256": "a0941ebd7dde324231d2204d1c53d556ce0c11cf026130bbf3f441b5dd39364d" }, "downloads": -1, "filename": "allocator-0.1.7.tar.gz", "has_sig": false, "md5_digest": "db5685b67b160695ef8791cd10314a3c", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 25418348, "upload_time": "2017-07-16T06:25:04", "url": "https://files.pythonhosted.org/packages/7a/4d/160163df199e40214f6f1939d38530c48384f9736320703896ca19aaf114/allocator-0.1.7.tar.gz" } ] }