Patent ID: 12247839

DETAILED DESCRIPTION

This disclosure provides techniques for increasing efficiency of vehicle operation by determining an optimal ordering of a set of waypoints through which the vehicle can travel. A computer divides the waypoints into clusters, arranges the clusters into an upper-level ordering by executing an optimization algorithm, arranges the waypoints within the clusters into respective lower-level orderings by executing the optimization algorithm on the clusters, and outputs the waypoints in a final ordering by concatenating the waypoints in the lower-level orderings according to the upper-level ordering. The final ordering defines a route passing through the waypoints in the final ordering, along which the vehicle can travel. For example, the computer may divide the waypoints into a first cluster, a second cluster, and a third cluster. The computer arranges the clusters into an upper-level ordering of {second cluster, first cluster, third cluster}. The computer determines a first lower-level ordering of the waypoints in the first cluster, a second lower-level ordering of the waypoints in the second cluster, and a third lower-level ordering of the waypoints in the third cluster. The computer outputs the waypoints in a final ordering as follows: the waypoints in the second cluster in the second lower-level ordering, then the waypoints in the first cluster in the first lower-level ordering, and then the waypoints in the third cluster in the third lower-level ordering. The vehicle may then travel to the waypoints in the final ordering.

The use of these techniques may significantly reduce processing time. For example, an experiment based on the present disclosure was conducted to determine an order for a vehicle to travel through waypoints located in the San Francisco Bay Area. In one trial, the waypoints were divided into clusters geographically and an optimization algorithm to minimize energy consumption (e.g., fuel or charge) was applied to the waypoints in each cluster and to the clusters as a group, as described herein (illustrated inFIG.4). The processing time was approximately 2.5 hours. In a second trial, the same optimization algorithm was applied to the waypoints without clustering. The processing time was approximately 7.5 hours, and the expected energy consumed by the vehicle traveling to the waypoints was also higher.

A computer includes a processor and a memory, and the memory stores instructions executable by the processor to divide a plurality of waypoints in a geographic area into a plurality of clusters according to at least one metric, arrange the clusters into an upper-level ordering by executing an optimization algorithm, arrange the waypoints within the respective clusters into a plurality of respective lower-level orderings by executing the optimization algorithm on the respective clusters, and output the waypoints in a final ordering by concatenating the waypoints in the lower-level orderings according to the upper-level ordering. The final ordering defines a final route passing through the waypoints in the final ordering.

In an example, the instructions may further include instructions to instruct a vehicle to navigate the final route.

In an example, the instructions may further include instructions to determine a plurality of intermediate routes between consecutive waypoints in the final ordering, the final route including the intermediate routes.

In an example, the at least one metric may include at least one of distance, geographical density, travel time, or energy consumption.

In an example, the instructions to execute the optimization algorithm may include instructions to minimize a cost associated with a route defined by an ordering outputted by the optimization algorithm. In a further example, the cost may include at least one of distance, travel time, or energy consumption.

In an example, the instructions may further include instructions to, before arranging the waypoints into the lower-level orderings, determine a plurality of start waypoints and end waypoints for the respective clusters, and the start waypoints and end waypoints may serve as constraints on the optimization algorithm when executed on the respective clusters. In a further example, the instructions to determine the start waypoints and end waypoints may include instructions to determine the start waypoints and end waypoints based on the upper-level ordering.

In another further example, the instructions to determine the start waypoints and end waypoints may include instructions to determine the start waypoints and end waypoints to minimize a pairwise cost between consecutive ones of the clusters in the upper-level ordering. In a still further example, the pairwise cost may include at least one of distance, travel time, or energy consumption.

In an example, the instructions may further include instructions to determine representative waypoints for the respective clusters, and the instructions to determine the upper-level ordering may include instructions to execute the optimization algorithm on the representative waypoints.

