Upgrading Arc Median Shortest Path Problem for an Urban Transportation Network
Publication: Journal of Transportation Engineering
Volume 135, Issue 10
Abstract
In this paper, we propose an algorithm for an upgrading arc median shortest path problem for a transportation network. The problem is to identify a set of nondominated paths that minimizes both upgrading cost and overall travel time of the entire network. These two objectives are realistic for transportation network problems, but of a conflicting and noncompensatory nature. In addition, unlike upgrading cost which is the sum of the arc costs on the path, overall travel time of the entire network cannot be expressed as a sum of arc travel times on the path. The proposed solution approach to the problem is based on heuristic labeling and exhaustive search techniques, in criteria space and solution space, respectively. The first approach labels each node in terms of upgrading cost, and deletes cyclic and infeasible paths in criteria space. The latter calculates the overall travel time of the entire network for each feasible path, deletes dominated paths on the basis of the objective vector and identifies a set of Pareto optimal paths in the solution space. The computational study, using two small-scale transportation networks, has demonstrated that the algorithm proposed herein is able to efficiently identify a set of nondominated median shortest paths, based on two conflicting and noncompensatory objectives.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The writers are grateful to three anonymous reviewers who made constructive comments on the earlier versions of this paper.
References
Aneja, Y. P., and Nair, K. P. K. (1979). “Bicriteria transportation problems.” Manage. Sci., 25, 73–78.
Bar-Gera, H. (2007). Transportation network test problems, ⟨http://www.bgu.ac.il⟩ (May 20, 2007).
Campbell, A. M., Lowe, T. J., and Zhang, L. (2006). “Upgrading arcs to minimize the maximum travel time in a network.” Network, 47(2), 72–80.
Chen, A., Lee, D. H., and Jayakrishnan, R. (2002). “Computational study of state-of-the-art path-based traffic assignment algorithms.” Math. Comput. Simul., 59, 509–518.
Coutinho-Rodrigues, J. M., Climaco, J. C. N., and Current, J. R. (1999). “An interactive bi-objective shortest path approach: searching for unsupported nondominated solutions.” Comput. Oper. Res., 26, 789–798.
Current, J. R., and Marsh, M. (1993). “Multiobjective transportation network design and routing problems: taxonomy and annotation.” Eur. J. Oper. Res., 65(1), 4–19.
Current, J. R., and Min, H. (1986). “Multiobjective design of the transportation networks: Taxonomy and annotation.” Eur. J. Oper. Res., 26, 187–201.
Current, J. R., ReVelle, C. S., and Cohon, J. L. (1985). “The maximum covering/shortest path problem: A multiobjective network design and routing formulation.” Eur. J. Oper. Res., 21, 189–199.
Current, J. R., ReVelle, C. S., and Cohon, J. L. (1987). “The median shortest path problem: A multiobjective approach to analyze cost vs. accessibility in the design of the transportation networks.” Transp. Sci., 21, 188–197.
Dijkstra, E. W. (1959). “Note on two problems in connection with graphs.” Numer. Math., 1, 269–271.
Gandibleux, X., Beugnies, F., and Randriamasy, S. (2006). “Martins’ algorithm revisited for multiobjective shortest paths problems with a MaxMin cost function.” 4OR: A Quarterly Journal of Operations Research, 4(1), 47–59.
Hansen, P. (1980). “Bicriterion path problems.” Multiple criteria decision making, G. Fandel and T. Gal, eds., Springer, Berlin.
Jayakrisshnan, R., Tsai, W. K., Prashker, J. N., and Rajadhyaksha, S. (1994). “Faster path-based algorithm for traffic assignment.” Working paper, Univ. of California Transportation Center.
Jones, D. F., Mirrazavi, S. K., and Tamiz, M. (2002). “Multiobjective meta-heuristics: An overview of the current state-of-the-art.” Eur. J. Oper. Res., 137, 1–9.
Martins, E. Q., Santos, J. L., Paixao, M., and Rosa, M. (2007). Ranking multiobjective shortest paths, ⟨http://citeseer.ist.psu.edu⟩ (July 20, 2007).
Martins, E. Q. V. (1984). “On a multicriteria shortest path problem.” Eur. J. Oper. Res., 16, 236–245.
Martins, E. Q. V., and Santos, J. L. (1999). The labeling algorithm for the multiobjective shortest path problem, ⟨http://citeseer.ist.psu.edu⟩ (May 20, 2007).
Modesti, P., and Sciomachen, A. (1998). “A utility measure for finding multiobjective shortest paths in urban multimodal transportation network.” Eur. J. Oper. Res., 111, 495–508.
Moore, E. F. (1957). “The shortest path through maize.” Proc., Int. Symp. on Theory of Switching, Harvard Univ.
Nepal, K. P., and Park, D. (2005). “Solving the median shortest path problem in the planning and design of urban transportation networks using a vector labeling algorithm.” Transp. Plan. Technol., 28(2), 113–133.
Pangilinan, J. M. A., and Janssens, G. K. (2007). “Evolutionary algorithm for the multiobjective shortest path problem.” Transactions on Engineering, Computing and Technology, 19, 205–210.
Park, D., Sharma, S. L., Rilett, L. R., and Chang, M. (2002). “Identifying multiple and reasonable alternative routes: Efficient vector labeling approach.” Transp. Res. Rec., 1783, 111–118.
Steenbrink, P. (1974). Optimization of transport networks, Wiley, New York.
Sun, M. (2003). “Procedures for finding nondominated solutions for multiple objective network programming problems.” Transp. Sci., 37(2), 139–152.
Zhang, L. (2005). “Upgrading arc problem with budget constraint.” Proc., 43rd ACM Southeast Conf., Kennesaw, Ga.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 135 • Issue 10 • October 2009
Pages: 783 - 790
Copyright
© 2009 ASCE.
History
Received: Jun 23, 2006
Accepted: Feb 11, 2009
Published online: Sep 15, 2009
Published in print: Oct 2009
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.