Transport
and Telecommunication Vol.
18, no. 3, 2017
Transport
and Telecommunication, 2017, volume 18, no. 3, 231–233
Transport
and Telecommunication Institute, Lomonosova 1, Riga, LV-1019, Latvia
DOI
10.1515/ttj-2017-0020
HISTORICAL
COMMENTS ON APPLIED RESEARCH
Globalization in the modern world
creates unique opportunities for researchers in access to scientific
information in various applied fields. However, even today, many
national studies, which were performed at different times not in
English, remain inaccessible to the modern researchers. Meanwhile,
many of them have not only historical value, but still retain
scientific importance and are of scientific interest to the research
community.
In order to at least partially
eliminate this problem, the Editorial Board decided to open a special
section of the journal with the provisional title "Historical
Comments on Applied Research".
This
issue of the journal opens the above rubric with two articles:
Original paper “On the Problem
of Constructing Routes: Methodology and Numerical Example” by Linis
and Maksim. It marks 50-year to the deficit function model initially
developed in this 1967 work. This model then paved the way to further
research of vehicle-fleet management in terms of optimal routing and
scheduling.
Announcement
of this work by Ilya B. Gertsbakh, Tao Liu and Avishai (Avi) Ceder.
This
work is a preface to the above
mentioned article and explains the motivation of the authors to
prepare an article for publication in the journal.
The Editorial Board hopes that
the new rubric will be of interest to readers. The Editorial Board
will be glad to receive comments from the readers on this matter, as
well as possible proposals for the preparation of similar materials
from the national scientific heritage of different countries for
future issues of the journal.
Prof.
Igor Kabashkin, Editor-in-Chief
Prof.
Irina Yatskiv, Deputy/ Managing Editor
PART
I: PREFACE
Ilya
B. Gertsbakh1,
Tao Liu2,
Avishai (Avi) Ceder3
1Department
of Mathematics, Ben-Gurion University of the Negev
Beer-Sheva
84105, Israel
E-mail:
elyager@bezeqint.net
2Department
of Civil and Environmental Engineering, The University of Auckland
Auckland
1142, New Zealand
E-mail:
tliu773@aucklanduni.ac.nz
3IDEC,
Hiroshima University, Japan,
Faculty
of Civil and Environmental Engineering, Technion-Israel Institute of
Technology,
Haifa
32000, Israel
E-mail:
a.ceder@auckland.ac.nz
This
is a preface of the translation of the 1967 paper by Linis and
Maksim, “On the problem of constructing routes” (in Russian) (in
the Proceedings of the Institute of Civil Aviation Engineering, Issue
102, pp. 36-45). It marks 50-year to the deficit function (DF) model
initially developed in this 1967 work; the DF model then paved the
way to further research of vehicle-fleet management in terms of
optimal routing and scheduling. The merit of this translation is to
describe the roots of the DF modelling to enable further studies to
emerge with more contributions.
Keywords:
deficit
function, routing, scheduling, transportation
1. Introduction
In 1967, Vald K. Linis and Misha
S. Maksim published the paper “On the problem of constructing
routes” (in Russian) in the Proceedings of the Institute of Civil
Aviation Engineering Issue 102, pp. 36-45. This paper based, in
essence, on their research work conducted in the Central Scientific
Research
231
Unauthenticated
Download
Date | 7/1/17 11:03 AM
Institute of Civil Aviation
(Riga) combined with practical experience gained from the actual
scheduling activities conducted in Moscow. During the period of 1965
to 1974, the problem of constructing aircraft routes was dealt with
the project of designing Central Aviation Schedule for the Aeroflot
Company in the Central Scientific Research Institute of Civil
Aviation (Riga). The project was led scientifically by Professor Kh.
B. Kordonsky with its core group members of Vald K. Linis, Valery
Venevcev, Misha S. Maksim and Ilya B. Gertsbakh. The limitation of
computer’s power, in those days, made the routing and scheduling
problem of 2,000 daily trips of the central Aeroflot schedule as a
problem of formidable difficulty.
The seminal work of Linis and
Maksim (1967) has the following merits. First, it introduced the
concept of characteristic functions, later called deficit functions
(DFs) because of representing the deficit number of vehicles required
at a particular terminal in question in a multi-terminal
transportation system. Second, it presented the first proof of the
minimal fleet size theorem in the terms of maxima of the DF’s.
Third, it developed the idea of utilizing DFs for fleet size
minimization through shifting flight departure times. Fourth, it
proposed a heuristic algorithm for constructing aircraft routes.
Fifth, it proposed an algorithm for constructing the minimal complete
chain system (MCCS). Sixth, it described, in non-formal terms, a new
graph- theoretic construction of the so-called Linis graph (see
Gertsbakh and Gurevich, 1982), which allows to solve the so-called
Center Problem and develop further the research associated with the
crew scheduling activity. These ideas escribed in the paper of Linis
and Maksim (1967) were well ahead of their time and preserve their
importance and novelty even for today and for future further
research.
The DF concept and modelling
attracted the attention of the English-spoken community through the
work by Gertsbakh and Gurevich (1977), Gertsbakh and Stern (1978) and
Ceder and Stern (1981). Since then, there have been plenty of
developments in the understanding of the theoretical, methodological
and applied aspects of the DF advantages. That is, the DF concept and
modelling proffers a graphical person-computer interactive approach
and provides a highly informative graphical technique that is simple
to interact with and use. Practical suggestions can be interjected,
by the scheduler/planner followed immediately by describing the
effects of the suggestions on the vehicle’s schedule. Thus the
graphical DF concept helps in creating an efficient public transport
(PT) vehicle schedules, timetables, crew duties, networks of routes,
bus rapid transit systems, and operational parking spaces (Gertsbakh
and Gurevich, 1982; Ceder, 2016). For a detailed description of the
major developments of the DF modelling and applications in PT
planning and operations over the past 50 years, readers are referred
to Ceder (2016) and Liu and Ceder (2017).
The year 2017 marks the 50th
anniversary of the publication of Linis and Maksim 1967 paper. To
commemorate this historical event in transportation science and
stimulate further use of the DF concept as a bridge between the world
of researchers and the world of practitioners, we translated the
original Russian article into English with the title of ‘on the
problem of constructing routes, part II: methodology and numerical
example’; it follows this part. In this preface, we provide a
historical overview of the Linis-Maksim paper, add remarks, and
clarify some concepts and facts.
2. Remarks
and Commentary
Following the Russian publication
tradition in those days, the 1967 paper of Linis and Maksim has
neither an abstract nor references. It mainly comprised of seven
sections.
Section 1 of the paper provides a
description of the problem considered. This section starts by
introducing the background of the local civil aviation
schedule-design problem. It follows by two main questions: (1) what
is the minimal fleet size required for a given schedule, and (2) how
to construct the optimal routes for each aircraft.
Section 2 aims at answering the
first question of fleet size estimation and minimization. It starts
by introducing the basic notations with the employment of a 22-trip,
5-terminal example to explicate the notations. Then it provides the
definition of the step (or characteristic) function, i.e., the DF,
using graphical illustrations of the 22-trip, 5-terminal example. It
continues by the presentation of the well-known fleet size formula
describing the relationship between the fleet size and the total
deficits of all the terminals. Similar fleet size formulations were
independently derived by Bartlett (1957) and Salzborn (1972, 1974).
Sections
3 and 4 focuses on answering the second question of constructing
routes. Section 3 introduces the “balance” property of schedule
followed by the definition of the minimal complete chain system
(MCCS). The MCCS serves as the basis of constructing aircraft routes
and crew duties. Next, a simple algorithm for constructing MCCS is
described. The final part of Section 3 provides an extension of
232
Unauthenticated
Download
Date | 7/1/17 11:03 AM
the MCCS with some insights for
constructing balanced crew duties. Section 4 is another interesting
extension of the MCCS making each chain to visit a base airport
calling it a Centre Problem. An intuitive-based procedure, utilizing
the so-call “hollow zones” of the DFs, is provided to construct
closed chains to visit the base airports.
Section 5 provides an eight-step
algorithm for solving the problem of route construction with minimal
fleet size. The DF-based fleet size estimation and minimization
procedures are incorporated within this algorithm in its fifth step.
Fleet size reduction through shifting departure times appears in the
sixth step. The seventh step is about the feasibility check of the
MCCS, and in the last step, MCCSs are constructed according to an
optimization criterion.
Section 6 employs the 22-trip,
5-terminal example to illustrate (i) fleet size estimation procedure
using the DF tool; (ii) fleet size reduction procedure through
shifting flight departure times; and (iii) aircraft route
construction. The example has shown that the DF-based tool is simple
and easy to use graphically for fleet size estimation and
minimization, and for aircraft route construction.
The last section of the paper
notes that the DF-based methodology can be extended from one to many
airline companies simultaneously, which will maximize the
effectiveness and efficiency of the DF-based methodology.
3. Concluding
Remark
It is remarkable that the 50-year
ago paper by Linis and Maksim (1967) doesn’t only provide the
DF-based methodology for fleet size estimation and minimization, but
also provides a good algorithm for route construction based on the
MCCS of the DFs. In addition, it is fascinating that the construction
of the MCCS is directly related to the crew scheduling activity,
which is not addressed in their paper. Moreover, the construction of
a MCCS with each chain visiting a base airport using the “hollow
zones” of the DFs, is related to the depot-constrained vehicle
scheduling problem appearing years after. All in all, the merit of
this 1967 paper’s translation is to describe the roots of the DF
modelling so as to enable further studies to emerge with more
contributions.
Postscript
Misha S. Maksim passed away ten
years ago. Vald K. Linis is retired long time ago. The Central
Scientific Research Institute of Civil Aviation where Misha S. Maksim
and Vald K. Linis worked was founded around 1964 and does not exist
for almost 25 years.
References
- Bartlett, T.E. (1957) An algorithm for the minimum number of transport units to maintain a fixed schedule. Naval Research Logistics Quarterly, 4(2), 139-149.
- Ceder, A. (2016) Public Transit Planning and Operation: Modelling, Practice and Behaviour, second ed. CRC Press, Boca Raton, USA.
- Ceder, A., and Stern, H.I. (1981) Deficit function bus scheduling with deadheading trip insertions for fleet size reduction. Transportation Science, 15(4), 338-363.
- Gertsbach (Gertsbakh), I., and Gurevich, Y. (1977) Constructing an optimal fleet for a transportation schedule. Transportation Science, 11(1), 20-36.
- Gertsbakh, I., and Gurevich, Y. (1982) Homogeneous optimal fleet. Transportation Research Part B: Methodological, 16(6), 459-470.
- Gertsbakh, I., and Stern, H.I. (1978) Minimal resources for fixed and variable job schedules.
Operations
Research, 26(1),
68-85.
- Linis, V.K., and Maksim, M.S. (1967) On the problem of constructing routes. Proceedings of the Institute of Civil Aviation Engineering Issue 102, pp. 36-45 (in Russian).
- Liu, T., and Ceder, A. (2017) Deficit function related to public transport: 50 year retrospective, new
developments,
and prospects. Transportation
Research Part B: Methodological,
100, 1-19.
- Salzborn, F.J.M. (1972) Optimum bus scheduling. Transportation Science, 6(2), 137-148.
- Salzborn, F.J.M. (1974) Minimum fleet size models for transportation systems. In: D.J. Buckley (Ed.), Proceedings of the 6th International Symposium on Transportation & Traffic Theory (ISTTT6), Sydney, Australia, 607-624.
