FIELD OF THE INVENTION

The present invention relates to a method and system for predicting best suitable route-mode
travel in a multimodal transit network. Also, the invention relates to methods and systems for
finding set of K journeys plans and more particularly to multi-modal journey planning in
transport network for long/short distance travel, from which the best path may be selected
comprising an optimized journey from an origin to a destination in the transport network meeting
criteria not used in the obtaining of the set of K journey plans.

BACKGROUND OF THE INVENTION

In earlier days, people used to go to the individual transportation/logistics provider personally to obtain tickets for the respective mode of transportation/logistics. But these scenarios have changed over the last decade, everything can be obtained online and people need not to go and stand in the queue for hours together without even knowing ticket availability.

In this internet era, it has made life so easy that the user can check the availability of tickets online and accordingly, the user can plan his travel accordingly.

Recently, there has been a lot of development in the area of web based travel assistance.

Consequently, the user need not go to each and every individual transportation provider service website to plan a trip. Instead, the user can go to a single travel assistance web server to get consolidated details of all the schedule of the entire service provider in a single click.

Even in this situation, the users are finding it a complex task to personally review complete list and choose a best travel mode and the route to reach a particular destination. More specifically, it makes the task more complex and time taking to review each planner listed and pin down to a single route-mode.

Also, there are places where persons cannot reach the destination directly using single means. In that situation, the user has to travel on various modes to reach the destination.

In this regard, there is no web assistance available to the user to get one-click-information on the
combination of modes that are available to reach a destination. Particularly, all the web based assistance provides travel data only for one mode of travel to reach a destination and not a combination of modes.

Hence, it is really difficult for a person to identify various available and feasible modes to reach a remote place.

However, identifying the optimal route is a complex search problem, over which attempts have are being made to solve it for intercity and intra city networks. Route planning requires finding an ideal route from a departure point to a destination point. Users often have many alternatives for routes, but are faced with highly incomplete data and difficult to obtain information on routes. Journey planning technique in commercially available journey planners merely provides pre-calculated "reasonable" paths between defined interchange points.

Also, there is difference in requirement of intra city travel and intercity mode of travel. No existing system provides separate details for intra city travel and intercity mode of travel.

The limitations and disadvantages of conventional and traditional approaches of arbitration are apparent to one of skill in the art, Hence, there exists a strong need for a method and separate for identifying the best route-mode travel to reach a particular destination. Wherein user is able to find and compare various different routes, not only on user preference of mode of travel, duration and cost but also over total cost of a group travel, availability and different dates search together in an easy way for a given source and destination location inputs along with his/her preference and various user generated content / preferences. Further, there exists need to invent a simple, robust and user friendly system which can self suggest best possible connections for his journey in each of the solutions suggested with the power of filtering, viewing similar, and shorting the routes. Hence, there exists a strong need to provide arbitration methods that are effective and at the same time, simple to implement.

Objectives of the Invention:

The primary objective of the present invention is to provide a method and system for predicting best suitable route-mode travel in a multimodal transit network which addresses at least some of the disadvantages of the conventional technique.

Another objective of the present invention is to provide a simple, effective, robust and user friendly method and system to self suggest best possible connections for user’s journey to reach the destination with the power of filtering, viewing similar, and shorting the routes.

Yet another objective of the present invention is to provide suitable route-mode result in a quick time.

Further objective of the present invention is to monitor the behavioral and response pattern of the users to provide to improve the prediction of best suitable route-mode.

Furthermore objective of the present invention is to develop a user preference data mining report to enhance the prediction rate. Another objective of the present invention is to provide the result including single or combination of modes to reach a destination.

Yet another objective of the present invention is to provide the user a single click & consolidated information on the best available connections.

SUMMARY OF THE INVENTION

The present invention relates to a method for predicting best suitable route-mode travel in a multimodal transit network, said method comprising: receiving travel specifications from the user; identifying user preferences and user generated content preferences if any; searching a travel database to retrieve a plurality of results available on the received travel specification; computing a user-specific value for each result, the user-specific value being calculated based on travel specification associated with the user and demographic details of the user; ranking the computed results based on a predetermined parameters and based on the travel history on the particle travel specification; and generating a display of information related to the highest-ranked result indicating best suitable travel mode.

The present invention also relates to a system for predicting best suitable route-mode travel in a multimodal transit network, the system comprising: a receiver for receiving inputs from a user device; plurality of interface units connected to plurality of servers to retrieve current travel schedule; a database for storing multimodal graphs; a processing unit operationally coupled to said database, interface units and receiver configured to search the database to retrieve a plurality of results available on the received travel specification; computing a user-specific value for each result, the user-specific value being calculated based on travel specification associated with the user and demographic details of the user; ranking the computed results based on a predetermined parameters and based on the travel history on the particle travel specification; and generating the highest-ranked result indicating best suitable travel mode; and a transmitter coupled to the said processing unit for transmitting the highest-ranked result to the user device.

The present invention further relates to a computer program product comprising: program instructions operable to perform a process in a computing device, the process comprising: receiving travel specifications from the user; identifying user preferences and user generated content preferences if any; searching a travel database to retrieve a plurality of results available on the received travel specification; computing a user-specific value for each result, the userspecific value being calculated based on travel specification associated with the user and demographic details of the user; ranking the computed results based on a predetermined parameters and based on the travel history on the particle travel specification; and generating a display of information related to the highest-ranked result indicating best suitable travel mode.

The present invention furthermore relates to a method and system for predicting best travel route-mode to reach a destination in a multimodal travel, the said method comprising:

identifying source point and destination point; retrieving from a database, a list of possible routes along with atleast one associated mode of travel for each of said possible routes between said source and departure point; parallely computing each of the possible routes and one or more associated mode of travel for each listed routes based on a predetermined condition to formulate a route-mode matrix; filtering from the route-mode matrix to form atleast one subset including route-modes based on predetermined conditions; ranking each route mode of the subset; serving the best predicted travel route and mode to reach a destination to the user.

