There are 10 bus routes in the city. 50 trips by the buses need to be made. We have 6 buses. We know that at any given point, no more than 6 trips run simultaneously. We need to allocate the 6 buses to the 50 trips such that utilization of the buses is maximized. We want to minimize the idle time of buses.
We want to identify the bus that needs to be deployed for each trip. Can this be modeled as a Linear/Integer/Mixed Integer-Linear Problem? If so, how do we model the above problem?
If not, what technique needs to be used?
Regards
This is called the Vehicle Routing Problem (VRP), probably with time windows (VRPTW). In normal VRPTW, a customer has 1 location (and a service duration). In this VRPTW, a bustrip (= the customer in original VRPTW) has a different arrival and departure point (and a long service duration), so you're basically planning the routes between the busstrips (= customers in original VRPTW).
There are several ways to solve this, see for example my video of solving VRPTW with an open source metaheuristics framework. IIRC, the academic Roadef Challenge of 2010 or 2008 had such a bus scheduling problem. You'll probably find a good list of papers around that to detail which algo's work well.