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


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
Page 3 of 3
| Previous |