求解网络最大流问题的一个算法

为了便于建立与网络最大流问题有关的决策支持系统，本给出一个求解网络最大流问题的数值算法。证明了算法的理论依据，并举例说明了算法的应用。该算法能求出网络最大流和最小截，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

有上下界网络最大流与最小截问题

为了便于建立与有上下界网络最大流与最小截问题有关的决策支持系统，本文给出一个求有上下界网络最大流与最小截的数值算法，证明了算法的理论依据，并举例说明了算法在堵塞流理论中的应用。该算法能判定问题是否有可行解，在问题有可行解的情况下能求得问题的最优解。该算法具有易于编程实现、收敛性好等优点。数值实验表明该算法有较高的计算效率，可用于求解最小饱和流问题。     

最大利润流问题及算法

最大利润流是以运输利润最大为目标的网络优化问题 .一个利润可行流可分解为若干个路流和圈流 ,相应地该可行流的利润也等于这些路流和圈流的利润之和 .本文证明了一个可行流为最大利润流的充要条件是不存在利润增广路 ,并据此提出了求解算法 .文章最后给出了一个计算实例 .     

运输网络中求最小费用最大流的一个算法

给出一个求动输网络中的最小费用最大流的数值算法,证明了算法的理论依据,并举例说明算法的应用。     

求解交通均衡配流问题的新算法

给出了一个求解交通均衡配流问题的新算法，证明了新算法的收敛性，并在小型交通网络上进行了初步的数值试验．     

带有模糊容量限制的网络中的最佳最小费用量大流

本文主要讨论当网络中弧容量限制和最大流目标要求带有模糊性时的最小费最大流问题，通过构造带费用的增量网络并设法寻找其中的最佳最小费用路，给出了求解这类模糊网络流问题的算法。     

求解指派问题的一个算法

为了便于建立与指派问题有关的决策支持系统，本给出了一个求解指派问题的数值算法，证明了算法的理论依据。该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

带有模糊容量限制的网络中的最佳最小费用最大流

本文主要讨论当网络中的弧容量限制和最大流目标要求带有模糊性时的最小费用最大流问题，通过构造带费用的增量网络并设法寻找其中的最佳最小费用路，给出了求解这类模糊网络流问题的算法。     

需求区间型运输问题的求解算法

为了便于建立与需求区间型运输问题有关的决策支持系统，本给出了一个求解需求区间型运输问题的数值算法，证明了算法的理论依据，并举例说明算法的应用，该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法有较高的计算效率。     

竞争环境下截流设施选址问题

研究企业新建设施时,市场上已有设施存在的情况下,使本企业总体利润最大的截流设施选址问题。在一般截留设施选址模型的基础上引入引力模型,消费者到某个设施接受服务的概率与偏离距离及设施的吸引力相关,同时设施的建设费用与设施吸引力正相关,建立非线性整数规划模型并使用贪婪算法进行求解。数值分析表明,该算法求解速度快,模型计算精度较高。     

Comparative analysis of the machine repair Problem with imperfect coverage and service pressure condition

In this paper we analyze the warm-standby M/M/R machine repair problem with multiple imperfect coverage which involving the service pressure condition. When an operating machine (or warm standby) fails, it may be immediately detected, located, and replaced with a coverage probability c by a standby if one is available. We use a recursive method to develop the steady-state analytic solutions which are used to calculate various system performance measures. The total expected profit function per unit time is derived to determine the joint optimal values at the maximum profit. We first utilize the direct search method to measure the various characteristics of the profit function followed by Quasi-Newton method to search the optimal solutions. Furthermore, the particle swarm optimization (PSO) algorithm is implemented to find the optimal combinations of parameters in the pursuit of maximum profit. Finally, a comparative analysis of the Quasi-Newton method with the PSO algorithm has demonstrated that the PSO algorithm provides a powerful tool to perform the optimization problem.     

A specialized network simplex algorithm for the constrained maximum flow problem

