This research explores one way of enhancing the operational efficiency of the of the Cairo Transport Authority (CTA) bus fleet (The CTA is the government agency in charge of operating the public bus network in the Greater Cairo Region). It proposes bus route allocation to depots in a way that minimizes the total dead mileage of the bus network.
Figure 1: Bus Depots in Greater Cairo
The dead mileage problem is modelled as a 0-1 assignment problem with constraints on depot capacities (Sharma and Prakash 1986). Hsu (1988) added an all or nothing constraint to the problem; all buses on the same route must be assigned to one depot. This was done to resemble real-life bus operations where depots are used for fleet management as well as vehicle storage. Prakash et. al (1999) formulate the problem as a multi-objective problem, with the objectives being 1) minimizing dead mileage, and 2) minimizing the maximum distance covered by any bus from its depot to its starting terminal. Nasibov et al. (2013) solve the dead mileage problem for the bus transport system of Izmir by removing depot capacity constraints to show which depots could be expanded to reduce dead mileage.
The problem is solved using the all or nothing constraint proposed by Hsu (1988). One alteration is that this constraint is applied on a trip level, not a route level (trip here is defined as one leg of a route).
Figure 2: Potential benefit of trip level constraint (right) over route-level constraint (left)
The detailed report can be viewed here
Pure binary assignment problems (variables must be integers; 0 or 1) are known to be NP- Complete (Floudas 1995). If n variables are each assigned one of 2 integer values, there are 2n solutions. Finding the exact solution by enumerating all possible solutions is prohibitively time consuming and so approximation algorithms are used (Vazirani 2001). This problem is solved using the Gurobi Solver (Gurobi Optimization, LLC 2019) which utilizes the branch and bound algorithm. This algorithm is able to cover all solutions even though it evaluates only a fraction of them.
The problem is solved using cvxpy, leveraging Gurobi, a powerful but proprietary mathematical optimization solver which has a free academic license. The problem formulation is in the optimization script
Solving the problem with all constraints yields a total dead mileage of 33,324 km. Removing the depot capacity constraint reduces the dead mileage by almost 2,500 km. The results show which depots could be expanded to reduce dead mileage (Imbaba, Gesr Al Suez, and Fom El-Khalig), and which depots could be closed or better utilized for other purposes (Maadi).
Figure 3: Depot Utilization with capacity constraints (left), and without capacity constraints (right)