Methods and systems for rendering an optimized route in accordance with GPS data and a shopping list

• US 9,595,062 B2
• Filed: 10/12/2012
• Issued: 03/14/2017
• Est. Priority Date: 10/12/2012
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal-Mart Stores Texas LLC (WalMart Inc.)
• Inventors: Goulert, Valerie
• Primary Examiner(s): Allen, William
• Application Number:
  US13/650,652
• Publication Number:
  US 20140108193A1
• Time in Patent Office: 1,614 Days
• Field of Search: 705 141- 147, 705 261- 2723
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 20/322 Aspects of commerce using mobile devices [M-devices]
• CPC Class Codes: G06Q 30/0259 based on store location
• CPC Class Codes: G06Q 30/0633 Lists, e.g. purchase orders, compilation or processing
• CPC Class Codes: G06Q 30/0639 Item locations
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/024 Guidance services

Abstract

Techniques for optimizing a shopping agenda are disclosed. The techniques include receiving an electronic shopping list containing one or more items, each item indicating a product sold by a retailer. The techniques further include obtaining a store map, the store map being indicative of a layout of a store associated with the retailer. The techniques further include determining one or more product waypoints based on the one or more items in the electronic shopping list and the store map, each product waypoint of the one or more product waypoints corresponding to one of the one or more items and being indicative of a location of the product indicated by the item in the store. The techniques also include determining a route traveling through each of the one or more product waypoints and providing the route for display.

Claims

1. A computer-implemented method comprising:

receiving by a computer system comprising a communication device including one or more wireless transceivers for performing wireless communication, an electronic shopping list containing a plurality of items intended to be purchased, each item indicating a product sold by a retailer, the items being added to the electronic shopping list from the computer system or from a mobile computing device of a user, and wherein one of the items of the plurality is a last item listed on the electronic shopping list;

acquiring, by the communication device of the computer system, GPS location data of the mobile computing device of the user;

obtaining, by the computer system, a store map, the store map being indicative of a layout of a store associated with the retailer and wherein the store map is selected from a plurality of store maps each corresponding to one of a plurality of stores by comparing the GPS location data of the mobile computing device with GPS location data associated with each of the stores and being stored in a locations database to determine which store is most proximate to the GPS location data of the mobile computing device;

determining, by the computer system, a plurality of product waypoints based on the plurality of items in the electronic shopping list and the store map, each product waypoint of the plurality of product waypoints corresponding to one of the plurality of items and being indicative of a location of the product indicated by the item in the store, and wherein the computer system further determines the product waypoints by querying the locations database using the items received from the electronic shopping list and the obtained store map;

comparing, by the computer system, a number of items listed on the electronic shopping list to a predetermined threshold;

determining, by the computer system, a first checkout lane type if the number of items is greater than the predetermined threshold, wherein a plurality of checkout lanes are of the first checkout lane type;

determining, by the computer system, a second checkout lane type if the number of items is less than the predetermined threshold, wherein a plurality of checkout lanes are of the second checkout lane type;

selecting, by the computer system, a checkout lane from among the checkout lanes of the first checkout lane type if the first checkout lane type is determined, wherein the checkout lane is selected for being the nearest checkout lane to the last item listed on the electronic shopping list from among the checkout lanes of the first checkout lane type;

selecting, by the computer system, a checkout lane from among the checkout lanes of the second checkout lane type if the second checkout lane type is determined, wherein the checkout lane is selected for being the nearest checkout lane to the last item listed on the electronic shopping list from among the checkout lanes of the second checkout lane type;

determining, by the computer system, a checkout waypoint corresponding to selected checkout lane from the locations database;

determining, by the computer system, a route traveling through each of the plurality of product waypoints and the determined checkout waypoint, and wherein the computer system optimizes the route by determining a plurality of paths defined between product waypoints, assigning a weight to each path based on a distance or time of travel between product waypoints and by applying an algorithm to analyze the weights to optimize the route;

rendering, by the computer system, an image of the store map having the location of the mobile computing device, the route, each of the plurality of product waypoints and the determined checkout waypoint; and

providing, by the communication device of the computer system, the the rendered image of the store map for display on the mobile computing device of the user.

2. The method of claim 1, further comprising:

determining, by the computer system, an entrance waypoint indicating an entrance location of the store based on one or more of the product waypoints;

determining, by the computer system, the route traveling through the entrance waypoint; and

rendering, by the computer system, the image of the store map having the entrance waypoint.

3. The method of claim 1, wherein any one or more of the items are deselectable from the electronic shopping list by the mobile computing device, wherein the computer system removes an existing product waypoint in response to deselection of the item from the electronic shopping list.

4. The method of claim 3, further comprising the step of updating, by the computer system, the route to account for removal of the existing product waypoint.

5. The method of claim 1 wherein the items are added to the electronic shopping list by converting a digital photograph of an image captured by a digital camera of the mobile device and determining one or more items to add to the electronic shopping list in response to converting the digital photograph.

6. The method of claim 1 wherein the items are added to the electronic shopping list by analyzing with the computer system at least one of a previous electronic shopping list of the user and a purchase history of the user.

