We address a single commodity Pickup and Delivery Vehicle Routing Problem from the literature. A network of customer nodes is given with both travel times and costs. A fleet of vehicles of limited capacity is exploited to satisfy node demands, and a set of routes must be found such that the vehicle capacities are never exceeded, each route does not exceed time resource, and cost is minimized. The demands of both pickup and delivery nodes can be split, and each node can be visited more than once. We provide new theoretical insights. We propose a new formulation where routes are decomposed into sequences of simpler substructures called clusters, mitigating the combinatorial explosion of feasible solutions. We introduce valid inequalities, and design a branch-and-price algorithm, exploiting ad hoc pricing routines and branching strategies, and embedding a rounding heuristic to speed up pruning. An extensive experimental analysis shows our method to offer simultaneously more modelling flexibility and more computational effectiveness than previous attempts from the literature. Our investigation opens also interesting insights into the use of route decomposition strategies.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    A route decomposition approach for the single commodity Split Pickup and Split Delivery Vehicle Routing Problem



    Erscheinungsdatum :

    10.07.2019



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    000



    The split-demand one-commodity pickup-and-delivery travelling salesman problem

    Salazar-González, Juan-José | Online Contents | 2015



    Study on the One-Commodity Pickup-and-Delivery Vehicle Routing Problem

    Zhang, Linlin / Hu, Dawei / Wei, Yu | ASCE | 2015


    MULTIPLE DEPOT VEHICLE ROUTING PROBLEM WITH SPLIT DELIVERY

    Pongmanawut, Pitchaya / Likasiri, Chulin | TIBKAT | 2020


    Split Delivery Weighted Vehicle Routing Problem: Comparison perspective

    Ma, Yuyan / Tang, Jiafu / Guan, Jing | IEEE | 2013