The multiobjective average network flow problem: Shortest path and minimum cost flow formulations, algorithms, heuristics, and complexity

Transportation mode selection is becoming increasingly popular in the field of logistics and operations research. Several modeling challenges exist, one being the consideration of multiple factors into the transportation decision. While the Analytic Hierarchy Process is quite popular in the literature, other multicriteria decision analysis methods such as value focused thinking (VFT) are used sparingly, as is the case across the entirety of the supply chain literature. We provide a VFT tutorial for supply chain applications. The transportation environment lends itself naturally to network optimization; we therefore integrate multicriteria decision analysis (MCDA), specifically VFT, with the shortest and longest path problem. Since a decision maker desires to maximize value with these techniques, this creates the Multiobjective Average Longest Path (MALP) problem. The MALP allows multiple quantitative and qualitative factors to be captured in a network environment without the use of multicriteria optimization methods, which typically only capture 2–3 factors before becoming intractable. The MALP (equivalent to the average longest path) and the average shortest path problem for general graphs are NP-hard, proofs are provided. The MALP for directed acyclic graphs can be solved quickly using an existing algorithm or a dynamic programming (DP) approach. The existing algorithm is reviewed and a new algorithm using DP is presented. We also create a faster heuristic allowing solutions in O(m) as opposed to the O(n3) and O(nm) solution times of the optimal methods. This scaling heuristic is empirically investigated under a variety of conditions and easily modified to approximate the longest or shortest average path problem for directed acyclic graphs. Furthermore, a decision maker may wish to make tradeoffs between increasing value in the network and decreasing the number of arcs used. We show the DP algorithm and scaling heuristic automatically generate the efficient frontier for this special case of the more general bicriteria average shortest path problem, thus providing an efficient algorithm for this multicriteria problem. Since most organizations ship multiple products, the clear extension to the multiobjective average shortest path is the multiobjective average minimum cost flow. Similar to the multiobjective average shortest path problem, we implement MCDA into the minimum cost flow problem; this creates a multiobjective average minimum cost flow (MAMCF) problem, a problem equivalent to the average minimum cost flow problem. We show the problem is also NP-hard. However, for directed acyclic graphs efficient pseudo-polynomial time heuristics are possible. The average shortest path DP algorithm is implemented in a successive shortest path fashion to create an efficient average minimum cost flow heuristic. Furthermore, the scaling heuristic is used successively as an even faster average minimum cost flow heuristic. Both heuristics are then proven to have an infinitely large error bound. However, in random networks the heuristics generate solutions within a small percentage of the optimal solution. Finally, a general bicriteria average minimum cost flow (BAMCF) problem is given. In the case of the MAMCF, decision makers may choose to minimize arcs in a path along with maximizing multiobjective value. Therefore, a special case of the BAMCF is introduced allowing tradeoffs between arcs and value. This problem is clearly NP-hard, however good solutions are attainable through the use of the average minimum cost flow heuristics.