US-12620316-B2 - Systems and methods for determining vehicle routes for trip optimization

Abstract

Systems and methods including one or more processors and one or more non-transitory storage devices storing computing instructions configured to run on the one or more processors and perform: receiving input information for generating one or more routes for one or more vehicles, the input information including one or more group classifiers; processing the input information based on the one or more group classifiers; analyzing, using one or more solving engines, the input information to generate the one or more routes for the one or more vehicles; selecting, from each of the one or more solving engines, a vehicle route from the one or more routes that satisfies a threshold; and transmitting the vehicle route to a dispatcher to facilitate coordinating, by the dispatcher, operation of a vehicle from the one or more vehicles along the vehicle route. Other embodiments are disclosed herein.

Inventors

• Yu Wang
• Shixiang Luo
• Ou Sun
• Yiru Wen
• Lijie Wan
• Jing Huang
• Mingang Fu
• Ishaan Das
• Toshi Prakash

Assignees

• WALMART APOLLO, LLC

Dates

Publication Date

20260505

Application Date

20240131

Claims (20)

1. 1 . A system comprising: one or more processors; and one or more non-transitory computer-readable media storing computing instructions that, when run on the one or more processors, cause the one or more processors to perform: receiving input information for generating one or more routes for one or more vehicles, the input information including one or more group classifiers; using, before invoking Open Source Routing Machine (OSRM) application programming interface (API) calls, a validation unit to validate the input information; selecting, based on a group classifier of the one or more group classifiers, one or more solving engines, from a plurality of solver engines, that generate one or more routes that are more optimal than routes generated by a solver greedy application programming interface (API); generating the one or more routes, for the one or more vehicles, by sending, to the one or more solving engines, the input information and information obtained by invoking the OSRM API calls based on using the validation unit to validate the input information and based on selecting the one or more solving engines; selecting, after the one or more solving engines generate the one or more routes, a vehicle route from the one or more routes; and causing a vehicle, of the one or more vehicles, to operate along the vehicle route, by transmitting information regarding the vehicle route in a JSON format that is consumable by a downstream system associated with the vehicle.
2. 2 . The system of claim 1 , wherein the input information includes order information, vehicle information, and store information.
3. 3 . The system of claim 1 , wherein the one or more group classifiers include in-home, chaining, or dynamic batching.
4. 4 . The system of claim 1 , wherein the one or more solving engines include at least one of an Adaptive Large Neighborhood Search (ALNS) solver, an optimization solver, or a generic neighborhood search solver.
5. 5 . The system of claim 4 , wherein the one or more solving engines are operated in parallel.
6. 6 . The system of claim 4 , wherein the ALNS solver includes a destroy operator and a repair operator.
7. 7 . The system of claim 1 , wherein generating the one or more routes comprises: receiving vehicle routes from each of the one or more solving engines; and comparing the vehicle routes from each of the one or more solving engines.
8. 8 . The system of claim 1 , wherein causing the vehicle to operate along the vehicle route comprises: generating a scheduling of vehicles for each of the one or more vehicles to operate along the plurality of vehicle routes.
9. 9 . A method, the method comprising: receiving input information for generating one or more routes for one or more vehicles, the input information including one or more group classifiers; using, before invoking one or more application programming interface (API) calls, a validation unit to validate the input information; selecting, based on a group classifier of the one or more group classifiers, one or more solving engines, from a plurality of solver engines, that generate one or more routes that are more optimal than routes generated by a solver greedy application programming interface (API); generating, based on using the validation unit to validate the input information and based on selecting the one or more solving engines, the one or more routes, for the one or more vehicles, by using the one or more solving engines to analyze the input information and information obtained by invoking the one or more API calls; selecting, after generating the one or more routes, a vehicle route from the one or more routes; and causing a vehicle, of the one or more vehicles, to operate along the vehicle route by transmitting information regarding the vehicle route.
10. 10 . The method of claim 9 , wherein the input information includes order information, vehicle information, and store information.
11. 11 . The method of claim 9 , wherein the one or more group classifiers include in-home, chaining, or dynamic batching.
12. 12 . The method of claim 9 , wherein the one or more solving engines include at least one of an Adaptive Large Neighborhood Search (ALNS) solver, an optimization solver, or a generic neighborhood search solver.
13. 13 . The method of claim 12 , wherein the one or more solving engines are operated in parallel.
14. 14 . The method of claim 12 , wherein the ALNS solver includes a destroy operator and a repair operator.
15. 15 . The method of claim 9 , wherein generating the one or more routes comprises: receiving vehicle routes from each of the one or more solving engines; and comparing the vehicle routes from each of the one or more solving engines.
16. 16 . The method of claim 9 , further comprising: generating a scheduling of vehicles for the one or more vehicles to operate along a plurality of vehicle routes that include the one or more routes.
17. 17 . A non-transitory computer readable storage medium storing one or more computing instructions that, when run on one or more processors, cause the one or more processors to: receive input information that includes information regarding one or more group classifiers; use, before invoking one or more application programming interface (API) calls, a validation unit to validate the input information; select, based on a group classifier of the one or more group classifiers, one or more solving engines that are configured to generate routes that are more optimal than other routes generated by a solver greedy application programming interface (API); select a vehicle route based on selecting the one or more solving engines and after using the validation unit to validate the input information; and cause a vehicle to operate along the vehicle route by transmitting information regarding the vehicle route in a format that is consumable by a downstream system associated with the vehicle.
18. 18 . The non-transitory computer readable storage medium of claim 17 , wherein the vehicle route is selected based on the vehicle route utilizing less resources than any other vehicle route of the routes.
19. 19 . The non-transitory computer readable storage medium of claim 17 , wherein the one or more computing instructions further cause the one or more processors to: invoke the solver greedy API to generate the other routes based on the one or more solving engines failing to provide information regarding the routes within a time limit; and select the vehicle route from the other routes.
20. 20 . The non-transitory computer readable storage medium of claim 17 , wherein the one or more computing instructions further cause the one or more processors to: invoke the one or more API calls to retrieve distance information and time information; and sending the input information, the distance information, and the time information to the one or more solving engines after selecting the one or more solving engines.

