Capacity Optimization Heuristic for Bus Transportation Problem
According to Investopedia[1],
A heuristic, or heuristic technique, is any approach to problem-solving that uses a practical method or various shortcuts in order to produce solutions that may not be optimal but are sufficient given a limited timeframe or deadline.
In some climes, a heuristic is considered an algorithm i.e. they are used interchangeably. However, they differ in the sense that the latter refers to a step-by-step technique for addressing a specific problem in a finite number of steps. Moreover, given the same input parameters, an algorithm’s outcome is predictable and reproducible; while, the former(heuristic), is an educated guess, using trial and error or rule of thumb, that serves as a starting point for further investigation[2]. There is a whole lot about heuristics given the numerous research books and journal publications.
Case Study
We’ve all taken a bus at one time or the other. Isn’t it? Well, in this case study, a heuristic method is used to solve an interesting but non-trivial problem as described in the following statement. For in-depth discussions on the theoretical basis, the reader can refer to optimal transportation with capacity constraints[3]
Problem Statement
There is a popular bus stop where buses of various sizes arrive to pick up commuters, daily. Due to the varying sizes, the seating capacity and the maximum weight the bus can hold varies with the size of the bus. At the bus stop, there is usually a queue of people of different weights waiting for the bus.
The following are the underlying assumptions:
- All the buses are heading to the same destination
- The number of people waiting at the bus stop can vary
Solution Approach
In operations research, this problem type can be regarded as a capacity optimization problem[4] — in which the primary solution approach requires some form of data deduplication and data compression as often used in disk and data storage (capacity) optimization.
Our solution steps are outlined as follows:
Step 1: Create the objective function and constraints definitions
Step 2: Implement the capacity optimization heuristic
Step 3: Set up the test case function
The heuristic returns feasible solutions for each test case in the test suite:
Reference
- Chen(2021), “Heuristics” https://www.investopedia.com/terms/h/heuristics.asp.
Accessed Dec 30, 2021 - “Comparison of algorithms and heuristics”. https://www.bioinformatics.org/wiki/Comparison_of_algorithms_and_heuristics. Accessed Dec 30, 2021
- Korman J, and McCann R.(2014) “Optimal transportation with capacity constraints”. https://www.ams.org/journals/tran/2015-367-03/S0002-9947-2014-06032-7/S0002-9947-2014-06032-7.pdf. Accessed Dec 30, 2021
- “Capacity optimization”. https://en.wikipedia.org/wiki/Capacity_optimization. Accessed Dec 30, 2021
