VRPTW-Bench: A New Evaluation Benchmark for Large Language Models Solving Vehicle Routing Problems with Time Windows

VRPTW-Bench is a fine-grained evaluation benchmark for large language models (LLMs) solving Vehicle Routing Problems with Time Windows (VRPTW). It aims to assess LLMs' capabilities in three core dimensions: route generation, constraint diagnosis, and multi-objective optimization, providing a tool to explore the application boundaries of LLMs in the field of operations research and optimization.

VRPTW is a classic NP-hard problem in operations research, requiring compliance with constraints such as customer time windows and vehicle capacity. Traditionally, it relies on optimization algorithms like genetic algorithms. The reasoning ability, generalization ability, and potential for integrating domain knowledge of LLMs make them a new exploration direction for solving VRPTW.

1. Direct Route Generation: Requires the model to output feasible routes, evaluating solution quality (total distance, number of vehicles) and feasibility; 2. Constraint Violation Diagnosis: Identifies constraint violations in candidate solutions and explains the reasons; 3. Non-Dominated Solution Identification: Finds non-dominated solutions for multi-objective optimization from candidate solutions, testing the ability for trade-off analysis.

1. Prompt engineering significantly affects performance (structured input, examples, and reasoning processes improve performance); 2. Model size is positively correlated with performance but with diminishing marginal returns; 3. LLMs perform well on small instances, but their performance decreases significantly as the problem size increases.

LLMs cannot replace professional VRP solvers, but they can quickly generate initial solutions to assist decision-making, serve as educational and training tools, and act as natural language interfaces for human-machine collaboration. This research expands the boundary of LLM capabilities, and a solution paradigm integrating LLMs with traditional algorithms may emerge in the future.

Currently, it is limited to standard VRPTW and does not cover complex variants; there is little consideration for computational efficiency. In the future, it is necessary to expand the evaluation scope, optimize efficiency, and explore collaboration modes between LLMs and traditional algorithms (such as generating initial solutions or neighborhood operators).