Some novel traffic coordination problems and their analytical study based on Lagrangian Duality theory

摘要

We consider a class of scheduling problems that concern the routing of a set of mobile agents over the edges of an underlying guidepath network. These problems are motivated by (i) the operations of some unit-load, automated material handling systems that are employed in many contemporary production and distribution facilities, and also by (ii) the operations that take place in the physical layouts implementing the elementary logical operations that are employed in quantum computing. The presented results include (a) a systematic formulation of the considered scheduling problems as mixed integer programs (MIPs), (b) a Lagrangian relaxation of these MIP formulations, and (c) the development of a customized dual-ascent algorithm for the systematic and expedient solution of the corresponding dual problem. The latter provides lower bounds for the original MIP formulations and potentially useful information for the construction of near-optimal routing schedules for the original problems.