A Methodology and Modelling Technique for Taxi Path Optimization

Abstract:

Vehicle Routing Problem (VRP) is a typical combinatorial optimization problem. A new type of bionic algorithm-ant colony algorithm is very appropriate to solve Vehicle Routing Problem because of its positive feedback, robustness, parallel computing and collaboration features. In view of the taxi route optimization problem, this article raised the issue of the control of the taxi, by using the Geographic Information System (GIS), through the establishment of the SMS platform and reasonable taxi dispatch control center, combining ant colony algorithm to find the most nearest no-load taxi from the passenger, and giving the no-load taxi the best path to the passenger. Finally this paper use Ant Colony laboratory to give the simulation. By using this way of control, taxis can avoid the no-load problem effectively, so that the human and material resources can also achieve savings.

• Periodical: Advanced Materials Research (Volume 711)
• Pages: 816-821
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.711.816
• Online since: June 2013
• Authors: Zhi Ping Hou, Feng Jin, Qin Jian Yuan, Yong Yi Li
• Keywords: Ant Colony Algorithm (ACA), Geographic Information System (GIS), Optimal Path, Vehicle Routing Problem (VRP)

References

[1] G.B. Dantzig, R.H. Ramser: The Truck Dispatching Problem. Management Science. Vol.6 (1959), p.80.

DOI: 10.1287/mnsc.6.1.80

[2] L.D. Bodin, B.L. Golden, A.A. Assad, M. Hall: Routing and Scheduling of Vehicles and Crews, The State of Art. Computers & Operations Research.Vol.10 (1983),p.63.

[3] K. Altinkemer, B. Gavish: Parallel Savings Based Heuristic for the Delivery Problem,Operations Research.Vol.39(1991),p.456.

DOI: 10.1287/opre.39.3.456

[4] Laporte G,The Vehicle Routing Problem. An Overview of Exact and Approximate Algorithms. European Journal of Operational Research. Vol.59 (1992),p.345.

DOI: 10.1016/0377-2217(92)90192-c

[5] S Salhi, G.K. Rand: Incorporating Vehicle Routing into the Vehicle Fleet Composition Problem. European Journal of Operational Research.Vol.62(1993),p.323.

DOI: 10.1016/0377-2217(93)90220-h

[6] M. Dorigo, V. Maniezzo, A. Colorni: The ant system:Optimization by a colony of cooperating agents. IEEE Transactions on Systems,Man,and Cybernetics–Part B(1996).

DOI: 10.1109/3477.484436

[7] M. Dorigo, L.M. Gambardella: Ant Algorithms for Discrete Optimization. Artificial Life.Vol.5 (1999), p.137.

[8] M. Dorigo, L.M. Gambardella: Ant colony system:a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. Vol.1(1997), p.53.

DOI: 10.1109/4235.585892

[9] T. Stutzle, H. Hoos: Max-Min Ant System. Preprint submitted to Elsevier Science(1999).

[10] M. Dorigo, E. Bonabeau, G. Theraulaz: Ant algorithms and stigmergy. Future Generation Computer Systems. Vol.16(2000),p.851.

DOI: 10.1016/s0167-739x(00)00042-x

[11] T. Stutzle, H. Hoos: The MAX-MIN ant system and local search for the traveling salesman problem.In:Proc.of 20d Int.Conf.on Metaheuristics.Wien:springer-Verlag(1997).

DOI: 10.1109/icec.1997.592327

[12] B. Bullnheimer, R.F. Hartl,C. Strauss: Applying the Ant System to the Vehicle Routing Problem.Paper 2nd International Conference on Metaheuristics,Sophia-Antipolis,France(1997).