DescriptionBranch-And-Price-And-Check Model For The Vehicle Routing Problem With Location Resource Constraints
Abstract: 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.
US20180268371A1 - United States
|Period||20 Sep 2018|
|Held at||The Regents of the University of Michigan, United States of America|
|Degree of Recognition||National|