In a map data generation apparatus, probe map data is generated for each of data management units corresponding to (i) road sections, (ii) road links, or (iii) meshes into which a map is divided, based on a plurality of probe data collected from a plurality of vehicles. Difference data are obtained by comparing basic map data with the probe map data; the basic map data is updated based on a plurality of difference data, for each of the data management units. A transient data is discriminated from data corresponding to the probe data or the difference data; the transient data is excluded from the data.