TECHNICAL FIELD
[001] The present invention relates generally to manage routes and generate schedule for vehicles, and, particularly but not exclusively, to a control system for route management as well as schedule management of multiple-convoy of vehicles.
BACKGROUND
[002] Typically, a set of vehicles forms a part of a convoy, and occupies considerable amount of transportation network space (more than a kilometer). Each convoy of vehicles needs to be routed and scheduled in correlation with other similar convoy of vehicles. Every convoy may start and finish their moves from possibly different locations on the network. Smaller related convoys starting from different locations are required to amalgamate with each other en-route to form a larger convoy. Every movement of the convoy is regulated and needs to adhere to pre-determined move restrictions that involve the need to adhere to speed limitations and the requirement of periodic halts.
[003] In a decision support system, where multiple-convoy of vehicles are to be routed on the transportation network and scheduled adhering to the pre-determined move restrictions, such as the requirement of periodic halts, adherence to speed limitations, the requirement of related convoys requiring to meet en-route and moving as groups wherever possible, the problem of generation of an optimum schedule for all the convoys with efficient management of the transportation network space becomes inherently complex owing to the number of factors involved.
[004] Existing systems route and schedule individual vehicles that occupy negligible transportation network space, but these systems do not solve multiple-convoy of vehicles routing and scheduling problem, as every single convoy occupies considerable amount of transportation network space. Additionally, considering additional movement restrictions that are to be considered in scheduling of such convoys like restricted speed and pre-determined halt requirements, and the requirement that smaller related convoys join each other en-route to form a larger convoy. Hence, customizing existing single vehicle routing solutions become complex and may not be a best fit to the problem.
[005] For example, consider a train timetabling problem, where trains occupy considerable space on the network and the fact that multiple different trains are to be scheduled from distinct locations. The train timetabling problem is proven to be a NP-hard (Non-Deterministic Hardness) problem and solutions for the same generally adopt a heuristic approach. Techniques such as branch-and-bound and mixed integer linear model have also been used. Additionally, simulations techniques can also be applied in solving the problem, wherein the entire solution space is scanned, and subsequent optimization of result is carried out through solution space reduction by comparison. These approaches would more often than not lead to solutions, that are sub-optimal and moreover such solutions are generally inefficient with regard to time.
[006] Therefore, there is a need for a control system that provides management of multiple-convoy of vehicles in the transportation network space and generates optimum schedule for the multiple-convoy of vehicles adhering to the pre-determined move restrictions.