In an example, the instructions may further include instructions to divide the waypoints in a first cluster of the clusters into a plurality of further clusters, and arrange the further clusters in the first cluster into a mid-level ordering. In a further example, the instructions to arrange the clusters into the upper-level ordering may include instructions to insert the further clusters into a position of the first cluster in the upper-level ordering with the further clusters in the mid-level ordering.

In an example, the instructions may further include instructions to determine that a first cluster of the clusters satisfies a clustering condition, and upon determining that the first cluster satisfies the clustering condition, divide the waypoints in the first cluster into a plurality of further clusters. In a further example, the instructions may further include instructions to, upon dividing the waypoints in the first cluster into the further clusters, arrange the further clusters in the first cluster into a mid-level ordering. In a still further example, the instructions to arrange the clusters into the upper-level ordering may include instructions to insert the further clusters into a position of the first cluster in the upper-level ordering with the further clusters in the mid-level ordering.

In another further example, the instructions may further include instructions to iteratively divide the waypoints in the first cluster into further clusters until the clustering condition fails to be satisfied. In a still further example, the instructions to determine the upper-level ordering may include instructions to iteratively arrange the further clusters in one iteration within the respective further clusters in an immediately previous iteration into respective mid-level orderings. In a yet still further example, the instructions to determine the upper-level ordering may include instructions to iteratively insert the further clusters from one iteration into a position of the further cluster that includes the further clusters from the one iteration in an immediately previous iteration with the further clusters from the one iteration in the respective mid-level ordering.

A method includes dividing a plurality of waypoints in a geographic area into a plurality of clusters according to at least one metric, arranging the clusters into an upper-level ordering by executing an optimization algorithm, arranging the waypoints within the respective clusters into a plurality of respective lower-level orderings by executing the optimization algorithm on the respective clusters, and outputting the waypoints in a final ordering by concatenating the waypoints in the lower-level orderings according to the upper-level ordering. the final ordering defines a final route passing through the waypoints in the final ordering.

With reference to the Figures, wherein like numerals indicate like parts throughout the several views, a computer100includes a processor and a memory, and the memory stores instructions executable by the processor to divide a plurality of waypoints205in a geographic area into a plurality of clusters210according to at least one metric, arrange the clusters210into an upper-level ordering by executing an optimization algorithm, arrange the waypoints205within the respective clusters210into a plurality of respective lower-level orderings by executing the optimization algorithm on the respective clusters210, and output the waypoints205in a final ordering by concatenating the waypoints205in the lower-level orderings according to the upper-level ordering. The final ordering defines a final route410passing through the waypoints in the final ordering.

With reference toFIG.1, the computer100is a microprocessor-based computing device, e.g., a generic computing device including a processor and a memory. The memory of the computer100can include media for storing instructions executable by the processor as well as for electronically storing data and/or databases, and/or the computer100can include structures such as the foregoing by which programming is provided. The computer100can be multiple computers coupled together.

The computer100is connected to a network105. The network105represents one or more mechanisms by which the computer100may communicate with a remote server. Accordingly, the network105may be one or more of various wired or wireless communication mechanisms, including any desired combination of wired (e.g., cable and fiber) and/or wireless (e.g., cellular, wireless, satellite, microwave, and radio frequency) communication mechanisms and any desired network topology (or topologies when multiple communication mechanisms are utilized). Exemplary communication networks include wireless communication networks (e.g., using Bluetooth, IEEE 802.11, etc.), local area networks (LAN) and/or wide area networks (WAN), including the Internet, providing data communication services.

One or more vehicles110may be connected to the computer100via the network105. Each vehicle110may be any passenger or commercial automobile such as a car, a truck, a sport utility vehicle, a crossover, a van, a minivan, a taxi, a bus, etc.

