Dissertation > Excellent graduate degree dissertation topics show

Research on Inquiry Algorithm HCCS in Public Transport System

Author: GaoZuo
Tutor: QiHong;SunChengMin
School: Jilin University
Course: Computer technology
Keywords: public traffic networks the shortest path algorithm the least transfer times the transfer times algorithm HCCS
CLC: TP311.52
Type: Master's thesis
Year: 2008
Downloads: 128
Quote: 1
Read: Download Dissertation

Abstract


In the inquiry system of public transportation, the most critical problem is that how to choose the travel path. In order to help those who use public transport system to make a choice in the path, changing routes, this paper proposed the inquiry algorithm HCCS, and use it in the transportation design. After testing, it was improved that this algorithm has a certain credibility and feasibility. It can solve transport problems in multi-point at the minimum number of change for the first goal, and the least time at the second.By statistical analysis in passengers, we may conclude that the factors they concerned most are as follows: frequency of bus-change, expenses, distance, and so on. Above all, the first two attract their attention most. Freight car drivers concerned about the shortest path in order to the greatest degree of time-saving fuel-efficient, but bus passengers tend to taken convenience and comfort into more account Therefore, the meaning of shortest-path in road network and bus lines is different. In road network, the target is only to find the path at the shortest distance between two points. But in transportation, passengers would not change their bus in order to seek the shortest path. Because a transfer to another line is time-consuming and laborious, In many cases, bus-change need to take a trip on foot to another site, and this will take some time. So to the bus passengers, the significance of the shortest path is not the shortest distance, but the least change times. Consequently the research of inquiry algorithm HCCS based on the number of transfer is of great significance.Considering passengers’travel psychoanalysis.the public model of optimum route is proposed,which goal is minimal transfer times.On the integrated analysis of the space relationship between station,basing on the searching model,the least transfer times problem is solved by translating to the problem of the shortest route between two stations.The improved Dijkstra algorithm is proposed,which can efficiently solve the travel project of all the least transfer times between two spots.The operating efficiencies of the existing shortest path searching algorithms such as Dijkstra algorithm on the limiting ellipse,etc.,are low and inconvenient in practical application,so they need to be improved. Although the algorithm on the limiting ellipse reduce the size of search scale greatly, but in the process of calculation for each node must determine whether it is in the oval, there are a large number of non-linear method of operation, all of the above make this algorithm inefficiency. With the increase in the number of polygon edges, the area of the polygon gradually reduce, finally approaching the end of the oval area. On the other hand, with the increase in the number of polygons edge, the calculate amount will be multiplied. Because each node and each side should be compared, so as to determine the point inside the edge or outside, In the end, to determine whether the nodes is in the polygon. Therefore, there is a certain side of the optimal number of polygons which could make the smallest capacity of calculating. By comparison in calculation, we find the optimal number which is 4.0n the basis of the Dijkstra algorithm on the limiting ellipse,by means of linearizing the ellipse and optimizing the limiting polygon.an optimal path algorithm based on the limiting parallelogram was proposed to improve significantly the searching efficiency.Through the above-mentioned algorithms for comprehensive, this paper proposed the inquiry algorithm HCCS, which aimed at minimum number of change and the least travel time.On this basis, established the optimal model of transportation.The innovation of algorithm HCCS is that it combined the algorithm of shortest path, transfer time, geometric method to limit the scope of the path, and improved the efficiency of the classical algorithms, bus travel can be more convenient in multi-point, and had also brought up a new viewpoint about sites next to each other. In the algorithm, only when the different lines have a point of intersection, interchange can be achieved. But the result is not always in line with the actual situation, for example, it may cost only twice interchange to the destination, However, the result of change requires three or four times.The reason is that we ignored the appearance of human habits, that they used to walk a short distance than taking a bus . People often choose this way to reduce the number of transfer. Sites next to each other is a semi-quantitative concept of distance used to describe the distance between sites,usually based on people’s behavior and the average length of the road. If there are no buses for interchange indirectly after getting off at a site, we may consider whether there is a site nearside. According to this idea, the above method had been improved, analysis about sites next to each other had been added to each transfer,therefore, the first goal is to reduce the number of interchange and least travel time as the second one. Changchun public traffic data is used as an example to prove that the algorithm applied in transportation is feasible and efficient. This transport system can solve transport problems in multi-point, and can also find variety plans between two sites. It is an improvement on the shortest path algorithm. To apply the algorithm HCCS to practice can improve the efficiency of the public transport inquiry system, thus may help people enjoy a fast and convenient inquiry service.

Related Dissertations

  1. Collection and Processing of Picking Routing Information in Distribution Center,F253.9
  2. Spatial information service based on SSH traffic control system analysis and design,U495
  3. Collaborative Design and Implementation of Communication Platform,TP311.52
  4. Periodic time-varying networks in grain logistics optimization problem,F304.3
  5. Research on Dynamic Time Shortest Path and Application of the CGIS,P208
  6. Seismic Wavefield Modeling and Its Application,P631.4
  7. Design and Implementation of the Dynamical Presentation and Analysis of Fiber Network Resource Based on WEB GIS,TN929.11
  8. Urban Mass Transit Bus Joint Planning,F572
  9. Research and Implementation of the Armed Police Manpower Deployment System,E277
  10. Based on the heterogeneity of railway passenger demand transfer service programs and system optimization,U293.1
  11. Study on the Logistics Park Location with Bi-level Distribution,F224
  12. Time Expanded Network in the Hurricane Evacuation System Application,TP319
  13. Chinese word segmentation key technology research,TP391.1
  14. Reseach and Implementation of Distribution Management System Based on Collection and Distribution,TP311.52
  15. The Electronic Map System Based on PDA,P208
  16. The Research of Related Technology of Active Parking Guidance System,TP273.5
  17. Research on Surveillance Video Cropping Methods,TP391.41
  18. Study of Moving Target Detection and Tracking in Video Based on Trajectory,TP391.41
  19. Protein Structure Prediction Based on Fragment Database,TP399-C8
  20. Research and Development of Urban Transportation Network Analysis Systems Based on ComGIS,TP311.52
  21. Research of Key Technology Based on GIS Spatial Analysis,P208

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer software > Program design,software engineering > Software Engineering > Software Development
© 2012 www.DissertationTopic.Net  Mobile