n-Tokyoites’ loop-line commuter problem Original Research Article

We present an O(n2) order algorithm to an n-Tokyoites’ loop-line commuter problem. The n-Tokyoites’ loop-line commuter problem comprises a special class of the more general Gilmore–Gomory weighted bipartite matching problem where weights assigned to arcs are given in terms of integrals of some functions. The algorithm of O(n2) complexity developed is faster than the more popularly used Hungarian-type O(n3) algorithms (Naval Res. Logist. Quart. 2 (1955) 83; Management Sci. 12 (1964) 578) applicable to the more general weighted bipartite matching problem, but is slower than the original, more restricted Gilmore–Gomory O(n log n) algorithm (Oper. Res. 12 (1964) 655). The algorithm we have developed allows to impose some novel angular constraints which find an immediate application not only to the n-Tokyoites’ loop-line commuter problem itself, but also to the data association problem involved in the multisensor–multitarget tracking process (Design and Analysis of Modern Tracking Systems, Artech House, Norwood, MA, 1999) and to the specifically defined Gilmore–Gomoryʹs original TSP problem.