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

Abstract: The multi-compartment vehicle routing problem with flexible compartment sizes is a variant of the classical vehicle routing problem in which customers demand different product types and the vehicle capacity can be separated into different compartments each dedicated to a specific product type. The size of each compartment is not fixed 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 effective two-stage approach. Extensive computational tests have been conducted to compare the different 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 flexible compartment sizes instead of discretely flexible compartment sizes.

Keywords: routing; branch-price-and-cut; multi-compartment (search for similar items in EconPapers)
Pages: 33 pages
Date: 2020-04-03
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:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2007.pdf First version, 2020 (application/pdf)

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: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 ().