Abstract In recent literature, several approaches have been developed to solve over-constrained travel planning problems, which are often framed as conditional temporal problems with discrete choices. These approaches are able to explain the causes of failure and recommend alternative solutions by suspending or weakening temporal constraints. While helpful, they may not be practical in many situations, as we often cannot compromise on time. In this paper, we present an approach for solving such over-constrained problems, by also relaxing non-temporal variable domains through the consideration of additional options that are semantically similar. Our solution, called Conflict-Directed Semantic Relaxation (CDSR), integrates a knowledge base and a semantic similarity calculator, and is able to simultaneously enumerate both temporal and domain relaxations in best-first order. When evaluated empirically on a range of urban trip planning scenarios, CDSR demonstrates a substantial improvement in flexibility compared to temporal relaxation only approaches.