Split-Delivery Capacitated Arc-Routing Problem With Time Windows

Qidong Lai; Zizhen Zhang; Mingzhu Yu; Jiahai Wang

doi:10.1109/TITS.2020.3029055

Author(s)

Qidong Lai
Zizhen Zhang
Mingzhu Yu
Jiahai Wang

Related Research Unit(s)

Department of Management Sciences

Detail(s)

Original language	English
Pages (from-to)	2882-2887
Journal / Publication	IEEE Transactions on Intelligent Transportation Systems
Volume	23
Issue number	3
Online published	15 Oct 2020
Publication status	Published - Mar 2022

Link(s)

DOI	DOI https://doi.org/10.1109/TITS.2020.3029055 Final Published version
	Check@CityULib
Link to Scopus	https://www.scopus.com/record/display.uri?eid=2-s2.0-85127911978&origin=recordpage
Permanent Link	https://scholars.cityu.edu.hk/en/publications/publication(cd461ac9-60dc-4b7f-8611-8c515cd36df5).html

Abstract

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)

[ RIS ] [ BibTeX ]

Split-Delivery Capacitated Arc-Routing Problem With Time Windows. / Lai, Qidong; Zhang, Zizhen; Yu, Mingzhu et al.
In: IEEE Transactions on Intelligent Transportation Systems, Vol. 23, No. 3, 03.2022, p. 2882-2887.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

Lai, Q, Zhang, Z, Yu, M & Wang, J 2022, 'Split-Delivery Capacitated Arc-Routing Problem With Time Windows', IEEE Transactions on Intelligent Transportation Systems, vol. 23, no. 3, pp. 2882-2887. https://doi.org/10.1109/TITS.2020.3029055

Lai, Q., Zhang, Z., Yu, M., & Wang, J. (2022). Split-Delivery Capacitated Arc-Routing Problem With Time Windows. IEEE Transactions on Intelligent Transportation Systems, 23(3), 2882-2887. https://doi.org/10.1109/TITS.2020.3029055

Lai Q, Zhang Z, Yu M, Wang J. Split-Delivery Capacitated Arc-Routing Problem With Time Windows. IEEE Transactions on Intelligent Transportation Systems. 2022 Mar;23(3):2882-2887. Epub 2020 Oct 15. doi: 10.1109/TITS.2020.3029055

Lai, Qidong ; Zhang, Zizhen ; Yu, Mingzhu et al. / Split-Delivery Capacitated Arc-Routing Problem With Time Windows. In: IEEE Transactions on Intelligent Transportation Systems. 2022 ; Vol. 23, No. 3. pp. 2882-2887.