Method for analyzing and generating optimal transportation schedules for vehicles such as trains and controlling the movement of vehicles in response thereto
First Claim
1. A method for controlling the movement of vehicles traveling in a transportation system, comprising the steps of:
- (a) inputting data into a processor indicative of at least i) a physical description of a routing network on which said vehicles travel, and ii) a proposed transportation schedule for each vehicle traveling in said transportation system, each proposed schedule having at least a time of departure from a specified origin and a time of arrival at a specified destination;
(b) identifying potential conflicts between two vehicles based on said proposed schedules, and a set of conflict resolution points based upon said routing network and said potential conflicts, each conflict resolution point being a meetpoint at which one of said two vehicles can be delayed to permit the other of said two vehicles to pass thereby avoiding a collision between said two vehicles, said potential conflicts being chronologically sequenced based on said proposed schedules and said conflict resolution points being identified according to said chronological sequence and taking into consideration a possible delay of said one vehicle in each identified potential conflict;
(c) generating an initial meet-pass plan using a depth-first search bounded by delay costs arising from delaying said one vehicle at one of said identified conflict resolution points for each potential conflict for an amount of time such that each potential conflict is resolved without a collision, said initial plan having a delay cost substantially equal to an accumulation of all delay costs resulting from said one vehicle being delayed in each potential conflict, said delay cost defining an upper bound;
(d) estimating a maximum cost benefit arising from shifting from said one conflict resolution point used to resolve each respective potential conflict in said initial meet-pass plan to another conflict resolution point, said shifting resulting in a potential alternative plan;
(e) generating alternative meet-pass plans using the depth-first search bounded by delay costs from said other conflict resolution point in each potential alternative plan where said estimated maximum cost benefit is positive, said alternative meet-pass plan having a delay cost substantially equal to an accumulation of all delay costs resulting from said one vehicle being delayed in each potential conflict, and if said delay cost of said alternative meet-pass plan so generated is lower than said upper bound, the step further comprising replacing said upper bound with said delay cost of said alternative meet-pass plan;
(f) identifying one meet-pass having a substantially minimal delay cost among said initial and alternative meet-pass plans so generated by comparing each alternative meet-pass plan generated to said upper bound; and
(g) controlling the movement of said vehicles according to said identified meet-pass plan, said vehicles being delayed at said identified conflict resolution points for the amount of time specified by said identified meet-pass plan.
2 Assignments
0 Petitions
Accused Products
Abstract
A method of analyzing transportation schedules in a schedule analysis (SCAN) decision support system to determine the feasibility of the schedules is disclosed. In a transportation system, vehicles are delayed to avoid conflicts with other vehicles which would otherwise collide because the vehicles may be travelling along the same travel paths at different speeds or in opposite directions. The invention utilizes information relating to the vehicle travel paths, the vehicle'"'"'s speed and mobility characteristics, a function based on the vehicle'"'"'s on-time performance, proposed transportation schedules and real-time data associated with the travel paths and vehicles. This information is used to provide substantially optimal vehicle schedules with respect to cost resulting from vehicle delay.
-
Citations
16 Claims
-
1. A method for controlling the movement of vehicles traveling in a transportation system, comprising the steps of:
-
(a) inputting data into a processor indicative of at least i) a physical description of a routing network on which said vehicles travel, and ii) a proposed transportation schedule for each vehicle traveling in said transportation system, each proposed schedule having at least a time of departure from a specified origin and a time of arrival at a specified destination; (b) identifying potential conflicts between two vehicles based on said proposed schedules, and a set of conflict resolution points based upon said routing network and said potential conflicts, each conflict resolution point being a meetpoint at which one of said two vehicles can be delayed to permit the other of said two vehicles to pass thereby avoiding a collision between said two vehicles, said potential conflicts being chronologically sequenced based on said proposed schedules and said conflict resolution points being identified according to said chronological sequence and taking into consideration a possible delay of said one vehicle in each identified potential conflict; (c) generating an initial meet-pass plan using a depth-first search bounded by delay costs arising from delaying said one vehicle at one of said identified conflict resolution points for each potential conflict for an amount of time such that each potential conflict is resolved without a collision, said initial plan having a delay cost substantially equal to an accumulation of all delay costs resulting from said one vehicle being delayed in each potential conflict, said delay cost defining an upper bound; (d) estimating a maximum cost benefit arising from shifting from said one conflict resolution point used to resolve each respective potential conflict in said initial meet-pass plan to another conflict resolution point, said shifting resulting in a potential alternative plan; (e) generating alternative meet-pass plans using the depth-first search bounded by delay costs from said other conflict resolution point in each potential alternative plan where said estimated maximum cost benefit is positive, said alternative meet-pass plan having a delay cost substantially equal to an accumulation of all delay costs resulting from said one vehicle being delayed in each potential conflict, and if said delay cost of said alternative meet-pass plan so generated is lower than said upper bound, the step further comprising replacing said upper bound with said delay cost of said alternative meet-pass plan; (f) identifying one meet-pass having a substantially minimal delay cost among said initial and alternative meet-pass plans so generated by comparing each alternative meet-pass plan generated to said upper bound; and (g) controlling the movement of said vehicles according to said identified meet-pass plan, said vehicles being delayed at said identified conflict resolution points for the amount of time specified by said identified meet-pass plan. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. In a transportation system having a plurality of vehicles, each vehicle having a scheduled departure time from an origin and a scheduled arrival time at a destination, there being a routing network defined by travel paths between the origin and destination, and delay points along each path for permitting one vehicle to wait until a second vehicle passes so as to avoid collision, a method comprising the steps of:
-
(a) inputting into a computer system at least one of the following data indicative of; (i) a description of said routing network; (ii) speed and mobility characteristics of each vehicle; (iii) proposed transportation schedules for each vehicle specifying at least scheduled departure and arrival times; (iv) a vehicle tardiness function for each vehicle indicative of an importance of each vehicle arriving at its destination on time; (v) any changes in said routing network, (vi) any changes in a physical characteristic of any path in said routing network; and
,(vii) vehicle status in said routing network; (b) initializing at least one of; (i) a first variable indicative of a maximum cost due to vehicle delays for said proposed transportation schedules input in step (a), said first variable defining an upper bound; (ii) a second variable indicative of the minimum cost due to vehicle delays for said proposed transportation schedules input in step (a), said second variable defining a lower bound; (c) grouping said vehicles into vehicle pairs having a first and second vehicle comprising substantially all possible combinations; (d) determining, based upon the data input in (a), whether a potential conflict exists between said two vehicles of each vehicle pair, and if so, identifying said vehicle pair as a level, (e) identifying substantially all delay points at a first level where at least one vehicle in said vehicle pair could be delayed so that the second vehicle in said pair could pass without collision therebetween, defining said delay points so identified as conflict resolution points, (f) selecting one conflict resolution point identified in step (e) for said first level; (g) determining an amount of time at least one vehicle in said vehicle pair must be delayed at said selected conflict resolution point so that the second vehicle can pass by without collision therebetween, said amount of time said vehicle is delayed defining a delay time; (h) updating said vehicles'"'"' scheduled departure and arrival times based upon said delay times determined in step (g); (i) repeating steps (e) through (i) for each level identified in step (d); (j) calculating a delay cost, based upon each delay time determined in step (g) and said respective vehicle tardiness functions input in step (a), for each vehicle delayed in step (g); (k) calculating a cumulative delay cost by adding together said delay costs calculated in step (j), and defining said cumulative delay cost as a plan cost when said delay costs for substantially all levels have been added together; (l) defining the arrival and departure times for each vehicle at each point along the vehicle'"'"'s travel path between said origin and destination as a current plan if said plan cost is less than said upper bound, and setting said upper bound equal to said plan cost; (m) selecting an alternative conflict resolution point from said conflict resolution points identified in step (e) but not selected in step (f); (n) identifying substantially all vehicles whose delays determined in step (g) could be reduced by shifting said selected conflict resolution point to said alternative conflict resolution point selected in step (m), the vehicles so identified defining benefitted vehicles; (o) estimating, based on said alternative conflict resolution point, an amount indicative of a potential net cost reduction by computing a difference in potential delay reductions at other levels and any delay increases, where said delay reductions and delay increases result from shifting to said alternate conflict resolution point in step (m), said difference computed defining a first maximum net benefit; (p) repeating step (o), wherein the computation is based on said vehicles arriving at said alternate conflict resolution point on time with respect to their scheduled arrival times, said difference so computed defining a second maximum net benefit; (q) estimating, based on said alternative conflict resolution point, any cost reduction to said plan cost by merging delays of vehicles which are delayed at different levels over at least partially the same time interval thereby determining each vehicle'"'"'s actual delay time, said estimated cost reduction defining a merged cost decrease; (r) redefining said lower bound by subtracting at least one of;
(i) said second maximum net benefit; and
(ii) said merged cost decrease(s) defining said set of conflict resolution points selected in step (f) and (m), the vehicles delayed in step (g) and their respective delay times, and said cumulative delay cost as a fathomed path if any cumulative delay cost is greater than said upper bound, and redefining the cumulative delay cost of said path as said upper bound; (t) identifying vehicle pairs at levels having both a positive second maximum net benefit and negative first maximum net benefit, and defining the vehicles of said vehicle pairs so identified as potential vehicles; (u) repeating steps (h) through (l) based on said alternate conflict resolution point selected in step (m) when at least one of the following occurs; (i) said level for which said alternate conflict resolution point has been selected has a positive first maximum net benefit; and (ii) at least one benefitted vehicle is a potential vehicle for said level and second maximum net benefits at previous levels are negative; (v) repeating step (u) until one of the following events; (i) no alternative conflict resolution points are available to be selected in one of steps (f) and (m); (ii) said plan cost is less than a tolerance indicative of an acceptable difference between said upper bound and said lower bound, a plan having said plan cost defining a feasible plan; and (iii) a predetermined time limit has expired and no feasible plans have been identified the step further comprising identifying said current plan as an optimal plan when one of said events has occurred; and (w) controlling the movement of said vehicles so that the arrival and departure times for each vehicle at each point along the vehicle'"'"'s respective travel path between said origin and said destination is controlled according to said optimal plan. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
Specification