Global Optimal Travel Planning for Massive Travel Queries in Road Networks

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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Global Optimal Travel Planning (GOTP)</i> 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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">GOTP</i> 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 <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">serial model</i> that optimizes travel plans one by one, followed by the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">batch model</i> that improves processing efficiency, and the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">iterative model</i> 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.