SUMMARY
[007] This summary is provided to introduce concepts related to providing route management and schedule management of multiple-convoy of vehicles. This summary is neither intended to identify essential features of the present invention nor is it intended for use in determining or limiting the scope of the present invention.
[008] For example, various embodiments herein may include one or more control systems and methods for route management and schedule management of multiple-convoy of vehicles.
[009] In one of the embodiments, the present invention discloses a method for route management and schedule management of multiple-convoy of vehicles. The method includes a step of storing, in a database, information related to pre-defined transportation network routes, pre-defined priorities, pre-defined locations, and pre-determined halt patterns. The method includes a step of receiving, by an input module, inputs from the plurality of user devices, wherein the inputs include source location information, destination location information, start time, and end time, of each of the multiple-convoy of vehicles. Further, the method includes a step of identifying, by a path identification module, at least one minimal cost path between a source location and a destination location. Subsequently, the method includes a step of computing, by a computational module, a blocking time for at least one convoy of vehicles, and allotting the blocking time to the convoy of vehicles for the path. Furthermore, the method includes a step of generating, by a node generation module, a computational node based on conditional grouping of a plurality of convoys with time constraints, and a step of providing, by a transformation module, the blocking time to the convoy of vehicles for movement at the computational node. The method includes a step of scheduling, by a scheduler, the multiple-convoy of vehicles based on the pre-defined priorities. Each of the multiple-convoy of vehicles is scheduled from a start node with the start time. Further, the method includes a step of computing, by the scheduler, time by visiting the nodes by each of the multiple-convoy of vehicles in the path.
[0010] In another implementation, a control system is configured to provide route management of multiple-convoy of vehicles. The control system includes a plurality of user devices and a control engine. The control engine further includes a memory, a processor, a database, an input module, a path identification module, a determination module, a computational module, a node generation module, transformation module, and a scheduler. The memory is configured to store pre-determined rules. The processor is configured to process system processing commands. The database is configured to store information related to pre-defined transportation network routes, pre-defined priorities, pre-defined locations and pre-determined halt patterns. The input module is configured to receive inputs from the plurality of user devices. The inputs include source location information, destination location information, start time, and end time, of each of the multiple-convoy of vehicles. The path identification module is configured to identify at least one minimal cost path between a source location and a destination location. The determination module is configured to determine a plurality of nodes associated with the path. The computational module is configured to compute a blocking time for at least one convoy and allot the blocking time to the convoy for the path. The node generation module is configured to combine the nodes associated with the path, and generate a computational node, wherein the computational node is generated based on conditional grouping of the convoys with time constraints. The transformation module is configured to provide the blocking time to the convoy of vehicles for movement at the computational node. The scheduler is configured to schedule the multiple-convoy of vehicles based on the pre-defined priorities, wherein each of the multiple-convoy of vehicles is scheduled from a start node with the start time.
BRIEF DESCRIPTION OF ACCOMPANYING DRAWINGS
[0011] The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The same numbers are used throughout the drawings to reference like features and modules.
[0012] Figure 1 illustrates a block diagram depicting a control system for route management and schedule management of multiple-convoy of vehicles, according to an exemplary implementation of the present invention.
[0013] Figure 2 illustrates a network graph depicting a dissolved transportation network graph, according to an exemplary implementation of the present invention.
[0014] Figure 3 illustrates a network graph depicting the flow of data between a computational node and other nodes in a transportation network by application of transformation functions, according to an exemplary implementation of the present invention.
[0015] Figure 4 illustrates a graphical view depicting sequencing and clash avoidance at a computational node, according to an exemplary implementation of the present invention.
[0016] Figure 5 illustrates a flowchart depicting scheduling of multiple-convoy of vehicles, according to an exemplary implementation of the present invention.
[0017] Figure 6 illustrates a flowchart depicting a method for route management and schedule management of multiple-convoy of vehicles, according to an exemplary implementation of the present invention.
[0018] It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative systems embodying the principles of the present invention. Similarly, it will be appreciated that any flowcharts, flow diagrams, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.
DETAILED DESCRIPTION
[0019] In the following description, for the purpose of explanation, specific details are set forth in order to provide an understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these details. One skilled in the art will recognize that embodiments of the present invention, some of which are described below, may be incorporated into a number of systems.
[0020] The various embodiments of the present invention provide a control system and method for route management and schedule management of multiple-convoy of vehicles.
[0021] Furthermore, connections between components and/or modules within the figures are not intended to be limited to direct connections. Rather, these components and modules may be modified, re-formatted or otherwise changed by intermediary components and modules.
[0022] References in the present invention to “one embodiment” or “an embodiment” mean that a particular feature, structure, characteristic, or function described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment.
[0023] In one of the embodiments, the present invention discloses a method for route management and schedule management of multiple-convoy of vehicles. The method includes a step of storing, in a database, information related to pre-defined transportation network routes, pre-defined priorities, pre-defined locations, and pre-determined halt patterns. The method includes a step of receiving, by an input module, inputs from the plurality of user devices, wherein the inputs include source location information, destination location information, start time, and end time, of each of the multiple-convoy of vehicles. Further, the method includes a step of identifying, by a path identification module, at least one minimal cost path between a source location and a destination location. Subsequently, the method includes a step of computing, by a computational module, a blocking time for at least one convoy of vehicles, and allotting the blocking time to the convoy of vehicles for the path. Furthermore, the method includes a step of generating, by a node generation module, a computational node based on conditional grouping of a plurality of convoys with time constraints, and a step of providing, by a transformation module, the blocking time to the convoy of vehicles for movement at the computational node. The method includes a step of scheduling, by a scheduler, the multiple-convoy of vehicles based on the pre-defined priorities. Each of the multiple-convoy of vehicles is scheduled from a start node with the start time. Further, the method includes a step of computing, by the scheduler, time by visiting the nodes by each of the multiple-convoy of vehicles in the path.
[0024] In another implementation, the step of identifying the path includes a step of determining a plurality of nodes associated with the path.
[0025] In another implementation, the step of identifying the path includes a step of integrating two or more identified minimal cost paths, and generating an integrated path.
[0026] In another implementation, the method further includes a step of blocking the movement of the multiple-convoy of vehicles for a pre-defined interval of time.
[0027] In another implementation, the method further includes a step of generating a sequence of the multiple-convoy of vehicles’ movement within the grouped movement.
[0028] In another implementation, the step of identifying the path further includes a step of determining the minimal cost between the source location and the destination location.
[0029] In another implementation, the step of providing the blocking time to the convoy of vehicles, further includes a step of performing forward transformation and inverse transformation functions for processing bidirectional data along with a timeline depending on the position of the computational node. The transformation functions check feasibility during sequencing and scheduling of the multiple-convoy of vehicles at the computational node.
[0030] In another implementation, the method includes step of broadcasting data related to the movement of the scheduled convoys to the non-scheduled convoys.
[0031] In another embodiment, a control system is configured to provide route management of multiple-convoy of vehicles. The control system includes a plurality of user devices and a control engine. The control engine further includes a memory, a processor, a database, an input module, a path identification module, a determination module, a computational module, a node generation module, transformation module, and a scheduler. The memory is configured to store pre-determined rules. The processor is configured to process system processing commands. The database is configured to store information related to pre-defined transportation network routes, pre-defined priorities, pre-defined locations and pre-determined halt patterns. The input module is configured to receive inputs from the plurality of user devices. The inputs include source location information, destination location information, start time, and end time, of each of the multiple-convoy of vehicles. The path identification module is configured to identify at least one minimal cost path between a source location and a destination location. The determination module is configured to determine a plurality of nodes associated with the path. The computational module is configured to compute a blocking time for at least one convoy and allot the blocking time to the convoy for the path. The node generation module is configured to combine the nodes associated with the path, and generate a computational node, wherein the computational node is generated based on conditional grouping of the convoys with time constraints. The transformation module is configured to provide the blocking time to the convoy of vehicles for movement at the computational node. The scheduler is configured to schedule the multiple-convoy of vehicles based on the pre-defined priorities, wherein each of the multiple-convoy of vehicles is scheduled from a start node with the start time.
[0032] In an implementation, the path identification module is configured to integrate two or more identified minimal cost paths, and generate an integrated path.
[0033] In another implementation, the control system includes a barrier blockade module. The barrier blockade module is configured to block the movement of the multiple-convoy of vehicles at a specific location in the network for a pre-defined interval of time.
[0034] In another implementation, the control system includes a sequence generation module. The sequence generation module is configured to generate a sequence of the multiple-convoy of vehicles movement within the grouped movement.
[0035] In another implementation, the path identification module is configured to identify at least one minimal cost path by determining the minimal cost between the source location and the destination location.
[0036] In another implementation, the transformation module is configured to perform forward transformation and inverse transformation functions for processing bidirectional data along with a timeline depending on the position of the computational node. The transformation functions check feasibility during sequencing and scheduling of the multiple-convoy of vehicles at the computational node.
[0037] In another implementation, the conditional grouping of the convoys is based on speed of the multiple-convoy of vehicles and the pre-determined halt patterns stored in the database.
[0038] In another implementation, the control system further includes a broadcasting module. The broadcasting module is configured to broadcast data related to the movement of the scheduled convoy of vehicles to the non-scheduled convoy of vehicles.
[0039] In another implementation, the blocking time includes start time and end time, and represents the blocked time duration of at least one convoy holding or blocking the node.
[0040] Figure 1 illustrates a block diagram of a control system for route management and schedule management of multiple-convoy of vehicles (100) (hereinafter referred as “system”), according to an exemplary implementation of the present invention. The system (100) includes a plurality of user devices (102a, 102b, 102c,…., 102n) and a control engine (104). In an embodiment, each of the user devices (102a, 102b, 102c,…., 102n) is associated with respective users to access the system (100). In one embodiment, the user devices (102a, 102b, 102c,…., 102n) may be mobile devices, personal computers, laptops, PDAs, and the like.
[0041] The control engine (104) is configured to cooperate with the plurality of user devices (102a, 102b, 102c,…., 102n) via a network (not shown in figure). In one embodiment, the network (106) includes wired and wireless networks. Examples of the wired networks include a Wide Area Network (WAN) or a Local Area Network (LAN), a client-server network, a peer-to-peer network, and so forth. Examples of the wireless networks include Wi-Fi, a Global System for Mobile communications (GSM) network, and a General Packet Radio Service (GPRS) network, an enhanced data GSM environment (EDGE) network, 802.5 communication networks, Code Division Multiple Access (CDMA) networks, or Bluetooth networks.
[0042] The control engine (104) includes a memory (106), a processor (108), a database (110), an input module (112), a path identification module (114), a determination module (116), a computational module (118), a node generation module (120), a transformation module (122), and a scheduler (124).
[0043] The memory (106) is configured to store pre-determined rules related to identifying routes, and scheduling multiple-convoy of vehicles. In an embodiment, the memory (106) can include any computer-readable medium known in the art including, for example, volatile memory, such as static random-access memory (SRAM) and dynamic random-access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. The memory (106) also includes a cache memory to work with the system (100) more effectively.
[0044] The processor (108) is configured to cooperate with the memory (106) to receive the pre-determined rules. The processor (106) is further configured to generate system processing commands. In an embodiment, the processor (108) may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the at least one processor (108) is configured to fetch the pre-determined rules from the memory (106) and execute different modules of the control engine (104).
[0045] The database (110) is configured to store information related to pre-defined transportation network routes, pre-defined priorities, pre-defined locations, and pre-determined halt patterns.
[0046] The input module (112) is configured to receive inputs from the plurality of user devices (102a, 102b, 102c,…., 102n). The inputs include source location information, destination location information, start time, and end time of each of multiple-convoy of vehicles.
[0047] In an exemplary embodiment, a network topology G, made of a set of nodes/junctions N = {n1, n2, n3…ni… nn}, and a set of edges E = {e1, e2, e3 …ei …en} that connect the nodes of the network. Let, C = {C1, C2 …Ci…Cn} represents a set of convoys that have to be routed and scheduled in the network topology G. Let, Li represents the length of ith convoy Ci. The length Li is calculated by aggregating the length of all the vehicles that form a part of the convoy, along with necessary gaps between vehicles. Let, S represents the speed restriction on each convoy, and H represents a halt pattern that every convey needs to adhere to. Let, I = {G1, G2 …Gi…. Gn}, where G1 = {Ci, Cj …}, G2 = {Ck, Cm …} represents a set of groups of related convoys that need to join en-route. Let, Mi represents the maximum time a convoy of group Gi, be delayed to group itself with another convoy of the same group. Let, start location of ith convoy be represented by SLi and its destination by DLi. If each of the convoy can start earliest by time t (earliest time to start), the system (100) is configured to provide an optimal solution in scheduling the multiple convoy of vehicles C1 to Cn by performing transportation network space management in order to avoid clashes between convoys and strict adherence to the pre-determined halt pattern H and speed restriction S, and avoiding the timed barriers on the transportation network. In an embodiment, the system (100) is configured to solve the multiple-convoy of vehicles routing and scheduling problem using a Single Node Based Computation (SNBC) technique. In one embodiment, the SNBC technique involves reducing the computable space. The SNBC technique brings down the time complexity.
[0048] The path identification module (114) is configured to cooperate with the input module (112) and the database (110) to receive the inputs and the stored information. The path identification module (114) is further configured to identify at least one minimal cost path between a source location and a destination location. In an embodiment, the path identification module (114) is configured to integrate two or more identified minimal cost paths, and generate an integrated path. In another embodiment, the path identification module (114) is configured to identify at least one minimal cost path by determining the lowest cost between the source location and the destination location using a minimal cost path technique. The minimal cost path technique includes path finding, or graph traversal technique.
[0049] In an embodiment, the path identification module (114) is configured to identify best minimal cost path and an alternative path, i.e. another best path after the identified minimal cost path, for each of the convoys in the convoy set C from the start locations of multiple-convoy of vehicles to their specified destination locations using minimal cost path techniques. Example of minimal cost path techniques include Dijkstra’s technique, or A* technique. The obtained minimal cost paths are merged, as a result, a subset of nodes and edges forming a smaller network G’ from G is formed. The path identification module (114) then considers the smaller network G’ for further processing. In one of the embodiment, the smaller network G’ has lesser number of nodes and edges. Subsequently, the path identification module (114) further configured to dissolve the smaller network G’ to shrink the size of the transportation network. In one embodiment, the obtained minimal cost paths can share common transportation network edge, and common nodes/ junctions for the multiple-convoy of vehicles. The shared nodes/ junctions and edges are replaced by single instance of a node and an edge. Further, intermediate nodes of G’, with degree two are eliminated. The obtained minimal cost paths are merged and dissolved to form a virtual network G’’ with the nodes placed only at the nodes who have a degree of more than two, where the minimal cost paths share common node and the common edges.
[0050] The determination module (116) is configured to cooperate with the path identification module (114) and the database (110) to receive the identified path and the stored information. The determination module (116) is further configured to determine a plurality of nodes associated with the path.
[0051] The computational module (118) is configured to cooperate with the input module (112) and the determination module (116) to receive the inputs receive from the plurality of user devices (102a, 102b, 102c,…., 102n), and the determined nodes. The computational module (118) is further configured to compute a blocking time for at least one convoy of vehicles, and allot the blocking time to the convoy of vehicles for the path. In an embodiment, the blocking time includes start time and end time, and represents the blocked time duration of the at least one convoy of vehicles holding or blocking the node.
[0052] In an embodiment, the computation module (118) is configured to identify effector parameters. The effector parameters include properties related to the multiple-convoy of vehicles, which when changed, bring their effect to the properties of its other related objects. The effect can propagate along the relational link chain in the transportation network. The effector parameter is a blockade, which is a time window, comprising of start time and end time, which represents the blocked time duration by a convoy of vehicles holding or blocking a transportation network resource. The resource includes an edge or a node of the transportation network, resulting in the blocking of other convoy of vehicles which share the same path of movement. A slight shift in the blockade can affect the movement of the other convoy of vehicles in the transportation network. A node-based computation strategy considers junctions as resources.
[0053] In an exemplary embodiment, for a convoy Ci in movement with speed S, the blockade at some point in the transportation network at time b1 is represented as:
b = {b1, b2};
where b2 = b1 + (Li / S) + eg, Equation (1)
where Li is the length of the convoy
eg is the extra gap behind the convoy (in time)
[0054] The node generation module (120) is configured to cooperate with the determination module (116) to receive the determined nodes. The node generation module (120) is further configured to combine the nodes associated with the path, and generate a computational node. In an embodiment, the computational node is generated based on conditional grouping of the convoys with time constraints. In one embodiment, the conditional grouping of the convoys is based on speed of the multiple-convoy of vehicles and the pre-determined halt patterns stored in the repository (110).
[0055] The transformation module (122) is configured to cooperate with the node generation module (120) and the computational module (118) to receive the computational node and the blocking time for the convoy of vehicles. The transformation module (122) is further configured to provide the blocking time to the convoy of vehicles for movement at the computational node. In an embodiment, the transformation module (122) is configured to perform forward transformation and inverse transformation functions for processing bidirectional data along with a timeline depending on the position of the computational node. The transformation functions check feasibility during sequencing and scheduling of the multiple-convoy of vehicles at the computational node.
[0056] In an embodiment, the computational node is used in the SNBC technique, where the data of other nodes is transformed to the computational node, and the optimization logic is run. The advantage of this technique is that it can accommodate handling of multiple constraints including clash avoidance and grouping of group able convoys in the set I.

