Page 31 - Krész, Miklós, and Andrej Brodnik (eds.). MATCOS-13. Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science. Koper: University of Primorska Press, 2016.
P. 31
• If trip J0 is compatible with duty F1, and there is • An integer parameter that gives the maximum number
enough time to insert it to the available gap (together of feasible schedules which can be modified.
with any necessary deadhead trips), then we can solve
the problem. • A parameter that limits the maximum length of the
newly introduced deadhead trips.
• If we want to insert J0 to duty F2, we have to remove
trip J2. There are several different places we can insert • A parameter, which gives the latest point in time, by
this newly removed trip. It might fit into the gaps in the end of which the algorithms should not modify any
duties F1 or F5 (if compatible, and there is enough more feasible schedules.
time for deadheads). We might also be able to insert
them to duties F3 or F4. However this would mean we • A parameter on the number of suggestions (feasible
have to remove trip J3,2 or J4 respectively, and finding solutions).
a new duty for them.
• A parameter on the maximum running time.
• Following the above logic, there are several different
scenarios that utlizie removing trip from a duty, and As it can be seen in the list of proposed parameters, there
inserting it to another one. are none that correspond driver rules. Driver regulations
are very strict, and most of them are defined by the EU,
• We might delay trip J3,2 in duty F4. This can give us and cannot be violated by any means. Depot compatibility
a big enough gap to insert our trip J0 (if it is allowed and vehicle type correspondence might also be strict, but we
by compatibility and deadheads). decided to let the operator of the system decide about their
violation.
As it can be seen from the above examples, there are some
other constraints as well that are connected to the original 3. THE SOLUTION FRAMEWORK
duties or tasks (eg. modifying starting time, or removing a
trip from its original duty). In the previous sections, we presented our basic ideas behind
the methodology for the problem. We described a framework
A solution method for this problem need to know the ex- that does not depend on the solution algorithm it executes,
tent to which it can violate the constraints we introduced and can be controlled through a list of different parameters.
above, and it also needs to know the hardness of the con- In Figure 2, we give a layout of the different parts of the
straint. This information can be given easily with the use of system.
parameters.
Figure 2: The structure of the framework
2.4 Parameters
The input for the system consists of two parts. One part
In this subsection, we introduce parameters for the differ- is the list of parameteres, that we described in the pre-
ent rules and constraints given in the previous subsections. vious section. The other part is the problem data itself,
These parameters need to be considered by any algorithm containing the problem specific data tables. The type and
solving the bus rescheduling problem: structure of these tables of course can vary between differ-
ent implementations of such a system, but it is important
• A binary parameter that allows the violation of depot- that it contains the disrupted schedule and the disrupted
compatibilities. A penalty parameter for each viola- trips. For the remainder of the paper, we will refer to
tion of depot-compatibility is also needed. the pair of {disruptedschedule, setof disruptedtrips} as a
conf iguration.
• A binary parameter that allows the violation of ve-
hicle type correspondence. A penalty parameter also The input determines the starting configuration of our prob-
has to be introduced for each violation of vehicle type lem, which is a schedule that contains feasible duties, and a
correspondence. set which contains the disrupted trips, that are not executed
currently by any vehicle. A configuration is supposed to be
• A binary parameter that allows the introduction of feasible, if its set of trips is empty, and all the duties in its
lateness. A penalty parameter also has to be intro- schedule are feasible and do not violate any regulations or
duced per 1 unit (minute) of lateness. parameters.
• A binary parameter that allows the movement of trips Once all the input is read, it is then transferred to the main
between feasible schedules. A penalty parameter is module of the system, which we call the Rescheduling Black
also needed that gives the cost of each such move. Box (RBB). This is the part that carries out the solution
process, and consists of two parts:
• An integer parameter that limits the maximum amount
of lateness which can introduced by the algorithms to
the schedule.
• An integer parameter that limits the maximum amount
of lateness an algorithm can introduce to a single event.
• An integer parameter that limits the maximum amount
of lateness an algorithm can introduce to one duty.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 31
Koper, Slovenia, 10-11 October
enough time to insert it to the available gap (together of feasible schedules which can be modified.
with any necessary deadhead trips), then we can solve
the problem. • A parameter that limits the maximum length of the
newly introduced deadhead trips.
• If we want to insert J0 to duty F2, we have to remove
trip J2. There are several different places we can insert • A parameter, which gives the latest point in time, by
this newly removed trip. It might fit into the gaps in the end of which the algorithms should not modify any
duties F1 or F5 (if compatible, and there is enough more feasible schedules.
time for deadheads). We might also be able to insert
them to duties F3 or F4. However this would mean we • A parameter on the number of suggestions (feasible
have to remove trip J3,2 or J4 respectively, and finding solutions).
a new duty for them.
• A parameter on the maximum running time.
• Following the above logic, there are several different
scenarios that utlizie removing trip from a duty, and As it can be seen in the list of proposed parameters, there
inserting it to another one. are none that correspond driver rules. Driver regulations
are very strict, and most of them are defined by the EU,
• We might delay trip J3,2 in duty F4. This can give us and cannot be violated by any means. Depot compatibility
a big enough gap to insert our trip J0 (if it is allowed and vehicle type correspondence might also be strict, but we
by compatibility and deadheads). decided to let the operator of the system decide about their
violation.
As it can be seen from the above examples, there are some
other constraints as well that are connected to the original 3. THE SOLUTION FRAMEWORK
duties or tasks (eg. modifying starting time, or removing a
trip from its original duty). In the previous sections, we presented our basic ideas behind
the methodology for the problem. We described a framework
A solution method for this problem need to know the ex- that does not depend on the solution algorithm it executes,
tent to which it can violate the constraints we introduced and can be controlled through a list of different parameters.
above, and it also needs to know the hardness of the con- In Figure 2, we give a layout of the different parts of the
straint. This information can be given easily with the use of system.
parameters.
Figure 2: The structure of the framework
2.4 Parameters
The input for the system consists of two parts. One part
In this subsection, we introduce parameters for the differ- is the list of parameteres, that we described in the pre-
ent rules and constraints given in the previous subsections. vious section. The other part is the problem data itself,
These parameters need to be considered by any algorithm containing the problem specific data tables. The type and
solving the bus rescheduling problem: structure of these tables of course can vary between differ-
ent implementations of such a system, but it is important
• A binary parameter that allows the violation of depot- that it contains the disrupted schedule and the disrupted
compatibilities. A penalty parameter for each viola- trips. For the remainder of the paper, we will refer to
tion of depot-compatibility is also needed. the pair of {disruptedschedule, setof disruptedtrips} as a
conf iguration.
• A binary parameter that allows the violation of ve-
hicle type correspondence. A penalty parameter also The input determines the starting configuration of our prob-
has to be introduced for each violation of vehicle type lem, which is a schedule that contains feasible duties, and a
correspondence. set which contains the disrupted trips, that are not executed
currently by any vehicle. A configuration is supposed to be
• A binary parameter that allows the introduction of feasible, if its set of trips is empty, and all the duties in its
lateness. A penalty parameter also has to be intro- schedule are feasible and do not violate any regulations or
duced per 1 unit (minute) of lateness. parameters.
• A binary parameter that allows the movement of trips Once all the input is read, it is then transferred to the main
between feasible schedules. A penalty parameter is module of the system, which we call the Rescheduling Black
also needed that gives the cost of each such move. Box (RBB). This is the part that carries out the solution
process, and consists of two parts:
• An integer parameter that limits the maximum amount
of lateness which can introduced by the algorithms to
the schedule.
• An integer parameter that limits the maximum amount
of lateness an algorithm can introduce to a single event.
• An integer parameter that limits the maximum amount
of lateness an algorithm can introduce to one duty.
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 31
Koper, Slovenia, 10-11 October
