CAREER: Efficient Network Design and Routing Algorithms for Logistics and Communications Networks

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

The primary goal of this Faculty Early Career Development (CAREER) Program research project is to develop state-of-the-art fast solution methodologies that generate high quality solutions for complex problems in designing and managing logistics and communications networks. Real-world communications and logistics problems are large-scale, time sensitive, and coupled with side constraints that further contribute to the hardness of underlying mathematical structures. The specific tasks that will be undertaken for achieving the goal of this project include: understanding the applications in detail, analyzing the underlying mathematical structures, and evaluating the various solution approaches through computational testing. A logistics network rarely functions as planned due to external factors such as unscheduled delays or dynamically changing customer demand. The main thrust of the proposal is a study on techniques for augmenting a given solution in order to incorporate a disruption to a large-scale system. In the literature, these types of problems are usually solved by extracting a subset of the problem through preprocessing and then re-solving this smaller problem. This research, proposes to develop techniques that consider a large part of the problem by designing auxiliary networks together with fast augmentation algorithms that find near optimal solutions in almost real-time. Also, two important network design and routing problems related to: (i) identifying synergies in a collaborative logistics network, and (ii) routing multiple packets on partially disjoint paths over a communications network, will be studied as collaborative research projects. With the advancement of globalization and new technologies in telecommunications, not only does the importance of solving network problems keep growing but also this task is becoming harder to accomplish efficiently. For example, global trade has created logistics networks that span several continents, and the possibility of real-time multi-media communications introduced network problems that need to be solved in less than a second. To face this challenge, it is necessary to employ fast approximation (heuristic) algorithms that try to find good solutions rather than identify an optimal one. This research plan proposes (i) to study fast heuristic techniques for generating close to optimal solutions for large-scale and time-sensitive logistics and communications network applications that are implementable in practice and (ii) to further the theoretical understanding of problems arising from these applications.