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.


    Access

    Download


    Export, share and cite



    Title :

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



    Publication date :

    2019-07-10



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    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