ROLLING STOCK SCHEDULING APPARATUS AND METHOD

• US 20090119145A1
• Filed: 10/28/2008
• Published: 05/07/2009
• Est. Priority Date: 10/29/2007
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Aisu, Hideyuki, OTSUKI, TOMOSHI
• Granted Patent: US 8,392,233 B2
• Time in Patent Office: Days
• US Class Current: 705/8
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 50/28 Logistics, e.g. warehousing, loading, distribution or shipping

Abstract

A rolling-stock-scheduling apparatus includes a creation unit creating a graph from an initial day to a target day, the graph including nodes representing initial-day sites, target-day sites, and first operations, the first operations being defined by a departure time, a departure site, an arrival time, and an arrival site, the graph including arcs each of which indicates nodes'"'"' connectability, a setting unit setting paths that connect second operations on each day from the initial day to the target day, an exchange unit exchanging, if there is a first car which does not exist at the target-day site on the target day, each arc so that all the cars exist at target-day sites on the target day, and an output unit outputting, if second paths on which all the cars exist at the target-day sites are found, third operations corresponding to each of the second paths as a car-operation.

Claims

1. A rolling stock scheduling apparatus comprising:

a creation unit configured to create an operation connection graph for each car from an initial day to a target day, the graph including nodes representing initial day sites, target day sites, and first operations, the first operations being defined by a departure time, a departure site, an arrival time, and an arrival site, the graph also including arcs each of which indicates nodes'"'"' connectability based on the departure site, the arrival site, the departure time and the arrival time;

a setting unit configured to set a plurality of paths that connect second operations for each car on each day sequentially from the initial day to the target day, the second operations being included in the first operations;

an exchange unit configured to exchange, if there is a first car which does not exist at the target day site on the target day, each arc so that all cars exist at target day sites on the target day; and

an output unit configured to output, if second paths on which all the cars exist at the target day sites on the target day are found, third operations corresponding to each of the second paths as a car operation, the second paths being set by the setting unit.

2. The apparatus according to claim 1, wherein if a first node is one of a node of the same day as a second node and a node of a next day of the second node, if the arrival site of the second node matches the departure site of the first node, and if the arrival time of the second node is earlier than the departure time of the first node, the creation unit determines that the first node is connectable to the second node.

3. The apparatus according to claim 1, wherein if there is a second car not corresponding to the nodes and the arcs included in the graph, the setting unit assigns an extra node to the second car in each day, the extra node indicating staying at an arrival site of a preceding day.

4. The apparatus according to claim 1, wherein the exchange unit sequentially sets, from 1, number of times of exchange representing number of arcs exchanged for each path, and exchanges the arcs up to a threshold value of the number of times of exchange to make all cars corresponding to all paths exist at the target day sites on the target day.

5. The apparatus according to claim 4, wherein the exchange unit sets a number obtained by subtracting the number of times of exchange from the threshold value as a new threshold value for a third car which does not exist at the target day site on the target day, and exchanges the arcs up to the new threshold value.

6. The apparatus according to claim 1, wherein if there is a fourth car which does not exist at the target day site on the target day and if there is a fifth car which has an operation limiting constraint that limits an operation of the fifth car, the exchange unit exchanges the arcs.

8. The method according to claim 1, wherein if a first node is one of a node of the same day as a second node and a node of a next day of the second node, if the arrival site of the second node matches the departure site of the first node, and if the arrival time of the second node is earlier than the departure time of the first node, creating the graph determines that the first node is connectable to the second node.

9. The method according to claim 1, wherein if there is a second car not corresponding to the nodes and the arcs included in the graph, setting the path assigns an extra node to the second car in each day, the extra node indicating staying at an arrival site of a preceding day.

10. The method according to claim 1, wherein exchanging each arc sequentially sets, from 1, number of times of exchange representing number of arcs exchanged for each path, and exchanges the arcs up to a threshold value of the number of times of exchange to make all cars corresponding to all paths exist at the target day sites on the target day.

11. The method according to claim 4, wherein exchanging each arc sets a number obtained by subtracting the number of times of exchange from the threshold value as a new threshold value for a third car which does not exist at the target day site on the target day, and exchanges the arcs up to the new threshold value.

12. The method according to claim 1, wherein if there is a fourth car which does not exist at the target day site on the target day and if there is a fifth car which has an operation limiting constraint that limits an operation of the fifth car, exchanging each arc exchanges the arcs.

7. A rolling stock scheduling method comprising:

creating an operation connection graph for each car from an initial day to a target day, the graph including nodes representing initial day sites, target day sites, and first operations, the first operations being defined by a departure time, a departure site, an arrival time, and an arrival site, the graph also including arcs each of which indicates nodes'"'"' connectability based on the departure site, the arrival site, the departure time, and the arrival time;

setting a plurality of set paths that connect second operations for each car on each day sequentially from the initial day to the target day, the second operations being included in the first operations;

exchanging, if there is a first car which does not exist at the target day site on the target day, each arc so that all cars exist at target day sites on the target day; and

outputting, if second paths on which all the cars exist at the target day sites on the target day are found, third operations corresponding to each of the second paths as a car operation, each of the second paths being set by setting the set path.