Department of Economics and Business Economics

A symmetry-free polynomial formulation of the capacitated vehicle routing problem

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

In: Discrete Applied Mathematics, Vol. 296, 06.2021, p. 179-192.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Bibtex

@article{5499640d7df6488f8ec642d5f03e0947,
title = "A symmetry-free polynomial formulation of the capacitated vehicle routing problem",
abstract = "In this paper we propose a new polynomially sized formulation of the well known symmetric capacitated vehicle routing problem. Formulations of polynomial size have already been published in the academic literature for this problem, but they all possess the feature that they contain many equivalent solutions. As such, the optimal set of routes will be represented by several equivalent integer feasible solutions to the formulation, potentially leading to excessive computation times. The equivalence between solutions results from the possibility of reversing the order of visit on any route, starting and ending at the depot, without affecting feasibility or route length. In contrast, the formulation proposed in this paper eliminates the existence of equivalent integer solutions. In particular, instead of describing a route as a path starting and ending at the depot, we represent a route as two paths originating from the depot and ending at a so called peak customer on the route. Moreover, in our formulation there is only one possible peak customer for any such two paths, resulting in a unique representation of any route. Our formulation has shown very competitive computing times compared to a classical formulation of comparable size. Consequently, our formulation can be recommended in combination with the use of algebraic modeling languages for entering a formulation in its entirety into a mixed-integer linear programming solver.",
keywords = "Integer programming, Polynomial formulation, Symmetry breaking, Vehicle routing",
author = "Gadegaard, {S. L.} and J. Lysgaard",
year = "2021",
month = jun,
doi = "10.1016/j.dam.2020.02.012",
language = "English",
volume = "296",
pages = "179--192",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier BV * North-Holland",

}

RIS

TY - JOUR

T1 - A symmetry-free polynomial formulation of the capacitated vehicle routing problem

AU - Lysgaard, J.

PY - 2021/6

Y1 - 2021/6

N2 - In this paper we propose a new polynomially sized formulation of the well known symmetric capacitated vehicle routing problem. Formulations of polynomial size have already been published in the academic literature for this problem, but they all possess the feature that they contain many equivalent solutions. As such, the optimal set of routes will be represented by several equivalent integer feasible solutions to the formulation, potentially leading to excessive computation times. The equivalence between solutions results from the possibility of reversing the order of visit on any route, starting and ending at the depot, without affecting feasibility or route length. In contrast, the formulation proposed in this paper eliminates the existence of equivalent integer solutions. In particular, instead of describing a route as a path starting and ending at the depot, we represent a route as two paths originating from the depot and ending at a so called peak customer on the route. Moreover, in our formulation there is only one possible peak customer for any such two paths, resulting in a unique representation of any route. Our formulation has shown very competitive computing times compared to a classical formulation of comparable size. Consequently, our formulation can be recommended in combination with the use of algebraic modeling languages for entering a formulation in its entirety into a mixed-integer linear programming solver.

AB - In this paper we propose a new polynomially sized formulation of the well known symmetric capacitated vehicle routing problem. Formulations of polynomial size have already been published in the academic literature for this problem, but they all possess the feature that they contain many equivalent solutions. As such, the optimal set of routes will be represented by several equivalent integer feasible solutions to the formulation, potentially leading to excessive computation times. The equivalence between solutions results from the possibility of reversing the order of visit on any route, starting and ending at the depot, without affecting feasibility or route length. In contrast, the formulation proposed in this paper eliminates the existence of equivalent integer solutions. In particular, instead of describing a route as a path starting and ending at the depot, we represent a route as two paths originating from the depot and ending at a so called peak customer on the route. Moreover, in our formulation there is only one possible peak customer for any such two paths, resulting in a unique representation of any route. Our formulation has shown very competitive computing times compared to a classical formulation of comparable size. Consequently, our formulation can be recommended in combination with the use of algebraic modeling languages for entering a formulation in its entirety into a mixed-integer linear programming solver.

KW - Integer programming

KW - Polynomial formulation

KW - Symmetry breaking

KW - Vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=85081923663&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2020.02.012

DO - 10.1016/j.dam.2020.02.012

M3 - Journal article

AN - SCOPUS:85081923663

VL - 296

SP - 179

EP - 192

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -