We propose a new approach for solving a variant of the transportation Network Design Problem (NDP) where network congestion is reduced via traffic pattern redesign. The investigated NDP selects a set of roads to be converted from two-way traffic to one-way traffic. This allows increased traffic flow in the selected roads at the cost of restricting flow in the opposing direction roads. An optimal set of converted roads can result in significant congestion reduction for the network without the high construction costs associated with network capacity expansion. The new approach builds on the recently developed Chemical Reaction Optimization (CRO) metaheuristic and leverages Markov chain traffic assignment to predict traffic flow changes in response to network modifications. We propose an elitist and adaptive version of the CRO metaheuristic allowing it to more efficiently search for optimal solutions. We deploy the proposed approach to the cities of Abu Dhabi and Sioux Falls and report on our results. We also compare the Elitist Adaptive CRO (EACRO) results to those of Genetic Algorithm (GA) to demonstrate its performance. Compared to GA, the proposed approach reduces network congestions faster using fewer objective function evaluations. It also produces lower network congestion designs using long optimization runs. However, we find the algorithm to be sensitive to parameter calibration and dependent on the use of elitism for good performance. We explore the internal dynamics of the proposed algorithm and investigate its search effectiveness to understand its superior performance when compared to GA.