Enumeration of Dominant Solutions: An Application in Transport Network Design

Document Type : Research Paper

Authors

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 One-Dimensional Binary Integer Programming Problem (1DB-IPP) 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 travel-time links. The problem is a case study of 1DB-IPPs in the transportation planning literature which arises in the networks where the link travel-times 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 Branch-and-Bound (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

References

- Alba, E. (2005) “Parallel metaheuristics: A new class of algorithms”, Wiley Series on Parallel and Distributed Computing.
- Angulo, E., Castillo, E., García-Ródenas, R. and Sánchez-Vizcaíno, J. (2013) “A continuous bi-level 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 University-Science, Vol. 23, No. 3, pp. 293-300.
- Bar-Gera, 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 NP-completeness”, 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. 1-40.
- Ibaraki, T. (1976) "Theoretical comparisons of search strategies in branch-and-bound algorithms", International Journal of Computer & Information Sciences, Vol. 5, No. 4, pp. 315-44.
- Ochoa-Rosso, 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. 251-273.
- Rust, J. (2006) “Dynamic programming”, New Palgrave Dictionary of Economics.
- Sheffi, Y. (1985) “Urban transportation networks: Equilibrium  analysis with mathematical programming methods”, Prentice-Hall Englewood Cliffs, NJ.
- Vitins, B. J., and Axhausen, K. W. (2009) “Optimization of large transport networks using the ant colony heuristic”, Computer-Aided Civil and Infrastructural Engineering Journal of ASCE, Vol. 24, No. 1, pp. 1-14.
- 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) “Genetic-algorithms-based approach for bi-level programming models.” , Transportation Engineering Journal of ASCE, Vol. 126, No. 2, pp. 115-120.
International Journal of Transportation Engineering
Volume 1, Issue 4 - Serial Number 4
April 2014
Pages 335-348

Files

Share

How to cite

Statistics