Route planning and optimization for traveling salesman problem and variants
US12393887B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 8, 2021 |
| Grant date | Aug 19, 2025 |
| Priority date | — |
| Expiry date | May 18, 2042 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06Q10/06315
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The invention relates to route planning and optimization. In some embodiments, the invention includes obtaining vertex data describing target attributes, including at least one target location, and process dynamics data describing system constraints of a process: defining vertex functionals, describing attribute requirements, and edge functionals, which use the system constraints to determine cost requirements, for cost objectives; and using the data, the functionals, and the cost objectives to construct a T-graph that includes a label space representing the target attributes. Next, the T-graph is solved to construct a label space trajectory by determining waypoints such that the process (1) travels through all target locations and (2) satisfies the attribute requirements, dynamically calculating travel cost by applying the cost requirements to each intervening edge, and minimizing the travel cost according to the cost objectives. The optimal space trajectory is executed to navigate the process through the target locations.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.