The Regents of the University of Michigan (External organisation)

  • Pascal Van Hentenryck (Inventor)
  • Lam, E. (Inventor)

Activity: Industry, Government and Philanthropy Engagement and PartnershipsPatentsPatent

Description

Branch-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
Period20 Sep 2018
Held atThe Regents of the University of Michigan, United States of America
Degree of RecognitionNational