考虑占位决策的围堵嫌犯模型

研究了2011年中国大学生数学建模竞赛B题的突发事件中交巡警对在逃嫌犯的围堵问题。不同于对该问题的以往的研究,本文考虑了交巡警在包围圈中可以占据某些路口,使得嫌犯不能通过这些被交巡警占据的路口,从而为形成包围圈的交巡警赢得更多时间。利用两篇相关文献的关于点截集判断的结论和考虑占位决策的建模方法,以不同的目标函数建立了考虑占位决策的围堵嫌犯问题的三个混合0-1非线性整数规划模型。通过选取部分线性约束和目标函数一起组合成混合0-1线性整数规划模型,设计了基于混合0-1线性整数规划方法的算法,并给出了算例。     

封锁嫌疑犯的数学建模方法

本文是对《数学建模及其应用》第一期“问题征解”的题目的一个解答。利用一对一的匹配模型建立了交巡警平台围堵嫌疑犯的基本模型,而对于何时完成有效的围堵,可以通过逐次逼近的方法解决。利用所设计的模型和给出的算法,得到了该问题的最优解。最后给出在具体假设下的一个优化围堵方案。     

交巡警平台设置与调度模型

设置交巡警平台需要考虑各平台工作量的均衡性以及最长出警时间不能超过3min这两个方面,可利用0-1整数规划,建立平台管辖区域划分模型。发生突发事件时,交巡警平台的警力需要被调度到指定的路口执行任务,最快到达指定路口并且总调度距离最短的方案,即为最佳调度方案,运用0-1规划可以解决这类指派问题。在犯罪嫌疑人从P逃跑3min后,为尽快抓捕逃犯,以点P为中心,从不可封锁点向外逐步延伸,在平台警力能成功封锁的前提下形成最小围堵圈,再利用平台警力调度模型,最终设计出了最佳围堵方案。     

《实用数学建模》介绍

设置交巡警平台需要考虑各平台工作量的均衡性以及最长出警时间不能超过3min这两个方面,可利用0-1整数规划,建立平台管辖区域划分模型。发生突发事件时,交巡警平台的警力需要被调度到指定的路口执行任务,最快到达指定路口并且总调度距离最短的方案,即为最佳调度方案,运用0-1规划可以解决这类指派问题。在犯罪嫌疑人从P逃跑3min后,为尽快抓捕逃犯,以点P为中心,从不可封锁点向外逐步延伸,在平台警力能成功封锁的前提下形成最小围堵圈,再利用平台警力调度模型,最终设计出了最佳围堵方案。     

带机会约束的警务调度模型及其解法

研究在紧急情况发生时,城市中不同交巡警服务平台的警务人员封锁指定区域的最优调度问题.把交巡警服务平台到达指定要道的时间视为满足正态分布的随机变量,从而建立了满足机会约束的警务调度模型并将该模型等价地转化为极小极大模型.给出了模型的求解算法及其计算复杂度.最后,通过一个数值例子来说明算法的有效性.     

具有非对称模糊加工时间工期指派调度优化问题的一类加权模型及其求解算法

根据模糊变量截集所表达的信息的重要程度,建立了模糊环境下工期指派调度优化问题的一类加权模型,该模型中工件加工时间为非对称三角模糊数,目标函数为极小化提前完工惩罚和拖期完工惩罚和的加权可能性均值.证明了当工件加工时间具有相同宽度比时,模型是多项式可解的,并给出了求解的多项式算法.数值实验表明加权模型与现有的非加权模型相比能有效的降低总费用.     

基于α—水平截集的模糊TOPSIS方法在公共危机管理能力评价中的应用研究

科学、客观地评价公共危机管理能力,对于完善危机管理系统有着重要的意义。本文从危机前预警能力,危机中处理能力和危机后恢复能力三个维度构建了公共危机管理能力评价指标体系。考虑到人们对复杂事物判断的模糊性,采用三角模糊数将专家给出的定性评价结果量化,结合α-水平截集和TOPSIS建立了公共危机管理能力综合评价模型,并通过求解非线性规划问题得出危机管理能力的模糊相对贴近度,进而去模糊化得出评价结果。最后用该模型对公共危机管理能力进行实证分析,验证了该模型的可行性和有效性。     

卫星舱三维布局优化模型及判断不干涉性算法

