DROVER: Diffusion-Based Routing with Verbal Preferences
Published in Under review, 2026
Authors & Affiliations
Jesse van Remmerden, Yaoxin Wu, Yingqian Zhang, Zaharah Bukhsh — Information Systems, Department of Industrial Engineering & Innovation Sciences, Eindhoven University of Technology (TU/e), The Netherlands.
Corresponding author: j.v.remmerden@tue.nl
This paper is currently under review. A preprint will be linked here once it is available.
Abstract
Neural combinatorial optimization has produced vehicle routing solvers that construct high-quality tours at a fraction of the cost of exact methods, but all of them optimize a fixed, scalar objective. Practitioners, by contrast, routinely impose preferences that are stated in natural language and vary from day to day — requests such as visiting one customer before another, or keeping a given set of stops on a single vehicle — which cannot practically be encoded as reward terms in advance. We introduce DROVER, a language-conditioned discrete diffusion model that accepts such requests directly as input. DROVER encodes the request with a frozen language model and steers its denoising trajectory toward solutions that satisfy it through a new guidance technique. To evaluate this setting, which no existing benchmark covers, we construct a dataset spanning 26 request types and approximately 3 × 10⁹ distinct phrasings, paired with reference solutions from established solvers and an automatic verifier that determines whether a proposed tour obeys its request. DROVER satisfies the stated request in 98–99% of instances with 50 to 1,000 nodes, compared with roughly 32% for the strongest existing neural solvers, and attains 87–90% on request types held out from training, where competing methods satisfy none. In the unconditioned setting it remains competitive with state-of-the-art neural solvers on tour length, achieving the best results among them at 100 nodes.
Keywords
Vehicle routing; Neural combinatorial optimization; Discrete diffusion models; Classifier-free guidance; Language-conditioned generation; Instruction following; Benchmark design
Links
Recommended citation: van Remmerden, J., Wu, Y., Zhang, Y., & Bukhsh, Z. DROVER: Diffusion-Based Routing with Verbal Preferences. Under review.