A branch-and-price algorithm for a vehicle routing with demand allocation problem

Mohammad Reihaneh and Ahmed Ghoniem
Additional contact information
Mohammad Reihaneh: LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique

Post-Print from HAL

Abstract: We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.

Keywords: Routing; Vehicle routing-allocation problem; Logistics and distribution; Branch-and-price; Dynamic programming (search for similar items in EconPapers)
Date: 2019-01-16
References: Add references at CitEc
Citations: View citations in EconPapers (8)

Published in European Journal of Operational Research, 2019, 272 (2), pp.523-538. ⟨10.1016/j.ejor.2018.06.049⟩

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:hal:journl:hal-02117608

DOI: 10.1016/j.ejor.2018.06.049

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().