本以人造卫星仪器舱布局问题为背景。建立了在抛物圆柱体空间中带性能约束的长方体群的布局优化模型。分析模型中不干涉性约束的性质，利用凸集分离定理给出了等价的显式表达式，并构造了判断不干涉性的算法。     

区间值模糊集的区间值水平截集、分解定理和表现定理

给出了区间值模糊集的区间值水平截集的新定义,建立了基于此类截集的分解定理和表现定理。首先,将区间值模糊集的区间值水平截集定义为三值模糊集,给出了区间值模糊集的四类截集的定义,指出这些截集与模糊集的截集有完全一样的性质。其次,建立了区间值模糊集的分解定理和表现定理。这些工作为研究区间值模糊集提供了新的工具。     

模糊数在投资组合优化中的应用研究及实证分析

采用模糊数处理不确定性信息.以模糊期望收益率最大为目标函数,使总的风险不高于给定的模糊数,建立了一种新的模型.在给定的截集下,期望收益率转化为区间数,目标函数转化为对该区间数的下限求最大值.基于模糊数大小的概率比较,从而将模糊优化模型转化为不等式约束下的线性规划模型.利用Matlab编程可解得其最优解.最后通过实例分析,验证该模型的可行性.     

110警车配置及巡逻方案

针对110警车调度问题,引入了图论中的最短路算法以及计算几何的相关理论,建立了车辆调配模型、巡逻路线模型以及基于模糊数学的评价指标模型.另外,用C++编写了一个可视化的软件,不仅实现了手动描点,自动求出覆盖线段集合的功能,同时利用计算机模拟警车的巡逻路线,最后通过计算机检验得到结果,其合理性和实用性都令人满意.针对问题一,通过人机结合,配置17辆警车就能实现D1的目标,很好地兼顾了警车巡逻的运行成本,减少公安部门车辆和人员等的投入.针对问题二,采用模糊数学相关理论使评价指标实现了从定性到定量的转变.针对问题三和六,在D1的基础上,兼顾了巡逻效果的显著性,采用最少被巡逻道路优先的贪心算法建立了动态巡逻模型,得到了合理的巡逻方案.在此方案中,我们动用了30辆警车完成了问题一的目标.另外还额外考虑了案发事件概率不均匀分布的情况,建立了改进模型.针对问题四,在完成问题三指标的基础上,为了尽可能提高巡逻车辆的隐蔽性和增强巡逻效果,采用轮盘赌算法来引入随机性.针对问题五,采用最远距离道路优先贪心策略,使模型尽可能满足条件D1,D2.针对问题七,提出了一些额外因素及其解决方案,进一步完善了模型,使模型更贴近现实.     

最小封堵圈的扩张算法设计

在发生突发事件之后,及时制定有效的封堵方案才能掌握抓捕嫌疑犯的主动权.提出了对逃跑罪犯实施完全封堵的最小包围圈的计算机算法,通过规则图形的仿真演示,验证了该算法的正确性.最后以某市案发时候的警力分布和交通图作为实例,模拟了对嫌疑犯实施封堵时计算最小包围圈的最优方案.结果证明该算法具有简洁、可靠的优点.     

Location-allocation models for traffic police patrol vehicles on an interurban network

This research investigates the traffic police routine patrol vehicle (RPV) assignment problem on an interurban road network through a series of integer linear programs. The traffic police RPV’s main task, like other emergency services, is to handle calls-for-service. Emergency services allocation models are generally based on the shortest path algorithm however, the traffic police RPV also handles other roles, namely patrolling to create a presence that acts as a deterrence, and issuing tickets to offenders. The RPVs need to be located dynamically on both hazardous sections and on roads with heavy traffic in order to increase their presence and conspicuousness, in an attempt to prevent or reduce traffic offences, road accidents and traffic congestion. Due to the importance of the traffic patrol vehicle’s location with regard to their additional roles, allocation of the RPVs adheres to an exogenous, legal, time-to-arrival constraint. We develop location-allocation models and apply them to a case study of the road network in northern Israel. The results of the four models are compared to each other and in relation to the current chosen locations. The multiple formulations provide alternatives that jointly account for road safety and policing objectives which aid decision-makers in the selection of their preferred RPV assignments. The results of the models present a location-allocation configuration per RPV per shift with full call-for-service coverage whilst maximizing police presence and conspicuousness as a proxy for road safety.     

A cutting-plane algorithm for solving a weighted influence interdiction problem