One or more of the vehicles110may be autonomous vehicles. A vehicle computer on board a vehicle110can be programmed to operate that vehicle110independently of the intervention of a human operator, completely or to a lesser degree. The vehicle computer may be programmed to operate a propulsion system, a brake system, a steering system, and/or other vehicle systems. For the purposes of this disclosure, autonomous operation means the vehicle computer controls the propulsion system, brake system, and steering system without needing input from a human operator; semi-autonomous operation means the vehicle computer controls one or two of the propulsion system, brake system, and steering system and a human operator controls the remainder, or that the vehicle computer controls all three of the propulsion system, the brake system, and the steering system but the human operator must be prepared to take over control of the vehicle110; and nonautonomous operation means a human operator controls the propulsion system, brake system, and steering system.

Each vehicle110may include a user interface115. The user interface115presents information to and receives information from an occupant of the vehicle110. The user interface115may be located, e.g., on an instrument panel in a passenger cabin of the vehicle110, or wherever may be readily seen by the occupant. The user interface115may include dials, digital readouts, screens, speakers, and so on for providing information to the occupant, e.g., human-machine interface (HMI) elements such as are known. The user interface115may include buttons, knobs, keypads, microphone, and so on for receiving information from the occupant.

One or more mobile devices120associated with the vehicles110may be connected to the computer100via the network105. Each mobile device120is a portable computing device such as a mobile phone, e.g., a smartphone, or a tablet. The mobile device120is a computing device including a processor and a memory. For example, the mobile device120may be owned and carried by a person who is the operator or owner of a respective one of the vehicles110.

With reference toFIG.2, the computer100is programmed to receive a plurality of the waypoints205. (To increase legibility, only some of the waypoints205are marked inFIGS.2and3.) The waypoints205are points within a geographic area. The waypoints205may be represented as geographic coordinates. The waypoints205may include one or two terminal waypoints240, designated as first or final waypoints205of the final ordering.

The waypoints205are arrangeable into an ordering. For the purposes of this disclosure, an “ordering” is defined as a set of objects with a specified order or sequence of the objects relative to one another, i.e., one of the objects is first, another object is second, and so on. For example, an ordering may be an order or sequence in which the waypoints205are visited along a route.

The computer100is programmed to divide the waypoints205into the clusters210. For the purposes of this disclosure, a “cluster” is defined as an unordered set of objects. The waypoints205may be sorted into the clusters210based on one or more characteristics of the waypoints205, e.g., the closest together waypoints205along one or more dimensions. The terminal waypoints240may be left out of the clusters210.

The computer100may be programmed to divide the waypoints205into the clusters210by executing a clustering algorithm. The computer100may use any suitable clustering algorithm for the waypoints205, e.g., k-means clustering, mini-batch k-means, density-based spatial clustering of applications with noise (DBSCAN), Gaussian mixture model, balance iterative reducing and clustering using hierarchies (BIRCH), affinity propagation clustering, mean-shift clustering, ordering points to identify the clustering structure (OPTICS), agglomerative hierarchy clustering, divisive hierarchical clustering, spectral clustering, etc. The clustering algorithm may be one for which a final number of clusters210is unspecified before executing the clustering algorithm (though an initial estimate of the number of clusters210may be a parameter of the clustering algorithm), e.g., affinity propagation, BIRCH, DBSCAN, mean shift, or OPTICS.

The computer100is programmed to divide the waypoints205into the clusters210according to at least one metric. For example, the metric may include at least one of distance, geographical density, travel time, or energy consumption. The computer100may determine values for a parameter of the clustering algorithm based on the metric. For example, a parameter of affinity propagation is similarity between pairs of the waypoints205, and the similarity may be determined as one or a combination of a distances between a pair of the waypoints205(either Euclidean distance or distance as traveled), a travel time between the pair of waypoints205, or an energy consumed traveling between the pair of waypoints205. For another example, a parameter of BIRCH is density of the waypoints205, and the density may be determined as the geographical density, i.e., the number of waypoints205per unit area.

