MODELING AND OPTIMIZING A VEHICLE NAVIGATION SYSTEM BY G-NETWORK

Abstract

Increasing the production of vehicles and ne- cessity to use private and public cars have led to heavy traffic that has negative effects in that respect. The aim of intelligent transportation systems (ITS) is improving the quality of transportation, re- ducing travelling time and reducing fuel consump- tion via advanced technologies. Clearly, analyzing the routing problems of vehicles and finding opti- mized routes are among the considerable challenges in intelligent transportation systems. Vehicle navigation systems are the systems used for leading and routing. Using GPRS communica- tion, these systems provide on-line services for col- lecting instant traffic information, such as vehicles coordination, speed and type, for enhancing them for efficient routing of vehicles. Furthermore, they can prepare diverse traffic reports regarding time, period, max. and min. speeds, the total driven dis- tance in a desired specific date or time limit. Many navigation systems have used offline city maps and pre-set maps together with the history of nav- igation data obtained from GPS. These systems are not suitable due to rapid changes in the traffic con- ditions. Since, online systems are preferred. Focusing on online navigation systems and dynamic VRP, we pre- sented a navigation system for the vehicles to receive updated traffic information on reaching each junc- tion, and select the best route with lower traffic to their destination, in case they are permitted to move in it. In this paper, we used G-Network for modeling the proposed vehicles navigation system. G-Networks are queuing networks with the idea of considering negative customers against positive ones. Negative customers or signals can be considered actual or virtual, operating in different manners in the net- work. They can destruct positive customers in a queue , cause momentary passing of the customers to another queue, or remove a group of customers from the network. Vehicles in our proposed model are positive cus- tomers and routing decisions are negative custom- ers, here with considered virtual. The queue net- work is the map of an assumed city. Vehicles may be of different types, such as cars, heavy vehicles and rescue vehicles. Therefore, positive customers in the modeling include different classes. In this graph, each junction and also segments distribut- ed uniformly in each pathway establish the queues of the queuing network. Accordingly, the relevant performance metrics of the network are presented. The given model provide the possibility for us to use gradient descent method for optimization of the routing. Gradient descent is a first order op- timization algorithm, used for finding the mini- mum rate of functions. In optimizing the behavior of the network, it was attempted to minimize the cost function, which includes parameters such as the probability of passing a type of vehicle from a junction and also probability of a routing decision in the junction. The obtained results from optimization show that the routing problems are improved by con- sidering different criteria including average delay for the vehicles, average delay for routing decisions, average delay for the whole network and average usefulness.

Keywords

• Vehicle routing,navigation system,G-Network

References

1. [1] E. Gelenbe, "Product-form queueing networks with negative and positive customers,"Applied Probability J., vol.28, no.3, 1991,pp.656–663.
2. [2] E. Gelenbe, "G-networks with instantaneous customer movement,"Applied ProbabilityJ.,vol.30,no.3, 1993,pp. 742–748.
3. [3] E. Gelenbe, "G-networks with signals and batch removal,"Probability in the Engineering and Informational Sciences , vol.7 ,1993, pp. 335–342.
4. [4] Dantzig and Ramser, "The truck dispatching problem," Management Science, vol.6,no.1,1959, pp. 80–91.
5. [5] Cooke and Halsey,"The shortest route through a network with time dependent in the rnodal transit times,"Mathematical Analysis andApplications J,vol.14, no.3,1966, pp.493–498.
6. [6] Speidel, "EDP-assisted fleet scheduling in tramp and coastal shipping," In Proceedings of the 2nd international ship operation automation symposium,Washington, D.C., Aug. 30_Sep.2, 1976, pp.507–510.
7. [7] Psaraftis, "A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem," Transportation Science, vol.14,no.2, 1980, pp.130–154.
8. [8] Ghiani et al.,"Real-time vehiclerouting: solution concepts," algorithms and parallel computing strategies.European Journal of Operational Research, vol.151,no.1,2003,pp.1–11.

