A Multi-Objective Genetic Algorithm (MOGA) designed to solve the Multi-Commodity Flow Problem (MCFP) with the aim of improving network efficiency is presented. This work improves on our previous MOGA, using new objectives that better represent the routing solutions we seek. The new algorithm increases the total network flow by 6% and 25% when compared with a setup similar to OSPF and our previous work, respectively, without resorting to multipath routing. Network simulations for TCP flows show that our proposed algorithm achieves the highest total network flow and the lowest number of unallocated flows when compared with our previous MOGA, the OSPF-like setup, and the optimal path-constrained Maximum-Flow Minimum-Cost solution. The flow delay performance is similar to the other algorithms, even though the proposed algorithm is pushing more data onto the network.