7. The method of claim 1 further comprising:

acquiring, by the computer system, GPS location data of the mobile computing device of the user while the user navigates the store; and

comparing, by the computer system, the GPS location data of the mobile computing device with location data associated with the determined route.

8. The method of claim 7 further comprising:

detecting, by the computer system, whether the location of the mobile computing device deviates from the determined route; and

updating, by the computer system, the route in response to detecting that the mobile computing device has deviated from the determined route.

9. The method of claim 1 wherein determining, by the computer system, the route further comprises determining a plurality of routes traveling through each of the plurality of product waypoints and the determined checkout waypoint and presenting the plurality of routes to the mobile computing device for selection by the user.

10. The method of claim 1 wherein applying the algorithm is further defined as applying Dijkstra'"'"'s algorithm.

11. A server comprising:

at least one processor;

a communication device including one or more wireless transceivers for performing wireless communication;

memory operably connected to the at least one processor; and

the memory storing;

a store locator module configured to obtain a store map, the store map being indicative of a layout of a store associated with a retailer and wherein the store locator module is configured to acquire GPS location data of a mobile computing device of the user using the communication device and select the store map from a plurality of store maps each corresponding to one of a plurality of stores by comparing the GPS location data of the mobile computing device with GPS location data associated with each of the stores and being stored in a locations database to determine which store is most proximate to the GPS location data of the mobile computing device;

a route determination module configured to receive an electronic shopping list containing a plurality of items intended to be purchased, from a mobile computing device, each item indicating a product sold by a retailer, the items being added to the electronic shopping list from the server or from a mobile computing device of a user, and wherein one of the items of the plurality is a last item listed on the electronic shopping list;

a locator module configured to;

determine a plurality of product waypoints based on the plurality of items in the electronic shopping list and the store map, each product waypoint of the plurality of product waypoints corresponding to one of the plurality of items and being indicative of a location of the product indicated by the item in the store and wherein the locator module is further configured to determine the product waypoints by querying the locations database using the items received from the electronic shopping list and the obtained store map;

compare a number of items listed on the electronic shopping list to a predetermined threshold;

determine a first checkout lane type if the number of items is greater than the predetermined threshold, wherein a plurality of checkout lanes are of the first checkout lane type;

determine a second checkout lane type if the number of items is less than the predetermined threshold, wherein a plurality of checkout lanes are of the second checkout lane type;

select a checkout lane from among the checkout lanes of the first checkout lane type if the first checkout lane type is determined, wherein the checkout lane is selected for being the nearest checkout lane to the last item listed on the electronic shopping list from among the checkout lanes of the first checkout lane type;

select a checkout lane from among the checkout lanes of the second checkout lane type if the second checkout lane type is determined, wherein the checkout lane is selected for being the nearest checkout lane to the last item listed on the electronic shopping list from among the checkout lanes of the second checkout lane type; and

determine a checkout waypoint corresponding to the selected checkout lane from the locations database;

and wherein the route determination module is further configured to;

determine a route traveling through each of the plurality of product waypoints and the determined checkout waypoint and to optimize the route by determining a plurality of paths defined between product waypoints, assigning a weight to each path based on a distance or time of travel between product waypoints, and by applying an algorithm to analyze the weights to optimize the route;

render an image of the store map having the location of the mobile computing device, the route, each of the plurality of product waypoints and the determined checkout waypoint; and

provide, using the communication device, the rendered image of the store map for display on the mobile computing device of the user.

12. The server of claim 11, wherein:

the locator module is further configured to determine an entrance waypoint indicating an entrance location of the store based on one or more of the product waypoints, and the route determination module is further configured to determine the route based on the entrance waypoint and to render the image of the store map having the entrance waypoint.

13. The server of claim 11 wherein the route determine module is further configured to receive a deselection of any one or more of the items from the electronic shopping list by the mobile computing device, wherein the route determine module removes an existing product waypoint in response to deselection of the item from the electronic shopping list.

14. The server of claim 13 wherein the route determine module is further configured to update the route to account for removal of the existing product waypoint.

15. The server of claim 11 wherein the route determine module is further configured to convert a digital photograph of an image captured by a digital camera of the mobile device and to determine one or more items to add to the electronic shopping list in response to converting the digital photograph.

16. The server of claim 11 wherein the route determine module is further configured to add one or more items to the electronic shopping list by analyzing at least one of a previous electronic shopping list of the user and a purchase history of the user.

17. The server of claim 11 wherein the store locator module is further configured to:

acquire GPS location data of the mobile computing device of the user while the user navigates the store; and

compare the GPS location data of the mobile computing device with location data associated with the determined route.

18. The server of claim 17 wherein the store locator module is further configured to:

detect whether the location of the mobile computing device deviates from the determined route; and

update the route in response to detecting that the mobile computing device has deviated from the determined route.

19. The server of claim 11 wherein the locator module is further configured to:

determine a plurality of routes traveling through each of the plurality of product waypoints and the determined checkout waypoint; and

present the plurality of routes to the mobile computing device for selection by the user.

20. The server of claim 11 wherein the algorithm is further defined as Dijkstra'"'"'s algorithm.