An extended transportation problem: a DEA-based approach

The transportation problem is an important network structured linear programming problem that arises in several contexts and that has received a great deal of attention in the literature. The existing transportation problems are limited to consideration unit of shipping cost or profit along an arc. However, in many real applications, various attributes are usually considered in a transportation problem. The current paper, proposes an extension to this problem in the presence of multiple in-commensurate inputs and outputs for each arc. The concept of relative efficiency is defined for each possible transportation plan. Two linear programming models are proposed to determine the transportation plan with the maximum efficiency. A numerical example is used to illustrate the applicability of the approach.     

The energy-constrained quickest path problem

This paper addresses a variant of the quickest path problem in which each arc has an additional parameter associated to it representing the energy consumed during the transmission along the arc while each node is endowed with a limited power to transmit messages. The aim of the energy-constrained quickest path problem is to obtain a quickest path whose nodes are able to support the transmission of a message of a known size. After introducing the problem and proving the main theoretical results, a polynomial algorithm is proposed to solve the problem based on computing shortest paths in a sequence of subnetworks of the original network. In the second part of the paper, the bi-objective variant of this problem is considered in which the objectives are the transmission time and the total energy used. An exact algorithm is proposed to find a complete set of efficient paths. The computational experiments carried out show the performance of both algorithms.     

结点有约束的交通网络最短路径模型

结点有约束的网络是一类特殊的网络，如具有禁止通行限制信息的交通路网等，由于最短路径的求解是有后效性的，经典的Dijkstra算法等不能直接用来求解该问题，本文提出了一种结点有约束的交通网络最短路径建模方法，该方法所建模型为一般网络模型，可用任一传统高效的算法求其最短路径，从根本上降低了问题的复杂性，为很好地解决交通、通信等领域中的此类问题提供了有益的方法。     

The first <Emphasis Type="Italic">K</Emphasis> minimum cost paths in a time-schedule network

The time-constrained shortest path problem is an important generalisation of the classical shortest path problem and in recent years has attracted much research interest. We consider a time-schedule network, where every node in the network has a list of pre-specified departure times and departure from a node may take place only at one of these departure times. The objective of this paper is to find the first K minimum cost simple paths subject to a total time constraint. An efficient polynomial time algorithm is developed. It is also demonstrated that the algorithm can be modified for finding the first K paths for all possible values of total time.     

Shortest path in the presence of obstacles: An application to ocean shipping

This paper presents the problem of determining the estimated time of arrival (ETA) at the destination port for a ship located at sea. This problem is formulated as a shortest path problem with obstacles, where the obstacles are modelled by polygons representing the coastlines. An efficient solution algorithm is proposed to solve the problem. Instead of generating a complete visibility graph and solving the problem as an ordinary shortest path problem, the algorithm constructs arcs to the ship node during the solution process only when needed. This greatly enhances the algorithmic performance. Computational results based on test problems from an actual dry-bulk shipping operation are provided. The proposed algorithm is implemented in a decision support system for the planning of ship operations and it has successfully been applied on several real life problems.     

Efficient Solution of the Single-item,Capacitated Lot-sizing Problem with Start-up and Reservation Costs

A capacitated dynamic lot-sizing model, where the costs incurred are a start-up cost for switching the production facility on and another reservation cost for keeping the facility on, whether or not it is producing, is considered. The resulting scheduling problem is NP-hard. An efficient shortest path model of the uncapacitated version of the problem is developed. This model is then included, via a redefinition of variables, into a tight capacitated model; tight in the sense that sharp lower bounds can be produced from it. The lower bound problems are solved efficiently by recovering the shortest path structure through column generation, and effective upper bounds are generated by solving a small capacitated trans-shipment problem. The results of computational tests to verify the computational efficiency of the resulting solution scheme are presented.     

A heuristic approach to hard constrained shortest path problems

Constrained shortest path problems have many applications in areas like network routing, investments planning and project evaluation as well as in some classical combinatorial problems with high duality gaps where even obtaining feasible solutions is a difficult task in general.We present in this paper a systematic method for obtaining good feasible solutions to hard (doubly constrained) shortest path problems. The algorithm is based essentially on the concept of efficient solutions which can be obtained via parametric shortest path calculations. The computational results obtained show that the approach proposed here leads to optimal or very good near optimal solutions for all the problems studied.From a theoretical point of view, the most important contribution of the paper is the statement of a pseudopolynomial algorithm for generating the efficient solutions and, more generally, for solving the parametric shortest path problem.     

