With the widespread use of map websites and on-line navigation systems

the need for multi-user concurrent queries for travel information is ever-increasing. In such a case

a bottleneck problem is how to improve the efficiencies of the multi-user concurrent path queries as much as possible

with only a controllable

as little as possible loss of the precisions of the query results. In this paper

an efficiency/accuracy trade-off control approach for the A* heuristic shortest path algorithm is presented

which fits a curve function of the heuristic factor

the efficiency and the accuracy with large samples

by the techniques of systematic sampling and intelligent symbolic regression. The efficiency and the accuracy of the A* algorithm are measured by the comparison with the Dijkstra exact algorithm. Through the use of the derived trade-off control model

the effective heuristic factor can be automatically determined with the input of the on-line user number and the required path accuracy

and as a result

the service response time for each user is much shortened.