The computer100may be programmed to divide the waypoints205in one of the clusters210into a plurality of further clusters210, e.g., according to the same metric. In the example illustrated inFIG.2, the computer100receives the waypoints205in a “zeroth” iteration220, divides the waypoints205into four clusters210in a first iteration225, and divides the waypoints205in two of those clusters210into two further clusters210for each of the two clusters210in a second iteration230. The computer100may iteratively divide the waypoints205in at least one of the clusters210into further clusters210, e.g., for a preset number of iterations or until a clustering condition fails to be satisfied, as described below. The preset number of iterations may be chosen based on a typical amount of clustering of a type of the waypoints205, e.g., a typical amount of clustering of waypoints on a delivery route. At each iteration, the computer100may divide the waypoints205in (some or all of) the clusters210from the immediately previous iteration into the further clusters210, e.g., the waypoints205in the clusters210in the first iteration225into further clusters210in the second iteration230, the waypoints205in the (further) clusters210in the second iteration230into further clusters210in a third iteration, etc. (The term “cluster” is used herein refer to clusters210at any iteration, and the term “further cluster” is used herein to refer to the clusters210in a next iteration.)

The computer100may be programmed to determine whether a cluster210satisfies a clustering condition. The clustering condition may be implemented as part of the clustering algorithm. For example, the clustering condition may be satisfied depending on whether the clustering algorithm divides the waypoints205into multiple clusters210. For another example, the clustering condition may include a threshold for the metric of the clustering algorithm, e.g., a minimum threshold for a change in the metric from one iteration to a next iteration. The change in the metric may be, e.g., an increase in density within the clusters210from one iteration to the next iteration or a decrease in a mean pairwise distance between the waypoints205within the clusters210from one iteration to the next iteration. The minimum threshold may be chosen to indicate a nonspurious increase or decrease. The computer100may iteratively divide the waypoints205in the clusters210satisfying the clustering condition until the clustering condition fails to be satisfied, e.g., none of the clusters210in an iteration satisfy the clustering condition.

The computer100may be programmed to determine representative waypoints235for the respective clusters210. The representative waypoint235can serve as a stand-in for the cluster210, e.g., for the optimization algorithm, which operates on waypoints205as described below. For example, the representative waypoint235may be a centroid of the cluster210. The computer100may determine the centroid by, for each dimension, determining a mean of the values for that dimension of the waypoints205. For example, the dimensions may be latitude and longitude, and the centroid may be represented as a geographical coordinate with a latitude equal to a mean of the latitudes of the waypoints205and a longitude equal to a mean of the longitudes of the waypoints205. For another example, the computer100may select one of the waypoints205of each cluster210as an exemplar of that cluster210, e.g., when using affinity propagation as the clustering algorithm.

With reference toFIG.3, the computer100may be programmed to determine a cost associated with an ordering of the clusters210or waypoints205. The cost may be associated with a lower-level ordering of the waypoints205within one of the clusters210, an upper-level ordering of the clusters210in the first iteration225, or a mid-level ordering of the clusters210(and possibly unclustered waypoints205) within a cluster210. The clusters210may be represented by the respective representative waypoints235when determining the cost. The cost may be defined as a function of the ordering, e.g., a value of a cost function taking the ordering as an argument. For example, the cost function may be a sum of transition costs between consecutive clusters210or waypoints205, e.g., as given in the following equation:

C=∑i=1N-1ci,i+1
in which C is the cost of the ordering, i is an index of placement in the ordering. N is the number of waypoints205or clusters210in the ordering, and ci,i+1is the transition cost from the ith waypoint205or cluster210to the next waypoint205or cluster210in the ordering. The cost may include at least one of distance, travel time, or energy consumption. For example, the transition costs may be the distance, travel time, or energy consumption to travel from one waypoint205or cluster210to a next waypoint205or cluster210in the ordering (with the clusters210represented by the representative waypoints235).

