Shortest Distance between Points using A* in Python or C++ and as a Visual Studio Solution with Output Shapefiles.
Budget: $10 – $30 AUD
The objective is to work through the dataset to identify the shortest route from a Start Point, through ALL points once and then return to the Start Point. CSV data will be provided in a basic form using ‘From’ and ‘To’ IDs and planar x,y coordinates. Optionally the solution could also process heuristic data as distance in metres from any point to any point. There is only one possible shortest route using this method.
The algorithm to be used is A* using Python or C++ in a Visual Studio Project. Once the shortest route is identified a Table field needs to be populated with a NEWID. This ID consist of consecutive integers starting from the start point 0 and finishing at the start/finish point. The range of values is limited to the range of the original ID values (e.g. 0-100 for 101 points). If the fixed start point = 0 then 1,2,3,4,5,6,7,8,..100 and back to the Start Point of 0.
While crossovers of lines may occur eg. the direct route back to the Finish Point, they should be avoided at all costs if possible. The output needs to be a CSV file with original inputs and the NEWID output. The output files are suffixed with the total distance in metres calculated eg Out_1234.csv.
The budget is low on this project as multiple A* algorithm codes exists (py or c++) and simply needs to be adapted with some lines of code for the simple CSV input and the addition of 1 column of sequential values as output from the generated array. A bonus will be considered for spatial output is using ‘Geopandas’ or equivalent to generate a projected UTM polyline shapefile of the optimal route. A UTM point layer would also be exported based on the original CSV data and the NEWID column. The project is preferred to be generated and managed in visual studio.
This is the brief. Please do not ask me what I want if you have not read and understood this project brief. This algorithm in no way uses Dijkstra or TSP. It should be fast and efficient and A*.
The algorithm to be used is A* using Python or C++ in a Visual Studio Project. Once the shortest route is identified a Table field needs to be populated with a NEWID. This ID consist of consecutive integers starting from the start point 0 and finishing at the start/finish point. The range of values is limited to the range of the original ID values (e.g. 0-100 for 101 points). If the fixed start point = 0 then 1,2,3,4,5,6,7,8,..100 and back to the Start Point of 0.
While crossovers of lines may occur eg. the direct route back to the Finish Point, they should be avoided at all costs if possible. The output needs to be a CSV file with original inputs and the NEWID output. The output files are suffixed with the total distance in metres calculated eg Out_1234.csv.
The budget is low on this project as multiple A* algorithm codes exists (py or c++) and simply needs to be adapted with some lines of code for the simple CSV input and the addition of 1 column of sequential values as output from the generated array. A bonus will be considered for spatial output is using ‘Geopandas’ or equivalent to generate a projected UTM polyline shapefile of the optimal route. A UTM point layer would also be exported based on the original CSV data and the NEWID column. The project is preferred to be generated and managed in visual studio.
This is the brief. Please do not ask me what I want if you have not read and understood this project brief. This algorithm in no way uses Dijkstra or TSP. It should be fast and efficient and A*.
Related categories:
Python
Algorithm
C++ Programming
Geographical Information System (GIS)
Visual Studio