Daugherty, Stephen G. ; Reveliotis, Spiridon Industrial and Systems Engineering Mohler, Gregory Erera, Alan Egerstedt, Magnus Ahmed, Shabbir Toriello, Alejandro ; Reveliotis, Spiridon
Motivated by a broad spectrum of applications ranging from automated zone-controlled, unit-load material handling systems to the movement of ions within a quantum computer, this thesis considers a class of multi-agent routing problems that seek to minimize the agents’ traveling time subject to certain congestion constraints. In more technical terms, the particular problem addressed in this work concerns the development of efficient, conflict-free, and deadlock-free schedules to route a set of non-interchangeable “agents” between their respective starting locations and destinations. Routes are specified as sequences of adjacent edges of the guidepath network, that are allocated sequentially and exclusively to the traveling agents by a traffic coordinator, according to an allocation protocol that seeks to ensure physical feasibility and other notions of “safety” for the agent motion. On the other hand, efficiency is measured by the schedule “makespan”—i.e., the time required for all agents to reach their respective destinations.In order to formally characterize the addressed scheduling problem and the corresponding notion of optimality for the sought schedules, this thesis first formulates the problem as a mixed-integer program (MIP). In this formulation, the system state at a given time is defined by the allocated edges and the directions of travel for the various agents, and the system is assumed to evolve this state at discrete time intervals that are defined by the required edge-traversal times. The presented MIP is derived according to a resource allocation system (RAS) perspective, and it is based on a set of binary decision variables that characterize the evolution of the system state over a sufficiently long time horizon. An additional auxiliary variable allows the computation of the schedule "makespan"—i.e., the number of discrete time periods required for the last agent to reach its designated destination. An important feature of the developed MIP formulation is its ability to accommodate a broad range of variations of the considered traffic-scheduling problem that result from the variation of certain structural elements of the underlying traffic system and of the adopted edge-allocation protocol. From a computational standpoint, the optimal solution of all these problems is very complex. In many cases, even the identification of a feasible solution for a given problem instance can be a challenging problem.In view of all this complexity, the second part of the thesis formulates a Lagrangian dual problem for the generation of lower bounds for the original scheduling problem, and then describes two distinct methods to optimize this dual problem: (i) a customized dual-ascent algorithm, and (ii) a reformulation of the dual problem as a single, large linear program (LP). The first approach is proven to find an exact solution in a finite number of iterations, but the availability of very efficient LP solvers renders the second method more robust for larger problem instances. The two approaches provide consistent lower bounds for the optimal makespans of various problem instances, as well as Lagrange multipliers that optimize the Lagrangian dual and may be useful in the guidance of other heuristic algorithms for an optimized schedule.The third part of the thesis presents and analyzes a heuristic, "local-search" type of algorithm for minimizing the makespans of multi-agent routes on a shared guidepath network. For the context of conflict-free ion routing within a quantum computer, the thesis describes a complete algorithm for finding an initial feasible solution, and for optimizing that schedule by iterative reduction of the makespan, using dynamic programming (DP) to revise agent routes while eliminating conflicts between agents. Various methods for strengthening the makespan-reduction procedure (e.g., multi-agent simultaneous route revision, or controlled excursions into the infeasible region) are described and analyzed.Finally, the dissertation provides a set of experimental results that are obtained from the implementation of the developed methods for a carefully selected set of problem instances. For each instance, we find lower bounds (obtained either by hand, or by solving the Lagrangian dual problem) on the optimal objective values, as well as actual makespans for feasible schedules discovered by the heuristic scheduler. The considered problem instances include: (i) a small but difficult problem used to motivate our early research; (ii) a more complex "challenge" problem designed to maximize congestion; and (iii) a series of 150 randomized trials formulated on a grid-based configuration of the guidepath network that is typical of the corresponding structures that are encountered in many practical applications. The third set of experiments is further designed to evaluate the performance of the heuristic scheduler under increasing levels of congestion. The obtained results reveal that our heuristic algorithm can provide very efficient solutions for the targeted variations of the guidepath-based traffic-scheduling problem, in a way that is computationally efficient and complete.The thesis concludes with suggestions for future research that are aimed at (a) the further enhancement of the heuristic algorithm, (b) the extension of this algorithm and of the corresponding methodology to other variations of the considered traffic-scheduling problems, and (c) the embedding of all these results in a broader “rolling-horizon” framework that will address the dynamic nature of the operational (i.e., the transport) requirements of the considered traffic systems.
PDF
download
878987797
028-85220240