The present invention furthermore relates to a data mining method and system for predicting best
route-mode to reach a destination in a multimodal travel, the said method comprising: identifying
source and destination point; determining the possible routes between the source and destination;
searching in the various servers possible mode of travel for each route between the source and
destination; receiving the demographic data from users; identifying the level of importance of
the travel date; providing search results to the user; monitoring the response & behavioural
pattern of the users based on the results shown; grouping the users into at least two levels based
on the demographic details and behavioural response pattern; creating a prediction table based on
the feedback received from the users and the demographic details; extrapolating the prediction
table to the rest of the users forming within the said groups to formulate the preference data for
identifying specific user group for providing best route-mode.

The following paragraphs are provided in order to describe the best mode of working the invention and nothing in this section should be taken as a limitation of the claims.

BRIEF DESCRIPTION OF THE DRAWINGS

In order that the invention may be readily understood and put into practical effect, reference will
now be made to exemplary embodiments as illustrated with reference to the accompanying drawings, where like reference numerals refer to identical or functionally similar elements throughout the separate views. The figures together with a detailed description below, are incorporated in and form part of the specification, and serve to further illustrate the embodiments and explain various principles and advantages, in accordance with the present invention where:

Figure 1 is a simplified view of the system flow architecture that may be used to determine best K connections/routes of the invention according to an aspect of the present invention.

Figure 2 is the flow chart representation of the methods used to find best connections and select,
refine the results according to an aspect of the present invention.

Figure 3 shows process through which input can be fed into the system according to an aspect of the present invention.

Figures 4a and 4b shows possible input parameters this system will take to find best K connections according to an aspect of the present invention.

Figure 5 shows graph search systems takes input to find the solution according to an aspect of the present invention.

Figure 6 shows wherein rules and heuristics can be applied to select best K connections according to an aspect of the present invention.

Figure 7 shows a data structure created in system’s memory called graph according to an aspect of the present invention.

Figure 8 shows flow chat of steps involved in a graph search for finding the best K connections according to an aspect of the present invention.

Figure 9 shows an example user interface for entering input information for the methods and systems according to an aspect of the present invention.

Figure 10 shows an example graphical user interface for the first output set of best K Connections for a source city to destination city travel returned by the system, which allow user to further refine and explore the results according to an aspect of the present invention.

Figure 11 illustrates general view of the overall system according to an aspect of the present invention.

Figure 12 illustrates block diagram of the system according to an aspect of the present invention.

Figure 13 illustrates block diagram of the processing unit according to an aspect of the present invention.

Figure 14 shows different multimodal routes and modes that are available to travel from a source to a destination.

Skilled artisans will appreciate that elements in the drawings are illustrated for simplicity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the drawings may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
Before describing in detail embodiments that are in accordance with the present invention, it should be observed that the embodiments reside primarily in combinations of method steps related to predicting best route-mode travel.

Accordingly, the method steps have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiments of the present invention so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art having benefit of the description herein.

The terms “comprises”, “comprising”, or any other variations thereof, are intended to cover a non-exclusive inclusion, such that a process, method that comprises a list of steps does not include only those steps but may include other steps not expressly listed or inherent to such process, method. Similarly, one or more elements in a system or apparatus proceeded by “comprises… a” does not, without more constraints, preclude the existence of other elements or additional elements in the system or apparatus.

The present invention relates to a method for predicting best suitable route-mode travel in a multimodal transit network, said method comprising: receiving travel specifications from the user; identifying user preferences and user generated content preferences if any; searching a travel database to retrieve a plurality of results available on the received travel specification; computing a user-specific value for each result, the user-specific value being calculated based on travel specification associated with the user and demographic details of the user; ranking the computed results based on a predetermined parameters and based on the travel history on the particular travel specification; and generating a display of information related to the highestranked result indicating best suitable travel mode.

The term ‘route-mode’ here refers to various routes that can be chosen to reach the destination and the corresponding modes of travel associated with the each route.

In another aspect of the present invention, wherein said travel specification includes i) a source
location ii) a destination location iii) date of travel iv) time of travel.

In yet another aspect of the present invention, wherein said source and destination locations are identified by geocoding input text to the locations and resolving a nearest station, city, state, country and/or exact address from the current locations.

In further aspect of the present invention, wherein the user preferences includes i) number of persons travelling ii) mode of travel iii) Change over stops iv) Travel time V) route.

In furthermore aspect of the present invention, wherein the step of searching performs HOP wise search, wherein HOP is a result comprising of a source, destination which can be reached with a mode of transport without changing the vehicle.

In another aspect of the present invention, wherein the search is an iterative process. In yet another aspect of the present invention, wherein Hop wise search may occur in parallel for each node expansion.
In further aspect of the present invention, wherein said searching includes searching multimodal
graphs being stored in the travel database, said multimodal graphs represents different travel routes, modes to reach the desired destination and transportation schedules.

In furthermore aspect of the present invention, wherein the step of computing comprises:

dividing the travel specification into several queries; performing parallel search for the queries;
and aggregating the filtered search.

In another aspect of the present invention, wherein the step of ranking comprises: comparing and filtering each route/result in detail as well as abstract level; and scaling the computed solutions to rank the computed results.

In yet another aspect of the present invention wherein the predetermined parameters include day of travel, departure/arrival time, mode of travel, schedule of travel, availability of tickets, travelling time, price trends of overall connections / journeys, distance, demographic details and

psychographic details, duration of travel, frequency of available mode of travel, fewest changes or transfers, convenience parameters such as preferred arrival and boarding time, community preference and Historical Booking Data.

In further aspect of the present invention, wherein duration of travel includes journey time and waiting time.

In furthermore aspect of the present invention, wherein the demographic details includes home location, gender, present location, age, salary, frequent travel memberships, co-travelers preferences, social connections.

In one or more aspect of the present invention, wherein the step of displaying is further capable

a) displaying the best connections to the user, b) displaying overview of the travel, c) displaying
detailed travel plan d) displaying travel map e) comparing results f) saving and/or sharing the
results g) partially or completely booking of the best travel mode suggested, h) fetching further
results similar to best connections displayed for refinement, i) fetching dates and check the
trends for the journeys displayed over a date range, refreshing and refining the results for
availability and pricing.

In another aspect of the present invention, further comprising monitoring user response and
behavioral pattern for providing the best connections.

In yet another aspect of the present invention, further comprising obtaining active feedback from
users wherein the results liked will assist in ranking.

In further aspect of the present invention, wherein best connections / journey / routes could be
different from each other in terms of mode of transport, stop over location chosen, demographic
details & physiographic details.

