Methods, systems, and computer readable media for scheduling jobs by using a one-to-many shortest path search based on travel costs between job locations. In some examples, a system includes one or more computers configured to schedule jobs based on travel from a geographic origin to a respective geographic job location for each job. The system also includes a one-to-many path searcher implemented on the one or more computers. The one-to-many path searcher searches for paths along edges of a graph from an origin node to destination nodes by traversing intermediate nodes between the origin node and the destination nodes using travel costs, including determining heuristic travel costs based on a geographic distance between an intermediate geographic location corresponding to the intermediate node and a boundary that initially surrounds the geographic job locations.