Optimization method and device of crew replanning for high-speed railway in typical scenarios

A computer-implemented method of crew replanning for multiple high-speed railway typical scenarios, comprising:

• building a high-speed railway crew connection network;
• establishing a model for high-speed railway crew replanning;
• decomposing the model into a first sub-model for team leaders and a second sub-model for general crew members;
• and
• designing a Lagrangian relaxation algorithm to solve the first sub-model and the second sub-model;
• automatically generating a replanned crew schedule based on results for the first sub-model for the team leaders and the second sub-model for the general crew members;
• and
• automatically transmitting the replanned crew schedule in real time to the team leaders and the general crew members, such that up-to-date information in the replanned crew schedule is notified to each crew member;
• wherein the railway crew connection network is built through steps of:
• performing node establishment;
• and
• establishing a connection arc;
• wherein the node establishment comprises steps of:
• denoting a day before a start of a scheduling cycle as d=0;
• denoting moment 0:00 of d=0 as time zero, in minutes;
• wherein for ∀e∈E, a start time tdestart is expressed as tdestart=testart+1440×de, and an end time tdeend is expressed as tdeend=teend+1440×de;
• for ∀eT∈ET, a start time tdeTstart is expressed as tdeTstart=teTstart+1440×deT, and an end time tdeTend is expressed as tdeTend=tdeTend+1440×deT;
• and
• establishing nodes respectively corresponding to an initial state of each crew member, a crew duty of each day within the scheduling cycle and a replanning crew duty according to schedule day;
• the node establishment further comprises:
• establishing virtual crew base source nodes m1O, m2O, . . . , mnO for all crew bases in a crew area involved in crew scheduling, respectively, and denoting a set of the virtual crew base source nodes as VO;
• wherein there is a unique crew base for ∀r∈R;
• establishing virtual crew base end nodes m1D,m2D, . . . , mnD for all crew bases in the crew area involved in the crew scheduling, respectively, and denoting a set of the virtual crew base end nodes as VD;
• and
• for ∀e∈R, de∈{d|d=1 . . . ND−1} and ∀eT∈ET, deT∈{d|d=1 . . . ND−1}, establishing an intermediate node ved corresponding to the crew duty and an intermediate node VeTd of the replanning crew duty;
• wherein the intermediate node ved and the intermediate node vdTd each has seven attributes, respectively start position, start time, end position, end time, duration, schedule day serial number and crew preference;
• locating, by a global positioning system (GPS), a start position and an end position of each crew member during the crew duty to determine the start position and the end position of the intermediate node corresponding to the crew duty;
• denoting a set of intermediate nodes of all crew duties in the scheduling cycle as VmidE;
• denoting a set of intermediate nodes of all replanning crew duties as VmidT;
• denoting a set of all intermediate nodes as Vmid;
• and
• denoting a set of all nodes as V;
• wherein R represents a set of all crew members;
• r is any one of all crew members;
• D is a set of all schedule days in the scheduling cycle, D={d|d=1, 2, 3, . . . , ND}, wherein d is any one of the schedule days, and ND is the total number of days in the scheduling cycle;
• E represents a set of all crew duties in the scheduling cycle;
• e is any one of all crew duties;
• testart is a start time of the crew duty e;
• teend is an end time of the crew duty e;
• te is a duration of the crew duty e;
• and de represents a schedule day serial number of the crew duty e;
• ET represents a set of all replanning crew duties in the scheduling cycle;
• eT is any one of all replanning crew duties;
• teTstart represents a start time of the replanning crew duty eT;
• teTend represents an end time of the replanning crew duty eT;
• teT represents a duration of the replanning crew duty eT;
• and deT represents a schedule day serial number of the replanning crew duty eT;
• and
• mn represents crew base, wherein n is a positive integer;
• wherein the connection arc is established as follows:
• a) for ∀r∈R, if a crew base to which the crew member r belongs is the same as a start position of ∀e∈E and ∀eT∈ET, and the crew member r conforms to a preference of ∀e∈E and ∀eT∈ET for crew member, establishing a crew On-duty arc (mno, ved) between a virtual crew base source node mno and the intermediate node ved, or establishing a crew On-duty arc (mno, veTd) between the virtual crew base source node mno and the intermediate node veTd;
• and
• denoting a set of all crew On-duty arcs as AOn-duty;
• b) from the schedule day d=0 to schedule day d=ND−1, for any one-day crew duty and replanning crew duty, if an end position of a previous crew duty is the same as a start position of a next crew duty, establishing a crew connection arc (ve1d,ve2d) between an intermediate node veid and an intermediate node ve2d a crew connection arc (veTd, ved) between the intermediate node veTd and the intermediate node ved, or a crew connection arc (ved, veTd) between the intermediate node ved and the intermediate node veTd;
• and
• denoting a set of all crew connection arcs as Aconnection;
• c) from the schedule day d=0 to the schedule day d=ND−1, for ∀r∈R, when the end position of an intermediate node, which crew r completed, is different from a start position of the next intermediate node to be completed but the same as a start position of the another intermediate node, establishing a deadheading arc (ve1d, ve2d) between the intermediate node ve1d and the intermediate node ve2d, a deadheading arc (veTd, ved) between the intermediate node veTd and the intermediate node ved, or a deadheading arc (ved, veTd) between the intermediate node ved and the intermediate node Vel;
• and
• denoting a set of all deadheading arcs as Adeadheading;
• d) for ∀r∈R, if the crew base to which the crew member r belongs is the same as an end position of ∀e∈E and ∀eT∈ET and the crew member r conforms to the preference of ∀e∈E and ∀eT∈ET for crew member, establishing a crew Off-duty arc (ved,mnD) between a virtual crew base end node mnD and the intermediate node ved, or a crew Off-duty arc (veTd,mnD) between the virtual crew base end node mnD and the intermediate node veTd;
• and
• denoting a set of all crew Off-duty arcs as AOff-duty;
• and
• e) denoting a set of all arcs as A;
• wherein the high-speed railway crew connection network is expressed as N(V,A).