In further more aspect of the present invention, wherein each of suggested route is best in terms
of cost function chosen to evaluate and compare the routes for that journey.

In one or more aspect of the present invention, wherein the cost function could be based upon:

Cost of travel- between source and destination cities; Availability of tickets of transport mode;

Waiting time for connections - a valid connection transfer is made based upon arrival and

departure time gap which lies within predefined range of minimum and maximum waiting time;

Convenience parameters such as preferred arrival and boarding times; Duration of travel – we further break it down into journey time and waiting time; Time of the day – if we are using connecting modes of transport; Booked and Preferred routes in the past; Frequency of the vehicle, available mode from that node; Departure/Arrival Time of the day; Fewest changes or transfers; User’s preference, value of time for that user; and Community preference- whether other people liked this route or not.

In another aspect of the present invention, wherein multimodal transit network includes any public transport modes and private transport modes combinations.

In yet another aspect of the present invention wherein multimodal transit network is stored in database which can be a plain table, or depicting a graph structure.

In further aspect of the present invention, wherein the database could be partitioned and grouped into smaller graphs and database like but not limited to i) storing one particular mode or agency network for the location / city / country they operate in; ii) graph of connections within a city for door to door transfer; and iii) graph of connections between city, between countries.

In furthermore aspect of the present invention wherein the filters at different stages are applied for efficient route finding with variety of modes and stops over involved, which are but not limited to a) at start of search, node expansion, b) during node expansion while calculating cost function of the route, c) while storing of route in a queue based on rules as well as cost function, d) while and after retrieving result set from the queue at end of search.

In one or more aspect of the present invention wherein the results could be further plugged in for
accurate price and availability by communicating real time network API or cache.

In another aspect of the present invention further comprising the step of creating a database from transit schedules into system specific formats and graphs.

In yet another aspect of the present invention wherein creating and updating the database is a
continuous process.

In further aspect of the present invention wherein at each level of search and results and instruction a cache database is involved.

In furthermore aspect of the present invention wherein search can be performed for a destination
or one to all destinations for a given source.

In one or more aspect of the present invention wherein search can be performed upon user query
or as a background job to cache the results.

The present invention further relates to a system for predicting best suitable route-mode travel in
multimodal transit network, the system comprising: a receiver for receiving inputs from a user
device; plurality of interface units connected to plurality of servers to retrieve current travel
schedule; a database for storing multimodal graphs; a processing unit operationally coupled to
said database, plurality of interface units and receiver, said processing unit configured to: search
the database to retrieve a plurality of results available on the received travel specification;

compute a user-specific value for each result, the user-specific value being calculated based on
travel specification associated with the user and demographic details of the user; rank the
computed results based on a predetermined parameters and based on the travel history on the
particular travel specification; and generate the highest-ranked result indicating best suitable
travel mode; and a transmitter coupled to the said processing unit for transmitting the highestranked
result to the user device.

In another aspect of the present invention wherein the receiver and transmitter is coupled to the user device via mobile communication network &/or cabled network.

In yet another aspect of the present invention, wherein each of the pluralities of servers is associated with various logistics/transportation service providers.

In still another aspect of the present invention, wherein the processing unit comprises a searching
processor, a comparator and a controller.

In further aspect of the present invention, further comprising a cache memory.

In another aspect of the present invention, wherein the processing unit performs HOP wise
search, wherein HOP is a result comprising of a source, destination which can be reached with a
mode of transport without changing the vehicle.

In yet another aspect of present invention, wherein the processing unit performs Hop wise search
in parallel for each node expansion.

In still another aspect of the present invention, wherein the processing unit configured for searching includes searching multimodal graphs being stored in the travel database, said multimodal graphs represents different travel routes, modes to reach the desired destination and transportation schedules.
In further aspect of the present invention, wherein the processing unit configured to perform
computing comprises: dividing the travel specification into several queries; performing parallel
search for the queries; and aggregating the filtered search.

In furthermore aspect of the present invention wherein the processing unit performs ranking comprises: comparing and filtering each route/result in detail as well as abstract level; and

scaling the computed solutions to rank the computed results.

In one or more aspect of the present invention wherein the processing unit configured to display

a) Displaying the best connections to the user, b) displaying overview of the travel, c) displaying detailed travel plan d) displaying travel map e) comparing results f) saving and/or sharing the results g) partially or completely booking of the best travel mode suggested, h) Fetching further results similar to best connections displayed for refinement, i) fetching dates and check the trends for the journeys displayed over a date range, refreshing and refining the results for availability and pricing.

In another aspect of the present invention wherein the processing unit further configured to monitor user response and behavioral pattern for providing the best connections.

In yet another aspect of the present invention wherein the processing unit further configured to obtain active feedback from users, wherein the results liked by users will assist in ranking.

In still another aspect of the present invention, wherein the database could be partitioned and grouped into smaller graphs and database like but not limited to storing one particular mode or agency network for the location / city / country they operate in; graph of connections within a city for door to door transfer; and graph of connections between city, between countries.

The present invention furthermore relates to a computer program product comprising: program instructions operable to perform a process in a computing device, the process comprising:

receiving travel specifications from the user; identifying user preferences and user generated content preferences if any; searching a travel database to retrieve a plurality of results available on the received travel specification; computing a user-specific value for each result, the userspecific value being calculated based on travel specification associated with the user and demographic details of the user; ranking the computed results based on a predetermined parameters and based on the travel history on the particle travel specification; and generating a display of information related to the highest-ranked result indicating best suitable travel mode.

In another aspect of the present invention, wherein the program includes a computer software application working together in a distributed manner which includes a web layer to interact with input and out devices; a application layer which serves core business logic and control process of other applications to communicate; a database layer to store data which includes but not limited to user data, transit network data, configuration parameters; a caching layer to store (not limited to) frequently searched routes, objects, configurations, price and availability of routes.

This invention relates to finding K best connections between source and destination addresses for a multimodal long distance (intercity) travel. We have discovered that since different modes of transport are not directly comparable with each other and have their own pros and cons it becomes very difficult to select and compare different routes. For example, given two cities some people may prefer one mode of transport over other depending on the cost of travel, time taken to travel and convenience. The complexity is also increased in intercity travel when availability and fare changes with travel dates are factored in and the user has flexible dates to choose from.

