Demand-Supply Oriented Taxi Suggestion System for Vehicular Social Networks with Real Time Charging Advisor

Demand-Supply Oriented Taxi Suggestion System for Vehicular Social Networks with Real Time Charging Advisor

1 2 3

Mr. K. Muthukumaran

1

Professor,

1. .,

   M. Shobana , A. Sowmiya ,

   4 5

   D. Vaishnavi , S. Venkatesh Kumar

   Department of Computer Science and Engineering,

   K.S.R. College of Engineering, Tiruchengode, India.

   2,3,4,5

   UG Students

   Department of Computer Science and Engineering,

   K.S.R. College of Engineering, Tiruchengode, India.

   Abstract Data mining based on large-scale taxi traces has become a hot research topic. A vital direction for analyzing taxi GPS dataset is to suggest cruising areas for taxi drivers. Most of the existing researches merely focus on how to maximize drivers profits while overlooking the profit of passengers. Such imbalance makes the existing solutions do not work well in a real-world environment. This paper constructs a recommendation system by jointly considering the profits of both drivers and passengers. The work first investigates the real-time demand-supply level for taxis, and then makes an adaptive tradeoff between the utilities of drivers and passengers for different hotspots. At last, the qualified candidates are suggested to drivers based on analysis. Results indicate that constructed suggestion system achieves a remarkable improvement on the global utility and make equilibrium between the utilities of drivers and passengers at the same time. It also considers a drivers utility with four factors, i.e, expected revenue, searching time for next passenger, travel distance and preference. The work also provides a real-time charging station recommendation system for EV taxis via large-scale GPS data mining. In addition, the proposed system providing the solutions and recommendation for the minimal time as well as for the minimal recharging cost for the Electronic Vehicle taxi drivers.

   KeywordsVehicular Social Networks, Hotspot location, Trajectory data mining, Supply-demand level.

   1. INTRODUCTION

      A social networking service (SNS) is a platform to build social networks or social relations among people who share similar interests, activities, backgrounds or real-life connections. A social network service consists of a representation of each user often a profile, his or her social links, and a variety of additional services. Social network sites are web-based services that allow individuals to create a public profile, create a list of users with whom to share

      connections, and view and cross the connections within the system.

      The Most social network services are web-based and provide means for users to interact over the Internet, such as e-mail and instant messaging. Social network sites are varied and they incorporate new information and communication tools such as mobile connectivity, photo, video, sharing. The Online community services are sometimes considered a social network service, though in a broader sense, social network service usually means an individual-centered service whereas online community services are group-centered. Social networking sites allow users to share ideas, pictures, posts, activities, events, and interests with people in their network.

      Social Networking has become the following feature, Social networking are the popular trend in modern days. With its immense popularity, small business houses have also started using social networking websites for brand promotion .Todays age is an age of advanced technology. With boon of Internet reaching almost every corner of the world, there has been an immense transformation in each and every field. Be it setting up a better platform of communication or connecting the globe under a common network, Internet has truly contributed in making world much a smaller place to live in. From video chats to Video conferencing, from online marketing to socializing via social media, Internet has truly and surely blessing for the global societies. Social media marketing is (SMM) referred to define certain websites that facilitate inter-personal communication through certain websites where in people can create their own profile page and communicate with friends and associates through online messages or scraps. A user can create a network of friends, create a group, initiate or take part in a group discussion. These Social Media websites became a tool that paved the way for advanced mode of communication between all the networks and internet users.

      The social media sites not only remained a platform to initiate informal dialogues and a facilitator of live messages,

      but became an integral part of marketing strategies of many a business houses. The application of these sites has spread to business houses that started using the Social Networking sites as a platform to promote their services and create brand awareness. Social Networking soon became a way for brand Marketing and promotion on social sphere, whereby, the enterprises started using these online communities or websites for developing contacts and driving traffic to their respective websites. These social networking websites form the main tool of social media marketing. The most commonly used websites Twitter and Facebook. Facebook is a Social Networking Site which helps friends and colleagues to share dialogues with each other through Wall Posts, Messages and Comments.

      Social Networking site, Facebook has more than 350 million members and still counting. This site experiences more than two million clicks per day. Statistics state that users spend an average of 20minutes per day in Facebook. Facebook is one of the lethal tools in SMM and SMO. Twitter is a social media platform where the users

      tweet to keep in touch with friends and his followers within his/her circle. Twitter allows posting "tweets" to all the people in their online network. Twitter also became a tool for social media marketing, the business posting a Tweet button on every post on its blog, makes it easy for anyone who reads the post to Tweet it to their followers. This helps channelize the information to spread from one end to another, creating proper brand awareness. Tweeting the up to date information of the business can be a great source of reaching a mass of audience. Linked In is a professional social media website where a stream of professional gets the chance to review and interact with their counterparts. Linked In offers a solid platform for establishing new business relationships. Linked In by facilitating more of a personal communication between the business professionals can help the business.

      My space also a massive impact in the social networking world, Once registered with MySpace, a user can not only inform the entire networking circle about their likes and dislikes but can also submit videos. This enables in building brand awareness and can be of immense help to small business houses. Social Media networking Sites is not only contributed to take inter-personal communication to a different level, but also a great marketing tool for the small businesses. Planned approach to social media marketing. This is the feature in social media marketing

      The main objectives of the Taxi Recommendation are

      • To focus on how to maximize drivers profits while overlooking the profit of passengers.

      • To evaluate two different levels of Demand Supply which are suitable for busy (peak) days and normal working days

      • To provides a real-time charging station recommendation system for taxis.

      • To calculate waiting time along with the distance for the recharging stations.

