Volume 16, Issue 2 (7-2019)
jor 2019, 16(2): 39-57 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Safari S, Zaferanieh M, Abareshi M, Rahimi E L. The Lagrangian Relaxation Method for the Shortest Path Problem Considering Transportation Plans and Budgetary Constraint. jor 2019; 16 (2) :39-57
URL: http://jamlu.liau.ac.ir/article-1-1631-en.html
URL: http://jamlu.liau.ac.ir/article-1-1631-en.html
Department of Applied Mathematics, Hakim Sabzevari University, Sabzevar, Iran
Abstract: (2685 Views)
In this paper, a constrained shortest path problem (CSP) in a network is investigated, in which some special plans for each link with corresponding pre-determined costs as well as reduction values in the link travel time are considered. The purpose is to find a path and selecting the best plans on its links, to improve the travel time as most as possible, while the costs of conducting plans do not exceed the available budget. Using the Lagrangian relaxation approach, some constraints of the problem are relaxed and the Lagrangian dual problem is decomposed into two smaller sub-problems. Then, by applying the sub-gradient algorithm, a near optimal solution is determined for the original problem. Finally, by considering the proposed model on a small-sized network and on Khorasan state network, solutions for different origin-destination pairs with different parameters are determined.
Keywords: Transportation Network, Constrained Shortest Path Problem, Lagrangian Dual Method, Sub-gradient Method.
Type of Study: Research |
Subject:
Special
Received: 2018/02/3 | Accepted: 2019/03/8 | Published: 2019/07/15
Received: 2018/02/3 | Accepted: 2019/03/8 | Published: 2019/07/15
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |
