Solving the School Bus Routing Problem at Scale via a Compressed Shareability Network

摘要: We consider the classic School Bus Routing Problem (SBRP), where a fleet of school buses is used to transport students from their residences and common destination (school) subject certain constraints. The constraints that are typically imposed include maximum size, walking distance pickup point commute time for each student. SBRP special case Vehicle (VRP) with destination. propose new approach solving based on existing notion shareability network, which has been recently in context dynamic ridepooling problems. To adapt this method large-scale instances, we i) node compression network optimality guarantees, ii) heuristic-based edge technique works well practice. show compressed problem leads an Integer Linear Programming (ILP) reduced dimensionality can be solved very efficiently using off-the-shelf ILP solvers. Numerical experiments small-scale, benchmark networks evaluate performance our compare it solver metaheuristic approach.