[0057] In an embodiment, the transformation module (122) is configured to perform transformation of data corresponding to the effector parameters using transformation functions adopting SNBC technique. The transformation functions bring the data from other nodes that are a part of the transportation network to the node of interest, transforming the data, and hence bringing in the effect of change in the Effector Parameters. In one embodiment, a transformation function for the multi-vehicle convoy is as described below.
Transformation function T = F (b, D, s, H)
where,
b: a blockade at node n1, containing a time window {b1, b2}, where b1 < b2 in the timeline
Distance function D = F (G’’, n1, n2),
where, G’’: a graph of the dissolved network,
n1: a node where blockade b is present,
n2: a node where the b needs to be taken to, between which the distance has to be calculated along the convoy’s movement path.
s: speed of the convoy
H: {h1,h2,h3,…, hi ,.. hm} is the halt set representing pattern of halts
where, |H| = m (m is always even and 01, when i is even,
Halt time = hi – hi-1, i>1 when i is odd.
The function T gives the transformed blockade ß of a convoy of vehicles after covering a distance returned by function D, moving with speed s and following pattern of movement H, from node n1 to node n2, represented by the equation:
ß = T(b, D, s, H) – Equation (2)
Blockade b containing the time window {b1, b2} is transformed as blockade ß of the time window {ß1, ß2}. The function T is a forward transformation function which does the transformation along the eastward direction in the time line.
An inverse transformation function T-1 preforms the reverse processing of what the forward Transformation function T does. In the SNBC technique, when the time dependent data needs to be brought to the computational node, movement of data will be bidirectional along the timeline depending on the position of the computational node. The movement of data in the reverse direction along the time line is handled by the inverse transformation function T-1. Similar to T, T-1 returns the blockades when moved against the time line.
b = T-1(ß, D, s, H) - Equation (3)
The time window of the convoy of vehicles on any of the nodes in the dissolved network can be found out. Nodes where the convoy of vehicles does not visit will also have the transformed timings representing the effect of the multiple-convoy of vehicles passing in the neighboring or far junctions.
[0058] In another embodiment, the transformation module (122) is configured to handle feasibility checks for conditional grouping with time constraints. In an exemplary embodiment, the grouping made using the network topology graph G’’ is checked for geographical feasibility. The grouping and sequencing of multiple-convoy of vehicles is within the group, the convoy of vehicles that are too far from the computational node shall be omitted to ensure that maximum wait time (Mi) is not violated for any given convoy Ci. This check is made using transformation functions T and T-1, after sequencing, by sending back the blockades to the first node of the each of the convoy’s path and deriving the start time tst. If test – tst< Mi, then the grouping is feasible, otherwise not.
[0059] The scheduler (124) is configured to cooperate with the database (110) to receive the stored information. The scheduler (124) is further configured to schedule the multiple-convoy of vehicles based on the pre-defined priorities. In an embodiment, each of the multiple-convoy of vehicles is scheduled from a start node with the start time, and end time computed by visiting the nodes in the path.
[0060] In an embodiment, scheduling the multiple-convoy of vehicles one after the other based on the priorities given to each of them is performed. Each convoy is scheduled from its start node with start timing test, then computing the time by visiting the nodes in minimal cost path one after the other. Clash avoidance is performed by iteratively delaying the start time of the convoy and subsequent rescheduling from the start node as and when the clashes are observed at each visited node, until the destination is reached. This approach is time consuming and cannot accommodate all constraints of the problem.

[0061] In another embodiment, the scheduler (124) is configured to schedule the convoy of vehicles at the computational node. A best feasible slot of time is found for each convoy of vehicles of the group, considering the following:

a) Individual convoy of vehicle’s own start time restriction (test), which appears as a transformed blockade
ßown = {-8, t’est} at the computational node

