Semantic Routing: Fusing LLMs and Combinatorial Optimization Problems within the Generative Problem Solving (GPS) Domain

Combinatorial optimization and particularly vehicle routing problems (VRP), as well as trip or itinerary planning remain a fundamental challenge in operations research. However, the advent of large language models introduces a paradigm shift towards more adaptable, context aware, and human-centric optimization frameworks. The study adopted a multidisciplinary literature review driven approach to examine the intersection of large language models and combinatorial optimization within the ambit of VRPs. The scope spans from professional practitioners using specialized optimization software to commuters and tourists navigating the built environment. The paper explores how LLMs may simultaneously strengthen underlying optimization processes and improve user interfaces – in particular by enhancing transparency, interactivity, and explainability. The study identified various opportunities for LLMs to enhance routing systems by, for example, enabling nuanced translation of (implicit) user input into personalized and context aware route generation. The integration of retrieval augmented generation (RAG) may enhance data fidelity and temporal relevance, while hybrid solver configuration and automated heuristic generation as well as self-debugging mechanism are amongst the proposed application areas of LLMs. Advances in semantic routing may be especially pertinent for active travelers who rely on nuanced environmental attributes such as lighting, terrain, and perceived safety when selecting routes. Effectively capturing and incorporating such complex, multi-objective preferences into a route recommender system may support a broader adoption of sustainable, non-motorized modes of transport.