1. RELATED WORKS

   Zhaolong Ning and Feng Xia [1] in this article emphasized the importance of high- efficiency and reliable

   transmissions in VSNs for smart cities. Particularly, we study a case on traffic anomaly detection for VSNs by trajectory data analysis. Although VSNs can be regarded as the integration of social networks and IoVs to improve the quality of life for citizens, the avenues of VSN studies are not flat, and many open issues are still ahead. They believed that VSNs will draw extensive attentions and research efforts in the near future as the integrations of information technology and social network services become more compacted.

   Azizur Rahim and Xiangjie Kong [2] considered social networking in a vehicular environment; the authors investigated the prospective applications of VSNs and communication architecture. VSNs benefit from the social behaviors and mobility of nodes to develop novel recommendation systems and route planning. They presented a state-of-the-art literature review on socially- aware applications of VSNs, data dissemination, and mobility modeling. Further, they gave an overview of different recommendation systems and path planning protocols based on crowd sourcing and cloud-computing with future research directions. Further, they discussed the different communication protocols design and data dissemination techniques to address the existing gap between VSNs and traditional ad-hoc networks which is the very first issue to be considered by the research community to realize the concept of VSNs publicly accepted. Finally, they presented some open research issue for future direction. From the intensive literature review, they concluded that VSNs are still in their infancy level. However, a diverse range of novel applications, socializing vehicular networks, exploiting mobility pattern, socially aware recommendation systems along the roads are some of the factors towards whom the research community has shown concrete interest.

   Weigang Hou and Zhaolong Ning [3] in this paper, they have designed a novel temporal, functional and spatial big data computing framework for a large-scale smart grid. In spatial dimension, a novel heuristic has been proposed to place the least number of PNs in a subset of candidate locations that have high computing resources. After determining the final location of PNs, in functional dimension, a classic K-means matrix clustering algorithm has been utilized to divide every dataset into several smaller groups, each of which is called as info. Thus, one sub-group of data items instead of a dataset (chunk) is switched out from the current PN to a specific DN, leading to the improvement of computing efficiency in temporal dimension. Simulation results have demonstrated that: 1) a promising computing efficiency has been close to the upper bound with 95 percent convergence ratio; 2) the improvement ratio of saving the in-path bandwidth has been 81 percent; 3) the switching functionality between chunk and info has been achieved with a quick response. In summary, the proposed big data computing framework is effective on improving the computing efficiency and saving the in-path bandwidth, especially for the large-scale smart grid that includes plentiful datasets. In the future work, they would further evaluate the effectiveness of their temporal,

   functional and spatial big data computing framework in a more realistic environment.

   Jiao Zhang and Xiping Hu [4] in this paper, single and multi-cell MEC network scenarios are considered at the same time. The residual energy of smart devices battery is introduced into the definition of the weighting factor of energy consumption and latency. In terms of the mixed integer nonlinear problem (MINLP) for computation offloading and resource allocation, we propose an iterative search algorithm combining interior penalty function with

   D.C. (the difference of two convex functions/sets) programming (IPDC) to find the optimal solution. Numerical results show that the proposed algorithm can obtain lower total cost (i.e., the weighted sum of energy consumption and execution latency) comparing with the baseline algorithms and the energy-aware weighting factor is of great significance to maintain the lifetime of smart mobile devices.

   Zhaolong Ning and Jun Huang [6] in this paper, the authors stated that Fog computing extends the facility of cloud computing from the center to edge networks. Although fog computing has the advantages of location awareness and low latency, the rising requirements of ubiquitous connectivity and ultra-low latency challenge the traffic management for smart cities. As an integration of fog computing and vehicular networks, Vehicular Fog Computing (VFC) is promising to achieve real- time and location-aware network responses. Since the concept and use case of VFC are in the initial phase, this article first constructed a three- layer VFC model for distributed traffic management, in order to minimize the response time of citywide events collected and reported by vehicles.

