The Elementary Shortest Path (ESP) problem on graphs with negative cycles and the Quorumcast Routing (QR) problem are two important NP-hard routing combinatorial optimization problems in operations research. The ESP problem seeks an elementary shortest path between two given nodes such that no node appears more than once, while the QR problem computes a minimum-cost tree that includes a predefined root node and at least a specified number of multicast nodes from a given set. Currently, Mixed-Integer Linear Programming (MILP) represents the state-of-the-art exact approach for both problems. This research proposes new MILP formulations by incorporating redundant variables and constraints into existing state-of-the-art formulations. Experimental results demonstrate that algorithms implementing these formulations using the CPLEX solver are faster and require less memory than existing methods.