
4f174a7fd39c20a
Zarrinmehr, A., Shafahi, Y. (2014). Enumeration of Dominant Solutions: An Application in Transport Network Design. International Journal of Transportation Engineering, 1(4), 335348. doi: 10.22119/ijte.2014.6302Amirali Zarrinmehr; Yousef Shafahi. "Enumeration of Dominant Solutions: An Application in Transport Network Design". International Journal of Transportation Engineering, 1, 4, 2014, 335348. doi: 10.22119/ijte.2014.6302Zarrinmehr, A., Shafahi, Y. (2014). 'Enumeration of Dominant Solutions: An Application in Transport Network Design', International Journal of Transportation Engineering, 1(4), pp. 335348. doi: 10.22119/ijte.2014.6302Zarrinmehr, A., Shafahi, Y. Enumeration of Dominant Solutions: An Application in Transport Network Design. International Journal of Transportation Engineering, 2014; 1(4): 335348. doi: 10.22119/ijte.2014.6302
Enumeration of Dominant Solutions: An Application in Transport Network Design
Article 7, Volume 1, Issue 4, Spring 2014, Page 335348
PDF (4470 K)
Document Type: Research Paper
DOI: 10.22119/ijte.2014.6302
Authors
Amirali Zarrinmehr ^{} ^{1}; Yousef Shafahi^{2}
^{1}MSc. Graduate, Department of Civil Engineering, Sharif University of Technology, Tehran, Iran
^{2}Professor, Department of Civil Engineering, Sharif University of Technology, Tehran, Iran
Abstract
A OneDimensional Binary Integer Programming Problem (1DBIPP) is concerned with selecting a subset from a set of k items in budget constraint to optimize an objective function. In this problem a dominant solution is defined as a feasible selection to which no further item could be added in budget constraint. This paper presents a simple algorithm for Enumeration of Dominant Solutions (EDS) and investigates its functionality. The algorithm is then applied on the formulation of the Network Design Problem (NDP) with fixed traveltime links. The problem is a case study of 1DBIPPs in the transportation planning literature which arises in the networks where the link traveltimes are not sensitive to the amount of flow. The results are reported in detail for three illustrative examples and compared with the results of the BranchandBound (B&B) algorithm. These examples suggest that in lower budget levels up to 40.2, 40.3 and 27.1 percentages the EDS algorithm outperforms the B&B algorithm. However, the overall performance of the B&B algorithm is notably faster in higher budget levels.
Keywords
Enumeration; Dominant Solution; BranchandBound Algorithm; Network Design Problem
References
 Alba, E. (2005) “Parallel metaheuristics: A new class of algorithms”, Wiley Series on Parallel and Distributed Computing.
 Angulo, E., Castillo, E., GarcíaRódenas, R. and SánchezVizcaíno, J. (2013) “A continuous bilevel model for the expansion of highway networks”, Computers and Operations Research, in press.
 Babazadeh, A., Poorzahedy, H. and Nikoosokhan, S. (2011) “Application of particle swarm optimization to transportation network design problem”, Journal of King Saud UniversityScience, Vol. 23, No. 3, pp. 293300.
 BarGera, H. (2011) "Transportation network test problems", Accessed September 19, http://www.bgu.ac.il/~bargera/tntp/.
 Cormen, T. H., Leiserson, C.E., Rivest, R. L. and Stein, C. (2011) “Introduction to algorithms”, Second edition. Cambridge, Massachusetts: MIT press.
 Garey, M. R. and Johnson, D. S. (1979) “Computers and intractability: a guide to the theory of NPcompleteness”, W. H. Freeman and Company, San Francisco.
 Grama, A.Y. and Kumar, V. (1993) "A survey of parallel search algorithms for discrete optimization problems", ORSA Journal on Computing, Vol. 7, pp. 140.
 Ibaraki, T. (1976) "Theoretical comparisons of search strategies in branchandbound algorithms", International Journal of Computer & Information Sciences, Vol. 5, No. 4, pp. 31544.
 OchoaRosso, F. and Silva, A. (1969) “Optimum project addition in urban transportation networks via descriptive traffic assignment models”, Transportation Systems Division, MIT.
 Pisinger, D. (1995) "Algorithms for knapsack problems", Ph.D diss., Department of Computer Science, University of Copenhagen.
 Poorzahedy, H. and Abulghasemi, F. (2005) "Application of ant system to network design problem", Transport, Vol. 32, No. 3, pp. 251273.
 Rust, J. (2006) “Dynamic programming”, New Palgrave Dictionary of Economics.
 Sheffi, Y. (1985) “Urban transportation networks: Equilibrium analysis with mathematical programming methods”, PrenticeHall Englewood Cliffs, NJ.
 Vitins, B. J., and Axhausen, K. W. (2009) “Optimization of large transport networks using the ant colony heuristic”, ComputerAided Civil and Infrastructural Engineering Journal of ASCE, Vol. 24, No. 1, pp. 114.
 Vitins, B. J. and Axhausen, K. W. (2010) “Patterns and grammars for transport network generation”, Proceedings of 14 the Swiss Transport Research Conference.
 Yin, Y. (2000) “Geneticalgorithmsbased approach for bilevel programming models.” , Transportation Engineering Journal of ASCE, Vol. 126, No. 2, pp. 115120.
StatisticsArticle View: 2,502PDF Download: 2,427