School Busing is quite an interesting problem in real life. For me, as an adult with no vehicle, I have to rely on public transportation. Luckily, I live near my workplace. However, for children, they might have to travel a long distance to go to school. In some cases, they have to take a bus to go to school. This is where the school busing problem comes in. The school busing problem is a classic optimization problem that involves determining the most efficient way to transport students to and from school using a limited number of buses. The goal is to minimize the total cost of transportation while ensuring that all students are picked up and dropped off on time. In this blog post, we will discuss the school busing problem and how it can be solved using heuristic algorithms.

Problem Background

Consider a school where most of the students are from rural areas so they must be bused. The buses might pick up all the students and go to the elementary school and then continue from that school to pick up more students for the high school.

A clear alternative would be to have separate buses for each school even though they would need to trace over the same routes. There are, of course, restrictions on time (no student should be in the bus more than an hour), drivers, equipment, money and so forth.

How can you set up school bus routes to optimize budget dollars while balancing the time on the bus for various school groups? Build a mathematical model that could be used by various rural and perhaps urban school districts. How would you test the model prior to implementation? Prepare a short article to the school board explaining your model, its assumptions, and its results.

Analysis

To be honest, I have come across this problem when I look for HiMCM problems which might not be highly related to residents in Macau. Therefore, I DO NOT consider the rural and suburban areas in the problem and I will focus on the urban areas. The problem is a variant of the Vehicle Routing Problem (VRP). The VRP is a classic optimization problem that involves determining the most efficient way to route a fleet of vehicles to deliver goods or services to a set of customers. The goal is to minimize the total distance traveled or the total cost of transportation while satisfying various constraints such as vehicle capacity, time windows, and customer demands.

To begin with, we need to define the problem more clearly. The problem can be formulated as follows:

• Objective: Minimize the total cost of transportation while ensuring that all students are picked up and dropped off on time.
• Decision Variables: The routes of the buses, including the sequence of stops and the time spent at each stop.
• Constraints:
  • Each bus has a limited capacity and can only pick up a certain number of students.
  • Each bus has a limited number of hours of operation per day.
  • Each student must be picked up and dropped off within a certain time window.
  • The total travel time for each student should not exceed a certain limit.
  • The buses must follow a predefined route and schedule.

Mathematical Model

To solve this problem, I would like to introduce a heuristic algorithm called Savings Algorithm. The Savings Algorithm is a simple and effective heuristic algorithm for solving the Vehicle Routing Problem (VRP). The algorithm works by identifying pairs of customers that can be served by a single vehicle, thus reducing the total distance traveled. The algorithm is based on the concept of “savings,” which represents the potential reduction in distance that can be achieved by combining two routes.

For more information about the Saving Algorithm, you may refer to the following link: VRP and the following paper: The vehicle routing problem: An overview of exact and approximate algorithms.

Brief Overview of the Savings Algorithm:

1. Concept of Savings:

The core idea of the Savings Algorithm is to measure how much we can “save” by combining two routes. In the context of our school bus routing problem:

• Suppose we have two stops $i$ and $j$, both assigned to the same school $S$.
• Initially, we might have two separate routes: ($S \rightarrow i \rightarrow S$) and ($S \rightarrow j \rightarrow S$).
• If we combine these into one route ($S \rightarrow i \rightarrow j \rightarrow S$), we save the distance:
• $\text{Saving} = d(i,S) + d(j,S) - d(i,j)$
• Where $d(x,y)$ is the distance between points $x$ and $y$.

1. Algorithm Steps:
   • Step 1: Initialization: Create an initial solution where each stop is served by a separate route (i.e., $S \rightarrow \text{stop} \rightarrow S$ for each stop).
   • Step 2: Compute Savings
     • For each pair of stops $(i, j)$ assigned to the same school, calculate the saving: $\text{saving}(i,j) = d(i,S) + d(j,S) - d(i,j)$
     • Create a list of all these savings.
   • Step 3: Sort Savings
     • Sort the list of savings in descending order.
   • Step 4: Merge Routes
     • Starting from the top of the sorted savings list:
       • $a$. Consider the pair of stops $(i, j)$ with the highest saving.
       • $b$. If $i$ and $j$ are on different routes and combining their routes doesn’t violate any constraints (e.g., bus capacity), merge the routes.
       • $c$. Continue down the sorted list, repeating steps $a$ and $b$.
   • Step 5: Finalize Routes
     • Once all possible merges have been made, add the assigned school to each route.

Solution

