多无人机协同任务策略优化

从研究多无人机协同任务的系统资源分配、任务分配、航线规划、轨迹优化等问题入手,建立了多基地多无人机协同侦察模型.针对问题,首先利用"栅格化聚拢"的思想对目标点进行过滤优化,进而对目标群和无人机基地进行了任务分配,而后结合蚁群算法、贪心算法、最短路径算法等思想,通过Matlab平台,计算出能够让无人机停留在雷达探测区域总时间最少的最优策略.     

一种无人机侦察航迹分层规划方法

给出了一个通用可行的无人机侦察航迹分层规划方法,并应用到第十三届"华为杯"全国研究生数学建模竞赛A题第一问中.将无人机侦察航迹规划问题划分为四个层次,从上至下分别是目标群间侦察顺序优化,目标群内各目标侦察顺序优化,侦察点位优化,转弯设计,依次求解获得侦察航迹.通过分层解算方法既有效控制了算法复杂度,又能在确保满足复杂约束的同时优化无人机在敌方雷达探测区域内的暴露时间.     

通行受限下需求可拆分的应急物资卡车-多无人机协同配送路径优化

研究通行受限情景下需求可拆分的应急物资卡车-多无人机协同配送路径优化问题,综合考虑灾区路网状况、卡车可途中发射/接受无人机、无人机单次起飞可配送多个需求点、需求可拆分等因素,以应急物资配送任务完成时间最短为目标,构建卡车-多无人机协同配送路径优化模型.根据问题与模型特征设计一种改进蚁群算法求解.实验结果表明:文章方法能合理分配卡车与无人机的配送任务,科学规划通行受限情景下需求可拆分的应急物资卡车-多无人机协同配送路径;卡车途中发射/接收无人机方式能有效缩短无人机飞行距离,减少卡车与无人机的协同时间,缩短通行受限情景下的应急物资配送时间,具有可行性、合理性与有效性.     

灾区中无人机巡查和通信问题的战略模型研究

无人机作为一种新型的运输工具,能够在震区救援行动中发挥重要作用.在地形复杂的震区,且在一定的约束条件下,将三维模型做二维化处理,建立巡查灾区的K均值聚类和最小包围圈模型,借助MATLAB软件使用蚁群算法求解,并给出两种以上的模型解决方案,最后核算时间和覆盖率,有效解决无人机巡查和通信问题.同时,解决文中问题时得出,遗传算法模型的时间复杂度小于蚁群算法的时间复杂度的结论.     

基于蚁群系统和2-opt方法求解同时送取货车辆路径VRPSPD问题

研究了一般意义下同时送取货的车辆路径VRPSPD问题,建立VRPSPD的整数规划模型.考虑到VRPSPD车辆不断变化的负载量,使得问题难以求解,设计了一种将蚁群系统(ACS)与2-opt方法相结合的启发式算法.通过在蚁群系统(ACS)中引入候选集合的策略,将启发因子设为目标函数值,同时利用2-opt算法的思想得到适用于VRPSPD的2-opt方法,使得设计的启发式算法对于求解VRPSPD是有效的.最后,实例运算的结果也证明了算法是一种较好的算法,能够得到满意的解.     

多目标0-1规划问题的蜂群算法

针对多目标0-1规划问题,本文给出一种新型的智能优化算法——蜂群算法进行求解,并通过实例验证,与遗传算法、蚁群算法和元胞蚁群算法作了相应比较。就多目标0-1规划问题而言,蜂群算法能得到更多的Pareto解,说明了蜂群算法在解决该类问题上的有效性。     

零售业连锁网点选址与布局演化模型

蚁群算法是近年来出现的一种新型仿生优化算法,是求解复杂优化问题有效方法.本文建立了基于蚁群算法的零售业连锁网点选址与布局演化模型,并利用Matlab进行仿真研究.通过对模拟结果的分析,验证了零售业连锁网点的选址与布局规律.     

复杂地势的无人机灾情巡查新方法

主要针对无人机在抢险救灾中的灾情巡查问题探究新型巡查方法.通过变"覆盖巡查面"为"有效巡查点",将传统的多无人机协同覆盖巡查问题转化为带有避障的VRP问题,并以所有无人机总飞行时间最少为目标建立相应的数学模型.运用MATLAB编写蚁群算法求解VRP中任意两点间的最短避障路线长度矩阵,进而用遗传算法来求解带有避障的VRP问题,得到不同需求下的最少无人机数量,规划出飞行路线.经过案例分析可得,此巡查路线覆盖率达到85.95%,具有较好的实用性.     

邮政运输网络中的邮路规划和邮车调度研究

邮政运输网络是邮政企业运营的重要保障,而邮路规划和邮车调度设计是决定邮政运输网络效率的关键因素,问题1的邮路规划问题归结为带返程货的车辆路由问题,该问题是NP-难的,采用改进蚁群算法,通过对单环路旅行商问题进行断环分析,将运行线路的好坏反馈给蚁群算法的目标函数,求取最终的优化路径.第二问邮路规划扩展到了全区,采用有优先级的分县优化途径寻求最佳邮路.最后,给出模型的评价及改进方向.     

基于改进蚁群算法的最短路径问题研究及应用

蚁群系统作为一种蚁群算法是解决最短路径问题的一种行之有效的方法.然而,它自身也存在着一些缺陷,主要针对基本蚁群算法易陷入局部最优这一缺陷对其进行改进,集中体现在初始信息素求解和信息素更新这两方面.为了进一步了解改进蚁群算法的优点,进行了实验仿真:将改进的蚁群算法应用子模拟医疗救护GIS中,利用GIS的网络分析功能对城市道路网络的最短路径选择算法进行了深入地探讨研究,并以山西省太原市的交通路线作为实例进行研究.计算机仿真结果表明,改进的蚁群算法在解决最短路径问题时较基本蚁群算法的性能好,它具有一定的理论参考价值和现实意义.     