Label Correcting Methods to Solve Multicriteria Shortest Path Problems

In this paper, we deal with the solution of the multicriteria shortest path problem. In particular, we present a class of labeling methods to generate the entire set of Pareto-optimal path-length vectors from an origin node s to all other nodes in a multicriteria network. The proposed methods are supported theoretically by the principle of optimality and they are defined on the basis of various innovative node and label selection strategies.Computational results comparing the proposed methods to state-of-the-art approaches to solve the problem considered are also reported. They indicate that our methods are competitive in general; in several cases, they outperform all the other codes.     

Multi-criteria approximation schemes for the resource constrained shortest path problem

In the resource constrained shortest path problem we are given a directed graph along with a source node and a destination node, and each arc has a cost and a vector of weights specifying its requirements from a set of resources with finite budget limits. A minimum cost source-destination path is sought such that the total consumption of the arcs from each resource does not exceed its budget limit. In the case of constant number of weight functions we give a fully polynomial time multi-criteria approximation scheme for the problem which returns a source-destination path of cost at most the optimum, however, the path may slightly violate the budget limits. On the negative side, we show that there does not exist a polynomial time multi-criteria approximation scheme for the problem if the number of weight functions is not a constant. The latter result applies to a broad class of problems as well, including the multi-dimensional knapsack, the multi-budgeted spanning tree, the multi-budgeted matroid basis and the multi-budgeted bipartite perfect matching problems.     

所有点对之间最快路问题

所有点对之间最快路问题就是要在所有点对(Vs，Vt)之间传送数据δs,t,并找出一条最快的路线．解决所有点对之间最快路问题的关键是产生有效解的等价集合．运用动态点对最短路的算法，本文首先设计了一个时间复杂性为O(mn^2)的产生有效解等价集合的算法，然后研究了静态点对之间最快路问题和动态点对之间最快路问题，其算法的时间复杂性分别为O(mn^2)和O(m^2n^2)．最后本文研究了求和对最小的路问题，证明该问题可以在O(mn^2)时间内解决．     

具有风险偏好的模糊网络最短路算法

运用结构元理论来求解具有风险偏好的、带有模糊权值的网络最短路问题.首先,简要介绍模糊结构元及相关定理.之后,提出了组合序,证明组合序是全序.组合序含有参数θ,随着θ的取值范围不同,序反映风险偏好的类型不同.在组合序和相关定理的基础上,证明了模糊网络最短路的判定定理,定理表明:求模糊网络最短路等价求一经典网络最短路,且风险偏好大小由θ的取值来确定.最后,通过一个例子来说明求解过程.     

Shortest paths in networks with vector weights

For a directed network in which vector weights are assigned to arcs, the Pareto analog to the shortest path problem is analyzed. An algorithm is presented for obtaining all Pareto shortest paths from a specified node to every other node.     

Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs

In this paper, we present an algorithm for solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs. The path cost function considered is comprised of two attributes, travel time and toll, that are combined into a nonlinear generalized cost. Travel demand is determined endogenously according to a travel disutility function. Travelers choose routes with the minimum overall generalized costs. The algorithm involves two components: a bicriteria shortest path routine to implicitly generate the set of non-dominated paths and a projection and contraction method to solve the nonlinear complementarity problem (NCP) describing the traffic equilibrium problem. Numerical experiments are conducted to demonstrate the feasibility of the algorithm to this class of traffic equilibrium problems.     

The combined cutting stock and lot-sizing problem in industrial processes

Despite its great applicability in several industries, the combined cutting stock and lot-sizing problem has not been sufficiently studied because of its great complexity. This paper analyses the trade-off that arises when we solve the cutting stock problem by taking into account the production planning for various periods. An optimal solution for the combined problem probably contains non-optimal solutions for the cutting stock and lot-sizing problems considered separately. The goal here is to minimize the trim loss, the storage and setup costs. With a view to this, we formulate a mathematical model of the combined cutting stock and lot-sizing problem and propose a solution method based on an analogy with the network shortest path problem. Some computational results comparing the combined problem solutions with those obtained by the method generally used in industry—first solve the lot-sizing problem and then solve the cutting stock problem—are presented. These results demonstrate that by combining the problems it is possible to obtain benefits of up to 28% profit. Finally, for small instances we analyze the quality of the solutions obtained by the network shortest path approach compared to the optimal solutions obtained by the commercial package AMPL.     