b) Set of transformed blockades from the other convoy of vehicles that are scheduled and already occupying the transportation network space represented by,
Set Bs = {ß1, ß2, … , ßn}
c) Set of transformed blockades from timed barriers represented by,
Set Bt = {ßt1, ßt2, … , ßt3}
The slot of time is found by avoiding overlapping of blockade ßown, and blockades in the set Bs and Bt, hence achieving the clash avoidance. Further, the same steps also determine the best sequence of convoy movement within the grouped move (referred to as sequencing activity).
[0062] In an embodiment, the control engine (104) further includes a barrier blockade module (126), a broadcasting module (128), and a sequence generation module (130).
[0063] The barrier blockade module (126) is configured to block the movement of the multiple-convoy of vehicles for a pre-defined interval of time. In an embodiment, the barrier blockade module (126) is configured to provide a timed barrier blockade as a distinctive blockade on the transportation network, which represents the unavailability of the network space for a particular interval of time. In an embodiment, the blockades can be from the multiple-convoy of vehicles that are already scheduled and cannot be altered, or from the timed barriers. These blockades are transformed to the common node of computation through the transformation functions.
[0064] The broadcasting module (128) is configured to broadcast data related to the movement of the scheduled convoys to the non-scheduled convoys. In an embodiment, when computation at the computational node is made, and the results of which are final, then the broadcasting technique is preferred. The broadcasting module (128) is configured to broadcast the effect of the movement of the scheduled convoy of vehicles to all the start nodes of the convoy of vehicles that are not yet scheduled. In one embodiment, the broadcasting module (128) broadcasts the blockades when the decision will not change until the complete solution is found, and the effect of the decision is on the entire transportation network. In another embodiment, when the computation made at the computational node is not final, and is based on some other conditions, then the broadcasting module (128) does not broadcast the data, as it builds invalid data over the nodes in the transportation network. Thus, the broadcasting module (128) is configured to request the blockades only when required. At the time of scheduling the multiple-convoy of vehicles, the blockades are requested from the convoy of vehicles whose schedule is fixed, and also blockades from the timed barriers are requested. In one embodiment, the fixed decision made at some node in the transportation network is required at another node. In another embodiment, the scope of the decision made is confined only to certain nodes of interest.
[0065] The sequence generation module (130) is configured to generate a sequence of the multiple-convoy of vehicles movement within the grouped movement.
[0066] Figure 2 illustrates a network graph (200) depicting a dissolved transportation network graph, according to an exemplary implementation of the present invention.
[0067] In an embodiment, the computational node is an imperative node and can be different based on the different set of constraints. Without the grouping constraint, the computational node becomes the first node in the convoy of vehicle’s path. The complete clash avoidance and sequencing can be done in this node. In order to schedule the convoy C4, from its start node, SL4 acts as the computational node Z, represented by Z2 in the Figure 2. Let, C1, C2 and C3 are scheduled, the data of blockades brought from convoys C1, C2 and C3 from their locations SL1, SL2 and SL3 respectively to the computational node Z2 using forward and inverse transformation functions. To bring the blockades from start locations to the intermediate node N, forward transformation function is applied. From node N to the SL4, inverse transformation function is applied to get the blocked timings at the computational node Z2. If C1, C2 and C3 are not scheduled yet, while scheduling C4 no blockades will be received at Z2. With the grouping constraint considered, the computational node shifts and have the following property:

