Yuta Hamachiyo

Digital microfluidic biochips are widely used for automated biochemical and diagnostic applications such as molecular analysis, immunoassays, and point-of-care testing. Among them, micro-electrode-dot-array (MEDA) biochips enable fine-grained droplet manipulation with shape-dependent velocity, which significantly increases routing flexibility but also computational complexity. This work proposes an efficient droplet routing method for MEDA biochips that reduces computational time while maintaining or improving solution quality. The proposed method introduces a guidance constraint that consistently directs droplets toward the target cell and integrates a solver-friendly model with a tight lower-bound design. Experimental results demonstrate that, for instances solvable by the existing method, the proposed method achieves comparable or better Routing time while reducing Solution-finding time by 72.3%. Moreover, the Solution-finding rate improves from 33.3% to 85.3% over all problem instances. Notably, for instances that cannot be solved within the time limit by the existing method, the proposed method successfully finds optimal solutions in 72.7% of the cases. These results indicate that the proposed method enables faster solution discovery, and extends solvability to previously intractable routing problems.

In recent years, digital microfluidic biochips (DMFBs), based on microfluidic technology, have attracted attention as compact and flexible experimental devices. DMFBs are widely applied in biochemistry and medical fields, including point-of-care clinical diagnostics and PCR testing. Among them, micro electrode dot array (MEDA) biochips, composed of numerous microelectrodes, have overcome the limitations of conventional chips by enabling finer droplet manipulation and real-time sensing, thus significantly improving experimental efficiency. While various studies have been conducted to enhance the utilization of MEDA biochips, few have considered the shape-dependent velocity characteristics of droplets in routing. Moreover, methods that do take such characteristics into account often face significant challenges in solving time. This study proposes a fast droplet routing method for MEDA biochips that incorporates shape-dependent velocity characteristics by utilizing the distance information to the target cell. The experimental results demonstrate that the proposed method achieves approximately a 67.5% reduction in solving time compared to existing methods, without compromising solution quality.