An operation method of an optimal route searching device includes: acquiring topology transformed map information; extracting a plurality of candidate routes based on the topology transformed map information; calculating a travel cost for each of the plurality of candidate routes based on a cost function; and determining a candidate route corresponding to a lowest cost one of the calculated travel costs as a travelling route.