The system and method invents finding of K best connections between source and destination addresses by incorporating other signals such as number of persons traveling, user’s value of time, which routes other people preferred while traveling, user intention to travel (immediate –within a week or long term – after a week or more), availability and fares with respect to multiple dates of travel, besides the cost, mode and duration of travel. Since we are taking into account user’s preferences such as his preferred time of travel, the value of his time, past history of routes selected and booked, the routes suggested are much more relevant to the user as compared to existing approaches. Importance is also given to change over time between connections and best connections are selected in top K routes.

Present system is based upon distributed computer systems, electronic computing devices and electronic / Print for input – output of display which may include without limitation desktop, laptop, notebook, palmtop, mobile, phones, tablet personal computers, kiosks, e-book devices and any interface capable for taking location input via text, voice sensors and displaying results.

One component of the system is a data structure created by us in System’s memory called Graph. It is used to search across millions of routes and comes out with best possible K routes, where K is an integer and a configurable parameter defined by the user of the system. A comprehensive data comprising of transport modes such as trains/flight/buses/cars routes and their scheduled is fed into the graph. Several such graphs are created by using the schedules and nodes at station (rail, bus, flights and other public modes of transport) level, city level, and country level. The system and methods uses these several graphs for finding best routes between source and destination addresses, searching them in parallel and aggregating the results later.

Once the graph has returned Best K Connections, availability, ranking based upon user and user generated content preferences, price are factored in and filtered before presenting the results.

To find the best K connections accurately the system takes duration and value of time for the user into account. Value of time for a user is indirectly calculated based upon user’s history of travel, preferences, and psychographic attributes. User generated content is also taken as a feedback for selecting best routes. The methods in the system also factors connection waiting Time for schedules and arrival – departure time of a schedule. The results returned by the method are then further filtered, sorted and ranked as per user preference and displayed to the user.

Further, the system then allows the user to plugin in various dates, compare and check different fares, availability and refine the results. He can view more options of a similar journey, sort the results over parameters not limited to duration, price, rank based on his preference, view the results over map, shortlist some routes, save, share them and finally book them. Shortlisting allows saving a particular journey and compare different journey at an independent place. This gives an edge to user to easily browse over numerous complex filters and inputs the user has. The systems and methods can operate in standalone mode or in conjunction with other systems and methods.

According to yet another aspect of the present invention, a method which finds K best connections / routes / journeys in a multimodal transit network best suited but not limited to a long distance (intercity) travel with a computer software application, comprising following steps:

a) receiving a source and destination location; b) optionally receiving (i) date of travel, (ii) number of persons traveling, (iii) mode of travel, (iv) change over stops location of travel; c) identifying user preferences and user generated content preferences; d) dividing the query into several queries to distribute and search for solutions over various multimodal graphs; e) hop wise searches in a graph; f) applying rules and filters at different stages of searching for efficient route finding with variety of modes and stops over involved; g) aggregating the results and factoring price, availability and user preferences again to refine and filter solution; h) displaying the best K connections to the user along with ability to i) give feedback to the system and train it for personalization, ii) filter, sort the results, iii) view more similar routes from one of suggested route, iv) compare routes with each at detailed as well as abstract level, v) factor in dates to check price trends of overall connections / journeys and compare the results.

According to one more aspect of the present invention, a system which finds K best connections / routes / journeys in a multimodal transit network best suited but not limited to a long distance (intercity) travel with a computer software application, said system comprising: a) means for receiving a source and destination location; b) means for optionally receiving: (i) date of travel, (ii) number of persons traveling, (iii) mode of travel, and (iv) change over stops location of travel; c) means for identifying user preferences and user generated content preferences; d) means for dividing the query into several queries to distribute and search for solutions over various multimodal graphs; e) means for performing hop wise searches in a graph; f) means for applying rules and filters at different stages of searching for efficient route finding with variety of modes and stops over involved; g) means for aggregating the results and factoring price, availability and user preferences again to refine and filter solution; h) means for displaying the best K connections to the user along with ability to i) give feedback to the system and train it for personalization, ii) filter, sort the results, iii) view more similar routes from one of suggested
route, iv) compare routes with each at detailed as well as abstract level, v) means for performing factor in dates to check price trends of overall connections / journeys and compare the results. The present invention helps a user find best route for a long distance journey by giving him various different mode and stops options where in each suggested route is efficient and best chosen as per user preference from all available options on that path. The present invention finds best K routes with complete itinerary details, which includes travel schedule and the modes to transport to use and their respective timings and numbers, prices of tickets, points of purchase of tickets, changeover locations, expected waiting time between connecting journeys, if any and times of arrival and departure.

Figure 1 describes the overall system blocks in a simplified manner according to an aspect of the present invention, wherein the input signal received via device (10) can be used to initiate a request for finding best K connections. This input signal can be initiated by user input means (31) as shown in Figure 3, which can be a person/user/user device or another system calling or sending an SMS or MMT (32), initiating a request through an API, software application or web browser (33), or through mobile, desktop, tablet application (34) , or part or full information being retrieved from a location sensor (35), or through indirect source of information like mobile tower location of the user from which he is receiving the signal, or social media connections, (36) or other applications not limiting to Google latitude.

As shown in figure 4(a), the location information entered for source and destination address (37) can be a geo location in the world, or a station where a mode of transport originates, a city or town, state and even a country. This information along with other optional information as shown in Figure 4b, like preferred date(s) of travel (38), mode of travel (45), user profile and preferences (53), and user generated content (63) are used. As regards date of travel, the information can be provided as a specific date when the user wants to travel (39), as a fuzzy term like indicate tentative month or intention of travel such as immediate, long term (40), as a destination oriented vague terms like offseason, peak season (41), or holiday (42), weekend, weekday (44) or in terms of earliest availability (43). Mode of travel (45) which system will use
to search best K connections include one or all combinations of air travel modes (46) like flights, chopper; rail network modes (47, 49) like trains, subway, metro, ropeway, tram; road transport (48, 51) like bus, car, bike, taxi, private vehicle, or rickshaw, cycle, walking (52); and water transport (50) like ferry, cruise, boats or any other public transport medium. If the inputs are not given, it is assumed that mode of travel is default to all available modes. This further can be personalized based upon user history, preferences information in profile (53).

