Developing an efficient algorithm for robust school bus routing with heterogeneous fleet

In many real-world optimization problems, we are facing uncertainties in parameters describing the problem. In general, as a simplifying assumption, uncertainty is ignored. In the school bus routing problem, there are uncertain parameters that are assumed to have deterministic values. As a result of this simplifying assumption, the obtained solutions may be mismatched with the real world. This issue arose by violating some hard constraints.

In this research, a mixed linear integer programming for school bus routing with mixed loading by using a heterogeneous fleet is presented. The uncertainty of travel times is modeled as interval numbers. We propose a heuristic algorithm to generate extreme scenarios. Each scenario is generated in order to make the last found optimal solution into an infeasible one as much as possible.

Experimental results show that deploying this novel algorithm for generating extreme scenarios, efficiently produces diverse scenarios. After the scenario generation algorithm is converged, the intersection of the feasible optimal solutions under diverse scenarios is extracted as robust sub-tours or robust trips.

Originality/Value: 

It is the first time to apply the notions of robust optimization using the extreme scenarios generation scheme. At each iteration of the extreme scenario’s generation, the most conflicting scenario against a given optimum solution is generated. The main advantage of this method over other present robust optimization methods is its emphasis on maintaining the feasibility of the optimal solution when dealing with the most diverse set of uncertainty scenarios while keeping the computational effort needed as low as desired.