The computer100is programmed to execute an optimization algorithm to arrange the waypoints205or clusters210within a cluster210into an ordering or to arrange the clusters210in the first iteration225into an ordering. The clusters210may be represented by the representative waypoints235when executing the optimization algorithm, i.e., the optimization algorithm may be executed on the representative waypoints235. The optimization algorithm may be any algorithm suitable for combinatorial optimization, e.g., Steiner trees, Eulerian cycles, linear programming, max flow, fastest path such as Dijkstra's algorithm, push-relabel algorithm, edge-contraction algorithm, etc. The optimization algorithm may determine the ordering, i.e., arrange the waypoints205or clusters210into the ordering, by minimizing the cost associated with the ordering, i.e., outputting the ordering for which the optimization algorithm found a minimum cost.

The computer100is programmed to arrange the clusters210into an upper-level ordering, e.g., by executing the optimization algorithm on the clusters210, e.g., on the clusters210in the first iteration225. The upper-level ordering is an ordering of the clusters210in the first iteration225. In the example illustrated inFIG.3, the upper-level ordering may be {fourth cluster210d, second cluster210b, first cluster210a, third cluster210c}.

The computer100may be programmed to arrange the further clusters210in each cluster210into a mid-level ordering, e.g., by executing the optimization algorithm on the further clusters210within that cluster210, e.g., on the further clusters210in the second iteration230within each cluster210of the first iteration225. Each mid-level ordering is an ordering within a cluster210from one iteration of the further clusters210in that cluster210in a next iteration; i.e., each mid-level ordering is an ordering of the further clusters210in iteration j+1 that are in a cluster210in iteration j. In the example illustrated inFIG.3, the mid-level ordering of the further clusters215a-cin the second cluster210bmay be {third further cluster215c, second further cluster215b, first further cluster215a}. The computer100may iteratively arrange the further clusters210in one iteration within the respective clusters210in an immediately previous iteration into respective mid-level orderings. The computer100may iteratively arrange the further clusters210until reaching an iteration for which the clusters210do not contain further clusters210, only waypoints205, e.g., the iteration at which the clustering condition was not satisfied as described above.

The computer100is programmed to arrange the waypoints205within the clusters210, e.g., within each cluster210that does not contain further clusters210, into respective lower-level orderings, e.g., by executing the optimization algorithm on the waypoints205within each cluster210that does not contain further clusters210. A lower-level ordering is an ordering of the waypoints205within a cluster210.

The computer100may be programmed to, before arranging the waypoints205or further clusters210in a cluster210into an ordering, determine a start waypoint205or start further cluster210and an end waypoint205or end further cluster210. The start waypoint205or start further cluster210may serve as a first waypoint205or cluster210in the ordering, and the end waypoint205or end further cluster210may serve as a final waypoint205or cluster210in the ordering. The computer100may determine the start waypoint205or start further cluster210and the end waypoint205or end further cluster210within a cluster210based on an ordering containing the cluster210, e.g., in the example ofFIG.3, the start waypoint205and end waypoint205in the third further cluster215cmay be based on the mid-level ordering of the further clusters215a-cwithin the second cluster210b, and the start further cluster210and end further cluster210in the second cluster210bmay be based on the upper-level ordering of the clusters210. For example, the computer100may determine the start waypoint205or start further cluster210and the end waypoint205or end further cluster210within a cluster210to minimize a pairwise cost between consecutive clusters210in the ordering containing the cluster210, e.g., in the example ofFIG.3, to determine the end waypoint205in the third further cluster215cby minimizing the pairwise cost from the third further cluster215cto the second further cluster215bin the mid-level ordering within the second cluster210b, and to determine the start further cluster215and end further cluster215in the second cluster210bby minimizing the pairwise costs between the fourth cluster210dand the second cluster210band between the second cluster210band the first cluster210ain the upper-level ordering. The pairwise cost may be, e.g., the transition cost as described above. The pairwise cost may include at least one of distance, travel time, or energy consumption.

