This control device is provided with: an acquiring unit 122 for acquiring a gradient function representing a relationship between a traveling position of a vehicle 100 and a gradient at the traveling position; an optimizing unit 123 for calculating a first control input value instructing engine torque of the vehicle, a second control input value instructing a gear shift position, and a third control input value instructing an operating state of an auxiliary brake, when an evaluation function is minimized or maximized, the evaluation function including, as variables, a first evaluation index relating to an instantaneous fuel consumption of the vehicle when traveling along a road having a gradient indicated by the gradient function, a second evaluation index relating to acceleration/deceleration, a third evaluation index relating to a speed deviation, which is a deviation between a vehicle speed and a target value, and a fourth evaluation index relating to the presence or absence of a change in the operating state of the auxiliary brake; and a travel control unit for controlling travel on the basis of the first control input value, the second control input value, and the third control input value, calculated by the optimizing unit 123.