Implemented a Google Maps prototype that provides the shortest route in terms of distance, the fastest route, the route with the fewest turns, and a scenic route that avoids roads when provided a source and destination. The algorithms used were DFS, BFS, A*, and Iterative Depth First Search.
Set of Valid states: Set of all probable segments which has routes in road-segments file.Successor Function: Set of all possible segments has route from city1 which consists of parameters such as distance,speedlimit,city1,city2,highwayname
After generating all the successor routes we calculate the heuristic_score and cost_function for specified cost_attribute.
Cost Function: We have four cost functions such as:
- Segments:The cost for this is uniform 1 since we have only one edge from city1 to city2.
- Distance: The cost for this is the distance between city1 and city2 which is specified in road-segments file.
- Time: The cost for this is the time taken to travel from city1 to city2 which is evaluated by distance divided by speed_limit provided in road-segmensts file.
-
Delivery: The cost for this is the time taken to deliver a product from city1 to city2. This will be evaluated by following conditions.
- If the speed_limit is above 50 then there is 5% chance of falling out of the truck and the product gets damaged. So, while using this the probability of mistake is calculated as tanh(distance/1000)
- So the time taken would incrase by two times because he has to go back to start city and pick the product.
- If the speed_limit is less than 50 then there is no extra time_taken to deliver the product.
Goal State: Reaching end city on shortest possible cost function which will be specified by the user.
Initial State: Initial state is the start city provided by the user.
Heuristic Functions: Finding distance using latitude and longitude from current city to destination city which are provided in city-gps file. For some of the cities, langitudes and longitudes are missing so for the city which is missing we are considering the heuristic score of the previous city and adding to to the current path distance which will be used as current city's heuristic score.
Implemented using A* algorithm with an heuristic and specified cost function.
- Intially by using pandas module loading all the data from specified files to get road-segments and gps details and converting them to lists for better accessing. As mentioned, including the bidirectional condition as well.
- Calculating the time taken for all segments and mistakes for delivery cost function and adding to the list.
- Adding the start city into the frontier(fringe)
- Maintaing explored routes which is empty at the initial point.
- Looping till the frontier is not empty:
- Pop the latest city using heappop method in heapq module which gives the minheap board which has less f_score.
- Checking whether the board popped is the destination city. If yes, the return and print the segments, distance travelled, time taken and delivery.
- Otherwise, add this segment to explored list
- Generate all the successors segments for this current_city.
- For each successor route, calculates the F_score which is the sum of heuristic score and cost function based on cost_attribute.
- If the successor route is not in explored and not in frontier, then heappush the board into frontier with f_score of travelled route.