Global Optimal Travel Planning for Massive Travel Queries in Road Networks

Yehong Xu, Lei Li*, Mengxuan Zhang, Zizhuo Xu, Xiaofang Zhou

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Travel 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.

Original languageEnglish
Pages (from-to)8377-8394
Number of pages18
JournalIEEE Transactions on Knowledge and Data Engineering
Volume36
Issue number12
DOIs
Publication statusPublished - 2024

Fingerprint

Dive into the research topics of 'Global Optimal Travel Planning for Massive Travel Queries in Road Networks'. Together they form a unique fingerprint.

Cite this