Once determined, the start waypoints205or start further clusters210and the end waypoints205or end further clusters210may serve as constraints on the optimization algorithm when executed on the clusters210containing the start waypoints205or start further clusters210and the end waypoints205or end further clusters210. In the example ofFIG.3, the start waypoint205and end waypoint205in the third further cluster215cmay serve as a constraint on the optimization algorithm when executed to arrange the waypoints205in the third further cluster215c, and the start further cluster210and end further cluster210in the second cluster210bmay serve as a constraint on the optimization algorithm when executed to arrange the further clusters215in the second cluster210b. The terminal waypoints240may similarly serve as a constraint on the optimization algorithm when determining the upper-level ordering. For the purposes of this disclosure, “serving as a constraint” is defined as restricting potential solutions to solutions satisfying the constraint.

The computer100may be programmed to insert the further clusters210or waypoints205in a cluster210into a position of that cluster210in an ordering containing that cluster210, with the further clusters210or waypoints205in the ordering of that cluster210. In the example ofFIG.3, the second cluster210bincludes the mid-level ordering {third further cluster215c, second further cluster215b, first further cluster215a}, and the waypoints205in each further cluster215in the respective lower-level ordering can be inserted into the position of the respective further cluster210in the mid-level ordering, resulting in {{waypoints205of third further cluster215cin lower-level ordering}, {waypoints205of second further cluster215bin lower-level ordering}, {waypoints205of first further cluster215ain lower-level ordering} }. In other words, the waypoints205of the further clusters215in the lower-level orderings are concatenated in the mid-level ordering of the further clusters215. Further in the example ofFIG.3, the upper-level ordering is {fourth cluster210d, second cluster210b, first cluster210a, third cluster210c}, and the further clusters215in the second cluster210bin the mid-level ordering can be inserted into the position of the second cluster210bin the upper-level ordering, resulting in {fourth cluster210d, {third further cluster215c, second further cluster215b, first further cluster215a}, first cluster210a, third cluster210c}. The same can be done with the other clusters210in the upper-level ordering. The computer100may iteratively insert the waypoints205or further clusters210from one iteration into a position of the cluster210that includes the waypoints205or further clusters210from that iteration in an immediately previous iteration with the waypoints205or further clusters210in the respective ordering. Iteratively combining the examples fromFIG.3just described results in {fourth cluster210d, {{waypoints205of third further cluster215cin lower-level ordering}, {waypoints205of second further cluster215bin lower-level ordering}, {waypoints205of first further cluster215ain lower-level ordering}}, first cluster210a, third cluster210c}.

The computer100is programmed to output the waypoints205in a final ordering by concatenating the waypoints205in the lower-level orderings according to the mid-level orderings and upper-level ordering, e.g., the lower-level orderings arranged in the mid-level orderings of the next iteration, those mid-level orderings arranged in the mid-level orderings of the next iteration, and so on to the upper-level ordering. In the example ofFIG.3, the waypoints205in the lower-level orderings are concatenated in the order of the mid-level orderings of the further clusters210within the clusters210, with those mid-level orderings following the upper-level ordering of the clusters210.

FIG.4shows the waypoints205in a geographic area. (To increase legibility, only some of the waypoints205are marked inFIG.4.) The final ordering defines a final route410passing through the waypoints205in the final ordering. The computer100may be programmed to determine the final route410from the final ordering. The computer100may determine intermediate routes between each pair of consecutive waypoints205. The intermediate routes may be turn-by-turn instructions from one waypoint205to the next waypoint205. For example, the computer100may determine the intermediate routes using a mapping algorithm, as is known.

The computer100may be programmed to instruct one of the vehicles110to navigate the final route410. For example, the computer100may transmit the final ordering of the waypoints205to the vehicle110via the network105. The computer100may transmit the final route410along with the final ordering, or a vehicle computer of the vehicle110may determine the final route410from the final ordering by determining the intermediate routes between each pair of consecutive waypoints205. The vehicle computer may autonomously or semi-autonomously navigate the vehicle110along the final route410. Alternatively or additionally, the vehicle computer may instruct the user interface115of the vehicle110to display the final route410to an operator of the vehicle110so that the operator can navigate the vehicle110along the final route410. For another example, the computer100may transmit the final ordering of the waypoints205to the mobile device120associated with the vehicle110via the network105. The computer100may also transmit the final route410, or the mobile device120may determine the final route410as described. The mobile device120may display the final route410to the operator of the vehicle110so that the operator can navigate the vehicle110along the final route410.

