Vehicle routing in urban areas based on the Oil Consumption Weight -Dijkstra algorithm

Jin-dong Zhang; Yu-jie Feng; Fei-fei Shi; Gang Wang; Bin Ma; Rui-sheng Li; Xiao-yan Jia

Vehicle routing in urban areas based on the Oil Consumption Weight -Dijkstra algorithm

View Fulltext

Author(s): Jin-dong Zhang ^{1, 2, 3} ; Yu-jie Feng ³ ; Fei-fei Shi ³ ; Gang Wang ³ ; Bin Ma ³ ; Rui-sheng Li ³ ; Xiao-yan Jia ⁴
- Affiliations: 1: State Key Laboratory of Automobile Simulation and Control, University of Jilin, Changchun 130012, People's Republic of China ;
  2: Key Laboratory of Symbol Computation and Knowledge Engineering of the Ministry of Education, University of Jilin, Changchun 130012, People's Republic of China ;
  3: College of Computer Science and Technology, University of Jilin, Changchun 130012, People's Republic of China ;
  4: Department of Hand Surgery, The First Hospital of Jilin University, Changchun 130021, People's Republic of China
Source: Volume 10, Issue 7, September 2016, p. 495 – 502
DOI: 10.1049/iet-its.2015.0168 , Print ISSN 1751-956X, Online ISSN 1751-9578

Received 19/08/2015, Accepted 09/05/2016, Revised 11/03/2016, Published 01/09/2016

In this study, the authors refine a route-planning algorithm, in order to improve the route planning strategy in urban areas under traffic congestion. Considering the Oil Consumption Weight (OCW) and route planning methods, they propose an OCW-Dijkstra algorithm. In the algorithm, the parameters concerning the vehicle and driving environment, such as distance, speed, driving time, idling time, travel flow, driving oil consumption and idling oil consumption, are used for producing the OCW with weighted calculation in each section of the journey. In the execution of the algorithm, an adjacency matrix of the OCW is first generated by loading segment description, regional routing and the point information in an urban map. After the initial point and the destination point are selected, the optimal route is planned and generated automatically. In addition, the algorithm has self-learning methods, which can update the parameters and the OCW in real time. From the results of simulating experiments and the comparison with exhaustive algorithm, they find that the OCW-Dijkstra algorithm performs more effectively and robustly, which consequently saves driving time, as well as decreases oil consumption.

References

1. 1)
  - 13. Jiang, X.K., Fan, H.J., Kang, D.: ‘Optimization strategy based on shortest path algorithm of Dijkstra’. Second Int. Conf. Communication and Technology, Melbourne, Australia, January 2015, pp. 78–82.
2. 2)
  - 8. Galan-Garcia, J.L., Aguilera-Venegas, G., Galan-Garcia, M.A., et al: ‘A new probabilistic extension of Dijkstra's algorithm to simulate more realistic traffic flow in a smart city’, Appl. Math. Comput., 2015, 267, pp. 780–789.
3. 3)
  - 15. Rosyidi, L., Pradityo, H.P., Gunawan, D., et al: ‘Timebase dynamic weight for Dijkstra algorithm implementation in route planning software’. First Int. Conf. Intelligent Green Building and Smart Grid, Taipei, Taiwan, April 2014, pp. 14394104-1–4.
4. 4)
  - 12. Hernandez-Aceituno, J., Acosta, L., Pineiro, J.D.: ‘Application of time dependent probabilistic collision state checkers in highly dynamic environments’, PLoS One, 2015, 10, (3), pp. (e0119930)1–17 (doi: 10.1371/journal.pone.0119930).
5. 5)
  - 2. Kahn, M.E.: ‘Fueling the future’, Science, 2015, 347, (6219), p. 239 (doi: 10.1126/science.aaa1579).
6. 6)
  - 6. Dijkstra, E.W.: ‘A note on two problems in connexion with graphs’, Numer. Math., 1959, 1, pp. 269–271 (doi: 10.1007/BF01386390).
7. 7)
  - 5. Li, Z.H., Yang, J., Yang, J., et al: ‘GPS route decisions research based on network theory’. Nineth Int. Conf. Computational Intelligence and Security, People's Republic of China, December 2013, pp. 484–488.
8. 8)
  - 1. Matthias, S.: ‘Does traffic congestion slow the economy?’, J. Plan. Lit., 2011, 26, (4), pp. 391–404 (doi: 10.1177/0885412211409754).
9. 9)
  - 17. Ekedebe, N., Chen, Z.J., Xu, G.B., et al: ‘On an efficient and effective intelligent transportation system (ITS) using field and simulation data’. Conf. Multisensor, Multisource Information Fusion: Architectures, Algorithms, and Applications, Baltimore, USA, May 2014, p. 91210B.
10. 10)
  - 4. Gayathri, N., Vijaya Chandrakala, K.R.M.: ‘A novel technique for optimal vehicle routing’. Int. Conf. Electronics and Communication Systems, Coimbatore, India, February 2014, pp. 1–5.
11. 11)
  - 7. Misa, T.J.: ‘An Interview with Edsger W. Dijkstra’, Commun. ACM, 2010, 53, (8), pp. 41–47 (doi: 10.1145/1787234.1787249).
12. 12)
  - 9. Altarelli, F., Braunstein, A., Dall'Asta, L., et al: ‘The edge-disjoint path problem on random graphs by message-passing’, PLoS One, 2015, 10, (12), pp. (e0145222)1–14 (doi: 10.1371/journal.pone.0145222).
13. 13)
  - 3. Guarnieri, M., Balmes, J.R.: ‘Outdoor air pollution and asthma’, Med. Gen. Intern., 2014, 383, (9928), pp. 1581–1592.
14. 14)
  - 18. Thomas, G., Voulgaris, P.G.: ‘Fuel minimization of a moving vehicle in suburban traffic’. American Control Conf., Washington, USA, June 2013, pp. 4009–4014.
15. 15)
  - 10. Li, F.Q., Long, C., Wu, N.Q.: ‘The problem of reserved-lane for hazardous chemicals transportation and heuristic algorithm’. Int. Conf. Engineering Technology and Application, Xiamen, China, May 2015, vol. 22, no. 01031, pp. 1–6.
16. 16)
  - 14. Sun, S.C., Duan, Z.Y., Sun, S., et al: ‘How to find the optimal paths in stochastic time-dependent transportation networks’. IEEE 17th Int. Conf. Intelligent Transportation Systems, Qingdao, China, October 2014, pp. 2348–2353.
17. 17)
  - 11. Parrado, N., Donoso, Y.: ‘Congestion based mechanism for route discovery in a V2I-V2V system applying smart devices and IoT’, Sensors, 2015, 15, (4), pp. 7768–7806 (doi: 10.3390/s150407768).
18. 18)
  - 16. Jiang, J.C., Wu, L.X.: ‘A re-optimization dynamic shortest path algorithm for vehicle navigation’. Int. Conf. Geoscience and Remote Sensing Symp., Quebec, Canada, November 2014, pp. 3109–3112.

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Vehicle routing in urban areas based on the Oil Consumption Weight -Dijkstra algorithm

References

Related content