2. METHODOLOGY

The proposed work makes a tradeoff between a drivers utility and a passengers waiting time. The score expression of each hotspot is given for recommendation. In this way, high utilities for drivers can be achieved and save a mass of waiting time for passengers meanwhile. This work constructs an adaptive recommendation system based on the supply-demand level, by which a tradeoff is made between the utilities of drivers and passengers. Then the hotspot with the highest score is recommended to available taxis. It considers a passengers utility with the waiting time for vacant taxis, which is predicted by mining the pick-up events.

Fig 1: Taxi recommendation system

First pick-up points for each time segment from the taxi trajectory are extracted. Then an adaptive Density-based Spatial Clustering of Applications with Noise algorithm (I- DBSCAN) for clustering is utilized. The essential knowledge of each hotspot is calculated for online recommendation. Passengers expected waiting time is predicted based on the information of different hotspots. For the online part, we retrieve hotspots within certain limits for the correct time segment according to the time and location of available taxis. Then the drivers utility can be calculated based on the knowledge. After evaluating the real-time demand-supply level of the whole area, we can make a tradeoff between the drivers and passengers utilities. The recommendation score is defined according to the abovementioned idea. Finally, the hotspot with the highest value is recommended to the driver.

A. DEMAND HOTSPOTS SCANNING BY CLUSTERING

By clustering the pick-up points, information from taxi trajectory can be extracted to identify candidate demand hotspots. Traditional DBSCAN algorithm is a kind of density-based clustering methods, which can discover arbitrary clusters and deal with noise or outliers effectively. However, the parameter, Eps is required to be input manually.

First, the distance distribution matrix is calculated, denoted by Dist nxn.

where n is the number of pick-up points we extract, and dist(i,j) is the Manhattan distance between GPS point pi and pj. The value of each element is obtained before sorting them in an ascending order line by line.

When the value of i increases, the number of clusters and noise both decrease. When they reach the convergence, the corresponding epsi is the optimal estimation of parameter Eps.

Algorithm: I-DBSCAN Clustering

Input: The pick-up points dataset to be clustered P Output: The nal set of clusters C

1: for pi,pj in P do

2: Dist[i][j] getManhattandis(pi,pj); 3: end for

4: Sort Dist in an ascending order line by line; 5: for the i-th column vector in Dist do

6: get average value as epsi; 7: end for

8: DBSCAN (epsi , xed MinPts) ;

9: Select optimal Eps by the number of cluster and noise; 10: N 0;

11: for in P do

12: N + getEpsNeighbourNum(p); 13: end for

14: MinPts N/|P|;

15: Perform DBSCAN with optimal Eps and MinPts;

B. PASSENGERS WAITING TIME PREDICTION

The arrival times of passenger for a particular vehicle and actual vehicle arrival time is taken. Then the average

B. PASSENGERS WAITING TIME PREDICTION

The arrival times of passenger for a particular vehicle and actual vehicle arrival time is taken. Then the average

Input: The pick-up points dataset to be clustered P Output: The nal set of clusters C

1: for pi,pj in P do

2: Dist[i][j] getManhattandis(pi,pj); 3: end for

4: Sort Dist in an ascending order line by line; 5: for the i-th column vector in Dist do

6: get average value as epsi; 7: end for

8: DBSCAN (epsi , xed MinPts) ;

9: Select optimal Eps by the number of cluster and noise; 10: N 0;

11: for p in P do

12: N + getEpsNeighbourNum(p); 13: end for

14: MinPts N/|P|;

15: Perform DBSCAN with optimal Eps and MinPts;

values of waiting times are calculated and thus the passenger waiting time is predicted. The following algorithm is used to predict the waiting time. With the input of pick up events time stamp sequences, the waiting time is calculated.

Input: The pick-up events timestamp sequence Tp = {pe1,pe2,··· ,pen}

Output: The estimated waiting time w for the hotspot

1: n1 penpe1;

2: Initiaize the passenger arrival events timetamp sequence Ta = {ae1,ae2,··· ,aen};

3: for i = 1 to n do 4: if i = 1 then

5: aei = random(0,pei); 6: // Uniform distribution 7: else

8: aei = aei1 + random(0,pei aei1);

9: // Truncated exponential distribution with 10: end if

11: end for

12: w 0;