[0068] If p represents a sequence of the nodes taken by the convoy C of the group g ? I (Grouping Set), then node Z has the following property:

Maximum(?i=0 to k presence(Z in Pi)) – Equation (4)
where k=|g|,

presence = F{returns 1 if present, 0 otherwise}

Minimum(?i=0 to k index(Z in p)) – Equation (5)

where index = F{returns the index of Node Z in path p}

Equation (4) refers to the maximum number of convoys that pass en-route and also multiple-convoy of vehicles present in the groupable set I. Equation (5) refers Z is the first node on the multiple-convoy of vehicles path adhering to the criteria specified by Equation (4). For the convoys C1, C2 and C3, Z1 is the computational node represented in the Figure 2.

[0069] Figure 3 illustrates a network graph (300) depicting the flow of data between a computational node and other nodes in a transportation network by application of transformation functions, according to an exemplary implementation of the present invention.
[0070] Figure 4 represents movement of blockades using transformations and sequencing of time windows. The forward transformation segments in the TWs at computational node Z1 along Y-axis represent the blockades received at the computational node Z1 for sequencing of convoys C1, C2 and C3. The inverse transformation segments represent the time windows for each of the multiple-convoy of vehicles after sequencing. When a good slot at the computational node is found, the same is transformed using the inverse transformation function T-1 to find out the start time for each of the multiple-convoy of vehicles. Similarly, the end time of the schedule is found out using the forward transformation function T. At other nodes in the network the blockades (if broadcasted) remain as useful information for the multiple-convoy of vehicles starting from those nodes.