FIG.5is a process flow diagram illustrating an example process500for determining the final ordering of the waypoints205. The memory of the computer100stores executable instructions for performing the steps of the process500and/or programming can be implemented in structures such as mentioned above. As a general overview of the process500, the computer100receives the waypoints205. The computer100iteratively divides the waypoints205or representative waypoints235into clusters210and determines the representative waypoints235for the clusters210until the clustering condition is not satisfied. The computer100iteratively arranges the waypoints205or representative waypoints235within each cluster210in a current iteration and determines the start waypoint205and end waypoint205of the immediately previous iteration until reaching the iteration with only waypoints205and no further clusters210. Finally, the computer100outputs the waypoints205in the final ordering.

The process500begins in a block505, in which the computer100receives the waypoints205, including the terminal waypoints240.

Next, in a block510, the computer100divides the waypoints205or representative waypoints235at a current iteration into clusters210, starting at the zeroth iteration220, as described above.

Next, in a decision block515, determines whether any of the clusters210at the current iteration, i.e., the clusters210created in the block510in the current iteration, satisfy the clustering condition, as described above. Upon determining that at least one of the clusters210at the current iteration satisfy the clustering condition, the process500proceeds to a block520. Upon determining that none of the clusters210at the current iteration satisfy the clustering condition, the process500proceeds to a block530.

In the block520, the computer100determines representative waypoints235for the clusters210at the current iteration, as described above.

Next, in a block525, the computer100advances to a next iteration. After the block525, the process500returns to the block510, in which the computer100will act on the representative waypoints235created in the block520in what is now the immediately previous iteration.

In the block530, the computer100arranges the waypoints205or representative waypoints235at a current iteration into orderings, either the waypoints205or representative waypoints235within the clusters210at the current iteration or the representative waypoints235of the clusters210at the first iteration225, by executing the optimization algorithm, as described above. The first execution of the block530starts with the first iteration.

Next, in a decision block535, the computer100determines whether there is a next iteration for which to arrange the waypoints205or representative waypoints235, i.e., whether the current iteration is the final iteration advanced to in the block525, i.e., whether the next iteration includes clusters210. If there is a next iteration, the process500proceeds to a block540. If there is not a next iteration, the process500proceeds to a block550.

In the block540, the computer100advances the current iteration to a next iteration.

Next, in a block545, the computer100determines the start waypoints205and end waypoints205of the clusters210at the current iteration, as described above. After the block545, the process500returns to the block530to arrange the waypoints205, constrained by the start waypoints205and end waypoints205, as described above.

In the block550, the computer100outputs the waypoints205in the final ordering, as described above.

Next, in a block555, the computer100determines the intermediate routes between the consecutive waypoints205to form the final route410, as described above.

Next, in a block560, the computer100instructs one of the vehicles110to navigate the final route410, as described above. After the block560, the process500ends.

In general, the computing systems and/or devices described may employ any of a number of computer operating systems, including, but by no means limited to, versions and/or varieties of the Ford Sync® application, AppLink/Smart Device Link middleware, the Microsoft Automotive® operating system, the Microsoft Windows® operating system, the Unix operating system (e.g., the Solaris® operating system distributed by Oracle Corporation of Redwood Shores, California), the AIX UNIX operating system distributed by International Business Machines of Armonk, New York, the Linux operating system, the Mac OSX and iOS operating systems distributed by Apple Inc. of Cupertino, California, the BlackBerry OS distributed by Blackberry, Ltd. of Waterloo, Canada, and the Android operating system developed by Google, Inc. and the Open Handset Alliance, or the QNX® CAR Platform for Infotainment offered by QNX Software Systems. Examples of computing devices include, without limitation, an on-board vehicle computer, a computer workstation, a server, a desktop, notebook, laptop, or handheld computer, or some other computing system and/or device.

