Evolving Robust Solutions to Uncertain Capacitated Arc Routing Problem with Time Window

Shuo Huang; Yinxi Tian; Xintong Duan

10.1109/SSCI51031.2022.10022223

2022

IEEE Symposium Series on Computational Intelligence (IEEE SSCI)

978-1-6654-8769-6

2022 IEEE Symposium Series on Computational Intelligence (SSCI)

488-495

4-7 Dec. 2022

Singapore, Singapore

345 E 47TH ST, NEW YORK, NY 10017 USA

IEEE

The capacitated arc routing problem with time window has been studied for years, while uncertainties in real-world scenarios, such as uncertain demands and uncertain routing conditions, were rarely considered. In this paper, we formulate an uncertain capacitated arc routing problem with time window that takes into account the uncertain demand of tasks, the uncertain deadheading costs and the uncertain presence of tasks and paths. A number of problem instances are generated based on the benchmark instances of static capacitated arc routing problem with time window considering the aforementioned four uncertain factors. To tackle this new challenging problem, we adapt a state-of-the-art algorithm for solving uncertain capacitated arc routing problem, an estimation of distribution algorithm (EDA) with a stochastic local search, to find robust solutions. Another algorithm, a memetic algorithm with extended neighborhood search, is also adapted as a baseline solution algorithm to this challenging problems. Our experimental results indicate that our EDA-based algorithm is effective in finding robust solutions to uncertain capacitated arc routing problems with time window.

Uncertain capacitated arc routing problem with time window (UCARP-TW) uncertain capacitated arc routing problem (UCARP) capacitated arc routing problem with time window (CARP-TW) robust optimisation estimation of distribution

First

English

CPCI-S

SUSTech Undergraduate Teaching Quality and Reform Project[SJZLGC202101]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Interdisciplinary Applications ; Computer Science, Theory & Methods

WOS:000971973800066

IEEE

Department of Computer Science and Engineering, Southern University of Science and Technology

Shuo Huang,Yinxi Tian,Xintong Duan. Evolving Robust Solutions to Uncertain Capacitated Arc Routing Problem with Time Window[C]. 345 E 47TH ST, NEW YORK, NY 10017 USA:IEEE,2022:488-495.