🌍 English | 🇵🇹 Português

BSc in Informatics and Computing Engineering
L.EIC016 - Algorithm Design
2024/2025

---

Collaborators 🤝

Name	Number
Bárbara Gomes	up202305089
Tomás Morais	up202304692
Tomás Silva	up202307796

Grade : 18,3

Route Planning Tool Project Report

• Class Diagram
• Dataset
• Graph - Representation of the Dataset
• Implemented Algorithms
  • Graph Generation
  • Dijkstra's Algorithm for Single Source Shortest Paths
  • Independent Route Planning
  • Restricted Route Planning
  • Environmentally-Friendly Route Planning

Class Diagram

Dataset

The dataset contains key information for representing an urban map as a graph, with intersections as nodes and street segments as edges. The driving and walking times provide weights for these edges, and the parking information at each location can be used to prioritize certain paths when considering travel routes. This dataset allows route optimization or travel time analysis, with the flexibility to handle different modes of transportation and parking considerations.

Graph - Representation of the Dataset

• The graph used to represent the dataset is composed of many nodes, each representing a different location in Porto, and edges between them representing the streets that connect the respective locations.
• To represent the two different travel times (driving and walking), each edge contains two “weight values”, one for each travel mode.
• We assume that every street is “two-way”, so between every two nodes with a connection, there are two directed edges with opposite directions.
• To check if a location has parking space (needed for some algorithms), a boolean member hasParking was added to the vertex class.

Implemented Algorithms

Graph Generation

1. A new instance of the Graph class is created.
2. File Locations.csv is opened and read.
3. For each line containing information about a specific location, a vertex is created with its attributes corresponding to the content and added to the graph.
4. File Distances.csv is opened and read.
5. For each line containing information about a street connecting two locations, the corresponding nodes are obtained and a bidirectional edge is added between them.

Time Complexity: O(V + E)

Dijkstra's Algorithm for Single Source Shortest Paths

Keep track of a set containing nodes for which the shortest path distance d(u) from the source s has already been determined:

• Start with S = {s}, setting d(s) = 0 while all other nodes have d(u) = ∞.
• Continuously select the unexplored node v with the smallest tentative distance, add it to S, and update d(v) as:
  d(v) = min(d(v), d(u) + w(u,v)) where (u,v) is an edge of the graph.
• A Mutable Priority Queue helps manage edge relaxation efficiently by prioritizing nodes with the shortest known distance.

After all iterations, the shortest path from the source node to any other node is obtained.

Time Complexity: O((V + E) log V)

Independent Route Planning

1. Source and Destination nodes are obtained from the graph based on user input.
2. Dijkstra is applied to find the shortest distances from the source node to all other nodes.
3. The desired path and corresponding traversal time are obtained from getDrivingPath (or getWalkingPath) and getDrivingDist (or getWalkingDist).
4. All nodes (except the source and destination) are removed from the graph.
5. Steps 2 and 3 are repeated to find the alternative independent route (if any exists).

Time Complexity: O(V log V + E)

Restricted Route Planning

1. Source and Destination nodes are obtained from the graph based on user input.
2. Apply restrictions:

• If IncludeNodes exist, these nodes must be included.
• If AvoidNodes exist, remove the corresponding vertices from the graph.
• If AvoidSegments exist, remove both directions of each edge to avoid.

3. Find the shortest path from Source to IncludeNode and then from IncludeNode to Destination using Dijkstra’s algorithm.
4. Calculate total driving distance and output the computed path and distance.

Time Complexity: O(N)

Environmentally-Friendly Route Planning

1. Source and Destination nodes are obtained from the graph based on user input.
2. Identify nodes with parking space.
3. Apply Dijkstra to obtain the minimum time to reach the destination from any parking node.
4. Sort parking nodes by their walking time relative to maxWalkTime and check for a valid route.
5. • If yes, select the solution with the smallest total time.
   • If no, select the two alternatives with the smallest walking time.

Time Complexity: O((V + E) log V)