The above information is fed by the user on to a web module/layer with other optional information of user profile (53) to personalize the system and methods. This includes user history of booking, (54), his personalized average purchase window (62), user search views, clicks of routes, personal preference which includes but not limited to preferred mode of travel (55), particular agency, operator, like / dislike (56) of routes. User’s demographic information (61) like home location, gender, present location, age, salary (58), frequent travel memberships (60), co –travelers preferences, age, count (59) and social connections and recommendations and profile information (57). User generated content (63) can also be included to suggest best routes to the user which includes trend of bookings, view and click analytics of routes (64), voting of like / dislike of routes (65), average salary (66), age (67) advance purchased window (68) attributed to demographic and psychographic segmentation and categorizing the city, station (69) based upon popularity which includes population, frequency of travel, cost of living and
attractions.

All the above inputs are fed directly or indirectly through a database (15) or cache (12) to the web server (12). This server forms the search request (as shown in figure 5) collating above inputs (72, 73, 74, 75, 76) into a query and sends the query to application server (14). The application server resolves input query (as shown in figure 5) by fetching information of missing parts if any from database (15), cache (13) or remote API calls (20). It first finds the solution in cache (13) and if not found, distributes query into small queries / processes to run in parallel (16) and send them to graph servers (17) after finding the sub queries again in cache (13). Graph servers (17) searches the best K connections in the multimodal network graphs and returns the best connections found back to the application server (14). The application server (14) then plugs-in date and updates availability and price from cache (18) and returns the results to web server (12). The cache (18) is updated upon missing the query request from application server
(20) by contacting remote network of transport API. The results are then present back from web
server (12) to output device or signal (11).

Figure 2 shows flow diagram according to an aspect of the present application and illustrated based on the information flow for a given input and output parameters of the system. At the start mode (21), the input query of source and destination location (22) is received as initiation signal which can be any geo location text (4a). Optionally (23) input of number of people travelling, date of travel and via stops could be entered into the system. The system then pulls up user profile or makes estimations about the user using his/her past or current interactions, preferences and user generated content (24) and divides the input query into sub query / process (25), for parallel searching and each query searches (26) best K connections. This division of queries for searching of routes is as follows –

Find the 1 or more circle elements of (37) for the given input. For example- for a given geo-location find nearest stop(s), and for the nearest stops found find the corresponding cities or city and for the corresponding cities find the countries.

• If input circle graph is not present, it will fall to inner circle graph by defaulting to a pattern, like capital of state, country or outer graph by calculating nearest point of interest to the graph.

• Graphs (as illustrated in figure 7) can be built upon individual circles, part of circles. For example for country there may exists a town graph and state graph may be optional if level of details for a state graph is not needed. Similarly for each country or city there exist different geo-location graphs detailing the station nodes.

• For each of these found locations / circle above, in a distributed parallel search find the way to reach from desired destination circle(s) from a given circle(s) input using the input parameters provided (26).

Finally all search results are aggregated (27) and the system suggests/outputs best K connections/routes to the user who initiated the request after updating results along with date and availability and price from cache (18) and sorting and pruning as per user preferences. The user can further change input parameters figures 4a and 4b to refine results.

Figure 2 is detailed out with help of Figure 7 and Figure 8. A graph (as illustrated in figure 7) is represented as nodes (114) and edges (113), wherein node (114) is a location representing a position (37) (latitude, longitude) or a station, or a city or a country. An edge (113) is a connection between two nodes and it can represent a vehicle and its schedule, type of a mode of travel or a group of vehicles combined as a mode of travel. Each node and edge has properties detailing its information. The term called HOP which is an edge or a group of edges in a graph which represents that an individual can travel from node X to node Y in a single vehicle without changing any vehicle/mode. For example, if a train goes from node A to node B to node C and we only represent graph edges as A to B, B to C. Then one HOP is equal to A to B to C route.

On the contrary if we modal graph as A to B, B to C, and A to C; then one HOP is equal to A to C route. In this case A to B to C route is 2 HOP.

The graph (as illustrated in figure 7) can be contracted to break a multi-modal graph into smaller graphs, enabling distributed search based on certain rules. Like, stations and positions nodes in a graph can be grouped / contracted to another graph. Similarly, there can be another graph where cities are contracted to a country. Similar technique can be applied over edges where one can group all edges of a similar mode of travel. Or group edges of same vehicle that make connections (like A to B, B to C, and A to C above).

Graph search (as shown in figure 8) uses several heuristics and rules for pruning routes at various stages of traversal and terminates at X + Y hop finding the best K routes. Where X is shortest hop path to a destination and Y is a number based upon routes found till X hop and few more rules based on user / community preference based upon user generated content (63).

As illustrated in figure 5, upon receiving signal and input parameters from application server (14) a graph search starts (83). Based on input parameters threshold values and queue (84) for storing best K connections are initialized. Then we expand the node for next HOP and search for the best routes. Expansion of a node (114) to next HOP nodes occurs in parallel.

The expansion of nodes can be pruned from search (86) based on level 1 and level 2 filters and rules. Level 1 filters / rules are applied when the node is about to expand, Depending on the query the nodes expansion or path expansion can be pruned by applying rules like - A. Meeting X + Y HOP, or till no path found to the destination or filter / rule of input (for example isochrones query or find all routes for an
agency) satisfies in that HOP expansion.

b. Y value can be determined based on

i. If a particular mode of travel found in search till now or not

ii. Number of transport modes available and how easily or frequently transport modes available.

iii. Availability

c. If a query has filtering parameters like via nodes and / or modes specified or a pattern query like same vehicle expansion the nodes can be pruned based on if the path or pattern meets this criteria or not.

d. Heuristics that determine the selection of a node for expansion are based on but not restricted to following parameters to be used or 0 or more such in a group i. Distance / radius of search,

ii. preferred nodes or modes, (Route via a certain city, connection or specific train )

iii. A particular pattern of modes should not occur. Exclude certain nodes, modes or a pattern of nodes, modes occurring in a path individually or in a group / pattern.

iv. Time to travel

v. Cities to visit

vi. Number of stops/hops

For Level 2 filters (86) and rules another factor is applied which is called the Cost function. This
is used to determine whether a route is among the best K routes or not for that pattern of path.