We consider a two-stage defender-attacker game that takes place on a network, in which the attacker seeks to take control over (or “influence”) as many nodes as possible. The defender acts first in this game by protecting a subset of nodes that cannot be influenced by the attacker. With full knowledge of the defender’s action, the attacker can then influence an initial subset of unprotected nodes. The influence then spreads over a finite number of time stages, where an uninfluenced node becomes influenced at time t if a threshold number of its neighbors are influenced at time t?1. The attacker’s objective is to maximize the weighted number of nodes that are influenced over the time horizon, where the weights depend both on the node and on the time at which that is influenced. This defender-attacker game is especially difficult to optimize, because the attacker’s problem itself is NP-hard, which precludes a standard inner-dualization approach that is common in many interdiction studies. We provide three models for solving the attacker’s problem, and develop a tailored cutting-plane algorithm for solving the defender’s problem. We then demonstrate the computational efficacy of our proposed algorithms on a set of randomly generated instances.     

Double-super-connected digraphs

A strongly connected digraph D is said to be super-connected if every minimum vertex-cut is the out-neighbor or in-neighbor set of a vertex. A strongly connected digraph D is said to be double-super-connected if every minimum vertex-cut is both the out-neighbor set of a vertex and the in-neighbor set of a vertex. In this paper, we characterize the double-super-connected line digraphs, Cartesian product and lexicographic product of two digraphs. Furthermore, we study double-super-connected Abelian Cayley digraphs and illustrate that there exist double-super-connected digraphs for any given order and minimum degree.     

Modelling Rural Police Patrol

Police patrol has been modelled extensively in the urban environment, but these urban models cannot usually be applied to rural settings. The length of travel times and the nature of calls for service in rural, wide-area, low-population regions demand special consideration. In this paper, we develop a Markov model that explicitly incorporates travel times and priority calls to analyse police patrol policies in rural areas. Results of the model using data from Washtenaw County, Michigan, USA, are given to show its utility.     

Multicriteria movement synchronization scheduling problems and algorithms

This article deals with multicriteria optimization models and algorithms of movement scheduling for many objects to synchronize their movement (2CMSS problem). The model consists of two parts: (1) node–disjoint path planning visiting specified nodes for K objects with a given vector of intermediate nodes for each one (NDSP problem); (2) movement synchronization in some intermediate nodes (MS problem). For synchronous movement, two categories of criteria are defined: time of movement and ‘distance’ of K-moved objects from the movement pattern. We defined the problem as a discrete-continuous, non-linear, two-criteria mathematical programming problem. We proposed to use a two-stage algorithm to solve the 2CMSS problem (as lexicographic solution): At first we have to find the vector of node–disjoint shortest paths for K objects visiting intermediate nodes to set optimal paths under the assumption that we use maximal possible velocities on each arc belonging to a path for each object (solution of the NDSP problem), and next we try to decrease the values of velocities to optimize the second criterion (synchronization, solution of the MS problem). Experimental analyses of effectiveness and complexity of the algorithms are presented.     

New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints

Given an undirected network with positive edge costs and a natural number p, the Hop-Constrained Minimum Spanning Tree problem (HMST) is the problem of finding a spanning tree with minimum total cost such that each path starting from a specified root node has no more than p hops (edges). In this paper, we develop new formulations for HMST. The formulations are based on Miller-Tucker-Zemlin (MTZ) subtour elimination constraints, MTZ-based liftings in the literature offered for HMST, and a new set of topology-enforcing constraints. We also compare the proposed models with the MTZ-based models in the literature with respect to linear programming relaxation bounds and solution times. The results indicate that the new models give considerably better bounds and solution times than their counterparts in the literature and that the new set of constraints is competitive with liftings to MTZ constraints, some of which are based on well-known, strong liftings of Desrochers and Laporte (1991).     

Optimizing State Patrol Manpower Allocation

One of the most difficult tasks of state highway patrol administrators is allocation of manpower; i.e. determining the most effective level of operational manpower for patrol tasks. Typically, administrators resolve the allocation problem by relying on prior statistical data and by employing subjective analysis. In general, only limited systematic analyses have been applied to the problem. This paper presents an integer goal programming model for allocating highway patrolmen to road segments within a patrol region. The model is demonstrated via a case example of the Nebraska State Patrol. The results of the model are valuable to the patrol administrator for considering departmental goals and priority structure, in addition to available historical data, in the assignment of state patrol manpower.