Traveling-Salesman and Related Scheduling Problems

Our proposal's main objective is to realize cyber-physical platform and principles for (i) interrogating global modalities of intracellular transport with causative factors isolated at the single-molecule scale and (ii) realizing efficient and robust infrastructure for transporting micron/molecular scale cargo using distributed strategies We are realizing in-vitro, a transport network with roadways formed by microtubules where motorproteins, kinesin and dynein, will form vehicles ferrying cargo. The microscale transport network realized will share a number of attributes of a modern transport infrastructure of a city such as (i) a global monitoring and control unit (gmcu) that obtains, a birds-eye view of the entire traffic, analyzes emerging modalities and instructs a finer probing system on what components of the infrastructure require more attention. Furthermore, its off-line tasks involve reaching causative factors to isolate essential factors that enable/disrupt transport (ii) a finer monitoring and control unit (fmcu) that provides a detailed analysis of a few components identified by the global monitoring system. We are developing an inference engine that will infer locations of interest in the traffic network using the gmcu data, which will be investigated by scarce but high-resolution fmcu. The limited/scarce resources results in a scheduling problem, where the fmcu has to be schedules to cover as many locations of interest as possible. This scheduling problem can be cast as a traveling salesman problem (TSP) with time windows; where fmcu (laser trap) is the salesman, and the time windows denote the time intervals within which probing respective locations is useful.

We present an algorithm to address such TSP problems with scheduling constraints. We view the Vehicle Routing Problem with Time-Windows (VRPTW) as a resource allocation problem on networks in time and space. We have developed a Deterministic Annealing (DA)-based approach to solving the VRPTW with its aspects of routing and scheduling, as well as to model additional constraints of heterogeneous vehicles (multiple laser traps with different capacities). This is the first time, to our knowledge, that a DA approach has been used for problems in the class of the VRPTW. Our DA approach is also designed to not get trapped in local minima, and demonstrates less sensitivity to initial solutions. The resulting algorithm is general; relevant to many applications: The algorithm trades off routing and scheduling in an n-dimensional space using a tunable parameter that allows us to generate qualitatively good solutions. Simulation results on randomly generated instances show that the constraints are respected and demonstrate near optimal results (when verifiable) in terms of schedules and tour length of individual tours in each solution