[0071] Figure 4 illustrates a graphical view (400) depicting sequencing and clash avoidance at a computational node, according to an exemplary implementation of the present invention. Figure 4 represents the activity of sequencing and clash avoidance logic to be run in the computational node and requesting and broadcasting to/from the other nodes. X represents a random node in the dissolved network G”.
[0072] Figure 5 illustrates a flowchart (500) depicting scheduling of multiple-convoy of vehicles, according to an exemplary implementation of the present invention.
[0073] The flowchart (500) starts at a step (502), providing a computational node Z and a grouping set G. In another embodiment, a node generation module (120) generates a computational node based on conditional grouping of a plurality of convoys with time constraints.
[0074] At a step (504), requesting blockades for each of the multiple-convoy of vehicles C in the grouping set G, from their respective start nodes at the computational node Z. In another embodiment, the transformation module (122) is configured to provide the blockade/ blocking time to each of the multiple-convoy of vehicles.
[0075] At step (506), requesting blockades from other scheduled multiple-convoy of vehicles and bringing the data to the computational node Z. In another embodiment, the scheduler (124) is configured to schedule the multiple-convoy of vehicles.
[0076] At step (508), requesting blockades from timed barriers and making data available at the computational node Z. In another embodiment, a barrier blockade module (126) is configured to block the movement of the multiple-convoy of vehicles for a pre-defined interval of time, and making data available at the computational node Z.
[0077] At step (510), finding slot and sequencing for each of the multiple-convoy of vehicles C. In another embodiment, the sequence generation module (130) is configured to generate a sequence of the multiple-convoy of vehicles movement within the grouped movement. A best feasible slot of time is determined by the scheduler (124), for each convoy of vehicles of the group.
[0078] At step (512), performing feasibility check for each multiple-convoy of vehicles C. In another embodiment, the transformation module (122) is configured to perform feasibility check for each of the multiple-convoy of vehicles.
[0079] Figure 6 illustrates a flowchart (600) depicting a method for route management of multiple-convoy of vehicles, according to an exemplary implementation of the present invention.
[0080] The flowchart (600) starts at a step (602), storing, in a database (110), information related to pre-defined transportation network routes, pre-defined priorities, pre-defined locations, and pre-determined halt patterns.
[0081] At step (604), receiving, by an input module (112), inputs from a plurality of user devices (102a, 102b, 102c,….,102n), wherein the inputs include source location information, destination location information, start time, and end time, of each of the multiple-convoy of vehicles.
[0082] At step (606), identifying, by a path identification module (114), at least one minimal cost path between a source location and a destination location.
[0083] At step (608), computing, by a computational module (118), a blocking time for at least one convoy of vehicles, and allotting the blocking time to the convoy of vehicles for the path.
[0084] At step (610), generating, by a node generation module (120), a computational node based on conditional grouping of a plurality of convoys with time constraints.
[0085] At step (612), providing, by a transformation module (122), the blocking time to the convoy of vehicles for movement at the computational node.
[0086] At block (614), scheduling, by a scheduler (124), the multiple-convoy of vehicles based on the pre-defined priorities, wherein each of the multiple-convoy of vehicles is scheduled from a start node with the start time.
[0087] At block (616), computing, by the scheduler (124), time by visiting the nodes by each of the multiple-convoy of vehicles’ in the path.
[0088] It should be noted that the description merely illustrates the principles of the present invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described herein, embody the principles of the present invention. Furthermore, all examples recited herein are principally intended expressly to be only for explanatory purposes to help the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass equivalents thereof.
,CLAIMS:
1. A method for route management and schedule management of multiple-convoy of vehicles, said method comprising the steps of:
storing, in a database (110), information related to pre-defined transportation network routes, pre-defined priorities, pre-defined locations, and pre-determined halt patterns;
receiving, by an input module (112), inputs from a plurality of user devices (102a, 102b, 102c,….,102n), wherein said inputs include source location information, destination location information, start time, and end time, of each of said multiple-convoy of vehicles;
identifying, by a path identification module (114), at least one minimal cost path between a source location and a destination location;
computing, by a computational module (118), a blocking time for at least one convoy of vehicles, and allotting said blocking time to said convoy of vehicles for said path;
generating, by a node generation module (120), a computational node based on conditional grouping of a plurality of convoys with time constraints;
providing, by a transformation module (122), said blocking time to said convoy of vehicles for movement at said computational node;
scheduling, by a scheduler (124), said multiple-convoy of vehicles based on the pre-defined priorities, wherein each of said multiple-convoy of vehicles is scheduled from a start node with said start time, and
computing, by said scheduler (124), time by visiting the nodes by each of said multiple-convoy of vehicles in said path.

