Best Route Finding Based on Cost in Multimodal Network With Care of...

Best Route Finding Based on Cost in Multimodal Network With Care of Networks Constraints

SHARE

Azadeh Keshtiarast
M.Sc. Student,
Department of Survey Engineering
K,N, Toosi university of Technology
[email protected]

Ali A. Alesheikh
Assistant Professor,
Faculty of Geodesy and Geomatics Eng.,
K,N, Toosi university of Technology
[email protected]

Ahad Kheirabadi
M.Sc. Student,
Faculty of Geodesy and Geomatics Eng.,
K,N, Toosi university of Technology
[email protected]

Abstract:
Many people in metropolitans have to use different modes of transportation systems in daily intercity journey. Because of complicated, compacted and dynamic networks of public transportation in metropolitans, travelers face many problems to find the best route based on cost, time, and mode of transportation.

A traveler in intercity journey from an origin to a destination can use various mode of transportation such as private vehicle, walking, bus, metro, taxi or combination of these modes (Chulmin, 2001). So it is so essential to design an algorithm to solve the problem in multimodal network. Moreover the best route should be checked for being viable based on logical constraints and sequence of different modes.

The aim of this work is the consideration of various modes of transportation and their constraints and presents an algorithm to find the best route with combination of various modes of transportation based on cost and minimum change of mode in traveling.

Introduction
In most routes finding application in intercity transportation the base is on privately-owned car. In this manner, a person can find the best route for traveling from the origin to destination in shortest way and shortest time.

An efficient public transportation must take into consideration, the extension of metropolitans, the ever-increasing population and the expansion of air pollution spreading. The main difference between route finding in public-transportation network and privately-owned car is that a passenger in public transportation, in traveling between origin and destination, can use different modes of transportation such as metro, taxi, bus, minibus and even walking.

So for measuring time in best route finding, the time of changing modes of transportation for example metro to bus should be considered. The feasibility of the route is an important parameter in finding the best route. This quality is defined by some terms and constraint of the system. For example since metro network is connected, its trains boards and its speed in traveling is the best choice for modes of transportation, so a passenger should use it as much as possible. As a result a passenger can use the mode of metro only one time.

Since in some route finding algorithms, a collection of answer is made, the user preference can be act as a filter of achieving the one answer through all choices. Many users do not have a tendency to change their transportation mode in a travel. So the maximum number of changing mode enter as a system constraint to take the routes, and the minimum number of changing mode is the best route through all answers(Lozano and Storchi,1999). In large cities of Iran, for example Tehran as a metropolis, with high mass traffic and air pollution there are many problems for people in their daily intercity journey. So it is vitally importance to improve the public transportation system to decrease the privately-owned car journey in urban area. Moreover, In Tehran, because of restricted traffic area in downtown, there is no possibilities for people to go there with their private car.

On one hand, metro network with does not cover all over the city. On the other hand, bus network is so scattered all over the city, hence it is possible to achieve anywhere in the city by bus.

So the passengers have many problems in daily intercity journey to choose the best route in a multimodal network based on their time and cost and other preference terms.

In this work the condition and constraints of route finding in a multi modal network contained bus, metro and private car are considered and finally an algorithm to models these conditions in route finding are presented.

Definition:
In this part different component of a multi modal network and their constraints are considered.
A multi modal network is a collection of arcs and nodes as a graph G = (N, A).
Node in a multi modal network is a place that traveler can decide to continue his route in the same mode or change the mode (Lozano and Storchi, 1999).
Arc in a multi modal network have two types:

  • Travel Arc
  • Transfer Arc

Travel arc is a connection of two nodes in the same mode. Transfer arc is a representation of transfer between two nodes in different modes (Lozano and Storchi, 1999).

A route from an origin (a) to a destination (b) (a, b ε N) is a continuous and finite collection of nodes and arcs that connects the origin and destination node.

The best route, through the collection of selective route, is the route that has minimum time of journey or cost and some other constraints such as number of changing mode. So a function as a cost function (c: A–>r) should transform a collection of arcs to a route from the origin to the destination.

