Xu, YehongLi, LeiZhang, MengxuanXu, ZizhuoZhou, Xiaofang2025-05-232025-05-231041-4347ORCID:/0000-0001-8155-4942/work/184102104http://www.scopus.com/inward/record.url?scp=85200802330&partnerID=8YFLogxKhttps://hdl.handle.net/1885/733751911Travel planning plays an increasingly important role in our society. The travel plans, which consist of the paths each vehicle is suggested to follow and its corresponding departure time, influence the traffic conditions naturally. However, existing travel planning algorithms cannot consider the planning results and their influences simultaneously, so traffic congestion could be created when many vehicles are directed to adopt similar travel plans. In this paper, we propose the Global Optimal Travel Planning (GOTP) problem that aims to minimize traffic congestion by continuously evaluating traffic conditions for a set of planning tasks. Achieving this global optimization goal is non-trivial because travel planning and traffic evaluation are time-consuming and interdependent. To break this dependency, we first propose a GOTP paradigm that interleaves travel planning and traffic evaluation for queries, where the planning consists of departure time planning and travel path planning. To implement the paradigm, we propose the serial model that optimizes travel plans one by one, followed by the batch model that improves processing efficiency, and the iterative model that further optimizes planning quality. Extensive experiments on large real-world networks with synthetic and real workloads validate the effectiveness and efficiency of our methods.This work was supported in part by Hong Kong Research Grants Council under Grant 16202722 and Grant T43-513/23-N - TRS, in part by the Natural Science Foundation of China under Grant 62072125 and Grant 62202116, in part by Guangzhou-HKUST(GZ) Joint Funding Scheme under Grant 2023A03J0135, in part by Guangzhou Basic and Applied Basic Research Scheme under Grant 2024A04J4455, and in part by the JC STEM Lab of Data Science Foundations funded by The Hong Kong Jockey Club Charities Trust.18enPublisher Copyright: © 1989-2012 IEEE.Massive-Scale route planningshortest path querytraffic-aware road network202410.1109/TKDE.2024.343940985200802330