Algorithms for the quickest path problem and the reliable quickest path problem

The quickest path problem consists of finding a path in a directed network to transmit a given amount of items from an origin node to a destination node with minimal transmission time, when the transmission time depends on both the traversal times of the arcs, or lead time, and the rates of flow along arcs, or capacity. In telecommunications networks, arcs often also have an associated operational probability of the transmission being fault free. The reliability of a path is defined as the product of the operational probabilities of its arcs. The reliability as well as the transmission time are of interest. In this paper, algorithms are proposed to solve the quickest path problem as well as the problem of identifying the quickest path whose reliability is not lower than a given threshold. The algorithms rely on both the properties of a network which turns the computation of a quickest path into the computation of a shortest path and the fact that the reliability of a path can be evaluated through the reliability of the ordered sequence of its arcs. Other constraints on resources consumed, on the number of arcs of the path, etc. can also be managed with the same algorithms.     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

Hybrid co-evolutionary particle swarm optimization and noising metaheuristics for the delay constrained least cost path problem

This paper presents a co-evolutionary particle swarm optimization (PSO) algorithm, hybridized with noising metaheuristics, for solving the delay constrained least cost (DCLC) path problem, i.e., shortest-path problem with a delay constraint on the total “cost” of the optimal path. The proposed algorithm uses the principle of Lagrange relaxation based aggregated cost. It essentially consists of two concurrent PSOs for solving the resulting minimization-maximization problem. The main PSO is designed as a hybrid PSO-noising metaheuristics algorithm for efficient global search to solve the minimization part of the DCLC-Lagrangian relaxation by finding multiple shortest paths between a source-destination pair. The auxiliary/second PSO is a co-evolutionary PSO to obtain the optimal Lagrangian multiplier for solving the maximization part of the Lagrangian relaxation problem. For the main PSO, a novel heuristics-based path encoding/decoding scheme has been devised for representation of network paths as particles. The simulation results on several networks with random topologies illustrate the efficiency of the proposed hybrid algorithm for the constrained shortest path computation problems.     

Multiobjective routing problems

Summary Many network routing problems, particularly where the transportation of hazardous materials is involved, are multiobjective in nature; that is, it is desired to optimise not only physical path length but other features as well. Several such problems are defined here and a general framework for multiobjective routing problems is proposed. The notion of “efficient solution” is defined and it is demonstrated, by means of an example, that a problem may have very many solutions which are efficient. Next, potentially useful solution methods for multiobjective routing problems are discussed with emphasis being placed on the use of shortest/k-shortest path techniques. Finally, some directions for possible further research are indicated. Invited by B. Pelegrin     

Solving nonlinear multicommodity flow problems by the analytic center cutting plane method

The paper deals with nonlinear multicommodity flow problems with convex costs. A decomposition method is proposed to solve them. The approach applies a potential reduction algorithm to solve the master problem approximately and a column generation technique to define a sequence of primal linear programming problems. Each subproblem consists of finding a minimum cost flow between an origin and a destination node in an uncapacited network. It is thus formulated as a shortest path problem and solved with Dijkstra’s d-heap algorithm. An implementation is described that takes full advantage of the supersparsity of the network in the linear algebra operations. Computational results show the efficiency of this approach on well-known nondifferentiable problems and also large scale randomly generated problems (up to 1000 arcs and 5000 commodities). This research has been supported by the Fonds National de la Recherche Scientifique Suisse, grant #12-34002.92, NSERC-Canada and FCAR-Quebec. This research was supported by an Obermann fellowship at the Center for Advanced Studies at the University of Iowa.     

Shortest path problem with forbidden paths: The elementary version

This paper addresses the elementary shortest path problem with forbidden paths. The main aim is to find the shortest paths from a single origin node to every other node of a directed graph, such that the solution does not contain any path belonging to a given set (i.e., the forbidden set). It is imposed that no cycle can be included in the solution. The problem at hand is formulated as a particular instance of the shortest path problem with resource constraints and two different solution approaches are defined and implemented. One is a Branch & Bound based algorithm, the other is a dynamic programming approach. Different versions of the proposed solution strategies are developed and tested on a large set of test problems.