Assigning the cost function is based on type of networks and their expense. For example in a bus network since travelers use a bus line only need a ticket but if we want to change the bus line it is needed to pay another ticket.

So it is not possible to link directly a cost to a traverse arc. In this situation, the determination of cost of journey must be taken with care of changing the modes of transportation. The final route is, hence, divided into parts named sub-route that has only nodes of the same mode and each line has a start and end node. The final route is a combination of these sub-routes and the connection of end of one sub-route to start of other in a transfer arc.

The transfer arc can be a walking route or even time of waiting for changing the mode. As such, the total cost for a route is the cost of travel arc in addition to transfer arc. Because of the time and cost of changing the modes of transportation, user usually enters the maximum number of changing modes as a constraint to the system.

Algorithm theory:
In a route finding application from the origin to the destination, many of the existing theory routes are not feasible due to insufficient consideration of especial conditions of the mode of transportation. In such a situation an assessment test is needed to check the feasibility of selected route.

Some of such conditions are:

  1. nonexistence of loop in a route
  2. possibility of car travel in a route with care of route direction
  3. Not using the privately-own care if the last used mode is not a car.
  4. Not using metro mode once more after changing the mode one time.

In route finding algorithm between two nodes, the algorithm starts from the origin and add a connect arc to the route. Then, the connected arcs of end points are considered and one of them is added to the route. Thus, in each step of algorithm, additions of each arc can be checked through the especial constraint of different modes of transportation. For this purpose, in each step we determine a parameter as “State” for any sub-route that these states are defined by use or by not using different types of mode (Lozano and Storchi, 1999).

In each step of the algorithm, adding an Arc to the route may change the state. It is also possible to omit impractical routes from the answer collection.

Implementation method:
Changing the modes of transportation in a multi-modal network is based on the users preference. As such, the maximum number of changing mode is considered as user input parameter for system (Pallottino and Scutella, 1997). Therefore, the main aim is finding the best route with minimum cost such that the maximum changing mode is not reached.

In brief, the best route at first is the route that connects the origin and destination with care of constraints and without any changing mode. Now, only the route that improves the cost will be replaced with the last route.

In the developed algorithm, each step determines a node from the origin, the cost of traveling, the state of route, and the number of changing mode. Then, once the next arc is added, the route is compared with other routes of this node base on the cost and number of changing modes. The second route is omitted if it can not improve the parameters.

This parameter in a route is saved through labeling the nodes of route (Lozano and Storchi, 1999). Any label has especial parameters. For example a label C(s, i) is a representation of cost of achieving node “i” and with state “s”. (Fig 1)


Fig1.Finding route with label correction

In continuation of the route from node i to node j, if connection of these two nodes is a travel arc so the label of “number of mode” T(s, i) is being fixed but if the connection is a transfer arc the label is equal to T(s, i) plus one. In this manner, all nodes in a route are labeled. In each step all conditions of new route are composed to the previous routes and if it improves the condition the new route is selected as one of the answers. Finally, the collections of feasible routes with different cost and number of modes are achieved.

Future works
The proposed algorithm is useful to find a collection of feasible path, where each user can select the number of transfer modes to obtain the best route.

The next step in this research is to implement the algorithm in a GIS environment such as ArcGIS with programming by one of programming Language in .Net Framework.

References

  • Lozano, G.Storchi, 1999. Shortest viable path algorithm in multimodal networks.
  • Pallottino, S., Scutella, M.G., 1997.shortest path algorithm in transportation models.
  • Chulmin,J. ,2001.Route selection in public transportation network using GA.
  • Gallo,G., pallottino,S, 1998.shortest path algorithm.Annual of operational Research.
  • ISO/DIS 19134 , 2005, Geographic information-Location Based Services- Multimodal routing and navigation.
  • Qiujin WU , Joanna HartLey ,2 002,Using K-shortest path algorithm to accommodate user preferences in public transportation travel