PROJECT SELECTION AND SCHEDULING OPTIMIZATION FOR THE MULTI-PERIOD NETWORK DESIGN PROBLEM
The traditional network design problem tries to increase surplus benefits of users over long-term period or increase the reliability of the system in short-term period. An implied...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | fas |
| Published: |
Sharif University of Technology
2017-08-01
|
| Series: | مهندسی عمران شریف |
| Subjects: | |
| Online Access: | https://sjce.journals.sharif.edu/article_4562_7503c892a7486d1c969aae8b05c749b6.pdf |
| _version_ | 1797736730592280576 |
|---|---|
| author | Y. Shafahi M. Ameri |
| author_facet | Y. Shafahi M. Ameri |
| author_sort | Y. Shafahi |
| collection | DOAJ |
| description | The traditional network design problem tries to increase surplus benefits of users over long-term period or increase the reliability of the system in short-term period. An implied assumption of most these studies is that all projects are selected and implemented in a short period of time and budget limitations are only considered within that short time. This assumption is not a valid assumption for some real transportation projects. It is more appropriate to consider the fluctuations in demand over long-term period. Demand for transportation infrastructures does not only change with time, but is also influenced by variations in supply. Transportation projects usually consist of several components that are continually implemented and operated during the projects' life cycle. The benefits and costs of operation of different parts of the projects at different times should be considered in project evaluation. This paper deals with formulating and solving the Multi-Period Network Design Problem (MPNDP). MPNDP is a variation of the Network Design Problem (NDP) which inserts timing into the problem. The model's outputs are the optimum set of projects and the optimal scheduling of the projects simultaneously.MPNDPs are complex problems, not only due to their large sizes, but also due to interdependency of costs and benefits among projects. In terms of difficulty of solving, they fall within the category of NP-hard problems. In this paper, two heuristic methods, which are based on steepest descent and Tabu search, are offered to solve the problem.In the solution procedures of both methods, three interdependent matrices track the annual projects progress, the annual projects' budget assignments, and the available projects.The results of our study show that while the steepest descent method provides more robust solutions than the Tabu based search method for smaller-sized problems, it fails to find solutions to large-sized problems. The Tabu search's relative performance increases as the size of the problem increases; Therefore, it is recommended for solving large networks. The performance of the model and the solution techniques are tested on the Sioux Falls City network which is a mid-sized network. |
| first_indexed | 2024-03-12T13:18:10Z |
| format | Article |
| id | doaj.art-1f8b7026f0df43009d55fb6406002307 |
| institution | Directory Open Access Journal |
| issn | 2676-4768 2676-4776 |
| language | fas |
| last_indexed | 2024-03-12T13:18:10Z |
| publishDate | 2017-08-01 |
| publisher | Sharif University of Technology |
| record_format | Article |
| series | مهندسی عمران شریف |
| spelling | doaj.art-1f8b7026f0df43009d55fb64060023072023-08-26T10:21:07ZfasSharif University of Technologyمهندسی عمران شریف2676-47682676-47762017-08-0133.22.211111810.24200/j30.2017.45624562PROJECT SELECTION AND SCHEDULING OPTIMIZATION FOR THE MULTI-PERIOD NETWORK DESIGN PROBLEMY. Shafahi0M. Ameri1Dept. of Civil Engineering Sharif University of TechnologyInstitute for management and planning studiesThe traditional network design problem tries to increase surplus benefits of users over long-term period or increase the reliability of the system in short-term period. An implied assumption of most these studies is that all projects are selected and implemented in a short period of time and budget limitations are only considered within that short time. This assumption is not a valid assumption for some real transportation projects. It is more appropriate to consider the fluctuations in demand over long-term period. Demand for transportation infrastructures does not only change with time, but is also influenced by variations in supply. Transportation projects usually consist of several components that are continually implemented and operated during the projects' life cycle. The benefits and costs of operation of different parts of the projects at different times should be considered in project evaluation. This paper deals with formulating and solving the Multi-Period Network Design Problem (MPNDP). MPNDP is a variation of the Network Design Problem (NDP) which inserts timing into the problem. The model's outputs are the optimum set of projects and the optimal scheduling of the projects simultaneously.MPNDPs are complex problems, not only due to their large sizes, but also due to interdependency of costs and benefits among projects. In terms of difficulty of solving, they fall within the category of NP-hard problems. In this paper, two heuristic methods, which are based on steepest descent and Tabu search, are offered to solve the problem.In the solution procedures of both methods, three interdependent matrices track the annual projects progress, the annual projects' budget assignments, and the available projects.The results of our study show that while the steepest descent method provides more robust solutions than the Tabu based search method for smaller-sized problems, it fails to find solutions to large-sized problems. The Tabu search's relative performance increases as the size of the problem increases; Therefore, it is recommended for solving large networks. The performance of the model and the solution techniques are tested on the Sioux Falls City network which is a mid-sized network.https://sjce.journals.sharif.edu/article_4562_7503c892a7486d1c969aae8b05c749b6.pdfnetwork designmulti-period network designheuristic methodstabu searchsteepest descent |
| spellingShingle | Y. Shafahi M. Ameri PROJECT SELECTION AND SCHEDULING OPTIMIZATION FOR THE MULTI-PERIOD NETWORK DESIGN PROBLEM مهندسی عمران شریف network design multi-period network design heuristic methods tabu search steepest descent |
| title | PROJECT SELECTION AND SCHEDULING OPTIMIZATION FOR THE MULTI-PERIOD NETWORK DESIGN PROBLEM |
| title_full | PROJECT SELECTION AND SCHEDULING OPTIMIZATION FOR THE MULTI-PERIOD NETWORK DESIGN PROBLEM |
| title_fullStr | PROJECT SELECTION AND SCHEDULING OPTIMIZATION FOR THE MULTI-PERIOD NETWORK DESIGN PROBLEM |
| title_full_unstemmed | PROJECT SELECTION AND SCHEDULING OPTIMIZATION FOR THE MULTI-PERIOD NETWORK DESIGN PROBLEM |
| title_short | PROJECT SELECTION AND SCHEDULING OPTIMIZATION FOR THE MULTI-PERIOD NETWORK DESIGN PROBLEM |
| title_sort | project selection and scheduling optimization for the multi period network design problem |
| topic | network design multi-period network design heuristic methods tabu search steepest descent |
| url | https://sjce.journals.sharif.edu/article_4562_7503c892a7486d1c969aae8b05c749b6.pdf |
| work_keys_str_mv | AT yshafahi projectselectionandschedulingoptimizationforthemultiperiodnetworkdesignproblem AT mameri projectselectionandschedulingoptimizationforthemultiperiodnetworkdesignproblem |