LLM-QL: A LLM-Enhanced Q-Learning Approach for Scheduling Multiple Parallel Drones
Qian Zhou, Jiayang Wu, Mengyue Zhu, Yuhang Zhou, Fu Xiao, Yanchun Zhang
Abstract
This study addresses the Multiple Flying Sidekicks Traveling Salesman Problem (mFSTSP), where parallel Unmanned Aerial Vehicles (UAVs, or Drones) work alongside truck to enhance delivery efficiency. Existing scheduling approaches face challenges in high computational costs and the risk of converging to local optima due to excessive exploration in unknown environments, especially in large-scale mFSTSP. This study proposed a Large Language Model Enhanced Q-Learning Approach (LLM-QL) to solve mFSTSP, which combines the local exploration advantages of Q-Learning with the global understanding of unknown environments provided by LLMs, thus improving the efficiency of path planning. A novel prompt strategy is also provided, transforming the problem modeling into a format easily understood by LLMs, guiding the algorithm's exploration and significantly improving convergence. We also provide a proof of the convergence of LLM-QL. Experimental results demonstrate that LLM-QL achieves up to a 1.35 x improvement in key performance metrics such as total completion time, algorithm runtime, and UAV utilization, compared to existing state-of-the-art methods.