This Cost function uses the following parameters as input– a) Cost of travel- between source and destination cities b) Availability of Tickets of transport mode.

c) Waiting time for connections - A valid connection transfer is made based upon arrival and departure time gap which lies within predefined range of minimum and maximum waiting time,

d) Convenience parameters such as preferred arrival and boarding times

e) Duration of travel – we further break it down into journey time and waiting time.

f) Time of the day – if we are using connecting modes of transport.

g) Booked and Preferred routes in the past.

h) Frequency of the vehicle, available mode from that node

i) Departure/Arrival Time of the day

j) Fewest changes or transfers

k) User’s preference- which kind of route/mode of transport the user used in the past

l) Community preference- whether other people liked this route or not

m) Whether route includes popular cities

As shown in figure 8, after passing through above rules and filters, the route is inserted into priority queue of best K connections keeping best cost function one (configurable) route of a particular mode and stops (88). If node which is expanded has more nodes for HOP 1 to expand then the process repeats itself (89). Once all expansions for a particular HOP are completed, we check if destination is found or not (90). This calculates Y and checks if maximum HOP found to the desired destination is greater than X + Y (threshold ) value to search (91). If not the expansion for next level of hop repeats by going to (85). If yes, we apply 3rd level filter and rules (92). This filtering includes refinement of results based on threshold values observed during searches. After this we filter the routes depending on the number of routes and schedules to return-generally specified by the user of the system and term it as level 4 filters (93).

The filter/rules to discard routes termed above are adaptive to user’s personalized preferences (53) as well as community preferences (63). Individual preferences are used as signals for finding best K patterned routes. Value of time for an individual is assumed directly or indirectly by his history of travel (54), psychographic attributes, and / or by categorizing the user to a specific community segment determined from his location, social connections, demographic or geographic segmentation. Value of time is used to normalize travel time and price for a route to one scale to determine cost function of a graph traversal (86). Community preferences gathered via voting, booking and viewing of routes are used as feedback signals for sorting, pruning of results (88). Community can further be divided either into three segments – social circle / connections of a person, demographic and psychographic segmentation of a group and results order and pruning can be manipulated at level 4 upon these parameters (93).

The search process described in figure 7 can be used to search a particular source and destination or a radius search which is from a source to all destinations in the graph. The later methods can help accelerate the caching (13) much faster to provide quick system response.

Figures 9 and 10 show an example graphical user interface which may be used to interact with the system.
In this example figure 9 a user can select a source city (96), destination city (97) and optionally input number of travelers (98) and date of travel (99) which can further be specific or fuzzy (38).

Present example only takes either specific date or assumes a long term planning if Not decided option is selected.

Figure 10 shows the system output and further interaction opportunities which user can use to interact with system for refining of results and selecting best option. A user can modify input parameters by clicking modify button (102). Filter the results displayed based on preferred mode of transport (103). Sort the results (104) based on rating given by system, duration of travel, total cost of travel. The user can see the routes (101) and details of the route (107), with ability to view the details over map (106), and shortlist the route for comparison at later stage. Further a feedback can be obtained to train the system (111), email, share or Book the desired route (109), and pricing trend graph or values of the route as per date (110). If the user like particular pattern of route and want to see more combinations for variety of arrival and departure timings and duration, the user can click (108). This (108) will fetch up similar schedules matching the mode of transport and changeover stops. In this example only 5 out of 31 (K) routes are displayed initially, he can wish to see all K routes by clicking (112).

Figure 11 shows a general view of an overall system according to an embodiment of the present application. The figure shows a system 1130 which is connected to via internet (1120) and via a
mobile communication network (1150) to a plurality of users of the system. Further, the system
is operationally connected to the logistic/transportation service provider servers. The system
(1130) can be a server with various variations.

As shown in figure 12, the system comprises of a processing unit (1230) which is coupled to receiver (1210) and transmitter (1220) to get data and transmit the date from and to the user respectively. Further, the proceeding unit is coupled to the logistics/transportation servers (1280) via interface unit (1240) to update the database with the latest travel information/schedule of various transportation mode.

Furthermore, the processing unit is coupled to the cache memory to store the current processing of data.

Figure 13 shows the block diagram of processing unit. The processing unit is the heart of the system Which performs the entire methodology of the invention. The proceeding unit comprises a searching processor, a controller and a comparator.

According to another embodiment, the inputs as defined earlier are fed into the processing unit (1300) via the receiver (1200) directly or indirectly through a database (1250) or cache (1260). The searching processor (1310) forms the search request collating the inputs received (72, 73, 74, 75, 76) into a query. Further, input query is resolved by fetching information of missing parts if any from database (1250), cache (1260) It first finds the solution in cache (1260) and if not found, distributes query into small queries / processes to run in parallel (16) and send them to graph servers (17) after finding the sub queries again in cache (13). Graph servers (17) searches the best K connections in the multimodal network graphs and returns the best connections found to the controller (1320). The Controller then plugs-in date and updates availability and price from cache and returns the results to the user via the transmitter (1220). The cache (18) is updated upon missing the query request from the Controller by contacting remote network.

The results are then present back from the web server (12) to output device or signal (11). Optionally,
The Comparator is used to compare routes with each at detailed as well as abstract level, factor in dates to check price trends of overall connections / journeys and compare the results. The comparator could be a processor. Not restricting the scope of the invention, the entire process of the invention can be performed by a single processor or controller.

Figure 14 shows different multimodal routes and modes that are available to travel from a source
to a destination.

It will be appreciated that embodiments of the invention described herein (especially the arbitration unit) may be comprises of one or more conventional processors and unique stored program instructions that control the one or more processors to implement, in conjunction with certain non-processor circuits, some, most, or all of the arbitration functions described herein.

Alternatively, some or all of the arbitration functions could be implemented by a state machine that has no stored program instructions or in one or more application specific integrated circuits (ASICs), in which each function or some combinations of certain of the functions are implemented as custom logic.

Of course, a combination of the two approaches could be used. Thus, method and means for these Functions have been described herein. Further, it is expected that one of ordinary skill, notwithstanding possibly significant effort and many design choices motivated by, for example, available time, current technology, and economic considerations, when guided by the concepts and principles disclosed herein will be readily capable of generating such software instructions and programs and ICs with minimal experimentation.

