We propose efficient algorithms that provide optimal or near-optimal solutions to two robotics problems that are important in robotics research and industrial applications. The objective of the two problems, named object rearrangement and multi-robot path planning, is to efficiently find a high-quality plan to move objects or robots from a start configuration to a goal configuration, following specific constraints. Studying these problems from a combinatorial aspect, we provide efficient and effective algorithmic solutions. Through extensive experimental evaluation, we prove that our methods achieve a high level of scalability, provide optimal or near-optimal solutions, and have a significant advantage over the compared approaches.