Balanced Vehicle Routing: Polyhedral Analysis and Branch-and-Cut Algorithm

Bektas, T ORCID: 0000-0003-0634-144X, Gouveia, Luis, Martinez-Sykora, Antonio and Salazar-González, Juan-José
(2019) Balanced Vehicle Routing: Polyhedral Analysis and Branch-and-Cut Algorithm. European Journal of Operational Research, 273 (2). pp. 452-463.

[thumbnail of LBVRP.pdf] Text
LBVRP.pdf - Author Accepted Manuscript

Download (634kB)


This paper studies a variant of the unit-demand Capacitated Vehicle Routing Problem, namely the Balanced Vehicle Routing Problem, where each route is required to visit a maximum and a minimum number of customers. A polyhedral analysis for the problem is presented, including the dimension of the associated polyhedron, description of several families of facet-inducing inequalities and the relationship between these inequalities. The inequalities are used in a branch-and-cut algorithm, which is shown to computationally outperform the best approach known in the literature for the solution of this problem.

Item Type: Article
Uncontrolled Keywords: routing, balanced, polyhedral study, branch-and-cut algorithm
Depositing User: Symplectic Admin
Date Deposited: 19 Sep 2018 09:53
Last Modified: 19 Jan 2023 01:17
DOI: 10.1016/j.ejor.2018.08.034
Related URLs: