A forward network simplex algorithm for solving multiperiod network flow problems

Jay E. Aronson and B. David Chen

Naval Research Logistics Quarterly, 1986, vol. 33, issue 3, 445-467

Abstract: An optimization model which is frequently used to assist decision makers in the areas of resource scheduling, planning, and distribution is the minimum cost multiperiod network flow problem. This model describes network structure decision‐making problems over time. Such problems arise in the areas of production/distribution systems, economic planning, communication systems, material handling systems, traffic systems, railway systems, building evacuation systems, energy systems, as well as in many others. Although existing network solution techniques are efficient, there are still limitations to the size of problems that can be solved. To date, only a few researchers have taken the multiperiod structure into consideration in devising efficient solution methods. Standard network codes are usually used because of their availability and perceived efficiency. In this paper we discuss the development, implementation, and computational testing of a new technique, the forward network simplex method, for solving linear, minimum cost, multiperiod network flow problems. The forward network simplex method is a forward algorithm which exploits the natural decomposition of multiperiod network problems by limiting its pivoting activity. A forward algorithm is an approach to solving dynamic problems by solving successively longer finite subproblems, terminating when a stopping rule can be invoked or a decision horizon found. Such procedures are available for a large number of special structure models. Here we describe the specialization of the forward simplex method of Aronson, Morton, and Thompson to solving multiperiod network network flow problems. Computational results indicate that both the solution time and pivot count are linear in the number of periods. For standard network optimization codes, which do not exploit the multiperiod structure, the pivot count is linear in the number of periods; however, the solution time is quadratic.

Date: 1986
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800330310

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:wly:navlog:v:33:y:1986:i:3:p:445-467

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().