The foregoing detailed description has described only a few of the many possible implementations of the present invention. Thus, the detailed description is given only by way of illustration and nothing contained in this section should be construed to limit the scope of the invention. The scope of claims is limited only by the following claims, including the equivalents thereof.

We Claim:

1. A method for predicting best suitable route-mode travel in a multimodal transit network, said method comprising:

receiving travel specifications from the user;

identifying user preferences and user generated content preferences if any;

searching a travel database to retrieve a plurality of results available on the received travel specification;

computing a user-specific value for each result, the user-specific value being calculated based on travel specification associated with the user and demographic details of the user;

ranking the computed results based on a predetermined parameters and based on the travel history on the particular travel specification; and

generating a display of information related to the highest-ranked result indicating best suitable travel mode.

2. The method as claimed in claim 1, wherein said travel specification includes i) a source location ii) a destination location iii) date of travel iv) time of travel.

3. The method as claimed in claim 1, wherein said source and destination locations are identified by geocoding input text to the locations and resolving a nearest station, city, state, country and/or exact address from the current locations.

4. The method as claimed in claim 1, wherein the user preferences includes i) number of persons travelling ii) mode of travel iii) Change over stops iv) Travel time V) route.

5. The method as claimed in claim 1, wherein the step of searching performs HOP wise search, wherein HOP is a result comprising of a source, destination which can be reached with a mode of transport without changing the vehicle.

6. The method of claim 5, wherein the search is an iterative process.

7. The method of claim 5, wherein Hop wise search may occur in parallel for each node expansion.

8. The method as claimed in claim 1, wherein said searching includes searching multimodal graphs being stored in the travel database, said multimodal graphs represents different travel routes, modes to reach the desired destination and transportation schedules.

9. The method as claimed in claim 1, wherein the step of computing comprises: dividing the travel specification into several queries;

performing parallel search for the queries; and

aggregating the filtered search.

10. The method as claimed in claim 1, wherein the step of ranking comprises:

comparing and filtering each route/result in detail as well as abstract level; and

scaling the computed solutions to rank the computed results.

11. The method as claimed in claims 1-10 wherein the predetermined parameters include day of travel, departure/arrival time, mode of travel, schedule of travel, availability of tickets, travelling time, price trends of overall connections / journeys, distance, demographic details and psychographic details, duration of travel, frequency of available mode of travel, fewest changes or transfers, convenience parameters such as preferred arrival and boarding time, community preference and Historical Booking Data.

12. The method as claimed in claim 11, wherein duration of travel includes journey time and waiting time.

13. The method as claimed in any of claims 1-11, wherein the demographic details includes home location, gender, present location, age, salary, frequent travel memberships, cotravelers preferences, social connections.

14. The method as claimed in claim 1, wherein the step of displaying is further capable a) displaying the best connections to the user, b) displaying overview of the travel, c) displaying detailed travel plan d) displaying travel map e) comparing results f) saving and/or sharing the results g) partially or completely booking of the best travel mode suggested, h) fetching further results similar to best connections displayed for refinement, i) fetching dates and check the trends for the journeys displayed over a date range, refreshing and refining the results for availability and pricing.

15. The method as claimed in claim 1, further comprising monitoring user response and behavioral pattern for providing the best connections.

16. The method as claimed in claim 1, further comprising obtaining active feedback from users wherein the results liked will assist in ranking.

17. The method of claim 1, wherein best connections / journey / routes could be different from each other in terms of mode of transport, stop over location chosen, demographic details & physiographic details.

18. The method of claim 1, wherein each of suggested route is best in terms of cost function chosen to evaluate and compare the routes for that journey.

19. The method of claim 17, wherein the cost function could be based upon:

a. Cost of travel- between source and destination cities;

b. Availability of tickets of transport mode;

c. Waiting time for connections - a valid connection transfer is made based upon arrival and departure time gap which lies within predefined range of minimum and maximum waiting time;

d. Convenience parameters such as preferred arrival and boarding times;

e. Duration of travel – we further break it down into journey time and waiting time; f. Time of the day – if we are using connecting modes of transport; g. Booked and Preferred routes in the past;

h. Frequency of the vehicle, available mode from that node;

i. Departure/Arrival Time of the day;

j. Fewest changes or transfers;

k. User’s preference, value of time for that user; and

l. Community preference- whether other people liked this route or not.

20. The method of claim 1, wherein multimodal transit network includes any public transport modes and private transport modes combinations.

21. The method of claim 1, wherein multimodal transit network is stored in database which can be a plain table, or depicting a graph structure.

22. The method of claim 1, wherein the database could be partitioned and grouped into smaller graphs and database like but not limited to storing one particular mode or agency network for the location / city / country they operate in;

graph of connections within a city for door to door transfer; and graph of connections between city, between countries.

23. The method of any of claims 1-22, wherein the filters at different stages are applied for efficient route finding with variety of modes and stops over involved, which are but not limited to a) at start of search, node expansion, b) during node expansion while calculating cost function of the route, c) while storing of route in a queue based on rules as well as cost function, d) while and after retrieving result set from the queue at end of search.

24. The method of claim 15, wherein the results could be further plugged in for accurate price and availability by communicating real time network API or cache.

25. The method of claim 1, further comprising the step of creating a database from transit schedules into system specific formats and graphs.

26. The method of claim 18, wherein creating and updating the database is a continuous process.

27. The method of claim 1, wherein at each level of search and results and instruction a cache database is involved.

28. The method of claim 1, wherein search can be performed for a destination or one to all
destinations for a given source.

29. The method of claim 1, wherein search can be performed upon user query or as a
background job to cache the results.

30. A system for predicting best suitable route-mode travel in a multimodal transit network,

the system comprising:

a receiver for receiving inputs from a user device;

plurality of interface units connected to plurality of servers to retrieve current travel
schedule;

a database for storing multimodal graphs;

a processing unit operationally coupled to said database, plurality of interface units and
receiver, said processing unit configured to:

search the database to retrieve a plurality of results available on the received travel specification;
compute a user-specific value for each result, the user-specific value being calculated based on travel specification associated with the user and demographic details of the user;

rank the computed results based on a predetermined parameters and based on the travel history on the particular travel specification; and

