An advanced Successive Derivative Shortest Path algorithm for concave cost network flow problems

Lu Yang and Zhouwang Yang

Operations Research Perspectives, 2025, vol. 14, issue C

Abstract: As production scales up, transportation networks increasingly involve nonlinear costs, leading to the concave cost network flow problem (CCNFP), which is notably challenging due to its nonlinearity. Existing nonlinear programming methods addressing the CCNFP often suffer from low efficiency and high computational cost, limiting their practical application. To overcome these limitations, this paper proposes the Successive Derivative Shortest Path (SDSP) algorithm, an efficient approach that combines a sequential linear approximation framework with regional first-order information of the objective function. By integrating regional first-order information and employing an interval reduction mechanism, the SDSP algorithm effectively avoids premature convergence to suboptimal solutions, thereby achieving higher-quality solutions. Numerical experiments, including parameter selection, validation, and comparative analysis, demonstrate that the SDSP algorithm outperforms existing methods in terms of both solution quality and convergence speed. This research offers a robust and efficient solution for the CCNFP, with potential applications in various fields, including logistics and supply chain networks, where concave cost network flow issues are common.

Keywords: Network flow; Non-convex problem; Approximation algorithm; Regional first-order information; Interval reduction (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S2214716025000077
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:oprepe:v:14:y:2025:i:c:s2214716025000077

DOI: 10.1016/j.orp.2025.100331

Access Statistics for this article

Operations Research Perspectives is currently edited by Rubén Ruiz Garcia

More articles in Operations Research Perspectives from Elsevier
Bibliographic data for series maintained by Catherine Liu ().