Split-Delivery Capacitated Arc-Routing Problem With Time Windows

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)2882-2887
Journal / PublicationIEEE Transactions on Intelligent Transportation Systems
Issue number3
Online published15 Oct 2020
Publication statusPublished - Mar 2022


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.

Research Area(s)

  • Routing, Microsoft Windows, Intelligent transportation systems, Heuristic algorithms, Computational modeling, Mathematical model, Dynamic programming, Split-delivery, arc-routing problem (ARP), tabu search, BRANCH, PRICE, CUT

Citation Format(s)