generate the highest-ranked result indicating best suitable travel mode; and a transmitter coupled to the said processing unit for transmitting the highest-ranked result to the user device.

31. The system of claim 30, wherein the receiver and transmitter is coupled to the user device via mobile communication network &/or cabled network.

32. The system of claim 31, wherein each of the pluralities of servers is associated with various logistics/transportation service providers.

33. The system as claimed in claim 31, wherein the processing unit comprises a searching processor, a comparator and a controller.

34. The system as claimed in claim 30, further comprising a cache memory. 35. The system as claimed in claim 30, wherein said travel specification includes i) a source location ii) a destination location iii) date of travel iv) time of travel.

36. The system as claimed in claim 30, wherein said source and destination locations are identified by geocoding input text to the locations and resolving a nearest station, city, state, country and/or exact address from the current locations.

37. The system as claimed in claim 30, wherein the user preferences includes i)number of persons travelling ii) mode of travel iii) Change over stops iv) Travel time V) route.

38. The system as claimed in claim 30, wherein the processing unit performs HOP wise search, wherein HOP is a result comprising of a source, destination which can be reached with a mode of transport without changing the vehicle.

39. The system of claim 38, wherein the search is an iterative process.

40. The system of claim 38, wherein the processing unit performs Hop wise search in parallel
for each node expansion.

41. The system as claimed in claim 30, wherein the processing unit configured for searching includes searching multimodal graphs being stored in the travel database, said

multimodal graphs represents different travel routes, modes to reach the desired destination and transportation schedules.

42. The system as claimed in claim 30, wherein the processing unit configured to perform computing comprises:

dividing the travel specification into several queries;

performing parallel search for the queries; and

aggregating the filtered search.

43. The system as claimed in claim 30, wherein the processing unit performs ranking comprises:
comparing and filtering each route/result in detail as well as abstract level; and

scaling the computed solutions to rank the computed results.

44. The system as claimed in claims 30-43 wherein the predetermined parameters includes day of travel, departure/arrival time, mode of travel, schedule of travel, availability of tickets, travelling time, price trends of overall connections / journeys, distance, demographic details and psychographic details, duration of travel, frequency of available mode of travel, fewest changes or transfers, convenience parameters such as preferred arrival and boarding time, community preference and Historical Booking Data.

45. The system as claimed in claim 44, wherein duration of travel includes journey time and waiting time.

46. The system as claimed in any of claims 30-45 wherein the demographic details includes home location, gender, present location, age, salary, frequent travel memberships, cotravelers preferences, social connections.

47. The system as claimed in claim 30, wherein the processing unit configured to display a) Displaying the best connections to the user, b) displaying overview of the travel, c) displaying detailed travel plan d) displaying travel map e) comparing results f) saving and/or sharing the results g) partially or completely booking of the best travel mode suggested, h) Fetching further results similar to best connections displayed for refinement, i) fetching dates and check the trends for the journeys displayed over a date
range, refreshing and refining the results for availability and pricing.

48. The system as claimed in claim 30, wherein the processing unit further configured to monitor user response and behavioral pattern for providing the best connections.

49. The system as claimed in claim 30, wherein the processing unit further configured to obtain active feedback from users, wherein the results liked by users will assist in ranking.

50. The system of claim 30,wherein best connections / journey / routes can be different from each other in terms of mode of transport, stop over location chosen, demographic details & physiographic details.

51. The system of claim 30, wherein each of suggested route is best in terms of cost function chosen to evaluate and compare the routes for that journey.

52. The system of claim 51, wherein the cost function is based upon:

a. cost of travel- between source and destination cities;

b. availability of Tickets of transport mode;

c. waiting time for connections - A valid connection transfer is made based upon arrival and departure time gap which lies within predefined range of minimum and maximum waiting time;

d. convenience parameters such as preferred arrival and boarding times; e. duration of travel – we further break it down into journey time and waiting time;

f. time of the day – if we are using connecting modes of transport; g. booked and Preferred routes in the past;

h. frequency of the vehicle, available mode from that node;

i. departure/Arrival Time of the day;

j. fewest changes or transfers;
k. user’s preference, value of time for that user; and

l. community preference- whether other people liked this route or not.

53. The system of claim 30, wherein multimodal transit network includes any public transport modes and private transport modes combinations.

54. The system of claim 30, wherein multimodal transit network is stored in database which can be a plain table, or depicting a graph structure.

55. The system of claim 30, wherein the database could be partitioned and grouped into smaller graphs and database like but not limited to storing one particular mode or agency network for the location / city / country they operate in;

graph of connections within a city for door to door transfer; and

graph of connections between city, between countries.

56. The system of any of claims 30-55, wherein the filters at different stages are applied for efficient route finding with variety of modes and stops over involved, which are but not limited to a) at start of search, node expansion, b) during node expansion while calculating cost function of the route, c) while strong of route in a queue based on rules as well as cost function, d) while and after retrieving result set from the queue at end of search.

57. The system of claim 30, wherein the results could be further plugged in for accurate price and availability by communicating real time network API or cache.

58. The system of claim 30, further comprising the step of creating a database from transit schedules into system specific formats and graphs.

59. The system of claim 30, wherein creating and updating the database is a continuous process.

60. The system of claim 30, wherein at each level of search and results and instruction a cache database is involved.

61. The system of claim 30, wherein search can be performed for a destination or one to all destinations for a given source.

62. The system of claim 30, wherein search can be performed upon user query or as a background job to cache the results.

63. A computer program product comprising:

program instructions operable to perform a process in a computing device, the process comprising:
receiving travel specifications from the user;

identifying user preferences and user generated content preferences if any;

searching a travel database to retrieve a plurality of results available on the received travel specification;
computing a user-specific value for each result, the user-specific value being calculated based on travel specification associated with the user and demographic details of the user;

ranking the computed results based on a predetermined parameters and based on the travel history on the particle travel specification; and generating a display of information related to the highest-ranked result
indicating best suitable travel mode.

64. The product of claim 63, wherein the program includes a computer software application working together in a distributed manner which includes a web layer to interact with input and out devices; a application layer which serves core business logic and control process of other applications to communicate; a database layer to store data which includes but not limited to user data, transit network data, configuration parameters; a caching layer to store (not limited to) frequently searched routes, objects, configurations, price and availability of routes.