2. The method as claimed in claim 1, wherein said step of identifying said path includes a step of determining, by a determination module (116), said nodes associated with said path.

3. The method as claimed in claim 1, wherein said step of identifying said path includes a step of integrating, by said path identification module (114), two or more identified minimal cost paths, and generating an integrated path.

4. The method as claimed in claim 1, further includes a step of blocking, by a barrier blockade module (126), the movement of said multiple-convoy of vehicles for a pre-defined interval of time.

5. The method as claimed in claim 1, further includes a step of generating, by a sequence generation module (130), a sequence of said multiple-convoy of vehicles’ movement within the grouped movement.

6. The method as claimed in claim 1, wherein said step of identifying said path includes a step of determining the minimal cost path between said source location and said destination location.

7. The method as claimed in claim 1, wherein said step of providing the blocking time to said convoy of vehicles includes a step of performing, by said transformation module (122), forward transformation and inverse transformation functions for processing bidirectional data along with a timeline depending on the position of the computational node, said transformation functions check feasibility during sequencing and scheduling of said multiple-convoy of vehicles at said computational node.

8. The method as claimed in claim 1, wherein said conditional grouping of said nodes is based on speed of said multiple-convoy of vehicles and said pre-determined halt patterns stored in said database (110).

9. The method as claimed in claim 1, further includes a step of broadcasting, by a broadcasting module (126), data related to the movement of the scheduled vehicles to the non-scheduled vehicles.