The constrained maximum flow problem is to send the maximum flow from a source to a sink in a directed capacitated network where each arc has a cost and the total cost of the flow cannot exceed a budget. This problem is similar to some variants of classical problems such as the constrained shortest path problem, constrained transportation problem, or constrained assignment problem, all of which have important applications in practice. The constrained maximum flow problem itself has important applications, such as in logistics, telecommunications and computer networks. In this research, we present an efficient specialized network simplex algorithm that significantly outperforms the two widely used LP solvers: CPLEX and lp_solve. We report CPU times of an average of 27 times faster than CPLEX (with its dual simplex algorithm), the closest competitor of our algorithm.     

The inverse maximum dynamic flow problem

We consider the inverse maximum dynamic flow (IMDF) problem. IMDF problem can be described as: how to change the capacity vector of a dynamic network as little as possible so that a given feasible dynamic flow becomes a maximum dynamic flow. After discussing some characteristics of this problem, it is converted to a constrained minimum dynamic cut problem. Then an efficient algorithm which uses two maximum dynamic flow algorithms is proposed to solve the problem.     

Approximate algorithms for the competitive facility location problem

We consider the competitive facility location problem in which two competing sides (the Leader and the Follower) open in succession their facilities, and each consumer chooses one of the open facilities basing on its own preferences. The problem amounts to choosing the Leader’s facility locations so that to obtain maximal profit taking into account the subsequent facility location by the Follower who also aims to obtain maximal profit. We state the problem as a two-level integer programming problem. A method is proposed for calculating an upper bound for the maximal profit of the Leader. The corresponding algorithm amounts to constructing the classical maximum facility location problem and finding an optimal solution to it. Simultaneously with calculating an upper bound we construct an initial approximate solution to the competitive facility location problem. We propose some local search algorithms for improving the initial approximate solutions. We include the results of some simulations with the proposed algorithms, which enable us to estimate the precision of the resulting approximate solutions and give a comparative estimate for the quality of the algorithms under consideration for constructing the approximate solutions to the problem.     

随机需求下多供应商和多零售商的生产-库存-运输联合优化模型

考虑随机需求下多供应商和多零售商的生产-库存-运输联合优化问题.在联合优化时,首先利用最近邻算法将各零售商分成不同区域,分区后问题转化为随机需求下单供应商对多零售商的生产-库存-运输联合优化问题.在每个分区内,由供应商统一决策其分区内各零售商的送货量和送货时间.利用粒子群算法和模拟退火算法相结合的两阶段算法求出最优送货量、最优运输路径和最大期望总利润.然后采用收入共享契约将增加的利润合理分配给各供应商和各零售商,使各方利润都得到增加,从而促使各方愿意合作.通过数值算例验证了联合优化模型优于独立决策模型.     

包含随机客户的选择性旅行商问题建模及求解

针对快递配送过程中客户需求具有不确定性的特征,提出一种新的路径优化问题——包含随机客户的选择性旅行商问题,在该问题中客户每天是否具有配送需求存在一定概率,并且对客户进行配送可获取一定利润。同时考虑以上两种因素,建立该问题的数学模型, 目标为在满足行驶距离限制的条件下,找出一条经过部分客户的预优化路径,使得该路径的期望利润最大。其可用于模拟构建最后一公里快递配送的路径问题,提供更具有经济效益的配送路径。随后提出包含精细化局部搜索策略的改进遗传算法,算法根据问题特点构建初始可行解。最后通过多个计算比对结果表明,该算法具有较高的计算效率。     

An adaptive ejection pool with toggle-rule diversification approach for the capacitated team orienteering problem

In the capacitated team orienteering problem (CTOP), we are given a set of homogeneous vehicles and a set of customers each with a service demand value and a profit value. A vehicle can get the profit of a customer by satisfying its demand, but the total demand of all customers in its route cannot exceed the vehicle capacity and the length of the route must be within a specified maximum. The problem is to design a set of routes that maximizes the total profit collected by the vehicles. In this article, we propose a new heuristic algorithm for the CTOP using the ejection pool framework with an adaptive strategy and a diversification mechanism based on toggling between two priority rules. Experimental results show that our algorithm can match or improve all the best known results on the standard CTOP benchmark instances proposed by Archetti et al. (2008).