For students who have ideas in Constraint Programming, you may wonder why I use heuristic algorithm instead of constraint programming. The reason is that the problem is a variant of the Vehicle Routing Problem (VRP) which is a well-known NP-hard problem. Solving the VRP optimally for large instances is computationally infeasible, so heuristic algorithms are often used to find good solutions in a reasonable amount of time. The Savings Algorithm is a simple and effective heuristic algorithm that can be used to solve the VRP and its variants.

Therefore, one may simply use Python to solve this problem. The following code is the implementation of the solution to the problem.

Question 1

First we import the necessary libraries.

# Importing the required libraries
import random
import matplotlib.pyplot as plt
import networkx as nx
from collections import defaultdict

# Set the seed for reproducibility
random.seed(23)

Then we can set up the parameters for the problem.

# Problem Parameters setup
num_stops = 150 # Number of stops
num_schools = 4 # Number of schools
bus_capacity = 40 # Bus capacity for each bus

After that, we generate some random data for the problem.

# Generate random data
stops = list(range(num_stops))

schools = list(range(num_stops, num_stops + num_schools))
all_nodes = stops + schools

coordinates = {node: (random.uniform(0, 800), random.uniform(0, 800)) for node in all_nodes}
students_at_stop = {stop: random.randint(1, 10) for stop in stops}
school_assignments = {stop: random.choice(schools) for stop in stops}

When we talk about the school busing problem, we need to consider the distance between stops. Therefore, we calculate the distance between each pair of stops. One may use the Euclidean distance as the distance metric; however, I will use the Manhattan distance as the distance metric since it is more realistic in urban areas.

def calculate_distance(node1, node2):
    x1, y1 = coordinates[node1]
    x2, y2 = coordinates[node2]
    return abs(x1 - x2) + abs(y1 - y2)

distances = {(i, j): calculate_distance(i, j) for i in all_nodes for j in all_nodes}

Now we implement the Savings Algorithm to solve the school busing problem.

# Savings Algorithm
def savings_algorithm():
    # Initialize routes: one route per stop
    routes = [[stop] for stop in stops]
    
    # Calculate savings
    savings = []
    for i in stops:
        for j in stops:
            if i != j and school_assignments[i] == school_assignments[j]:
                saving = (distances[i, school_assignments[i]] + distances[j, school_assignments[j]] 
                          - distances[i, j])
                savings.append((saving, i, j))
    
    # Sort savings in descending order
    savings.sort(reverse=True)
    
    # Merge routes based on savings
    for saving, i, j in savings:
        route_i = next(route for route in routes if i in route)
        route_j = next(route for route in routes if j in route)
        
        if route_i != route_j:
            merged_route = route_i + route_j
            if (sum(students_at_stop[stop] for stop in merged_route) <= bus_capacity and
                len(merged_route) <= bus_capacity):  # Limit route length
                routes.remove(route_i)
                routes.remove(route_j)
                routes.append(merged_route)
    
    # Add school to each route
    for route in routes:
        school = school_assignments[route[0]]
        route.append(school)
    
    return routes

We run the Savings Algorithm to obtain the routes for the buses.

# Run the algorithm
routes = savings_algorithm()

We also calculate the total cost of transportation based on the routes obtained.

# Calculate total cost
total_distance = sum(sum(distances[route[i], route[i+1]] for i in range(len(route)-1)) for route in routes)
total_cost = len(routes) * 100 + total_distance  # 100 is the fixed cost per bus

We print the results of the algorithm.

# Print results
print(f"Number of routes: {len(routes)}")
print(f"Total distance: {total_distance:.2f}")
print(f"Total cost: {total_cost:.2f}")

where the output will be:

Number of routes: 22
Total distance: 39013.64
Total cost: 41213.64

We visualize the routes on a map using the networkx library.

# Plot the results
plt.figure(figsize=(32, 30))
ax = plt.gca()
ax.set_title("School Bus Routes (Saving\'s Algorithm)", fontsize=28, fontweight='bold')

## Visualize routes
G = nx.Graph()
for route in routes:
    for i in range(len(route) - 1):
        G.add_edge(route[i], route[i+1])

pos = coordinates
# Draw the graph first
nx.draw_networkx_nodes(G, pos, nodelist=stops, node_color='b', node_size=600)
nx.draw_networkx_nodes(G, pos, nodelist=schools, node_color='r', node_size=600)
nx.draw_networkx_edges(G, pos, edge_color='gray')
nx.draw_networkx_labels(G, pos, font_size=14, font_weight='bold')

