Exact Algorithms for the Multi-Compartment Vehicle Routing Problem with Flexible Compartment Sizes
Katrin Heßler ()
Additional contact information
Katrin Heßler: Johannes Gutenberg-University Mainz, Germany
No 2007, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz
The multi-compartment vehicle routing problem with ﬂexible compartment sizes is a variant of the classical vehicle routing problem in which customers demand diﬀerent product types and the vehicle capacity can be separated into diﬀerent compartments each dedicated to a speciﬁc product type. The size of each compartment is not ﬁxed beforehand but the number of compartments is limited. We consider two variants for dividing the vehicle capacity: On the one hand the vehicle capacity can be discretely divided into compartments and on the other hand compartment sizes can be chosen arbitrarily. The objective is to minimize the total distance of all vehicle routes such that all customer demands are met and vehicle capacities are respected. Modifying a branch-and-cut algorithm based on a three-index formulation for the discrete problem variant from the literature, we introduce an exact solution approach that is tailored to the continuous problem variant. Moreover, we propose two other exact solution approaches, namely a branch-and-cut algorithm based on a two-index formulation and a branch-price-and-cut algorithm based on a route-indexed formulation, that can tackle both packing restrictions with mild adaptions and can be combined into an eﬀective two-stage approach. Extensive computational tests have been conducted to compare the diﬀerent algorithms. For the continuous variant, we can solve instances with up to 50 customers to optimality and for the discrete variant, several previously open instances can now be solved to proven optimality. Moreover, we analyse the cost savings of using continuously ﬂexible compartment sizes instead of discretely ﬂexible compartment sizes.
Keywords: routing; branch-price-and-cut; multi-compartment (search for similar items in EconPapers)
Pages: 33 pages
New Economics Papers: this item is included in nep-cmp and nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2007.pdf First version, 2020 (application/pdf)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:2007
Access Statistics for this paper
More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().