Discrete Structures (ITS66204)

Group Assignment (Weightage: 30%)

Case Study Title:

Due Date: Sunday, 01 December 2024 (Week 11), 11:59 PM

Group Assignment (30%)

MLO2: Demonstrate findings and insights derived from applications of discrete structure concepts in real-world and computational science scenarios.

CASE STUDY 1: OPTIMIZING A SMART CITY TRANSPORTATION AND LOGISTICS SYSTEM

Scenario:

You are part of a team hired by a smart city initiative to optimize the city's transportation and logistics system. The goal is to improve traffic flow, reduce congestion, optimize delivery routes, and ensure efficient allocation of resources such as public transport, delivery trucks, and road space. The project will also consider the impact of uncertainty (e.g., traffic delays, accidents) in the system and develop a model to minimize disruptions.

You are required to use concepts from Set Theory, Counting Principles, Graph Theory, and Probability to develop solutions that will enhance the efficiency and reliability of the city's transportation and logistics network.

Data Sources:

For this case study, students will access real-world data from the following platforms:

Kaggle: For datasets related to traffic incidents, transportation schedules, and other logistical data. OpenStreetMap: For road network data, including distances, locations, and travel times between different parts of the city.

Government Data Portals: For publicly available datasets on traffic volumes, vehicle types, public transport schedules, and traffic conditions.

CASE STUDY 1 TASKS

Task 1: Traffic Management Using Set Theory

The smart city initiative collects traffic data from multiple sensors across the city. These data points are organized based on vehicle types, time of day, road sections, and traffic conditions.

Data Source:

Traffic data from Kaggle or government data portals, representing vehicle types and congestion levels for various roads at different times of the day.

Questions:

1. Set Operations:

a)   Represent the data as sets, where each set contains data points related to different vehicle types (e.g., cars, trucks, buses), time slots, and traffic conditions (e.g., peak hours, nonpeak hours).

b)   Perform. set operations such as union and intersection to analyze traffic patterns.

2. Cartesian Product and Relations:

a)   Define a Cartesian product of road sections and time slots. Use this to establish a relation between different road sections and the severity of traffic congestion.

Task 2: Optimizing Public Transport Scheduling (Counting Principles)

The city operates a public transport network with multiple bus routes, and the challenge is to develop an optimal schedule that minimizes wait times while ensuring buses are evenly distributed.

Data Source:

Public transport schedules from Kaggle or government data portals for bus and train services.

Questions:

1. Permutations and Combinations:

a)   Calculate the number of different ways buses can be assigned to routes given specific constraints.

2. Applications of Number Theory:

a)   Use modular arithmetic to determine optimal time intervals for bus departures on different routes.

Note: Other suitable number theory concepts can also be used with proper justification.

Task 3: Designing Delivery Routes (Graph Theory)

The city’s logistics network needs to optimize delivery routes for trucks transporting goods between distribution centers and retailers across different districts.

Data Sources:

Road network data from OpenStreetMap, including distances and travel times, and historical traffic incident data from Kaggle.

Questions:

1. Graph Representation:

a)   Represent the logistics network as a weighted graph, where nodes represent locations and edge weights represent travel distances.

2. Minimum Spanning Tree (MST):

a)  Apply graph theory algorithms to find the minimum spanning tree that optimizes the delivery network. Justify the algorithm(s) selected.

Task 4: Probability of Delays and Traffic Disruptions

The city wants to assess the probability that deliveries and public transport operations will be completed on time under uncertainties like traffic delays and road closures.

Data Sources:

Traffic incident data from Kaggle or government portals.

Questions:

1. Basic Probability:

a)   Use real-world data on traffic incidents to model the probability of delays and propose strategies to mitigate their impact.

Learning Outcome:

Students will demonstrate their ability to integrate set theory, counting principles, graph theory, and probability using real-world data from platforms like Kaggle, OpenStreetMap, and government data portals. They will apply these discrete structure concepts to optimize a smart city’s transportation and logistics system.

CASE STUDY 2: OPTIMIZING HEALTHCARE DELIVERY WITH DISCRETE STRUCTURES

Scenario:

You have been hired by a healthcare company to optimize the delivery of medical supplies and improve scheduling for mobile health units. The company operates several mobile health units that visit various clinics and rural locations, providing healthcare services. They need to ensure optimal routing for the units, efficient scheduling for patient appointments, and reliable supply chain management for medical supplies.

Data Sources:

Kaggle: Healthcare data, patient appointments, and medical supply chain data. OpenStreetMap: Geographical data for mobile unit routes between health clinics. Government Data Portals: Public healthcare statistics and travel times.

Case Study 2 Tasks

Task 1: Mobile Unit Scheduling Using Set Theory

The company wants to optimize the mobile health unit schedules to ensure they visit the maximum number of clinics in a day while considering different clinic opening hours and vehicle availability.

Data Source:

Scheduling and clinic availability data from Kaggle or government health portals.

Questions:

1. Set Operations:

a)   Define sets for clinic opening hours and vehicle availability. Use set operations (union, intersection, etc.) to determine optimal schedules for the mobile units.

Note: Provide proper justification for the selected set theory operation(s).

2. Relations:

a)   Establish a relation between the mobile units and the clinics and analyze the constraints.

Task 2: Counting Principles in Patient Appointment Scheduling

The company wants to optimize appointment schedules to minimize patient wait times and reduce congestion at clinics.

Data Source:

Appointment data and patient visit records from Kaggle.

Questions:

1. Combinations and Permutations:

a)   Determine how many different ways patient appointments can be scheduled based on clinic capacity and time slots.

2. Inclusion-Exclusion Principle:

a)  Apply the inclusion-exclusion principle to avoid overlapping appointments at clinics where multiple mobile units operate.

Task 3: Routing Medical Supplies Using Graph Theory

The healthcare company needs to optimize delivery routes for medical supplies to different clinics. Each clinic has varying demand levels and distance from the central warehouse.

Data Source:

Delivery route data from OpenStreetMap, combined with demand data from Kaggle.

Questions:

1. Minimum Spanning Tree:

a)   Use the  minimum spanning tree to optimize the routes for medical supply deliveries, ensuring minimal travel time while covering all clinics.

Note: Provide proper justification for the selected algorithm to find the minimum spanning tree.

2. Shortest Path Algorithm:

a)  Apply Dijkstra’s algorithm to find the fastest route for high priority supplies.

Note: Algorithm(s) other than Dijkstra’s may also be used with proper justification provided.

Task 4: Probability of Service Interruptions

Traffic delays and unpredictable events such as vehicle breakdowns can disrupt the mobile units’ schedules. The company wants to assess the probability of service interruptions.

Data Source:

Vehicle incident data and traffic statistics from Kaggle or government data portals.

Questions:

1. Basic Probability:

a)   Calculate the  probability that  a  mobile  unit will  be delayed due to traffic or vehicle breakdowns based on historical data.

2. Conditional Probability:

a)   Use  Bayes’  Theorem  to  determine  the  likelihood  that  a  mobile  unit  experienced  a breakdown if it arrives significantly late to a clinic.

Learning Outcome:

Students will apply set theory, counting principles, graph theory, and probability to optimize healthcare delivery, using real-world data from Kaggle, OpenStreetMap, and government  data portals.

CASE STUDY 3: MANAGING SMART WASTE COLLECTION IN A SMART CITY

Scenario:

The city is implementing a smart waste management system where garbage trucks are equipped with sensors that track the fill levels of waste containers. The goal is to minimize fuel consumption and travel  time  for  waste  collection,  optimize  the  assignment  of  trucks  to  routes,  and  manage unpredictable delays caused by traffic.

Data Sources:

Kaggle: Waste management data, including waste container fill levels. OpenStreetMap: Route data for waste collection points.

Government Data Portals: Public traffic and road incident data.

Case Study 3 Tasks

Task 1: Waste Collection Route Optimization Using Set Theory

The waste management system tracks the status of containers at various collection points. You need to assign routes to trucks based on the fill levels of containers.

Data Source:

Waste container data from Kaggle or government data portals.

Questions:

1. Set Operations:

a)   Define sets for full, nearly full, and empty containers. Use set operations to determine which containers should be prioritized for collection. Justify the selection of set operations.

2. Cartesian Product:

a)   Create a Cartesian product between collection points and truck availability and use it to assign optimal routes.

Task 2: Assigning Trucks to Routes Using Counting Principles

The city needs to assign a fleet of trucks to waste collection routes, ensuring that all full containers are collected efficiently.

Data Source:

Truck availability and route data from Kaggle.

Questions:

1. Permutations and Combinations:

a)   Calculate the number of ways trucks can be assigned to routes given constraints on truck capacity and route length.

2. Inclusion-Exclusion Principle:

