Page 32 - 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. 32
• The Solver Library (SL) manages the different solution The second method is a local search heuristic (where a tabu
methods that are built into the system. The system list can also be applied effectively). This method creates
can have any number of implemented solution meth- a (probably infeasible) pseudo-schedule from the disrupted
ods, and the desired method can be invoked by pa- trips, without any regards to the regulations. In each it-
rameter setup. If there is a possibility to parallelize eration step of the search, either a move or a swap opera-
solution processes, multiple methods can also be exe- tion is executed. A trip is either moved from a schedule to
cuted at once. another, or is swapped with events from another schedule.
One important rule is that trips cannot be moved onto the
• The output of a solution method is sent to the Solu- pseudo-schedule. The local search finds a feasible solution,
tion Collector (SC). This sub-module is responsible for if the pseudo-schedule is empty.
managing feasible solutions. If more solution methods
are running in parallel, all of them send their results Test results of the framework in real life have been promis-
to the SC. The SC then filters any duplicate solutions, ing. All instances have a short running time (they all finish
and also gives an ordering of the remaining ones based under 1 minute even for bigger instances). It can also be
their cost. seen, that these methods will find multiple feasible solution
while exploring there solution space. Because of the SC in
Once all solution algorithms finish their execution, or the de- the system, the solutions can all be saved, and the ones that
sired maximum runtime is reached, the SC returns a number best suit the parameters of the operator can be chosen at
of feasible solutions. The desired number can be given by the end.
the operator as an input (number of suggestions), and their
order is determined mainly by their cost, but they can also Besides the real instances, we also tested our system on ran-
be filtered considering the different parameters (eg. ask for domly generated data. In Table 1 and Table 2, we present
ones with no lateness, if possible). The operator receives the results of the above methods. The tables give the in-
this data, and can use these to decide on how to solve the stance name, the number of original trips in the schedule,
arising problem. the number of the disrupted trips, and the running time
of the recursive and local search methods on seconds. All
4. A REAL LIFE APPLICATION instances in Table 1 are generated using the method in [5].
In this section, we briefly describe a real-life application of Table 1: Solution on random instances from [6].
the above system. As we mentioned earlier, solution for the
rescheduling problem has to be adequatly quick, as the order Instance Depots Trips Disrupted Rec. Loc.
in transportation has to be restored as soon as possible.
Because of this, the implemented heuristic methods must trips (s) (s)
have a running time of at most a couple of seconds to be
acceptable. random1 2 12 1 0.02 0.001
Also, because of the flexibility of the SC module, it is useful random2 4 100 1 0.05 0.004
to provide solution methods which find multiple feasible so-
lutions during their runtime. This gives the operator more random3 4 500 1 0.08 0.01
suggestion options to choose from. A simple approach that
we implemented in our system is a naive search, which ba- random4 4 800 1 0.08 0.05
sically finds all the possible trivial insertions in the starting
configuration (if any), and inserts them to the solution col- We also present two real-life test results from the city of
lector. If there is any trivial insertion, it is highly likely that Szeged, Hungary. The smaller instance is only for a district
it will be the cheapest solution with regards to any of the of the city on a workday, while the bigger instance is that of
parameters. a Saturday.
In one of our previous papers, we formulated a mathematical Table 2: Solution on real-life instances.
model for the bus rescheduling problem [6]. The size of the
problem is big, and it cannot be solved efficiently even for Instance Depots Trips Disrupted Rec. Loc.
smaller random instances. However, we also proposed two trips (s) (s)
solution heuristics in the same paper. These methods have szeged small 4 206 0.399 0.548
also been implemented to the system. szeged sat 4 1983 2 0.037 0.059
1
The first method is a recursive search, which uses the ini-
tial configuration as an input, and inserts a disrupted trip As it can be seen from the above tables, all test results have
into one of the schedules in each step. If the disrupted trip a good running time for both of our heuristics. The methods
cannot be inserted trivially, then other trips are moved from also returned several suggestions for the test cases.
the schedule to the disrupted set. To avoid exponential ex-
plosion, we gave a depth limit to the recursive calls, and 5. CONCLUSIONS AND FUTURE WORK
also have a function that cuts certain branches of the search
tree. The recursive search finds a feasible solution, if the The long-term plans of public transportation companies are
disrupted set is empty. disrupted on a daily basis. These disruptions have to be
addressed as soon as possible. In this paper, we introduced
a decision support framework for the rescheduling problem
in public bus transportation.
We analyzed both vehicle and driver regulations for the daily
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 32
Koper, Slovenia, 10-11 October
methods that are built into the system. The system list can also be applied effectively). This method creates
can have any number of implemented solution meth- a (probably infeasible) pseudo-schedule from the disrupted
ods, and the desired method can be invoked by pa- trips, without any regards to the regulations. In each it-
rameter setup. If there is a possibility to parallelize eration step of the search, either a move or a swap opera-
solution processes, multiple methods can also be exe- tion is executed. A trip is either moved from a schedule to
cuted at once. another, or is swapped with events from another schedule.
One important rule is that trips cannot be moved onto the
• The output of a solution method is sent to the Solu- pseudo-schedule. The local search finds a feasible solution,
tion Collector (SC). This sub-module is responsible for if the pseudo-schedule is empty.
managing feasible solutions. If more solution methods
are running in parallel, all of them send their results Test results of the framework in real life have been promis-
to the SC. The SC then filters any duplicate solutions, ing. All instances have a short running time (they all finish
and also gives an ordering of the remaining ones based under 1 minute even for bigger instances). It can also be
their cost. seen, that these methods will find multiple feasible solution
while exploring there solution space. Because of the SC in
Once all solution algorithms finish their execution, or the de- the system, the solutions can all be saved, and the ones that
sired maximum runtime is reached, the SC returns a number best suit the parameters of the operator can be chosen at
of feasible solutions. The desired number can be given by the end.
the operator as an input (number of suggestions), and their
order is determined mainly by their cost, but they can also Besides the real instances, we also tested our system on ran-
be filtered considering the different parameters (eg. ask for domly generated data. In Table 1 and Table 2, we present
ones with no lateness, if possible). The operator receives the results of the above methods. The tables give the in-
this data, and can use these to decide on how to solve the stance name, the number of original trips in the schedule,
arising problem. the number of the disrupted trips, and the running time
of the recursive and local search methods on seconds. All
4. A REAL LIFE APPLICATION instances in Table 1 are generated using the method in [5].
In this section, we briefly describe a real-life application of Table 1: Solution on random instances from [6].
the above system. As we mentioned earlier, solution for the
rescheduling problem has to be adequatly quick, as the order Instance Depots Trips Disrupted Rec. Loc.
in transportation has to be restored as soon as possible.
Because of this, the implemented heuristic methods must trips (s) (s)
have a running time of at most a couple of seconds to be
acceptable. random1 2 12 1 0.02 0.001
Also, because of the flexibility of the SC module, it is useful random2 4 100 1 0.05 0.004
to provide solution methods which find multiple feasible so-
lutions during their runtime. This gives the operator more random3 4 500 1 0.08 0.01
suggestion options to choose from. A simple approach that
we implemented in our system is a naive search, which ba- random4 4 800 1 0.08 0.05
sically finds all the possible trivial insertions in the starting
configuration (if any), and inserts them to the solution col- We also present two real-life test results from the city of
lector. If there is any trivial insertion, it is highly likely that Szeged, Hungary. The smaller instance is only for a district
it will be the cheapest solution with regards to any of the of the city on a workday, while the bigger instance is that of
parameters. a Saturday.
In one of our previous papers, we formulated a mathematical Table 2: Solution on real-life instances.
model for the bus rescheduling problem [6]. The size of the
problem is big, and it cannot be solved efficiently even for Instance Depots Trips Disrupted Rec. Loc.
smaller random instances. However, we also proposed two trips (s) (s)
solution heuristics in the same paper. These methods have szeged small 4 206 0.399 0.548
also been implemented to the system. szeged sat 4 1983 2 0.037 0.059
1
The first method is a recursive search, which uses the ini-
tial configuration as an input, and inserts a disrupted trip As it can be seen from the above tables, all test results have
into one of the schedules in each step. If the disrupted trip a good running time for both of our heuristics. The methods
cannot be inserted trivially, then other trips are moved from also returned several suggestions for the test cases.
the schedule to the disrupted set. To avoid exponential ex-
plosion, we gave a depth limit to the recursive calls, and 5. CONCLUSIONS AND FUTURE WORK
also have a function that cuts certain branches of the search
tree. The recursive search finds a feasible solution, if the The long-term plans of public transportation companies are
disrupted set is empty. disrupted on a daily basis. These disruptions have to be
addressed as soon as possible. In this paper, we introduced
a decision support framework for the rescheduling problem
in public bus transportation.
We analyzed both vehicle and driver regulations for the daily
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 32
Koper, Slovenia, 10-11 October
