Genetic Algorithm & Spatio-Temporal Networks: Optimization of Campus Shuttle Bus Schedule Part 1

Part 1: Spatio-Temporal Networks for problem formulation

Alison Yuhan Yao

Published in

CodeX

6 min readSep 11, 2021

Problem Introduction

Our university has our academic building and dorms separated (miles away from each other). A large majority of students utilize the designated school shuttle buses to commute between the academic building and the dorms. We have three residence halls, two only a block away from each other and the third one far far away. Shuttle buses go back and forth between the academic building and different dorms. I was a dorm resident for three years and like most students, I am not satisfied with our bus schedule. I might wake up early but end up not catching the bus and miss my class; in fear of missing the bus, I waste a lot of time going to the parking lot early. Why can’t the bus just leave for my destination every time I get on?

It is time to take the problem into my own hands and do something useful for our student community by using what I learned in class. Sounds pretty great, right?

So I did exactly that. I formulated this vehicle scheduling problem into 4 variations of spatio-temporal networks and implemented Genetic Algorithm in Python to reduce costs for the school by up to 20% while ensuring the students’ demands are met.

Let me tell you how it’s done in this series of blogs. If you want to watch a demo or see the code, please go directly to my project GitHub.

Problem Description

Typically, a real-life problem does not fit into any model. We need to simplify the problem by making assumptions and breaking it down into smaller pieces. In our case, although there are 3 residence halls, I first start with only one, the one with the most students and also the one I lived in for 2 years. That is, my model only concerns two locations, the academic building (AB) and the Jinqiao residence hall (JQ), and ignore the two other residence halls for now. I call this version “the baseline problem”. And I make the following assumptions:

All shuttle buses commute only between JQ and AB, not other residential halls.
All shuttle buses leave from JQ or wait at JQ for the first dispatch, which means no shuttle bus leaves from AB during the first dispatch in the morning. It is consistent with real-world operations.
Shuttle bus services start from 7:00 in the morning and end at 24:00 at night (17 hours per day) on weekdays with no schedule changes on special occasions.
All shuttle buses can only travel from AB to JQ or travel from JQ to AB once in an interval of 30 minutes (30 minutes typically guarantees arrival in time). The one and only exception of the assumption above is that during rush hours, all shuttle buses require 2 intervals (1 hour) to travel to their destinations.
Every shuttle bus has one bus driver to operate. He or she cannot work more than a maximum working hour of 4 hours consecutively.

After defining “the baseline problem”, I moved on to formulating the more complicated “extended problem”, where all three residence halls (Jinqiao-JQ, Jinyang-JY, and Pusan-PS) are taken into consideration. Please note that JQ and JY are only a block away, so they basically can be viewed as the same place. Again, we make some assumptions, but here I only list the ones different from above:

All shuttle buses may commute between JQ/JY and AB or PS and AB on any day if student demand requires.
All shuttle buses leave from JQ or PS or wait at JQ or PS for the first dispatch, which means no shuttle bus leaves from AB during the first dispatch in the morning.
All shuttle buses can only travel from AB to JQ/JY or PS or travel from JQ/JY or PS to AB once in an interval T of 30 minutes (again, 30 minutes typically guarantees arrival in time). The one and only exception of the assumption above is that during rush hours, all shuttle buses require 2 intervals (1 hour) to travel to their destinations.

So, there you go, I have described the problem with words, but we still need a mathematical representation. That’s where the Spatio-Temporal Networks come in.

What is a Spatio-Temporal Network?

The spatio-temporal networks model is a graphic model that captures changes across time and space. In our case of a vehicle scheduling problem, time is more important, so a time expanded graph is what we are looking for.

Think of a time expanded graph as a Mac time machine. You see the different versions of the same directory throughout time.

A time expended graph, therefore, has multiple nodes representing the same location throughout time. For example, all nodes 1 represent the same node, but it interacts with node 2 and node 3 at different time.

In the context of our problem, all nodes 1 can represent JQ and all nodes 2 can represent AB. An arrow pointing from 1 to 1 means that the shuttle bus stays at JQ during an interval; an arrow pointing from 1 to 2 means that the shuttle bus travels from JQ to AB during an interval.

How to formulate our problem into a Spatio-Temporal Network?

3.1 Baseline Problem

Let’s first consider the most simple scenario. Apart from the first dispatch, the spatio-temporal network is a repetition of the same network structure. Every shuttle bus can travel from node n to node n+1 or node (n+1)’ within one interval T = 30 minutes. We call this version 1.0.

In reality, rush hour delays the arrival time, so we are giving the buses 2 intervals (1 hour) to commute. Version 2.0 adds a rush hour constraint and changes the network structure from 7:30 to 8:30 and from 17:30 to 18:30. An example of one of the changes is that there is no longer an arrow pointing from node 2 to node 3’. Instead, node 2 is pointing to node 4’, because it takes more than 30 minutes to go from JQ to AB during rush hours. Everywhere else remains the same as version 1.0.

3.2 Extended Problem

In the extended problem, we are going to add JY and PS nodes to the baseline problem model formulation. JY nodes are all slightly shifted to the right because it takes 3 to 5 minutes to go from JQ to JY, but the JQ-JY-AB commute is still within one interval T of 30 minutes. The PS nodes are very similar to JQ, except that PS is far away from JQ and JY, so PS is treated as separate nodes.

In reality, skipping JY or not does not make any difference in terms of shuttle bus scheduling. Bus drivers who arrive at JY first will message the other drivers whether they need to drive to JY to pick up more students. Since JY has no effect on bus schedules, we can merge JQ nodes and JY nodes to formulate the problem in a simpler way. Version 1.0 is without the rush hour constraint.