Due to a large number of customers with different service requirements and scattered locations, the express companies are constantly facing the problems of untimely delivery. The uncertainty in customer demands and travel time make the problems becoming more challenging. To address this problem, this paper considers a class of vehicle routing problems with demand and travel time uncertainty for express delivery, from the perspective of robust optimization. We construct an uncertainty set to make sure all the possible realizations of uncertain parameters that have been bounded. The robust optimization model of express vehicle routing yields solutions that minimize the total distribution cost and penalty. A genetic-based hyper-heuristic algorithm is proposed to tackle this model. We perform a series of experiments to validate the proposed model and algorithm. Experimental results clearly show the strength of handling uncertainties and the superiority of the presented robust optimization approach over the original one.