A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints

Tian Liu, Zhixing Luo, Hu Qin and Andrew Lim

European Journal of Operational Research, 2018, vol. 266, issue 2, 487-497

Abstract: In this paper, we present a branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints (2E-CVRPGC), which is a new problem deriving from the classical two-echelon capacitated vehicle routing problem (2E-CVRP) by considering grouping constraints in the second echelon. Customers in the 2E-CVRPGC are divided into several disjoint groups, and the grouping constraints ensure that customers from the same group are served by vehicles from the same satellite. We formulate the problem as a mixed 0–1 linear program and propose five families of valid inequalities to strengthen the model. Based on the model and the inequalities, we implement a branch-and-cut algorithm to solve the problem. The proposed branch-and-cut algorithm was evaluated on two classes of randomly generated instances. The computational results show that the five families of valid inequalities can substantially improve the lower bounds yielded by the LP relaxation of the model, and the branch-and-cut algorithm can solve more instances to optimality than CPLEX. We also conduct additional experiments to analyze the impacts of the grouping constraints on the problem, and illustrate the differences between the 2E-CVRPGC and the 2E-CVRP.

Keywords: Cutting; Branch and cut; Polyhedral combinatorics; Two-echelon vehicle routing (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722171730930X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:266:y:2018:i:2:p:487-497

DOI: 10.1016/j.ejor.2017.10.017

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().