Deepti Abhay Panwalkar
Birla Institue of Technology and Science
Pilani, Rajasthan
[email protected]
Introduction
Indian Railways is the largest rail network in Asia and the world’s second largest under a single management. Spreading over the country’s vast geographical area, Indian Railways is a multi-gauge, multi-traction system covering over 1 lakh track kilometres. It runs some 11,000 trains everyday, including 7,000 passenger trains. The passenger traffic has increased from 1.28 to 4.2 billion in last 40 years, making Indian Railways (IR) a leading passenger carrying railway in the world. This has placed a difficult task on the passenger to choose the best route for his journey from many alternatives.
There are online query systems only for listing the trains for a journey through stations specified by the passengers. However there is a need for software that optimises the route. That is, choosing from many possible trains, the one that is best either in terms of 1) distance, 2) cost or 3) time. The optimisation based on distance may not at once seem useful, however it is important indirectly in that distance traversed in a journey determines it’s cost.
The work presented in this paper is a graphical user interface, which uses modified Djikstra’s algorithm for optimisation of a journey that the user wishes to pursue.
Fig 1: Sample network for finding least cost path
Methodology
The graphical user interface system is developed using Java. It accepts two inputs from the user, the stations of the journey and the criterion for optimisation namely Time, Distance or Cost. The program displays the optimal route in the form of straight lines between connecting stations. The trains that form this route are also listed.
The algorithm used for finding the optimal route requires a network of stations with some information about stations and their paths, from which it processes the optimal route. For the purpose of explanation, the network of IR can be considered as a graph and the stations as nodes. The paths between the adjacent stations are arcs (note: if a train passes through two stations without a stop at another in between, the two stations may be said to be adjacent), and the distance, the cost of journey and the duration of journey between adjacent stations can be commonly said to be the cost of the arcs. Thus the stations, paths and their cost together form a graph. The data used for forming the network and extracting information is stored in files, in a particular and convenient format. This database is directly obtained from the Railways Timetable book.
When the system gets the required details from the user, its first job is to find the network with which to work. Indian Railways is a large network and it is not advisable and even necessary to pass it directly to the algorithm — it has to be condensed. Only those trains are first chosen that pass through the start station and destination specified by the user. If the user wishes to have a break in journey, then those trains are chosen which have either the start station or destination in their path. That is, not all selected trains travel through both start station and destination. The journey can begin with one train, and end with another with a change of trains in an intermediate station, which is decided by the code. Next the information (e.g. names of stations, the distances between them etc.) is extracted for these trains. The intermediate stations of these trains and the costs (distances, duration or cost) between them, form the required network or graph.
Djikstra’s algorithm for finding the shortest path works well only for a connected graph. A connected graph is one in which there always exists an arc between any two nodes. The methodology of its working is based on finding the shortest path between two adjacent nodes at each step. From a ‘current’ node, that node is next chosen, which can be traversed with least cost (from current node) than any other node. This chosen node is then made ‘current node’ for the next iteration. This implies that the least cost path contains the arcs that have least cost in each step. In a graph that is not connected, the least cost path may not have least cost in every stage but the total cost will be least. The network in the present situation is mostly not connected. So there might arise a case where a path of least cost may not be chosen at all because the cost of one of its arcs was not least, in that stage. Hence Djikstra’s algorithm had to be modified.
In modified form the least cost path to every node is determined. One node is considered at a time and the best way to reach this node is determined. This can be easily understood by considering the example shown in Fig. 1. It is desired to find the least cost path from node 1 to node 9. To achieve this, the algorithm considers one node at a time and finds the cost of best path from node 1 till that node. The least cost till every node is shown in square beside the node, in Fig.1. The least cost till node 2 is directly the cost of the arc from 1 to 2. Similarly for node 3 it is 2. For node 4 it is the sum of cost of arcs (1,2) and (2,4). However to reach node 5 there are two possible paths, one from node 2 and the other from node 3. In such a case that node is chosen which when included gives a least cost path. Hence node 2 is chosen which gives the cost as 6, as compared with node 3, which gives 9. This process is continued till the last node is reached. The least cost to reach node 9 comes out to be 9. It can be seen that when a particular node is under consideration, all possible paths to reach that node are examined. Thus the choice of nodes for the best path to the last node is left open till that node is reached. In doing so all paths from the initial to the last node are considered in an exhaustive and systematic manner. This method is similar to the recursion algorithms of optimisation.
To find the optimal path the only requirement is network along with the costs. If the optimality is based on time considerations, then only a slight change is required in adding and comparing two ‘time’ quantities. Otherwise the algorithm remains the same. Other constraints can also be easily included. For example if there is a break in journey, it will be necessary to check if the two trains are scheduled for the same day, and also whether they can be boarded without a long wait. These constraints have been incorporated in the program. This feature is very useful, particularly for Indian Railways, which is very large and complex. Also since the algorithm processes a condensed network chosen from a larger one, it should work efficiently.
Conclusions
The software is designed and developed to find optimal route for a journey. Considering the present database, which has been constructed for a few tables of the timetable book, correct results were obtained for a combination of cases. The system should display correct results for all types of journeys provided the database is complete.
Acknowledgements
I would like thank Prof. M. K.. Rohil, BITS Pilani, for his invaluable guidance throughout the work. My thanks are also due to my institute, BITS Pilani for providing the facilities during my work.
Reference
- Langsam, Augenstein & Tenenbaun, 2001, Data structures using C and C++ , New Delhi: Prentice Hall of India Pvt. Ltd.
- Schildt Herbert, 2001, The complete reference JavaTM, New Delhi: Tata McGraw-Hill
- Eckstein Robert, Marc Loy & Dave Wood, 2000, JavaTM Swing, Calcutta: Shroff Publishers & Distributers Pvt. Ltd.
- Liang Y. D., 1998, An Introduction to Java Programming, New Delhi: Prentice Hall of India Pvt. Ltd.
