1. A map information generating system, comprising: a memory that stores map information including a road network; and a controller that: gathers traveling information including a plurality of loci, each locus representing a vehicle traveling along a road that is not included in the stored road network; separates the loci within the gathered traveling information into groups, each group related to a same road; and generates new road information relating to a single new road for each group of loci.