This paper presents an approach for optimization of segment-linked maintenance and rehabilitation plan for a pavement network by using shuffled complex evolution. It extends the works of Nunuo and Agyei (2000) by improving the exploration-exploitation balance of the algorithm and by using a realistic pavement deterioration model to solve the problem of multiple maintenance and rehabilitation activities. An example to maximize the serviceability of the road network under a fixed budget and minimum serviceability level policy is also presented. The result of the optimization process using a part of Kanagawa prefecture road network showed very good results with reasonable computational times.