a)   Use the inclusion-exclusion principle to prevent overlapping truck assignments on routes with high traffic.

Task 3: Optimizing Waste Collection Routes Using Graph Theory

The city’s road network and collection points need to be modeled as a graph to minimize travel time and fuel consumption.

Data Source:

Route data from OpenStreetMap and traffic incident data from Kaggle.

Questions:

1. Graph Representation:

a)   Model the waste collection points and routes as a graph. Use edge weights to represent travel times or fuel consumption.

2. Shortest Path:

a)  Apply the shortest path algorithm to determine the most efficient routes for trucks to minimize travel time. Justify the selection of algorithm to find the shortest path.

Task 4: Probability of Delays in Waste Collection

The city needs to factor in the probability of delays due to traffic congestion or road closures.

Data Source:

Traffic delay data from Kaggle or government traffic portals.

Questions:

3. Basic Probability:

a)   Calculate the probability that a waste collection truck will encounter delays based on traffic data.

4. Conditional Probability:

a)   Use conditional probability to model how likely it is that a truck will complete its route on time, given the current traffic conditions.

Learning Outcome:

Students will optimize a waste collection system by applying set theory, counting principles, graph theory, and probability, using real-world data from Kaggle, OpenStreetMap, and government data portals.

CASE STUDY 4: EMERGENCY RESPONSE OPTIMIZATION USING DISCRETE STRUCTURES

Scenario:

A city’s emergency response system needs to be optimized to improve response time and resource allocation. Emergency services (firefighters, police, and ambulances) are dispatched based on real- time data on incidents such as fires, accidents, and medical emergencies. The city wants to minimize response time, optimize resource allocation, and assess the probability of delays due to traffic and road closures.

Data Sources:

Kaggle: Emergency incident data and resource allocation data.

OpenStreetMap: Road network and travel time data for emergency services.

Government Data Portals: Traffic data, road closures, and real-time incident reports.

Case Study 4 Tasks

Task 1: Set Theory for Emergency Resource Allocation

The city needs to allocate emergency resources (e.g., police cars, fire trucks, and ambulances) to incidents based on their severity and location.

Data Source:

Emergency incident data from Kaggle.

Questions:

1. Set Operations:

a)   Define sets for different types of incidents (e.g., fires, accidents, medical emergencies) and available resources (e.g., fire trucks, ambulances). Use set operations with justification to allocate the appropriate resources to incidents.

2. Cartesian Product and Relations:

a)   Use  the  Cartesian  product  between  resource  availability  and  incident  locations  to determine optimal assignments.

Task 2: Counting Principles in Resource Scheduling

The city wants to optimize the number of available emergency vehicles and personnel based on historical incident data.

Data Source:

Resource allocation and incident frequency data from Kaggle.

Questions:

1. Permutations and Combinations:

a)   Calculate the different ways emergency personnel can be assigned to shifts to ensure full coverage during peak hours.

2. Inclusion-Exclusion Principle:

a)  Apply the inclusion-exclusion principle to avoid assigning too many vehicles to overlapping incidents in high-traffic areas.

Task 3: Routing Emergency Services Using Graph Theory

The city’s road network must be modeled as a graph to ensure the fastest response times for emergency services.

Data Source:

Road network data from OpenStreetMap and traffic incident data from Kaggle.

Questions:

1. Minimum Spanning Tree:

a)   Model the city’s emergency response network using a minimum spanning tree to minimize travel time between emergency stations and incident locations.

2. Shortest Path:

a)   Use Dijkstra’s algorithm to calculate the shortest path for an emergency vehicle to reach a high priority incident.

Note: Algorithm(s) other than Dijkstra’s may also be used with proper justification provided.

Task 4: Probability of Delays in Emergency Response

Traffic conditions and road closures can impact emergency response times. The city needs to estimate the probability of delays based on historical data.

Data Source:

Traffic delay data from Kaggle or government traffic portals.

Questions:

1. Basic Probability:

a)   Calculate  the  probability  of  delays  in  emergency  response  based  on  current traffic conditions and road closures.

2. Bayesian Probability:

a)   Use Bayes’ Theorem to update the probability of a delay given that an emergency vehicle has already encountered heavy traffic.

Learning Outcome:

Students will  apply  set theory,  counting  principles,  graph theory,  and  probability  to  optimize emergency  response  systems,  using  data from  Kaggle,  OpenStreetMap,  and  government data portals.