by Eric Johnson
When you hop on the highway, you rarely go on pure instinct. Most of us reach for a navigation system like Garmin and Google for directions. What if you could have as detailed “turn here” steps for your shopping trip? For H-E-B personal shoppers, saving a few steps can make a big difference, so we built a new service to do just that—introducing Pyxis developed by H-E-B Digital’s Inventory & Location Management team.
Pyxis is an easily consumable API designed to provide the most efficient paths through stores using a starting point, an ending point, and a list of products between. Named for Pyxis, the constellation in the southern sky that represents a Mariner’s compass, we originally designed Pyxis to improve the efficiency of our Curbside personal shoppers, but the potential uses are much greater.
How did shoppers know where to go?
Up until now, we provided “directions” for our personal shoppers through a service called Product Locator. This method was based on a static sequence designed for a traditional customer path—starting at the main entrance of the store and ending at the check stands. This is a super helpful way to direct a customer who needs to visit every aisle, but it’s not efficient for our Partners who work in Curbside (affectionally called “Curbies”). Couple that with the fact that maintaining up-to-date floor plans was very labor-intensive, and the generated paths felt like opening an atlas to navigate your way.
On average, 25% of our stores change some portion of their floor plan per week, so to support all of our use cases and have the ability to scale, we needed a dynamic, automated sequencing service that could solve multiple pathing needs.
Laying the foundation
To compute a path through a store, you need a map or graph of the floor plan that you can run a pathing algorithm against. If you have ever driven with a navigation system in your vehicle, you know how annoying an outdated map can be. It’s paramount that our floor plans are current.
Pyxis automatically checks for floor plan deltas on a daily basis and generates a new graph if a change is detected, ensuring optimal pathing. Each graph contains boundaries, nodes (which represent every fixture in the store), and edges that provide possible paths between nodes. These graphs are generated based on the coordinate and rotational data from an internal system used to create and modify floor plans.
Solving the Traveling Salesperson Problem
The classic algorithm quandary is “the traveling salesperson problem.” If you are given a list of cities and the distances between various pairs of them, what is the shortest possible route to visit each city and return to the origin point?
If our personal shoppers are our salespeople, how can we get them around the store faster? Now with our automatically generated, up-to-date graphs for every floor plan, we can run pathing algorithms against them by providing a list of products. We leverage Google’s OR Tools (open source software for combinatorial optimization) which seeks to find the best solution to a problem out of a very large set of possible solutions. In action, it looks like this.
Through the use of dynamic start and endpoints in combination with the traveling salesperson solver, our Pyxis paths are providing an average of a 16% decrease in the required distance to travel from the static sequencing method.
What is next for Pyxis?
We initially piloted this new sequencing service with personal shoppers across 8 stores, with the plan of being in all stores by the end of the summer. However, with the increase in digital orders during COVID, we were asked to accelerate the pilot to provide these improvements to personal shoppers faster and all of our eStores are now using PXYIS. So far, we have seen both qualitative and quantitative improvements based on Partner feedback and an increase in shopped items per hour respectively. In addition to personal shoppers, we will be developing specialized sequencing for setting tags and coupons, for our managers as they do their rounds around the stores, and for our customers’ shopping lists.
As we plan the next version of Pyxis, we’ll examine variables such as customer density in the aisles, test using the best location relative to path for products with multiple locations, and add the ability to reroute when hitting various obstacles. As we evolve the future of grocery, we’ll evolve our store maps, and keep looking to the stars for inspiration to provide the best in-store experience for our Partners and customers.
Eric Johnson is the Senior Manager for Engineering for Inventory & Location Management. You can connect with him on Linkedin.
