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.

Text LBVRP.pdf - Author Accepted Manuscript Download (634kB)

Abstract

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:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3026439