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

Part 2: Genetic Algorithm for Baseline Problem (with Python Code)

Alison Yuhan Yao

Published in

CodeX

7 min readSep 26, 2021

Code can be found in this GitHub Repo.

In the last blog, I introduced Spatio-Temporal Networks for problem formulation, which pretty much covers all the theory part of this project. Here, we will move on to the last bit of theory and then implementation. More specifically, this post will show you how to use Python to code a Genetic Algorithm solution for the baseline problem (to review what the baseline problem is, please check here).

Why Genetic Algorithm?

I chose Genetic Algorithm to solve this optimization problem because of its unique advantages:

1. Genetic Algorithm requires less computational power

Since the cost of a bus can only be determined if its path is enumerated, we tried the method of Column Generation first. Column Generation enumerates all possible paths in the solution set and uses brute force search to find the optimal solution. It is like finding a needle in a haystack by checking the hay one by one until we find the needle. However, the baseline case alone already has 2 ** 34 = 17,179,869,184 paths in total and my computer does not have the hardware capacity to store all this information. We can only see a random part of the haystack, with no idea if the needle is really in this part or not, so Column Generation becomes computationally infeasible. Therefore, I turned to Genetic Algorithm, a heuristic algorithm. It starts with a randomized suboptimal solution and then evolves to get better solutions that are closer to the optimal solution over time.

2. Genetic Algorithm is unaffected by black box formulation

In an ideal case, an optimization problem has an explicit objective function that I can express in the form of 𝑓(𝑥). However, in our case, formulating the problem using an explicit form is incredibly complicated and somewhat gratuitous. The main reason is that no closed-form function dictates the relationship between operation hours and price. Therefore, I formulate the objective as a black box, meaning I do not attempt to write an explicit objective function. Similarly, there is no need to explicitly express our constraints. Therefore, our problem is expressed as below.

Our objective is to minimize the total cost of the NYU Shanghai shuttle bus fleet. Depending on the different versions of network structure, constraints are susceptible to changes. The union of all constraints includes:

Demand Constraint: The shuttle bus fleet needs to satisfy the demand of students as much as possible with a small tolerance to spare. An example is that each bus holds 50 students, and the tolerance is 3. Even if 3 students are waiting for a trip, the bus will not leave. The tolerance depends on how much the school values students’ demands.
Rush Hour Constraint: During rush hours in the morning and in the afternoon, no bus can make a trip within an interval of 30 minutes.
Max Working Hour Constraint: Each bus is operated by one bus driver only and he or she cannot work more than 4 hours consecutively.

Despite the advantages, I do need to point out that Genetic Algorithm does not guarantee optimality. Chances are that GA can be stuck in suboptimal solutions. Despite that, if the baseline problem is already so computationally demanding and the extended problem only gets worse, GA is our best strategy in comparison.

Python Implementation for Baseline Problem

Before we dive into the Python code, we need to understand how each step of GA fits into the baseline problem. I highly recommend you to learn the basics of GA before moving forward.

For the baseline problem, one path in a solution looks something like 0110010100010111110000101110001011. It has 34 genes of 0 or 1 because there are 34 intervals in total. 0 represents a bus waiting still during an interval and does not carry any students; 1 represents a bus taking a trip either from JQ to AB or from AB to JQ. Please note that a gene of 1 does not necessarily mean that the bus carries students. The bus might go to JQ empty in order to fulfill the huge demand at the beginning of the next interval. One solution has a couple of buses, so a solution will be several path chromosomes concatenated together.

After a solution chromosome is generated, a fitness score can be calculated according to a fitness function. A fitness function has two components, a total cost, and a penalty cost. For the first component, although the price of each bus needs to be negotiated with the shuttle bus company, the prices generally depend on the duration starting from the beginning to the end of bus operation. Please note that as long as a driver starts his day of work and hasn’t clocked out, all intervals marked 0 still cost money even though the bus stayed still in one place. Therefore, I used the following mathematical formula:

where x is the operation duration of a bus (unit: hours). This formula is counterintuitive in many ways, but we are just using it as a case. For example, the path chromosome 0110010100010111110000101110001011 operates 33 intervals, which is 16.5 hours, so the cost for this bus is 20 * 16.5 = 330RMB. Then, the total cost is the sum of the cost of each bus. The second component of the fitness score is the penalty for violating constraints. Depending on which version of the base function you are considering, you may have one penalty where you only enforce the demand constraint, or two constraints, or all three penalties of the demand constraint, the rush hour constraint, and the max working hour constraint. A different amount of small penalty is added to the fitness score every time a student does not get on the bus, or a driver finishes a trip in one interval during rush hours, or a driver works longer than 4 hours consecutively.

Specifically, here is how constraint violations are detected. First, for the demand constraint, the chromosome paths need to be encoded to an array of size 4 * 34 which specifies what each 0 and 1 means.

In this example, the first 1 on the left corresponds to the first column on the right, in which the one and only 1 represents that the bus goes from JQ to AB. Similarly, the rest means the same. What helps us calculate the total bus capacity is the second and third row of the array. We can then add up all the JQ to AB buses and AB to JQ buses and then times the bus capacity to compare with the demand. Second, for the rush hour constraints, we need to check each chromosome for consecutive 1’s from 7:30 to 8:30 and from 17:30 to 18:30. 10, 01, and 00 are valid during rush hours, but not 11. Third, for the max working hour constraint, we need to keep track of the number of 1’s in a row. In cases of rush hour, a 0 during the rush hour could also mean that a bus is running, so we need to take care of this special case as well. If the working duration is greater than 4 hours, it causes a penalty.

Python Code

Now we can finally get to the Python code.

One place that I deviate from a typical GA implementation is the mutation function. I tested two implementations of the mutation step in the Genetic Algorithm. The first one is the conventional implementation where each gene might mutate given a probability mutation_prob. There is no guarantee if a chromosome will be mutated or how many places a chromosome will be mutated. The second one is randomly picking a gene out of a solution chromosome to mute. The mutation is guaranteed and there could only be one mutation. I tried the second implementation in an attempt to converge the algorithm faster. And test results show that the second one is indeed better than the conventional one in many ways. Also, the second implementation is faster because it does not need to loop through every gene and determine if it would be mutated.

Comparing tests 1&2 and 3&4, given a fixed evoluation_depth, mutation version 2 has fewer constraint violations and lower final costs. Comparing tests 1&3&5, mutation version 1 does not seem to converge very well even after creating 20,000 generations. Its performance plateaus early on and is far from satisfactory compared to test 4. Therefore, the self-designed implementation of the mutation function, rather than the conventional method, performs better. And this superiority persists no matter how much one tunes the parameter mutation_prob.