13: for i = 1 to n do 14: w + (pei aei); 15: end for

16: w w/n;

17: return expected waiting time w.

Input: The pick-up events timestamp sequence Tp = {pe1,pe2,··· ,pen}

Output: The estimated waiting time w for the hotspot

1: n1 penpe1;

2: Initiaize the passenger arrival events timetamp sequence Ta = {ae1,ae2,··· ,aen};

3: for i = 1 to n do 4: if i = 1 then

5: aei = random(0,pei); 6: // Uniform distribution 7: else

8: aei = aei1 + random(0,pei aei1);

9: // Truncated exponential distribution with 10: end if

11: end for

12: w 0;

13: for i = 1 to n do 14: w + (pei aei); 15: end for

16: w w/n;

17: return expected waiting time w.

1. DEMAND-SUPPLY LEVEL EVALUATION

   The following algorithm is used for demand supply level evaluation. Total time intervals among the trajectories and total free/busy counts are calculated and value is found out.

   Input: Record of trajectory points for the taxi R =

   {r1,r2,··· ,rn}

   Output: The real-time demand-supply level

   1: S ø;

   2: for each R do 3: for r in R do

   4: if r.location in area and r.state was FREE then 5: get r.timestamp as ta;

   6: while FREE IN THIS AREA do 7: get next record;

   8: end while

   9: get r.timestamp as tb; 10: get r.state as m;

   11: t (tb ta + 1m); 12: S (t,m);

   13: end if

   14: end for

   15: end for

   16: sum1 0,sum2 0; 17: for (ti,mi) in S do 18: sum1 + ti;

   19: sum2 + mi; 20: end for

   21: sum2/(sum1 + sum2);

   22: return real-time demand-supply level .

   Input: Record of trajectory points for the taxi R =

   {r1,r2,··· ,rn}

   Output: The real-time demand-supply level

   1: S ø;

   2: for each R do 3: for r in R do

   4: if r.location in area and r.state was FREE then 5: get r.timestamp as ta;

   6: while FREE IN THIS AREA do 7: get next record;

   8: end while

   9: get r.timestamp as tb; 10: get r.state as m;

   11: t (tb ta + 1m); 12: S (t,m);

   13: end if

   14: end for

   15: end for

   16: sum1 0,sum2 0; 17: for (ti,mi) in S do 18: sum1 + ti;

   19: sum2 + mi; 20: end for

   21: sum2/(sum1 + sum2);

   22: return real-time demand-supply level .

2. ADAPTIVE RECOMMENDATION

RTICCT – 2019 Conference Proceedings

The following A

The following A

lgorithm is carried out in which Input

is Available taxis current time curtime and location curloc, candidate hotspots set H and Output is the recommended hotspot. Tracing trajectory and computing the drivers recent spent time on each hotspot is found out. Real-time demand-supply level is taken from previous algorithm. Max Score is found out based on revenue in various pick up points. Hotspot with max score is recommended.

Input: Available taxis current time curtime and location curloc, candidate hotspots set H

Output: The recommended hotspot 1: MaxScore 0,MaxId 0; 2: U ø,w ø;

3: Tracing trajectory and computing the drivers recent spent time on each hotspots ST = {st1,st2,··· ,stn};

4: for hi in H do

5: d getManhattandis(curloc,hi.core);

6: V (hi.revenuehi.searchingtimed) ; 7: sti k stk ;

8: U (V + );

9: whi.waitingtime;

10: end for

11: Evaluate real-time demand-supply level based on curtime using previousAlgorithm

12: for U i , w i corresponding to each hotspot do 14: score (1)U i + w i ;

15: if score > MaxScore then 16: MaxScore score;

17: MaxId i; 18: end if

19: end for

20: return recommended hotspot hMaxId.

Input: Available taxis current time curtime and location curloc, candidate hotspots set H

Output: The recommended hotspot 1: MaxScore 0,MaxId 0; 2: U ø,w ø;

3: Tracing trajectory and computing the drivers recent spent time on each hotspots ST = {st1,st2,··· ,stn};

4: for hi in H do

5: d getManhattandis(curloc,hi.core);

6: V (hi.revenuehi.searchingtimed) ; 7: sti k stk ;

8: U (V + );

9: whi.waitingtime;

10: end for

11: Evaluate real-time demand-supply level based on curtime using previousAlgorithm

12: for U i , w i corresponding to each hotspot do 14: score (1)U i + w i ;

15: if score > MaxScore then 16: MaxScore score;

17: MaxId i; 18: end if

19: end for

20: return recommended hotspot hMaxId.

V CONCLUSION

In this paper, proposed a framework for adaptive recommendation system. The work constructs an adaptive recommendation system by jointly considering the benefits of drivers and passengers. First, a spatio-temporal clustering method named I-DBSCAN is leveraged to group pick-up locations into different clusters. Second, to improve the drivers utility, kinds of metrics including expected revenue, driving distance, searching time and preference are taken into consideration. By mining the taxi trajectory data, drivers utility calculation and passengers waiting time prediction can be fulfilled. Then, the real-time demand- supply level for the whole area is evaluated, and a tradeoff between drivers and passengers utilities is made off, by which the score function of each hotspot can be calculated. The hotspot with the highest value is recommended to the driver. At last, the experiment is conducted in two different areas based on real-world taxi trajectory data.

The future work, we plan to consider more metrics. For drivers, they may pick up a passenger halfway. Thus, the influence of middle source cannot be ignored. For passengers, tolerance threshold of waiting time deserves to be considered. In addition, some external metrics, such as road network and traffic controlling, are important. For the second phase work, real time charging system of vehicles is to be carried out.

REFERENCES

1. Z. Ning, F. Xia, N. Ullah, X. Kong, and X. Hu, Vehicular social networks: Enabling smart mobility, IEEE Communications Magazine, vol. 55, no. 5, pp. 1655, 2017.

2. A. Rahim, X. Kong, F. Xia, Z. Ning, N. Ullah, J. Wang, and S. K. Das, Vhicular social networks: A survey, Pervasive & Mobile Computing, DOI: 10.1016/j.pmcj.2017.12.004, vol. 43, 2017

3. W. Hou, Z. Ning, L. Guo, and X. Zhang, Temporal, functional and spatial big data computing framework for large-scale smart grid, IEEE Transactions on Emerging Topics in Computing, DOI: 10.1109/TETC.2017.2681113, 2017.

4. J. Zhang, X. Hu, Z. Ning, C. H. Ngai, L. Zhou, J. Wei, J. Cheng, and B. Hu, Energy-latency trade- off for energy-aware offloading in mobile edge computing networks, IEEE Internet of Things Journal, DOI: 10.1109/JIOT.2017.2786343, 2017

5. X. Kong, F. Xia, Z. Ning, A. Rahim, Y. Cai, Z. Gao, and J. Ma, Mobility dataset generation for vehicular social networks based on floating car data, IEEE Transactions on Vehicular Technology, vol. 67, no. 5, pp. 38743886, 2018

6. Z. Ning, X. Wang, and J. Huang, Vehicular fog computing: Enabling real-time traffic management for smart cities, IEEE Wireless Communications, 2018

7. X. Kong, X. Song, F. Xia, H. Guo, J. Wang, and A. Tolba, LoTAD: long-term traffic anomaly detection based on crowdsourced bus trajectory data, World Wide Web, vol. 21, no. 3, pp. 825 847, 2017.

8. J. Tang, H. Jiang, Z. Li, M. Li, F. Liu, and Y. Wang, A two-layer model for taxi customer searching behaviors using GPS trajectory data, IEEE Transactions on Intelligent Transportation Systems, vol. 17, no. 11, pp. 33183324, 2016.

9. H. Zhou, P. Wang, and H. Li, Research on adaptive parameters determination in DBSCAN algorithm, Journal of Xian University of Technology, vol. 9, no. 7, pp. 19671973, 2012.

10. G. Qi, G. Pan, S. Li, Z. Wu, D. Zhang, L. Sun, and

    L. T. Yang, How long a passenger waits for a vacant taxi large-scale taxi trace mining for smart cities, in Proc. IEEE Green Computing and Communications, pp. 10291036, 2013.

11. D. Shao, W. Wu, S. Xiang, and Y. Lu, Estimating taxi demand-supply level using taxi trajectory data stream, in Proc. IEEE ICDMW, pp. 407 413, 2015.

12. Z. Ning, F. Xia, X. Hu, Z. Chen, and M. S. Obaidat, Social-oriented adaptive transmission in opportunistic Internet of smartphones, IEEE Transactions on Industrial Informatics, vol. 13, no. 2, pp. 810820, 2017.

13. X. Wang, Z. Ning, and L. Wang, Offloading in Internet of vehicles: A fog-enabled real-time traffic management system, IEEE Transactions on

    RTICCT – 2019 Conference Proceedings

    Industrial Informatics, DOI: 10.1109/TII.2018.2816590, 2018.

14. K. Zhang, Z. Feng, S. Chen, K. Huang, and G. Wang, A framework for passengers demand prediction and recommendation, in Proc. IEEE SCC, pp. 340347, 2016.