A branch-and-price-and-check model for the vehicle routing problem with location congestion

Edward Lam, Pascal Van Hentenryck

Research output: Contribution to journalArticleResearchpeer-review

10 Citations (Scopus)

Abstract

This paper considers a vehicle routing problem with pickup and delivery, time windows and location congestion. 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). Locations can become congested if insufficient resources are available, upon which vehicles must wait until a resource becomes available before proceeding. The problem is challenging from a computational standpoint since it incorporates the vehicle routing problem and the resource-constrained project scheduling problem. The main contribution of this paper is a branch-and-price-and-check model that uses 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. Experimental results show the benefits of the branch-and-price-and-check approach.

Original languageEnglish
Pages (from-to)394-412
Number of pages19
JournalConstraints
Volume21
Issue number3
DOIs
Publication statusPublished - Jul 2016
Externally publishedYes

Keywords

  • Synchronization
  • Vehicle routing problem

Cite this