Wheelchair users frequently face uncertainty about which routes are accessible, and traditional navigation providers have limited functionality for such people with reduced mobility. Existing navigation apps typically tend to optimize on time, but the complexity of such route planning often results in multi-objective problem solving, often requiring computing a set of Pareto-optimal solutions or known user preferences a priori. Our work, WheelTailor, bridges this gap by presenting an interactive AI companion for accessible routing that supports preference elicitation and an efficient search strategy. We demonstrate WheelTailor on top of an AI companion blueprint and present it as a web-based tool operating on realistic, accessible map data.