ON THE PROBLEM OF CONSTRUCTING ROUTES, PART I

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

ON THE PROBLEM OF CONSTRUCTING ROUTES,

PART I: PREFACE

Ilya B. Gertsbakh¹, Tao Liu², Avishai (Avi) Ceder³

¹Department of Mathematics, Ben-Gurion University of the Negev

Beer-Sheva 84105, Israel

E-mail: elyager@bezeqint.net

²Department of Civil and Environmental Engineering, The University of Auckland

Auckland 1142, New Zealand

E-mail: tliu773@aucklanduni.ac.nz

³IDEC, 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

Transport and Telecommunication Vol. 18, no. 3, 2017

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

Transport and Telecommunication Vol. 18, no. 3, 2017

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

1. 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.

2. Ceder, A. (2016) Public Transit Planning and Operation: Modelling, Practice and Behaviour, second ed. CRC Press, Boca Raton, USA.

3. 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.

4. Gertsbach (Gertsbakh), I., and Gurevich, Y. (1977) Constructing an optimal fleet for a transportation schedule. Transportation Science, 11(1), 20-36.
5. Gertsbakh, I., and Gurevich, Y. (1982) Homogeneous optimal fleet. Transportation Research Part B: Methodological, 16(6), 459-470.

6. Gertsbakh, I., and Stern, H.I. (1978) Minimal resources for fixed and variable job schedules.

Operations Research, 26(1), 68-85.

7. 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).
8. 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.

9. Salzborn, F.J.M. (1972) Optimum bus scheduling. Transportation Science, 6(2), 137-148.
10. 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.

Источник