Genetic Algorithm & Spatio-Temporal Networks: Optimization of Campus Shuttle Bus Schedule Part 3
Part 3: Python Genetic Algorithm for Extended Problem & Web App Demo
Code can be found in this GitHub repo.
In the previous post, I explained every detail regarding the theory and implementation of the Baseline Problem. Here, I am going to extend it into a scenario closer to the real-life situation and walk you through what changes in the Extended Problem. If you forgot what the extended problem is, please go back to section 3.2 of the first blog of this series.
What is different with the Extended Problem?
The extended problem is more complicated than the baseline problem in that we have three choices to go instead of two choices 0 and 1. For example, a shuttle bus at AB can choose to park at AB for an interval’s time, or go to JQ/JY, or go to PS. Then, two numbers 0 and 1 are not enough to represent three choices. Therefore, the genes become 00, 10 and 01 in the extended problem. A path chromosome now looks like 0010100000101000100000010
1101010101000000010000000010110101010001010. It still has 34 genes but in 68 digits. 00 means that the bus stays still in the same location; 10 means that the bus travels between AB and JQ/JY; 01 means that the bus travels between AB and PS. Similarly, a gene of 10 or 01 does not necessarily mean that the bus carries students. The bus might go to JQ/JY or Pusan empty in order to fulfill the huge demand at the beginning of the next interval. The rest is the same as the baseline problem.
We consider 00 to be equivalent to 0 and 10 and 01 to be equivalent to 1, so the calculation of the cost and penalties is the same as the baseline problem. However, when mutating genes, we will need to mutate the two digits together.
Python Implementation
Basically, the implementation will be two baseline problems merged together, but we need to pay special attention to checking the integrity of paths and make sure every chromosome is a path that actually makes sense.
Outcome
Here is a comparison table of all the tests I have run. Unfortunately, I have not been able to find a feasible solution given an N between 24 to 27.
But comparing the constraint violation, tests 28 and 15 are the better ones.
For each test, you should be able to see an outcome that looks like this:
Therefore, the optimized bus schedule for the extension problem according to test 28 is as follows:
Web App Demo
I used basic HTML, CSS bootstrap, and Python Flask to build a simple web App.
Thank you for reading my blog! I hope you find it helpful.
My Github: https://github.com/AlisonYao
My Kaggle: https://www.kaggle.com/alisonyao
