A branch-cut-and-price algorithm for the generalized vehicle routing problem. Issue 2 (1st February 2018)

• Record Type: Journal Article
• Authors: Reihaneh, Mohammad; Ghoniem, Ahmed
• Is Part Of: Journal of the Operational Research Society. Volume 69:Issue 2(2018)
• Page Start: 307
• Page End: 318
• Publication Date: 2018-02-01
• Subjects: Generalized vehicle routing problem -- branch−cut−and−price -- dynamic programming -- column generation -- cut generation; Operations research -- Periodicals; 658.4034
• DOI: 10.1057/s41274-017-0231-6
• Languages: English
• ISSNs: 0160-5682

Abstract

Abstract: We develop a branch-cut-and-price algorithm for the generalized vehicle routing problem (GVRP)—a variant of the vehicle routing problem where customers are partitioned into mutually exclusive clusters. The decision-maker seeks to determine minimum cost routes using a limited number of vehicles such that every cluster is visited by exactly one route, and within any cluster a single customer is visited, subject to vehicle capacity constraints. The pricing subproblem is solved using a specialized dynamic programming algorithm. Computational results show that the proposed algorithm compares favorably against a state-of-the-art branch-and-cut algorithm and solves to optimality eight previously open GVRP instances in the literature.