Speaker: Đặng Thu Hương - University of Lancaster, UK

Thời gian: 20h-21h tối thứ 5, ngày 6/10/2022

Title: Fast Upper and Lower Bounds for a Large-Scale Real-World Arc Routing Problem

Abstract:

Arc Routing Problems (ARPs) are a special kind of vehicle routing problem, in which the demands are located on edges or arcs, instead of nodes. There is a huge literature on ARPs, and a variety of exact and heuristic algorithms are available. Recently, while working with an industrial partner, we encountered some very challenging real-life ARPs. These problems had multiple vehicles, capacity constraints, intermediate facilities, a time deadline, multiple objectives, and a combination of one- and two-way streets. Moreover, some instances had over ten thousand roads, which is much larger than those usually considered in the literature. To further complicate matters, the industrial partner wanted a procedure that could produce reasonably good upper and lower bounds within a couple of minutes for various reasons. 

The ARP in question is a (bi-objective) Mixed Capacitated Arc Routing Problem with Intermediate Facilities and a Deadline (MCARPIFD). Although there exist a few heuristics for the MCARPIFD in the literature, the severe restriction on computing time meant that we could not use any of them. Accordingly, we developed our own fast upper- and lower-bounding procedures. Our upper bound algorithm combines several ingredients, including a constructive heuristic, Euclidean approximation, local search, a minimum-cost flow routine and a tour-splitting technique. Our lower bound algorithm is based on a linear programming relaxation involving auxiliary flow variables, in combination with specialised cutting planes. We present extensive computational results to explore the quality of our bounding procedures. In particular, we create and solve 20 MCARPIFD instances, using real road network data from five cities across the world. For a sensitivity analysis, we experiment with varying parameters. It turns out that our algorithms work very well in most cases.

Bio: My name is Thu Huong Dang. Currently, I am a lecturer in Management Science at Lancaster University Management School. Previously, I worked at the University of Arizona, USA, as a research technician on mathematical modeling of different biological and virus infection processes. For my undergraduate degree, I went to the Eötvös Loránd University (ELTE) in Budapest, Hungary and got a 1st/outstanding degree in Applied Mathematics in 2014. In 2019, I completed the Master of Research in Statistics and Operation Research at Lancaster University and also obtained a distinction. I started my PhD in Statistics and Operation Research at Lancaster University from 2019 and finished it well within 3 years. My PhD research was with the STOR-i CDT, using exact algorithms and heuristic methods for large-scale and complex Vehicle Routing Problems . My supervisors are Prof. Adam Letchford and Dr. Burak Boyaci at Lancaster University and is in collaboration with Routeware, Inc. company. My research is focused on Combinatorial Optimisation Problems. I concentrate both on exact methods for solving problems to proven optimality, and heuristic methods for real-life problems.