Don't let the fact that you're dealing with a physical space throw you-- approach the project in the same way that you would an online issue. This is where it's helpful to have a set process you use in your UX work. For me, my process always follows the basic course of:
1.) Define the problem. What issues are you trying to solve? You cannot solve a problem you haven't identified or don't understand. You also can't solve all problems at once. Define a clearly stated problem or set of problems to address. Are you trying to decrease the amount of time a customer spends in a checkout line? Are you trying to make merchandise easier to find? Are you attempting to streamline the order online, pickup in-store process?
2.) Gather input and data. Once you've defined a problem, you can work to uncover the root cause of the problem. Speak with business stakeholders about what success might mean, what the root causes might be, and do some research to uncover relevant metrics. Limit your scope, and define what success would mean to you. After speaking with your stakeholders and observing lines in-store, something along the lines of "I'd like to decrease the amount of time customers spent waiting in line for a checkout by 10%" would work well to define the problem and the expected outcome. It clearly defines a problem to address and what success means.
3.) Iterate, present, and re-iterate. This is where you begin coming up with solutions to your issues. Things like sketches, wireframes, and whiteboarding are traditionally done here, and could still be useful in this situation. Make sure to work with both internal and external stakeholders at this stage. The earlier you get your design into the hands of your business partners and customers, the earlier you're going to get valuable feedback on the viability and reliability of your design and identify potential flaws that may require either tweaks or a re-design. Once you've been able to get buy in about a particular design, you can then move forward and hand the design off to the development team.
4.) Pass to development/QA. In the tech world, this step often means presenting your design to a team of developers and project managers, who then go about the process of implementing it in the codebase. In a physical world, this means handing your design off to the logistics and construction team that is responsible for actually installing and implementing your design. If you've done the groundwork well ahead of time, this stage should go smoothly and your role should be to simply support the implementation team during their process.
5.) Deployment. Your design is installed, and it's go-live time. Being around to watch the deployment process and ensure that your design has been implemented correctly is important to its success.
6.) Test, define new problems, return to square 1. Immediately post-deployment is a crucial stage for gathering metrics to measure success. Both subjective and objective data should be collected. You should always seek first to answer the question you began addressing, in this case "How long are customers actually spending in line?" You'll also want to check on other metrics. Does the process feel faster to the customer? Has there been a change in overall satisfaction rating? How about a rise or fall in repeat customers? Overall time spent at the checkout? How will you collect these data points?
Once you've completed this step, you'll likely have enough data to define new problems and return to step 1 with a new issue to tackle.