9. [9] T. Bieding, S. Gِrtz, A. Klose, "On-line routing per mobile phone: a case on subsequent deliveries of newspapers", Springer Berlin Heidelberg, vol. 619, 2009, pp. 29–51.
10. [10] F. Ferrucci, S. Block, M. Gendreau, "A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods,"European Journal of Operational Research,vol.225 , no.1,2013, pp.130–141.
11. [11] N. Azi, M. Gendreau, J.Y. Potvin, "A dynamic vehicle routing problem with multiple delivery routes, "Annals of Operations Research,Vol. 199, no .1, 2012, pp. 103-112
12. [12] Mu et al, "Disruption management of the vehicle routing problem with vehicle breakdown, "European Journal of Operational Research, vol.62, no.4, 2011, pp.742–749.
13. [13] Li et al., "Real-time vehicle routing problems with time windows, "European Journal of Operational Research, vol.194,no.3,2009, pp.711–727.
14. [14] Muand Eglese,"Disrupted capacitated vehicle routing problem withorder release delay,"Annals of Operations Research, Vol.207,no.1, 2011 ,pp 201–216.
15. [15] Pillac et al.,"A review of dynamic vehicle routing problems, "European Journal of Operational Research, vol.225,no.1, 2012,pp.1–11.
16. [16] Dhingral and Gull ,"Traffic flow theory historical research perspectives", 75 Years of the Fundamental Diagram for Traffic Flow Theory: Greenshields Symposium Proceedings, 2008, pp.45–62.
17. [17] Skordyli and Trigoni,"Delay-bounded routing in vehicular Ad-Hoc networks,"In 9th ACM International Symposium onMobile AD-Hoc Networking and Computing, New York, USA ,2008, pp. 341–350.
18. [18] Kitani et al., "Efficient VANET-based traffic information sharing using buses on regular routes,"Vehicular Technology Conference, 2008, pp. 3031–3036.
19. [19] Khosroshahiet al., "Acquiring real time traffic information using VANET anddynamic route guidance,"Computing, Control and Industrial Engineering (CCIE) IEEE 2nd International Conference on Volume:1,2011, pp.9–13.
20. [20]Yousefi ,Abbasi, Anvari,"Transportation Routing in Urban Environments Using Updated Traffic Information Provided through Vehicular Communications," Transportation Systems Engineering And Information TechnologyJ., Vol.14, no. 5, Oct.2014,pp.23–36.
21. [21] E. Gelenbe, "Random neural networks with negative and positive signals and product form solution," Neural Computation,vol.1,no.4,1989, pp. 502–510.
22. [22] J.M. Fourneau, E. Gelenbe, R. Suros, "G-networks with multiple classes of negative and positive customers," Theoretical Computer Science,vol.155, no.1,1996, pp.141–156.
23. [23] E. Gelenbe, A. Labed, "G-networks with multiple classes of signals and positive customers,"European Journal of Operations Research, vol.108 , no.2,1998, pp.293–305.
24. [24] V. Atalay, E. Gelenbe, N. Yalabik, "The random neural network model for texture generation,"IJPRAIJ.,vol.6, no.1,1992, pp.131–141.
25. [25] E. Gelenbe, F. Batty, "Minimum cost graph covering with the random network model,"presented at theProc. Conf. ORSA Techn. Committee Comput. Sci., Pergamon,Williamsburg, 1992.
26. [26] E. Gelenbe, "G-networks: an unifying model for queuing networks and neural networks,"Annals of Operations Research, vol.48, no.5, 1994,pp.433–461.
27. [27] J.M. Fourneau, M. Hernandez, "Modeling defective parts in a flow system using G-networks,"presented at the Proc. Second Int. Workshop on Performability ModelingofComput andCommunic. Syst., Le Mont Saint-Michel, 1993.
28. [28] E. Gelenbe, "The first decade of G-networks," European Journal Of Operational Research, Vol.126, no.2 , 2000, pp. 231-232.
29. [29] E. Gelenbe, "Steady-state solution of probabilistic gene regulatory networks,"Physical Review,vol.76 , no.3,2007.
30. [30] E. Gelenbe, "Network of interacting synthetic molecules in steady state,"Proceedings of the Royal Society,Proc. R. Soc. A464, 2008,pp.2219–2228.
31. [31] E. Gelenbe and C. Morfopoulou, "A framework for energy-aware routing in packet networks," The Computer Journal, Vol.54, No.6, 2011, pp. 850-859.
32. [32] E. Gelenbe, S. Timotheou," Random neural networks with synchronised interactions,"Neural Computation, vol.20, no.9,2008, pp.2308–2324.
33. [33] E. Gelenbe, Cognitive packet network, U.S. Patent 6,804,20, October 11, 2004.
34. [34] G. Sakellari, "The cognitive packet network: a survey," The Computer Journal,Vol. 53, no. 3, 2010,pp. 268-279.
35. [35] Christina Morfopoulou,"Network routing control with G-networks",Performance Evaluation, vol.68 , no.4,2011, pp.320–329.
36. [36] Babaei, Hamideh, Mahmood Fathy, and Morteza Romoozi. "Modeling and optimizing Random Walk content discovery protocol over mobile ad-hoc networks." Performance Evaluation 74 (2014): 18-29.
37. [37] Romoozi, Morteza, Mahmood Fathy, and Hamideh Babaei. "A Content Sharing and Discovery Framework Based on Semantic and Geographic Partitioning for Vehicular Networks." Wireless Personal Communications 85.3 (2015): 1583-1616.