Embedded Files
Abstract
Abstract
Recently, many works show promising results by using Large Language Models (LLMs) as translators to convert natural language into intermediate expressions that can be used by existing algorithms, which makes directly using LLMs to solve problems less promising. Although the method of directly using LLMs to solve problems does not perform well at the current stage, we argue that it is too early to conclude that we should favor the hybrid method. We propose that we should dive deeper and analyze what impedes the performance of LLMs and find ways to tackle these issues. In this work, we investigate the potential of using solely LLMs to solve Vehicle Routing Problems (VRP), which are widely used to model robot task planning, by directly generating code from natural language task descriptions. We begin by constructing a dataset comprising 80 problem instances, including 8 types of single- and multi-vehicle routing problems, to evaluate the performance of LLMs. We then design different frameworks and varying types of context. After that, we perform evaluations based on different frameworks and different contexts. We conduct an extensive study on what impedes LLMs from performing well and propose several potential directions for future work to improve the performance of LLMs in solving VRP.
Two illustrative examples of robot routing problems are as follows: On the left, a marine robot needs to visit a set of candidate locations to take ocean samples, and we want the robot to finish the sampling process as fast as possible. This corresponds to a Traveling Salesman Problem (TSP). On the right, an aerial robot with cameras needs to visit a subset of all the candidate viewpoints and ensure enough coverage of the bridge to construct it, which corresponds to the generalized TSP.
Two illustrative examples of robot routing problems are as follows: On the left, a marine robot needs to visit a set of candidate locations to take ocean samples, and we want the robot to finish the sampling process as fast as possible. This corresponds to a Traveling Salesman Problem (TSP). On the right, an aerial robot with cameras needs to visit a subset of all the candidate viewpoints and ensure enough coverage of the bridge to construct it, which corresponds to the generalized TSP.
An illustrative scenario based on the Capacitated Vehicle Routing Problem (CVRP). Left: an overview of acquiring solutions given task descriptions in a zero-shot manner. Right: solution visualization.
An illustrative scenario based on the Capacitated Vehicle Routing Problem (CVRP). Left: an overview of acquiring solutions given task descriptions in a zero-shot manner. Right: solution visualization.
Framework overview. (a) single attempt; (b) self-debugging; (c) self-debugging with self-verification. In (c), the solution generator and the verifier generator have the same structure as the generator in (b).
Framework overview. (a) single attempt; (b) self-debugging; (c) self-debugging with self-verification. In (c), the solution generator and the verifier generator have the same structure as the generator in (b).
Overview of prompt design. Based on the LLM framework: self-debugging with self-verification.
Overview of prompt design. Based on the LLM framework: self-debugging with self-verification.
Performance of three different frameworks based on GPT-4 Turbo
Performance of three different frameworks based on GPT-4 Turbo
Feel free to check our paper to get more details.
Feel free to check our paper to get more details.
Citation
@article{huang2024words,
title={From Words to Routes: Applying Large Language Models to Vehicle Routing},
author={Huang, Zhehui and Shi, Guangyao and Sukhatme, Gaurav S},
journal={arXiv preprint arXiv:2403.10795},
year={2024}
}
Page updated
Google Sites
Report abuse