Transit Optimizer

A Java-based tool to optimize transit routes by considering time, fare, and capacity constraints. It computes capacity-aware shortest paths for origin-destination (OD) pairs using a graph-based Dijkstra algorithm.

Features

• Build a transit network from segments and routes.
• Compute optimal paths for multiple OD pairs.
• Dynamic capacity-aware cost calculation combining:
  • Travel time
  • Fare (weighted)
  • Capacity penalties for full segments
• Greedy flow assignment of passengers respecting segment capacities.
• Prints estimated time, average fare, and assigned passengers for each OD pair.

---

## Example Input
Enter number of Segments (S), Routes (R), and OD pairs (P):
3 2 1

Enter details for 3 segments:
(Format: segmentId from to time capacity fare)
A O1 O2 10 100 5.0
B O2 O3 15 50 3.0
C O1 O3 30 200 10.0

Enter details for 2 routes:
(Format: routeId numOfSegments segmentId1 segmentId2 ...)
Route1 2 A B
Route2 1 C

Enter 1 Origin-Destination pairs:
(Format: origin destination passengers)
01 03 50

## Example Output
Chosen route: A B
Estimated time: 25 minutes
Average fare: 8.0
Assigned passengers: 50

---

How It Works

1. Build a directed graph using input segments as edges.
2. Apply a modified Dijkstra algorithm:
   • Edge cost = travel time + (fare × weight) + capacity penalty
3. Greedily assign passengers along the chosen path.
4. Update remaining capacities dynamically to avoid overbooking.

Improvements & Future Work

• Implement min-cost max-flow for global OD optimization.
• Add transfer penalties at nodes.
• Integrate real-time data via APIs.
• Support multi-modal transit (e.g., walking, buses, trains).
• Add JUnit tests and input validation.
• Consider BigDecimal for precise fare calculation.
• Build a web API using Spring Boot for visualization.

How to Run

1. Clone the repository.
2. Compile the Java file:

javac TransitOptimizer.java