Branch-And-Price-And-Check Model For The Vehicle Routing Problem With Location Resource Constraints

This disclosure considers a vehicle routing problem with pickup and delivery, time windows, and location resource constraints. Locations provide a number of cumulative resources that are utilized by vehicles either during service (e.g., forklifts) or for the entirety of their visit (e.g., parking bays). The problem is highly challenging from a computational standpoint as the resource constraints add temporal dependencies between vehicles and a scheduling substructure not featured in traditional vehicle routing problems. The main contribution of this disclosure is a branch-and-price-and-check model that incorporates a branch-and-price algorithm that solves the underlying vehicle routing problem, and a constraint programming subproblem that checks the feasibility of the location resource constraints, and then adds combinatorial nogood cuts to the master problem if the resource constraints are violated.