10. The method as claimed in claim 1, wherein said blocking time comprises start time and end time, and represents the blocked time duration of said at least one convoy of vehicles holding or blocking said node.

11. A control system (100) for route management and schedule management of multiple-convoy of vehicles, said control system (100) comprising:
a plurality of user devices (102a, 102b, 102c,…,102n); and
a control engine (104) configured to cooperate with said plurality of user devices (102a, 102b, 102c,….,102n), said control engine (104) comprising:
a memory (106) configured to store pre-determined rules;
a processor (108) configured to cooperate with said memory (106) to receive said pre-determined rules, said processor (108) configured to process system processing commands;
a database (110) configured to store information related to pre-defined transportation network routes, pre-defined priorities, pre-defined locations, and pre-determined halt patterns;
an input module (112) configured to receive inputs from said plurality of user devices (102a, 102b, 102c,….,102n), wherein said inputs include source location information, destination location information, start time, and end time, of each of multiple-convoy of vehicles;
a path identification module (114) configured to cooperate with said input module (112) and said database (110), said path identification module (114) configured to identify at least one minimal cost path between a source location and a destination location;
a determination module (116) configured to cooperate with said path identification module (114) and said database (110), said determination module (116) configured to determine a plurality of nodes associated with said path;
a computational module (118) configured to cooperate with said input module (112) and said determination module (116), said computational module (118) configured to compute a blocking time for at least one convoy of vehicles, and allot said blocking time to said convoy of vehicles for said path;
a node generation module (120) configured to cooperate with said determination module (116), said node generation module (120) configured to combine said nodes associated with said path, and generate a computational node, wherein said computational node is generated based on conditional grouping of said nodes with time constraints;
a transformation module (122) configured to cooperate with said node generation module (120) and said computational module (118), said transformation module (122) configured to provide said blocking time to said convoy of vehicles for movement at said computational node; and
a scheduler (124) configured to cooperate with said database (110), said scheduler (124) configured to schedule said multiple-convoy of vehicles based on the pre-defined priorities, wherein each of said multiple-convoy of vehicles is scheduled from a start node with said start time, and compute the time by visiting said nodes in said path.

12. The control system (100) as claimed in claim 11, wherein said path identification module (114) configured to integrate two or more identified minimal cost paths, and generate an integrated path.

13. The control system (100) as claimed in claim 11, wherein said control engine (104) includes a barrier blockade module (126) configured to block the movement of said multiple-convoy of vehicles for a pre-defined interval of time.

14. The control system (100) as claimed in claim 11, wherein said control engine (104) includes a sequence generation module (130) configured to generate a sequence of said multiple-convoy of vehicles movement within the grouped movement.

15. The control system (100) as claimed in claim 11, wherein said path identification module (114) configured to identify at least one minimal cost path by determining the minimal cost between said source location and said destination location.

16. The control system (100) as claimed in claim 11, wherein said transformation module (122) configured to perform forward transformation and inverse transformation functions for processing bidirectional data along the timeline depending on the position of the computational node, said transformation functions check feasibility during sequencing and scheduling of said multiple-convoy of vehicles at said computational node.

17. The control system (100) as claimed in claim 1, wherein said conditional grouping of said convoys is based on speed of said multiple-convoy of vehicles and said pre-determined halt patterns stored in said database (110).

18. The control system (100) as claimed in claim 1, further includes a broadcasting module (128) configured to broadcast data related to the movement of the scheduled convoys to the non-scheduled convoys.

19. The control system (100) as claimed in claim 1, wherein said blocking time comprises start time and end time, and represent the blocked time duration of said at least one convoy of vehicles holding or blocking said node.