The distance constrained multiple vehicle traveling purchaser problem

N. Bianchessi, R. Mansini*, M. G. Speranza

*Corresponding author for this work

    Research output: Contribution to JournalArticleAcademicpeer-review

    Abstract

    In the Distance Constrained Multiple Vehicle Traveling Purchaser Problem (DC-MVTPP) a fleet of vehicles is available to visit suppliers offering products at different prices and with different quantity availabilities. The DC-MVTPP consists in selecting a subset of suppliers so to satisfy products demand at the minimum traveling and purchasing costs, while ensuring that the distance traveled by each vehicle does not exceed a predefined upper bound. The problem generalizes the classical Traveling Purchaser Problem (TPP) and adds new realistic features to the decision problem. In this paper we present different mathematical programming formulations for the problem. A branch-and-price algorithm is also proposed to solve a set partitioning formulation where columns represent feasible routes for the vehicles. At each node of the branch-and-bound tree, the linear relaxation of the set partitioning formulation, augmented by the branching constraints, is solved through column generation. The pricing problem is solved using dynamic programming. A set of instances has been derived from benchmark instances for the asymmetric TPP. Instances with up to 100 suppliers and 200 products have been solved to optimality.

    Original languageEnglish
    Pages (from-to)73-87
    Number of pages15
    JournalEuropean Journal of Operational Research
    Volume235
    Issue number1
    DOIs
    Publication statusPublished - 16 May 2014

    Keywords

    • Branch-and-price
    • Column generation
    • Distance constraint
    • Formulations
    • Multiple vehicle traveling purchaser problem

    Fingerprint

    Dive into the research topics of 'The distance constrained multiple vehicle traveling purchaser problem'. Together they form a unique fingerprint.

    Cite this