Page 30 - 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. 30
ks (eg. parking, refueling) and driver specific tasks (eg. give a list of the most important rules in both groups. Note,
breaks, administration). that these are only the most common regulations. Other
ones might arise depending on a specific company or coun-
2.1 Disruption management try.
When a disruption happens, usually one of the vehicles in • Vehicle regulations
service becomes unavailable for a period of time. This leads – Vehicle depot and trip compatibility: As we men-
to the pre-planned schedule becoming infeasible, as one or tioned earlier, vehicles can be classified into de-
more of the tasks are not executed by a vehicle anymore. pots. Trips can only be serviced by a fixed set of
These trips are addressed from now on as disrupted trips. depots, and this should be respected when creat-
A vehicle schedule becomes infeasible if it contains such ing a new schedule to manage the disruption.
trips. Companies usually have a backup vehicle and driver – Vehicle type and trip characteristics: Similarly to
ready, which are dedicated to such situation, but this solu- depot compatibility, some trips can only be exe-
tion might not be the best one. cuted by vehicles of a certain type. For example,
trips that are carried out between different cities,
Moreover, most real-life cases have a so-called multiple depot or have a long distance, must have a bus with
problem. There are several different depot locations and/or special equipment (eg. air conditioning).
vehicle types, and every trip can only be serviced by vehicles
belonging to a set of pre-determined depots. Because of • Driver regulations
this fact, our problem is NP-hard in the case of 2 or more – Maximum driving time: Each driver has a maxi-
depots. The vehicle rescheduling problem can be reduced mum daily driving time, which they can not ex-
to the vehicle scheduling problem, which was proven to be ceed.
NP-hard by Bertossi et al. [1]. However, the problem itself – Driver breaks: After given time periods, drivers
should be solved as quickly as possible, and order should be have to be assigned breaks. Moreover, these breaks
restored with a new feasible solution. have to be assigned at specific geographical loca-
tions.
2.2 Related work – Maximum working time: Similarly to driving time,
the daily working time of drivers is also maxi-
To our knowledge, the literature regarding bus disruption mized. This does not equal driving time, as driver
management is scarce. Disruption management connected duties have other events as well, which do not re-
to different transportation fields has been researched for a quire a vehicle (eg. administration).
longer period of time.
Besides these regulations, some structural modifications should
The earliest papers regarding disruption management were also be considered in the schedule. For an illustrative exam-
published about the airline industry. An overview paper by ple, refer to Figure 1.
Clausen et al. can be read in [4, 3]. A bit younger field
is disruption management is railway transportation. Some Figure 1: An illustrative example
results regarding this area can be read in [7].
On the above figure, a disrupted daily schedule can be seen,
Both airline and railway disruption management differ from with a disruption represented by a vertical line. There is
bus disruption management in their underlying structure. one disrupted trip J0. Depending on some circumstances,
While buses are quite easy to move around with the help we can give several solutions for the problem. Here are a
of deadhead trips between different geographical locations, few examples:
the deadheading of airplanes is mainly prohibited by the
high arising cost, and railway deadheading is subject to the
underlying limited rail capacities.
As we have mentioned, the problem of bus rescheduling as
defined above was only considered by Li et al. In their pa-
pers, they studied the single depot BRP. They give a quasi-
assignment model and an auction algorithm for the prob-
lem in [9], and a network flow model is described in [10]
which is solved with the help of Lagrangian relaxation. In
[8], they also describe a possible decision-support system for
this problem, which is illustrated with the help of a small
real-world instance.
2.3 Real-life criteria
In a real-life application, there are several rules and con-
straints that make the problem more complicated. There
are regulations that cannot be violated, while the violation of
others should be penalized. As we mentioned earlier, we can
define daily schedules of both vehicles and drivers, thus we
classify our rules into two groups. In this subsection, we will
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 30
Koper, Slovenia, 10-11 October
breaks, administration). that these are only the most common regulations. Other
ones might arise depending on a specific company or coun-
2.1 Disruption management try.
When a disruption happens, usually one of the vehicles in • Vehicle regulations
service becomes unavailable for a period of time. This leads – Vehicle depot and trip compatibility: As we men-
to the pre-planned schedule becoming infeasible, as one or tioned earlier, vehicles can be classified into de-
more of the tasks are not executed by a vehicle anymore. pots. Trips can only be serviced by a fixed set of
These trips are addressed from now on as disrupted trips. depots, and this should be respected when creat-
A vehicle schedule becomes infeasible if it contains such ing a new schedule to manage the disruption.
trips. Companies usually have a backup vehicle and driver – Vehicle type and trip characteristics: Similarly to
ready, which are dedicated to such situation, but this solu- depot compatibility, some trips can only be exe-
tion might not be the best one. cuted by vehicles of a certain type. For example,
trips that are carried out between different cities,
Moreover, most real-life cases have a so-called multiple depot or have a long distance, must have a bus with
problem. There are several different depot locations and/or special equipment (eg. air conditioning).
vehicle types, and every trip can only be serviced by vehicles
belonging to a set of pre-determined depots. Because of • Driver regulations
this fact, our problem is NP-hard in the case of 2 or more – Maximum driving time: Each driver has a maxi-
depots. The vehicle rescheduling problem can be reduced mum daily driving time, which they can not ex-
to the vehicle scheduling problem, which was proven to be ceed.
NP-hard by Bertossi et al. [1]. However, the problem itself – Driver breaks: After given time periods, drivers
should be solved as quickly as possible, and order should be have to be assigned breaks. Moreover, these breaks
restored with a new feasible solution. have to be assigned at specific geographical loca-
tions.
2.2 Related work – Maximum working time: Similarly to driving time,
the daily working time of drivers is also maxi-
To our knowledge, the literature regarding bus disruption mized. This does not equal driving time, as driver
management is scarce. Disruption management connected duties have other events as well, which do not re-
to different transportation fields has been researched for a quire a vehicle (eg. administration).
longer period of time.
Besides these regulations, some structural modifications should
The earliest papers regarding disruption management were also be considered in the schedule. For an illustrative exam-
published about the airline industry. An overview paper by ple, refer to Figure 1.
Clausen et al. can be read in [4, 3]. A bit younger field
is disruption management is railway transportation. Some Figure 1: An illustrative example
results regarding this area can be read in [7].
On the above figure, a disrupted daily schedule can be seen,
Both airline and railway disruption management differ from with a disruption represented by a vertical line. There is
bus disruption management in their underlying structure. one disrupted trip J0. Depending on some circumstances,
While buses are quite easy to move around with the help we can give several solutions for the problem. Here are a
of deadhead trips between different geographical locations, few examples:
the deadheading of airplanes is mainly prohibited by the
high arising cost, and railway deadheading is subject to the
underlying limited rail capacities.
As we have mentioned, the problem of bus rescheduling as
defined above was only considered by Li et al. In their pa-
pers, they studied the single depot BRP. They give a quasi-
assignment model and an auction algorithm for the prob-
lem in [9], and a network flow model is described in [10]
which is solved with the help of Lagrangian relaxation. In
[8], they also describe a possible decision-support system for
this problem, which is illustrated with the help of a small
real-world instance.
2.3 Real-life criteria
In a real-life application, there are several rules and con-
straints that make the problem more complicated. There
are regulations that cannot be violated, while the violation of
others should be penalized. As we mentioned earlier, we can
define daily schedules of both vehicles and drivers, thus we
classify our rules into two groups. In this subsection, we will
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 30
Koper, Slovenia, 10-11 October
