Page 29 - 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. 29
Algorithmic Framework for Real-Time Rescheduling in
Public Bus Transportation
Balázs Dávid ∗
University of Szeged János Balogh
davidb@jgypk.u-szeged.hu University of Szeged
balogh@jgypk.u-szeged.hu
ABSTRACT complicated disruptions, but this solution is usually really
expensive. Operators might not be able to solve compli-
In this paper, we describe an algorithmic framework for the cated disruptions in short time, but a decision support sys-
vehicle rescheduling problem. This framework is based on tem could provide them with helpful suggestions in such a
problems arising in the operative planning of real-world pub- case.
lic transportation companies.
The goal of our paper is to introduce a solution framework
Categories and Subject Descriptors for the rescheduling problem in public transportation, which
could be used in aiding company operators responsible for
H.4 [[]: Information systems applications]; H.4.2 [[]: Types managing disruptions. An important requirement for this
of Systems]: Decision support (e.g., MIS), Logistics framework is to guide the solution process regardless of the
applied solution method. As the problem has to be solved
General Terms in almost real time, one of the main requirements for such
a system is to provide suggestions quickly. Optimization
Vehicle scheduling, Disruption management, Public trans- systems are already present for long-term planning [2, 11,
port 12], but these are all built around given solution methods.
However, the only paper to our knowledge that deals with a
1. INTRODUCTION system for bus rescheduling is the one by Li et al. [8].
Based on the available transportation data, the vehicle- and Although there are published mathematical models for the
driver schedules of a transportation company are created in problem [6, 10], these cannot be solved in short enough time.
advance. A unique schedule is created for each day (or day- This leads to the design of efficient heuristic methods [6, 9],
type) of the planning period in such a process. A daily sched- which are able to provide quick solutions. The system we
ule of a company is made up of vehicle and driver duties. A present in this paper is designed to work with any kind of
duty is considered as a series of tasks, which the correspond- solution method, and gives results for the problem based on
ing vehicle and driver has to complete in the given order. needs of the operators, which they can control through dif-
The most important tasks of these duties are the timetabled ferent parameters. The heuristic methods we use to demon-
trips, which come from the timetable of the company and strate the system were published in [6].
have to be executed.
The outline of our paper is the following: first, we give a
However, there are several difficulties that can arise while quick overview of the rescheduling problem and disruption
executing such a schedule in real-life: a problem with the management. We present the basic regulations, and give
vehicle itself, sickness of the driver, or other such things can a list of these that can be regarded in a flexible manner
make the pre-planned schedule infeasible. These unforeseen through parameters and penalizing. Based on these design
difficulties are called disruptions. If a disruption arises, a thoughts, we introduce the suggested framework itself. Fi-
new feasible schedule has to be created, usually by resche- nally, we give some ideas of solution methods that we pro-
duling the old one. pose for the framework.
Disruptions have to be managed almost immediately, which 2. TRANSPORTATION SCHEDULING AND
is usually the task of a company operator. Companies usu- DISRUPTION MANAGEMENT
ally have a backup vehicle with which they address more
∗supervisor The daily schedule of a transportation company consists of
several duties. Every duty is executed by a driver, and also
has a corresponding vehicle. Each duty is a series of tasks
that have to be carried out in the given order. The most
common tasks are the ones corresponding to the trips of the
timetable, and the so-called deadhead trips, which are re-
sponsible for moving the empty vehicle from one location to
another. There can also be several different vehicle specific
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 29
Koper, Slovenia, 10-11 October
Public Bus Transportation
Balázs Dávid ∗
University of Szeged János Balogh
davidb@jgypk.u-szeged.hu University of Szeged
balogh@jgypk.u-szeged.hu
ABSTRACT complicated disruptions, but this solution is usually really
expensive. Operators might not be able to solve compli-
In this paper, we describe an algorithmic framework for the cated disruptions in short time, but a decision support sys-
vehicle rescheduling problem. This framework is based on tem could provide them with helpful suggestions in such a
problems arising in the operative planning of real-world pub- case.
lic transportation companies.
The goal of our paper is to introduce a solution framework
Categories and Subject Descriptors for the rescheduling problem in public transportation, which
could be used in aiding company operators responsible for
H.4 [[]: Information systems applications]; H.4.2 [[]: Types managing disruptions. An important requirement for this
of Systems]: Decision support (e.g., MIS), Logistics framework is to guide the solution process regardless of the
applied solution method. As the problem has to be solved
General Terms in almost real time, one of the main requirements for such
a system is to provide suggestions quickly. Optimization
Vehicle scheduling, Disruption management, Public trans- systems are already present for long-term planning [2, 11,
port 12], but these are all built around given solution methods.
However, the only paper to our knowledge that deals with a
1. INTRODUCTION system for bus rescheduling is the one by Li et al. [8].
Based on the available transportation data, the vehicle- and Although there are published mathematical models for the
driver schedules of a transportation company are created in problem [6, 10], these cannot be solved in short enough time.
advance. A unique schedule is created for each day (or day- This leads to the design of efficient heuristic methods [6, 9],
type) of the planning period in such a process. A daily sched- which are able to provide quick solutions. The system we
ule of a company is made up of vehicle and driver duties. A present in this paper is designed to work with any kind of
duty is considered as a series of tasks, which the correspond- solution method, and gives results for the problem based on
ing vehicle and driver has to complete in the given order. needs of the operators, which they can control through dif-
The most important tasks of these duties are the timetabled ferent parameters. The heuristic methods we use to demon-
trips, which come from the timetable of the company and strate the system were published in [6].
have to be executed.
The outline of our paper is the following: first, we give a
However, there are several difficulties that can arise while quick overview of the rescheduling problem and disruption
executing such a schedule in real-life: a problem with the management. We present the basic regulations, and give
vehicle itself, sickness of the driver, or other such things can a list of these that can be regarded in a flexible manner
make the pre-planned schedule infeasible. These unforeseen through parameters and penalizing. Based on these design
difficulties are called disruptions. If a disruption arises, a thoughts, we introduce the suggested framework itself. Fi-
new feasible schedule has to be created, usually by resche- nally, we give some ideas of solution methods that we pro-
duling the old one. pose for the framework.
Disruptions have to be managed almost immediately, which 2. TRANSPORTATION SCHEDULING AND
is usually the task of a company operator. Companies usu- DISRUPTION MANAGEMENT
ally have a backup vehicle with which they address more
∗supervisor The daily schedule of a transportation company consists of
several duties. Every duty is executed by a driver, and also
has a corresponding vehicle. Each duty is a series of tasks
that have to be carried out in the given order. The most
common tasks are the ones corresponding to the trips of the
timetable, and the so-called deadhead trips, which are re-
sponsible for moving the empty vehicle from one location to
another. There can also be several different vehicle specific
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 29
Koper, Slovenia, 10-11 October