Computing devices generally include computer-executable instructions, where the instructions may be executable by one or more computing devices such as those listed above. Computer executable instructions may be compiled or interpreted from computer programs created using a variety of programming languages and/or technologies, including, without limitation, and either alone or in combination, Java™, C, C++, Matlab, Simulink, Stateflow, Visual Basic, Java Script, Python, Perl, HTML, etc. Some of these applications may be compiled and executed on a virtual machine, such as the Java Virtual Machine, the Dalvik virtual machine, or the like. In general, a processor (e.g., a microprocessor) receives instructions, e.g., from a memory, a computer readable medium, etc., and executes these instructions, thereby performing one or more processes, including one or more of the processes described herein. Such instructions and other data may be stored and transmitted using a variety of computer readable media. A file in a computing device is generally a collection of data stored on a computer readable medium, such as a storage medium, a random access memory, etc.

A computer-readable medium (also referred to as a processor-readable medium) includes any non-transitory (e.g., tangible) medium that participates in providing data (e.g., instructions) that may be read by a computer (e.g., by a processor of a computer). Such a medium may take many forms, including, but not limited to, non-volatile media and volatile media. Instructions may be transmitted by one or more transmission media, including fiber optics, wires, wireless communication, including the internals that comprise a system bus coupled to a processor of a computer. Common forms of computer-readable media include, for example, RAM, a PROM, an EPROM, a FLASH-EEPROM, any other memory chip or cartridge, or any other medium from which a computer can read.

Databases, data repositories or other data stores described herein may include various kinds of mechanisms for storing, accessing, and retrieving various kinds of data, including a hierarchical database, a set of files in a file system, an application database in a proprietary format, a relational database management system (RDBMS), a nonrelational database (NoSQL), a graph database (GDB), etc. Each such data store is generally included within a computing device employing a computer operating system such as one of those mentioned above, and are accessed via a network in any one or more of a variety of manners. A file system may be accessible from a computer operating system, and may include files stored in various formats. An RDBMS generally employs the Structured Query Language (SQL) in addition to a language for creating, storing, editing, and executing stored procedures, such as the PL/SQL language mentioned above.

In some examples, system elements may be implemented as computer-readable instructions (e.g., software) on one or more computing devices (e.g., servers, personal computers, etc.), stored on computer readable media associated therewith (e.g., disks, memories, etc.). A computer program product may comprise such instructions stored on computer readable media for carrying out the functions described herein.

In the drawings, the same reference numbers indicate the same elements. Further, some or all of these elements could be changed. With regard to the media, processes, systems, methods, heuristics, etc. described herein, it should be understood that, although the steps of such processes, etc. have been described as occurring according to a certain ordered sequence, such processes could be practiced with the described steps performed in an order other than the order described herein. It further should be understood that certain steps could be performed simultaneously, that other steps could be added, or that certain steps described herein could be omitted.

All terms used in the claims are intended to be given their plain and ordinary meanings as understood by those skilled in the art unless an explicit indication to the contrary in made herein. In particular, use of the singular articles such as “a,” “the,” “said,” etc. should be read to recite one or more of the indicated elements unless a claim recites an explicit limitation to the contrary. The adjectives “first.” “second,” “third,” and “fourth” are used throughout this document as identifiers and are not intended to signify importance, order, or quantity. Use of “in response to” and “upon determining” indicates a causal relationship, not merely a temporal relationship.

The disclosure has been described in an illustrative manner, and it is to be understood that the terminology which has been used is intended to be in the nature of words of description rather than of limitation. Many modifications and variations of the present disclosure are possible in light of the above teachings, and the disclosure may be practiced otherwise than as specifically described.