The maximum covering/shortest path problem: A multiobjective network design and routing formulation

In this paper the authors introduce the maximum covering/shortest path problem and the maximum population/shortest path problem, a special case of the former model. Both models are formulated as two objective integer programs. A summary of the results of a sample problem for the latter formulation is given. Possible modifications to, and extensions and applications of both models are also presented. With these formulations the authors extend the concept of ‘coverage’ from facility location analysis to network design and routing analysis.     

Neighboring extremals of dynamic optimization problems with path equality constraints

Neighboring extremals of dynamic optimization problems with path equality constraints and with an unknown parameter vector are considered in this paper. With some simplifications, the problem is reduced to solving a linear, time-varying two-point boundary-value problem with integral path equality constraints. A modified backward sweep method is used to solve this problem. Two example problems are solved to illustrate the validity and usefulness of the solution technique. This research was supported in part by the National Aeronautics and Space Administration under NASA Grant No. NCC-2-106. The author is indebted to Professor A. E. Bryson, Jr., Department of Aeronautics and Astronautics, Stanford University, for many stimulating discussions.     

Mean–variance optimal trading problem subject to stochastic dominance constraints with second order autoregressive price dynamics

The efficient modeling of execution price path of an asset to be traded is an important aspect of the optimal trading problem. In this paper an execution price path based on the second order autoregressive process is proposed. The proposed price path is a generalization of the existing first order autoregressive price path in literature. Using dynamic programming method the analytical closed form solution of unconstrained optimal trading problem under the second order autoregressive process is derived. However in order to incorporate non-negativity constraints in the problem formulation, the optimal static trading problems under second order autoregressive price process are formulated. For a risk neutral investor, the optimal static trading problem of minimizing expected execution cost subject to non-negativity constraints is formulated as a quadratic programming problem. Whereas, for a risk averse investor the variance of execution cost is considered as a measure for the timing risk, and the mean–variance problem is formulated. Moreover, the optimal static trading problem subject to stochastic dominance constraints with mean–variance static trading strategy as the reference strategy is studied. Using Static approximation method the algorithm to solve proposed optimal static trading problems is presented. With numerical illustrations conducted on simulated data and the real market data, the significance of second order autoregressive price path, and the optimal static trading problems is presented.     

On Models of Directed Path Graphs Non Rooted Directed Path Graphs

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted directed path graph is the intersection graph of a family of directed subpaths of a rooted tree. Clearly, rooted directed path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted directed path graphs. With the purpose of proving knowledge in this direction, we show in this paper properties of directed path models that can not be rooted for chordal graphs with any leafage and with leafage four. Therefore, we prove that for leafage four directed path graphs minimally non rooted directed path graphs have a unique asteroidal quadruple, and can be characterized by the presence of certain type of asteroidal quadruples.     

Nodal aggregation of resource constraints in a shortest path problem

The shortest path problem with resource constraints consists of finding the minimum cost path between two specified points while respecting constraints on resource consumption. Its solving by a dynamic programming algorithm requires a computation time increasing with the number of resources. With the aim of producing rapidly a good heuristic solution we propose to reduce the state space by aggregating resources. Our approach consists of projecting the resources on a vector of smaller dimension and then to dynamically adjust the projection matrix to get a better approximation of the optimal solution. We propose an adjustment based on Lagrangian and surrogate relaxations in a column generation framework, in which the sub-problems are shortest path problems with resource constraints. We adjust the multipliers only one time at each column generation iteration. This permit to obtain good solutions of the scheduling problem in few time.     

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.     

所有点对之间最快路问题

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

A bicriterion shortest path algorithm

Among the network models, one of the more popular is the so called shortest path problem. This model is used whenever it is intended to minimize a linear function which represents a distance between a predetermined pair of nodes in a given network.Often a single objective function is not sufficient to completely characterize some real-world problems. For instance, in a road network two parameters - as cost and time - can be assigned to each arc. Clearly the fastest path may be too costly. Nevertheless the decision-maker must choose one solution, possibly not the best for both criteria.In this paper we present an algorithm for this problem. With this algorithm a special set of paths (the set of Pareto optimal paths) is determined. One objective for any Pareto optimal path can not be improved without worsening the other one.     

On a negative-equivalency theorem in associative optimal path problems

In this we study a wide class of optimal path problem in acyclic digraphs, where path lengths are defined through associative binary operations:addition, multiplication, multiplication-addition, fraction and so on. Solving a system of two interrelated recur-sive equations, we simultaneously find both shortest and longest path lengths, Further, for every problem (primal problem), we associate the other related problem (negative-equivalent problem) where each path length is defined through the associative operation connected to it in the primal problem by DeMorgan’s law. The main objective of this paper is to derive a negative-equivalency theorem between the primal problem and the negative-equivalent one     

An extended shortest path problem: A data envelopment analysis approach

A special and important network structured linear programming problem is the shortest path problem. Classical shortest path problems assume that there are unit of shipping cost or profit along an arc. In many real occasions, various attributes (various costs and profits) are usually considered in a shortest path problem. Because of the frequent occurrence of such network structured problems, there is a need to develop an efficient procedure for handling these problems. This paper studies the shortest path problem in the case that multiple attributes are considered along the arcs. The concept of relative efficiency is defined for each path from initial node to final node. Then, an efficient path with the maximum efficiency is determined.