Fall 2022 Course Project: World Airline Route Search
Due date and grade:
- Due date: Dec. 9, 2022 ( No late submissions are accepted! )
- Full points: 100 (report: 40 points, code: 60 points)
Introduction:
In this project, you will be designing and implementing algorithms to store and search graphs. World Airline (WA) flies to many destinations worldwide including: Moscow, Seoul, Tokyo, Hong Kong, and London. Complete detailed information regarding airline flight routes can be found from the link flight.txt . The flight.txt contains a “from city” and its destination cities that WA flights to. Note that the flight.txt is a synthetically generated datasets by a graph data generator available from the link graphGen . You may want to download the graph generator and generate a few more graphs with different number of cities to test your algorithms.
Your task is to design and implement algorithms to answer the following questions:
- I am in city “A”, can I fly to city “B” with less than x connections? Give me the route with the smallest number of connections or tell me there is no such a route.
- Give me the route with the smallest number of connections from city “A” to city “D” through city “B” and “C”. (the order of “B” and “C” is not important). Or tell me there is no such a route.
- I am in city “A”, my friend John is in a different city “B”, and my other friend Ann is in yet another different city “C”. We want to find a city different from the three cities we are in to meet so that the total number of connections among three of us is minimized. Tell me the city we should fly to and the routes for us or tell me there is no such a city.
- routeSearch 1 <city_A> <city_B> <num_connection> sample output: city_A to city_x to city_y … to city_B total connection: 4
- usage: routeSearch 2 <city_A> through <city_B> and <city_C> to <city_D> sample output: city_A to city_x to city_C to city_y … to city_B to city_D smallest number of connection: 4
- usage: routeSearch 3 <city_A> <city_B> <city_C> sample output: You three should meet at city_D Route for first person: city_A to city_x … to city_D (3 connections) Route for second person: city_B to city_y … to city_D (1 connections) Route for second person: city_C to city_y … to city_D (0 connections) Total number of connection: 4
What to turn in:
There are two main parts in this project, all of them contributing to the final project grade.
- You will have to write a project report (about 3-5 typed pages – single space – 12pt font) that includes:
- design issues, what are the problems and how you solve them
- data structures you use, the decision behind selecting them
- algorithms you employ, again with a justification of your decision
- particular emphasis should be placed on the running time of your algorithm, please show the asymptotic costs for each of your algorithm
- optimization issues: what could you do to further optimize your algorithm
- you need to specifically address the problem of scalability: would you implementation be efficient in the case of very large species collections for larger scale geographic area?
- any other remarks about your design and implementation
- You will have to send in a fully working program, written in C/C++. We will test your algorithms extensively by generating graphs with different characteristics. It is mandatory that you include a README file, as detailed as possible, including compilation and running instructions. Is it also mandatory that your programs are fully documented, that is they should include detailed comments on what is included in each file and what each method does.
No late submissions are accepted!.
Locomotive Assignment Graph Model for Freight Traffic on Linear Section of Railway. The Problem of Finding a Maximal Independent Schedule Coverage
- Control Sciences
- Published: 16 May 2019
- Volume 80 , pages 946–963, ( 2019 )
Cite this article
- L. Yu. Zhilyakova 1 ,
- N. A. Kuznetsov 2 ,
- V. G. Matiukhin 3 ,
- A. B. Shabunin 3 &
- A. K. Takmazian 4
45 Accesses
Explore all metrics
The paper is devoted to the formal statement and solution of a problem arising when assigning the locomotives for freight transportation realization in accordance with preset schedule. The goal is to determine whether the number of locomotives is sufficient at a specified initial allocation of them to perform all transport operations. The solution is presented in the form of an algorithm that builds the coverage of the schedule: the complete one, if it exists, or else the partial one being the maximal independent. The theorem is proved on one-to-one correspondence between the existence of the complete coverage and the sufficiency of the number of locomotives.
This is a preview of subscription content, log in via an institution to check access.
Access this article
Subscribe and save.
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Price excludes VAT (USA) Tax calculation will be finalised during checkout.
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Similar content being viewed by others
Graph Methods for Solving the Unconstrained and Constrained Optimal Assignment Problem for Locomotives on a Single-Line Railway Section
Research on the Optimization for the Utilization of Passenger Train Stock of Existing Railway
Mathematical model applied to single-track line scheduling problem in brazilian railways.
Shabunin, A.B., Chekhov, A.V., Sazurov, S.V., et.al., Development of a Network-Centric Approach to the Creation of an Integration Platform and an Intelligent Resource Management System for Cargo Sorting Stations in Real Time, Proc. 3rd Russ. Conf. with Int. Particip. “Technical and Software Means for Control and Measurement” , Moscow: Inst. Probl. Upravlen., 2012, pp. 1560–1572.
Google Scholar
Shabunin, A.B., Markov, S.N., Dmitriev, D.V., et al., Integration Platform Implementation as Network-Centric Approach for Distributed Intelligent Resource Management JSC “RZD” Systems, Progr. Inzheneriya , 2012, no. 9, pp. 23–28.
Lazarev, A.A., Musatova, E.G., and Taracov, I.A., Two-Directional Traffic Scheduling Problem Solution for a Single-Track Railway with Siding, Autom. Remote Control , 2016, vol. 77, no. 11, pp. 2118–2131.
Article MathSciNet MATH Google Scholar
Gafarov, E., Dolgui, A., and Lazarev, A., Two-Station Single-Track Railway Scheduling Problem with Trains of Equal Speed, Comput. Indust. Eng. , 2015, vol. 85, pp. 260–267.
Article Google Scholar
Lazarev, A.A. and Musatova, E.G., Integer-Valued Problem Settings for Constructing Railroad Trains and Their Schedules, Upravlen. Bol’shimi Sist. , 2012, no. 38, pp. 161–169.
Piu, F. and Speranza, M.G., The Locomotive Assignment Problem: A Survey on Optimization Models, Int. Trans. Oper. Res. , 2014, vol. 21, pp. 327–352.
Ahuja, R.K., Liu, J., Orlin, J.B., et al., Solving Real-Life Locomotive Scheduling Problems, Transport. Sci. , 2005, vol. 39, no. 4, pp. 503–517.
Jaumard, B. and Tian, H., Multi-Column Generation Model for the Locomotive Assignment Problem, Proc. 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’16) , 2016, pp. 6:1–6:13.
Kasalica, S., Mandić, D., and Vukadinović, V., Locomotive Assignment Optimization Including Train Delays, Promet—Traffic&Transportation , 2013, vol. 25, no. 5, pp. 421–429.
Takmaz’yan, A.K. and Sheludyakov, A.V., A Multiagent Solution with the Method of Auctions for a Multiproduct Transportation Problem with United Needs, ISUZhT , 2015, no. 1, pp. 110–112.
Kuznetsov, N.A., Pashchenko, F.F., Ryabykh, N.G., Zakharova, E.M., and Minashina, I.K., Optimization Algorithms in Planning Problem on Rail Transport, Inform. Prots. , 2014, vol. 14, no. 4, pp. 307–318.
Azanov, V.M., Buyanov, M.V., Gainanov, D.N., and Ivanov, S.V., Algorithms and Software for Locomotive Assignment Intended to Transport Freight Trains, Vestn. YuUrGU, Ser. Mat. Modelir. Programmir. , 2016, vol. 9, no. 4, pp. 73–85.
Gainanov, D.N., Kibzun, A.I., and Rasskazova, V.A., Vertex Cover Algorithm for a Directed Graph with a Set of Directed Paths in the Optimal Assignment and Locomotive Moving Problem, Vestn. Komp. Informats. Tekhn. , 2017, no. 5, pp. 51–56.
Matyukhin, V.G., Shabunin, A.B., Kuznetsov, N.A., and Takmazian, A.K., Rail Transport Control by Combinatorial Optimization Approach, 11th Int. Conf. on Application of Information and Communication Technologies , 2017, vol. 1, pp. 419–422.
Matyukhin, V.G., Kuznetsov, N.A., Shabunin, A.B., Zhilyakova, L.Yu., and Takmaz’yan, A.K., Graph Dynamical Model for the Problem of Assigning Tractional Resources for Freight Railroad Transportation, Proc. ISUZhT-2017 , Moscow: AO “NIIAS”, 2017, pp. 14–18.
Mascis, A. and Pacciarelli, D., Job-shop Scheduling with Blocking and No-Wait Constraints, Eur. J. Operat. Res. , 2005, vol. 143, no. 3, pp. 498–517.
Erusalimskii, Ya.M., Flows in Networks with Nonstandard Reachability, Izv. Vyssh. Uchebn. Zaved., Severo-Kavkaz. Region, Estestv. Nauki , 2012, no. 1, pp. 5–7.
Erusalimskii, Ya.M., Skorokhodov, V.A., Kuz’minova, M.V., and Petrosyan, A.G., Grafy s nestandartnoi dostizhimost’yu: zadachi, prilozheniya (Graphs with Nonstandard Reachability: Problems and Applications), Rostov-on-Don: Yuzhn. Federal. Univ., 2009.
Lovász, L. and Plummer, M.D., Matching Theory , Budapest: Akademiai Kiado, 1986. Translated under the title Prikladnye zadachi teorii grafov. Teoriya parosochetanii v matematike, fizike , khimii, Moscow: Mir, 1998.
MATH Google Scholar
Sedgewick, R., Algorithms in C++ , vol 5: Graph Algorithms , Reading: Addison-Wesley, 2002.
Lovász, L. and Plummer, M.D., Matching Theory , Amsterdam: North-Holland, 1986.
Ahuja, R.K., Magnati, T.L., and Orlin, J.B., Network Flows: Theory, Algorithms and Applications Jersey: Prentice Hall, 1993.
Bollobas, B. and Riordan, O., Percolation , Cambridge: Cambridge Univ. Press, 2009, 2nd ed.
Tarasevich, Yu.Yu., Perkolyatsiya: teoriya, prilozheniya, algoritmy (Percolation: Theory, Application, Algorithms), Moscow: Librokom, 2002, 2nd ed.
Kuznetsov, O.P., Complex Networks and Activity Spreading, Autom. Remote Control , 2015, vol. 76, no. 12, pp. 2091–2109.
Radicchi, F., Percolation in Real Interdependent Networks, Nature Phys. , 2015, vol. 11, pp. 597–602.
Download references
Author information
Authors and affiliations.
Trapeznikov Institute of Control Sciences, Russian Academy of Sciences, Moscow, Russia
L. Yu. Zhilyakova
Kotel’nikov Institute of Radio Engineering and Electronics, Russian Academy of Sciences, Moscow, Russia
N. A. Kuznetsov
Research and Design Institute for Information Technology, Signalling and Telecommunications in Railway Transportation, Moscow, Russia
V. G. Matiukhin & A. B. Shabunin
JSC “ProgramPark,”, Moscow, Russia
A. K. Takmazian
You can also search for this author in PubMed Google Scholar
Corresponding authors
Correspondence to L. Yu. Zhilyakova , N. A. Kuznetsov , V. G. Matiukhin , A. B. Shabunin or A. K. Takmazian .
Additional information
Russian Text © The Author(s), 2018, published in Problemy Upravleniya, 2018, No. 3, pp. 65–75.
Rights and permissions
Reprints and permissions
About this article
Zhilyakova, L.Y., Kuznetsov, N.A., Matiukhin, V.G. et al. Locomotive Assignment Graph Model for Freight Traffic on Linear Section of Railway. The Problem of Finding a Maximal Independent Schedule Coverage. Autom Remote Control 80 , 946–963 (2019). https://doi.org/10.1134/S0005117919050126
Download citation
Received : 20 December 2017
Revised : 20 December 2017
Accepted : 08 November 2018
Published : 16 May 2019
Issue Date : May 2019
DOI : https://doi.org/10.1134/S0005117919050126
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- graph model
- network flows
- locomotive assignment
- freight rail transportation
- Find a journal
- Publish with us
- Track your research
IMAGES
VIDEO
COMMENTS
The auction algorithm is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in the ory and in practice and is also naturally well suited for parallel. computation. I derive the algorithm from first principles, ex.
⇒Partial 𝜖-optimal assignment •Auction algorithm consists of two phases Bidding phase: o Each unassigned person computes the "current value" of object (i.e., potential profit if is assigned to ) & bids for the object of his choice Assignment phase: o Each object (temporarily) offers itself to the highest bidder
Auction Algorithms. The auction algorithm is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in theory and in practice, and is also naturally well suited for parallel computation. In this article, we will sketch the basic principles of the ...
The term "auction algorithm" [1] applies to several variations of a combinatorial optimization algorithm which solves assignment problems, and network optimization problems with linear and convex/nonlinear cost.An auction algorithm has been used in a business setting to determine the best prices on a set of products offered to multiple buyers. It is an iterative procedure, so the name "auction ...
the auction algorithm for the assignment problem. This is an intuitive method that operates like a real auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from
September 1989. LIDS - P - 1908. NTAND OTHER NETWORK FLOW PROBLEMS'byDimitri P. Bertsekas2AbstractThis is a tutorial presentation of the auction algori. hm, an intuitive method for solving the classical assignment problem. The algorithm outperforms substantially its main competitors for important types of problems, both in theory and in.
The auction algorithm is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in theory and in practice, and is also naturally well suited for parallel computation. The algorithm represents a significant departure from the cost improvement idea ...
ods. The starting point is an intuitive algorithm for the assignment prob-lem, the auction algorithm, introduced by the author in the 1979 paper [Ber79] and studied together with its variations since then, including in the book [Ber98]. We will adapt this algorithm to solve other network optimization problems in new ways.
The Auction Algorithm for Assignment and Other Network Flow Problems. entand Other Network Flow ProblemsbyDimitri P. BertsekasAbstractThe auction algorithm. is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in theory and in p.
The naive auction algorithm proceeds in iterations and generates a sequence of price vectors and assignments. At the beginning of each iteration, the CS condition. aiji - Pji = j~A~l {aij - Pj} (2) is satisfied for all pairs (i, ji) of the assignment. If all persons are assigned, the algorithm terminates.
The conservative auction algorithm, which is a limiting form of the aggressive auction algorithm, was also discussed in these papers, and in fact it was suggested as an effective initialization of some of the cooperative algorithms of the paper [52], despite the fact that in general it does not guarantee convergence to an optimal assignment.2
Sec. 2.1 The Auction Algorithm for the Symmetric Assignment Problem 3 2.1.1 The Main Auction Algorithm We recall the auction algorithm, described in Section 1.4.1. It was moti-vated by the simpler but awed naive auction algorithm. A key notion, which made possible the correct operation of the algorithm was the -
Auction Algorithms for Network Flow Problems: A Tutorial Introductionl by Dimitri P. I3ertsekas 2 Abstract The auction algorithm is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in theory and in practice, and is also naturally well suited ...
[10]. The corresponding method, called the auction algorithm, is the subject of the present paper. Among the many methods for the assignment problem [11] - [25], the auction algorithm seems to be the only one that has a naturally parallel character and is well suited for implementation on a massively parallel machine.
October 2023. Arizona State University/SCAI Report. ignment Problem and Extensions ybyDimitri Bertsekas zAbstractWe consider the classical linear assignment problem, and we introduc. new auction algorithms for its optimal and suboptimal solution. The algorithms are founded on duality theory, and are related to ideas of competitive bidding by ...
Therefore another algorithm was discovered and the algorithm is solving the assignment problem using auctions. Solving an assignment problem using auctions was proposed by D. Bertsekas2 in 1989 and later in 1992 it has been modiï¬ ed by Bertsekas and Castanon3.
The auction algorithm is an intuitive method for solving the classical assignment problem. It outperforms substantially its main competitors for important types of problems, both in the ory and in practice and is also naturally well suited for parallel. computation. I derive the algorithm from first principles, ex.
CS 200 Algorithms and Data Structures, Spring 2013 Programming Assignment #5 1 Finding the Shortest Route using Dijkstra's Algorithm Due May. 7 noon Objectives In this assignment, you will implement the classic Dijkstra's shortest path algorithm to find the shortest path between two cities for an airline company. Background: Dijkstra's ...
Auction Algorithms for Assignment, Path Planning, and Network Transport by Dimitri P. Bertsekas, 2023, ISBN 978-1-886529-48-9 1. Lessons from AlphaZero for Optimal, Model Predictive, and Adap-tive Control by Dimitri P. Bertsekas, 2022, ISBN 978-1-886529-17-5, 245 pages 2. Abstract Dynamic Programming, 3rd Edition, by Dimitri P. Bert-
CSCE 3110 - Data Structures and Algorithms. Due date and grade: Due date: Dec. 9, 2022 ( No late submissions are accepted!) Introduction: In this project, you will be designing and implementing algorithms to store and search graphs. World Airline (WA) flies to many destinations worldwide including: Moscow, Seoul, Tokyo, Hong Kong, and London.
auction algorithm for the assignment problem. This is an intuitive method that operates like a real auction where persons compete for objects by raising their prices through competitive bidding; the prices can be viewed as dual variables. Conceptually, auction algorithms represent a significant departure from the cost
The naive auction algorithm proceeds in "rounds" (or "iterations") starting with any assignment and any set of prices. There is an assignment and a set of prices at the beginning of each round, and if all persons are happy with these, the process terminates. Otherwise some person who is not happy is selected.
The paper is devoted to the formal statement and solution of a problem arising when assigning the locomotives for freight transportation realization in accordance with preset schedule. The goal is to determine whether the number of locomotives is sufficient at a specified initial allocation of them to perform all transport operations. The solution is presented in the form of an algorithm that ...