Motivated by some practical applications in urban services such as water sparkling, we study a split-delivery capacitated arc-routing problem with time windows (SDCARPTW). It is a variant of arc-routing problem and is defined on an undirected graph where the demands on the arcs are splitable, and time window and capacity constraints must be satisfied. We propose a mathematical formulation for SDCARPTW and derive some nice properties of the split-delivery structure, which can help to well represent a solution of SDCARPTW. The dynamic programming, neighborhood search and perturbation process are combined to develop a tabu search algorithm. Through computational studies on CARPTW benchmark datasets, we validate the effectiveness and efficiency of our proposed algorithm. New datasets for SDCARPTW are further proposed and the impact of the split-delivery option is analyzed.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Split-Delivery Capacitated Arc-Routing Problem With Time Windows


    Contributors:
    Lai, Qidong (author) / Zhang, Zizhen (author) / Yu, Mingzhu (author) / Wang, Jiahai (author)


    Publication date :

    2022-03-01


    Size :

    1107382 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic

    Belenguer, J.-M. / Benavent, E. / Labadi, N. et al. | British Library Online Contents | 2010


    Heuristic Approach For Robust Counterpart Open Capacitated Vehicle Routing Problem With Time Windows

    Yuliza, Evi / Puspita, Fitri Maya / Supadi, Siti Suzlin | BASE | 2021

    Free access

    A REVIEW OF MEMETIC ALGORITHM FOR CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

    Pandey, Digesh / Srivastava, Namita | BASE | 2018

    Free access

    Optimasi Capacitated Vehicle Routing Problem with Time Windows dengan Menggunakan Ant Colony Optimization

    Soenandi, Iwan Aang / Joice, Joice / Marpaung, Budi | BASE | 2019

    Free access