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.
Split-Delivery Capacitated Arc-Routing Problem With Time Windows
IEEE Transactions on Intelligent Transportation Systems ; 23 , 3 ; 2882-2887
2022-03-01
1107382 byte
Article (Journal)
Electronic Resource
English
Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic
Online Contents | 2010
|Split-Delivery Capacitated Arc-Routing Problem: Lower Bound and Metaheuristic
British Library Online Contents | 2010
|Heuristic Approach For Robust Counterpart Open Capacitated Vehicle Routing Problem With Time Windows
BASE | 2021
|A REVIEW OF MEMETIC ALGORITHM FOR CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS
BASE | 2018
|