# Draw the routes
colors = ['salmon', 'lightgreen', 'skyblue', 'gold', 'violet', 'orange', 'cyan', 'red', 'lime']
for i, route in enumerate(routes):
    route_edges = [(route[j], route[j+1]) for j in range(len(route)-1)]
    nx.draw_networkx_edges(G, pos, edgelist=route_edges, edge_color=colors[i % len(colors)], width=2)

plt.legend(['Stops', 'Schools', 'Routes'], fontsize=14)
plt.axis('equal')
plt.show()

The output will be a map showing the school bus routes.

Finally, we print the routes obtained by the algorithm.

# Print route details
for i, route in enumerate(routes):
    print(f"\nRoute {i+1}:")
    print(f"Stops: {route[:-1]}")
    print(f"School: {route[-1]}")
    print(f"Students: {sum(students_at_stop[stop] for stop in route[:-1])}")
    print(f"Distance: {sum(distances[route[j], route[j+1]] for j in range(len(route)-1)):.2f}")

The output will be:

Route 1:
Stops: [129, 80, 146, 113, 101, 94, 65, 37, 23]
School: 150
Students: 40
Distance: 2498.03

Route 2:
Stops: [67, 86, 147, 83, 21, 9, 56]
School: 153
Students: 39
Distance: 2698.12

Route 3:
Stops: [95, 124, 78, 48, 34, 33, 31, 55, 6]
School: 152
Students: 40
Distance: 3811.66

Route 4:
Stops: [142, 98, 73, 72, 66]
School: 151
Students: 40
Distance: 1428.20

Route 5:
Stops: [143, 141, 117, 5, 46, 8, 92, 128, 125]
School: 150
Students: 40
Distance: 2797.28

Route 6:
Stops: [123, 108, 85, 115, 4, 61]
School: 151
Students: 40
Distance: 1487.25

Route 7:
Stops: [116, 102, 81, 11, 82, 53, 24, 25, 97]
School: 152
Students: 40
Distance: 2744.30

Route 8:
Stops: [132, 122, 74, 105, 17, 52, 110]
School: 150
Students: 39
Distance: 1683.44

Route 9:
Stops: [77, 62, 60, 14, 18]
School: 150
Students: 40
Distance: 1274.11

Route 10:
Stops: [104, 47, 38, 13, 10]
School: 153
Students: 39
Distance: 973.52

Route 11:
Stops: [107, 58, 145, 119, 138, 63, 70]
School: 153
Students: 40
Distance: 1438.52

Route 12:
Stops: [135, 114, 118, 112, 42, 12]
School: 150
Students: 40
Distance: 1683.81

Route 13:
Stops: [148, 103, 45, 111, 57, 16, 49, 51, 35, 0]
School: 151
Students: 40
Distance: 2210.60

Route 14:
Stops: [89, 140, 44, 41]
School: 150
Students: 33
Distance: 1006.22

Route 15:
Stops: [149, 144, 75, 54, 69, 50, 7, 39]
School: 152
Students: 38
Distance: 1145.62

Route 16:
Stops: [133, 134, 106, 43, 27, 96, 22, 19, 100, 109]
School: 151
Students: 40
Distance: 2602.73

Route 17:
Stops: [136, 139, 121, 79, 87, 2, 64, 30]
School: 153
Students: 40
Distance: 1658.95

Route 18:
Stops: [130, 90, 99, 88, 29, 76, 71, 28]
School: 151
Students: 40
Distance: 1476.29

Route 19:
Stops: [120, 137, 15, 3, 20, 1, 59]
School: 152
Students: 28
Distance: 1085.88

Route 20:
Stops: [127, 131, 68, 40]
School: 150
Students: 35
Distance: 1676.89

Route 21:
Stops: [36, 93, 91, 32, 84]
School: 153
Students: 29
Distance: 1548.79

Route 22:
Stops: [126, 26]
School: 151
Students: 4
Distance: 83.43

Therefore, the algorithm has successfully generated the routes for the school buses, minimizing the total cost of transportation while ensuring that all students are picked up and dropped off on time.

Conclusion

In this blog post, we discussed the school busing problem and how it can be solved using heuristic algorithms. The problem involves determining the most efficient way to transport students to and from school using a limited number of buses. We introduced the Savings Algorithm, a simple and effective heuristic algorithm for solving the Vehicle Routing Problem (VRP). We implemented the algorithm in Python and used it to solve the school busing problem. The algorithm successfully generated the routes for the school buses, minimizing the total cost of transportation while ensuring that all students are picked up and dropped off on time. The results were visualized on a map using the networkx library. The Savings Algorithm is a powerful tool for solving optimization problems like the school busing problem and can be applied to a wide range of real-world problems.