Speed-up Technique in Time-Varying Shortest Path Problems with Arbitrary Waiting Times
Network flow problems are considered a vital branch of operations research. These problems are classified into static and time-varying classes. Network flow problems are time-varying in real application, because any flow must take a given amount of time to traverse an arc. Moreover, all the paramete...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | fas |
| Published: |
University of Qom
2020-09-01
|
| Series: | مدیریت مهندسی و رایانش نرم |
| Subjects: | |
| Online Access: | https://jemsc.qom.ac.ir/article_1068_c81e51869e8e5eb621be93c818e5df13.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Network flow problems are considered a vital branch of operations research. These problems are classified into static and time-varying classes. Network flow problems are time-varying in real application, because any flow must take a given amount of time to traverse an arc. Moreover, all the parameters in the network can be time-dependent. In this paper, the speed-up technique on time-varying shortest path problems is studied. First of all, the time-varying shortest path problem is explained. The problem is to find the shortest paths from a specific vertex (which is called a source) to other vertices, so that the total cost of the path is minimized and the total travel times and waiting times reach a maximum value of T, where T is a given positive integer. Then the speed-up technique is explained for a shortest path problem. |
|---|---|
| ISSN: | 2538-6239 2538-2675 |