Description

TECHNICAL FIELD This disclosure relates generally to computing system management, and more particular to systems and methods for determining vehicle routes for trip optimization to deliver order packages. BACKGROUND At least some known systems and industries provide delivery services to their customers. For example, some companies in various industries provide the delivery of goods to their customers, such as the delivery of grocery items by grocers. In particular, the delivery of grocery items has increasingly become a method by which consumers obtain their grocery needs. To deliver goods, many of these companies employ delivery systems that include delivery vehicles. The delivery systems may include the scheduling and assignment of delivery orders to delivery vehicles. For example, a customer that purchases grocery items online may have the grocery items delivered to their home in a delivery vehicle. As the number of delivery orders increase, the determination of delivery routes, along with delivery costs, may increase as well. As such, there are opportunities to improve delivery systems and, in particular, to improve route assignments in a goods delivery system. BRIEF DESCRIPTION OF THE DRAWINGS To facilitate further description of the embodiments, the following drawings are provided in which: FIG. 1 illustrates a front elevational view of a computer system that is suitable for implementing various embodiments of the systems disclosed in FIG. 3; FIG. 2 illustrates a representative block diagram of an example of the elements included in the circuit boards inside a chassis of the computer system of FIG. 1; FIG. 3 illustrates a representative block diagram of a system, according to an embodiment; FIG. 4 illustrates a flowchart for a method, according to certain embodiments; FIG. 5 illustrates an exemplary system architecture, according to certain embodiments; FIG. 6 illustrates an exemplary solving service architecture, according to certain embodiments; and FIG. 7 illustrates an exemplary solving engine architecture, according to certain embodiments. For simplicity and clarity of illustration, the drawing figures illustrate the general manner of construction, and descriptions and details of well-known features and techniques may be omitted to avoid unnecessarily obscuring the present disclosure. Additionally, elements in the drawing figures are not necessarily drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help improve understanding of embodiments of the present disclosure. The same reference numerals in different figures denote the same elements. The terms “first,” “second,” “third,” “fourth,” and the like in the description and in the claims, if any, are used for distinguishing between similar elements and not necessarily for describing a particular sequential or chronological order. It is to be understood that the terms so used are interchangeable under appropriate circumstances such that the embodiments described herein are, for example, capable of operation in sequences other than those illustrated or otherwise described herein. Furthermore, the terms “include,” and “have,” and any variations thereof, are intended to cover a non-exclusive inclusion, such that a process, method, system, article, device, or apparatus that comprises a list of elements is not necessarily limited to those elements, but may include other elements not expressly listed or inherent to such process, method, system, article, device, or apparatus. The terms “left,” “right,” “front,” “back,” “top,” “bottom,” “over,” “under,” and the like in the description and in the claims, if any, are used for descriptive purposes and not necessarily for describing permanent relative positions. It is to be understood that the terms so used are interchangeable under appropriate circumstances such that the embodiments of the apparatus, methods, and/or articles of manufacture described herein are, for example, capable of operation in other orientations than those illustrated or otherwise described herein. The terms “couple,” “coupled,” “couples,” “coupling,” and the like should be broadly understood and refer to connecting two or more elements mechanically and/or otherwise. Two or more electrical elements may be electrically coupled together, but not be mechanically or otherwise coupled together. Coupling may be for any length of time, e.g., permanent or semi-permanent or only for an instant. “Electrical coupling” and the like should be broadly understood and include electrical coupling of all types. The absence of the word “removably,” “removable,” and the like near the word “coupled,” and the like does not mean that the coupling, etc. in question is or is not removable. As defined herein, two or more elements are “integral” if they are comprised of the same piece of material. As defined herein, two or more elements are “non-integral” if each is comprised of a diff