多级覆盖设施选址问题建模及求解方法研究

针对应急服务网络优化设计中的设施选址决策问题,分析了应急服务的特殊性以及现有的设施选址模型在求解该问题时的局限性,基于传统的最大覆盖模型提出了应急服务设施的多级覆盖选址模型.该模型对"覆盖"概念的定义进行了扩展,考虑了应急服务的多源服务特性以及对多个服务源提供服务时可存在的差异性.之后基于分布估计算法(Estimation of distribution algorilhms,简称EDAs)提出了模型的启发式求解方法,并基于实验结果对算法参数选取给出了参考意见.     

基于持续运营机会约束的竞争设施点选址研究——一种有效的实数编码遗传求解算法

竞争设施点选址是空间经济、区域发展、组合优化和系统工程的重要课题之一。本文以市场份额最大化为目标,研究了基于持续运营机会约束的竞争设施点选址问题,并给出了一种有效的实数编码遗传求解算法。在求解模型方面,首先假定运营成本是竞争设施点规模大小的函数,并对设施点持续运营概率进行机会约束,借鉴引力模型建立竞争设施点选址-设计问题的非线性混合整数规划模型。其次,考虑到选址变量和规模变量的数值类型,以及编码变换问题,设计了一种实数编码遗传求解算法。通过数值实验表明,对不同规模问题的实际计算结果,该算法可以在较短时间内获得最优解,可行解和精确解之间误差小于0.5%,相关比较分析也讨论了该算法的优越性和实用性,为竞争设施点选址问题的研究提供了不同的视角和实用求解算法。     

重大突发事件应急救援设施选址的多目标决策模型

常用的应急服务设施选址模型主要有覆盖模型、p-中心模型和p-中值模型,这些模型并不适合重大突发事件的应急救援设施选址.分析重大突发事件应急救援设施选址问题的特点,建立一个多目标决策模型,该模型考虑了应急救援设施的公平性和效率性,整合了传统选址模型中常用的最大覆盖模型、p-中心模型和p-中值模型,以适应重大突发事件应急救援设施的不同部署策略,通过实例讨论该模型的求解方法和求解策略.     

α-鲁棒随机截流选址问题的模型和算法

由于选址决策的长期性,相关参数会随着时间而变化,所以选址问题存在很多不确定因素。本文通过不同的情景来处理截流问题中流量的不确定性,并结合随机优化和鲁棒优化,提出α-鲁棒随机截流选址模型。该模型规定了在各情景下的相对后悔值不超过α的条件下,使截得的流量的期望值最大,该条件称为α-鲁棒约束。本文将该模型建立成为一个线性0-1整数规划,并给出了改进型贪婪算法和拉格朗日启发式算法。最后,本文使用这两种算法对不同规模的截流选址问题进行了研究。     

带有响应时间承诺的选址-分配问题研究

研究在服务行业中一类带有响应时间承诺的设施选址及对各选址点进行服务台数目分配的问题。将排队理论与选址理论有机结合,建立带有预算限制的非线性整数规划模型,以找到合适的选址地点和相应的服务台数目,使在承诺的响应时间内完成服务的需求数目最大。运用贪婪算法得出服务台分配的结果,采用下降算法和基于二进制编码的遗传算法对设施点选址,通过大量随机算例验证算法的有效性。数值模拟结果表明,目标值随着预算或承诺时间的增加而增加,但是随着需求数量的增加不是呈单调递增趋势,而且随着一些参数的变化平均每个需求的平均逗留时间和平均运输时间的波动基本上是相反的。     

跨境电商企业海外仓选址多目标优化研究

海外仓作为一带一路战略环境下的一种新型跨境物流模式,具有运输时间短、退换货快等特点。本文在跨境电商的背景下,综合考虑建仓成本、运输费用、运输时间和税费等因素,提出了海外仓选址多目标优化模型,随后基于分层序列法设计了二分搜索-最小费用流算法对该模型进行求解,并证明该算法在多项式时间内可以得到最优解,最后通过算例证实了该模型和算法的有效性和实用性,这为跨境电商海外仓选址提供了理论依据和决策支持。     

基于ASRank和MMAS的蚁群算法求解飞机指派问题

本文将航班串的飞机指派问题归结为车辆路径问题,考虑连续航班串之间衔接时间、衔接机场的约束、每架飞机的总飞行时间约束,建立了带有飞行时间约束的车辆路径问题的混合整数规划模型。构造了蚁群系统算法,引入基于排序的蚂蚁系统和最大最小蚂蚁系统算法的信息素更新策略。选取某航空公司7组初始航班串集合进行测试,并对算法中的重要参数进行了分析。实验结果表明,本文设计的模型和算法可以有效地减少连续航班串之间的总衔接时间,在可接受的计算时间内获得满意解。     

基于服务效率的自助服务设施选址模型与算法

研究了服务行业中基于服务效率的自助服务设施选址及选址点服务台数量分配的问题.通过确定选址数量,将排队理论与选址理论结合,以减少顾客访问的旅行成本和排队拥塞成本来提高设施的服务效率,对选址点的服务台进行合理分配,建立了非线性整数规划模型.运用下降算法和遗传算法对设施选址与服务台分配进行设计,并通过大量随机算例验证了算法的有效性.     

考虑空间随机需求的急救站点选址规划

随着人民生活水平的提高和人口老龄化加剧，公众对急救医疗服务的要求越来越高。为保证急救需求的响应及时性，急救站点的选址规划问题受到广泛关注。急救站点选址的依据是需求的分布，然而现有研究未能充分考虑急救需求在空间分布上的随机性影响，通常将其空间分布简化为若干个集中需求点，或将规划空间划分为若干矩形网格，然而这种需求刻画过于粗略，导致需求覆盖水平的计算不够准确，影响配置方案的有效性。针对该问题，本研究应用高斯混合模型解决了急救需求的空间分布刻画问题，创新性地提出基于高斯混合聚类的站点选址规划方法，考虑急救需求时空随机性，建立了相应的机会约束规划模型。实际数据的验证分析表明，该选址方法能够显著减少服务延误时间和次数，保证急救服务的响应及时性。     

服务水平保证下应急抢修点选址模型及求解算法研究

本文研究了一类故障率低但重要性较高设备的应急抢修点选址问题。设备的故障发生过程和从应急抢修点到故障设备的通行时间是随机的,每个设备被分配给一个应急抢修点进行抢修,并且整个应急抢修系统的服务水平要大于给定标准。本文以应急抢修点总开设成本最小作为目标,同时考虑了设备覆盖约束、抢修分配关系约束和抢修系统服务水平约束,在合理的假设下证明设备发生故障且应急抢修小组迟到的总次数服从泊松分布,最终将应急抢修点选址问题描述为一个0-1整数规划模型。通过对模型中的覆盖约束和抢修系统服务水平约束进行松弛,设计了相应的拉格朗日启发式算法。最后通过对大量随机算例进行计算,证明了该模型和算法的有效性。     

弹性约束CSP及其基于遗传算法的交互式求解Agent

本文在回顾了约束满足问题(CSP)及其演进优化算法的基础上,提出了弹性约束CSP模型(ECSP),并将该模型形式化为六元组。ECSP模型是对已有的PCSP模型的改进。为了寻求ECSP问题的决策满意解,我们还设计了集成多Ageng、GA优化以及分布式并行计算技术的一种交互式多Ageng体系。我们详细阐述了其中的GA求解器算法,包括适应函数的确定、编码方式的选择、算子定义以及初始种群定义等。最后,我们用一个简单的算例证明了方法的有效性。     

Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery

Today manufacturers have become much more concerned with the coordination of both manufacturing (of new products) and recycling (of reusable resources) operations. This requires simultaneous scheduling of both forward and reverse flows of goods over a supply chain network. This paper studies time dependent vehicle routing problems with simultaneous pickup and delivery (TD-VRPSPD). We formulate this problem as a mixed integer programming model, where the time step function is used to calculate the travel time. To efficiently solve this complex problem, we develop a hybrid algorithm that integrates both Ant Colony System (ACS) and Tabu Search (TS) algorithms. Our algorithm uses the pheromones, travel time and vehicle residual loading capacity as a factor structure according to the characteristics of TD-VRPSPD. In our computational experiments, 56 groups of benchmark instances are used to evaluate the performance of our hybrid algorithm. In addition, we compare the performance of our hybrid algorithm with those of individual ACS and TS algorithms. The computational results suggest that our hybrid algorithm outperform stand-alone ACS and the TS algorithms.     

A multi-objective particle swarm for a flow shop scheduling problem

Flow shop problems as a typical manufacturing challenge have gained wide attention in academic fields. In this paper, we consider a bi-criteria permutation flow shop scheduling problem, where weighted mean completion time and weighted mean tardiness are to be minimized simultaneously. Since a flow shop scheduling problem has been proved to be NP-hard in strong sense, an effective multi-objective particle swarm (MOPS), exploiting a new concept of the Ideal Point and a new approach to specify the superior particle's position vector in the swarm, is designed and used for finding locally Pareto-optimal frontier of the problem. To prove the efficiency of the proposed algorithm, various test problems are solved and the reliability of the proposed algorithm, based on some comparison metrics, is compared with a distinguished multi-objective genetic algorithm, i.e. SPEA-II. The computational results show that the proposed MOPS performs better than the genetic algorithm, especially for the large-sized problems.     

A General Model of Some Inverse Combinatorial Optimization Problems and Its Solution Method Under l ∞ Norm

This paper proposes an optimization model and shows that most inverse combinatorial optimization problems so far discussed can be fit into this model as special cases. We propose a Newton-type algorithm for this model under l norm. This algorithm can solve the model in strongly polynomial time if the subproblem involved is solvable in strongly polynomial time for any fixed value of the parameter appearing in the subproblem, and it is shown that most particular inverse optimization problems encountered are this kind. Therefore, through this paper we show that a large group of inverse optimization problems can be handled in a uniform way and solved in strongly polynomial time.     

突发公共事件应急系统中的模糊多目标定位-路径问题研究

本文从应急系统集成优化的角度出发,以应急系统中各资源需求点的应急救援时间满意度之和最大及系统总成本最小为目标,建立了一个应急资源需求和应急救援时间范围均模糊的多目标定位-路径问题(LRP)模型,并提出了一种混合多目标遗传算法。算例分析结果表明,所提模型和算法可以有效解决应急系统优化中的模糊多目标LRP。     

Non‐dominated Time‐Window Policies in City Distribution

Urban freight contributes significantly to pollution, noise disturbance, traffic congestion, and safety problems in city centers. In many cities, local governments have introduced policy measures, in particular time‐access restrictions, to alleviate these problems. However, setting time windows is very challenging due to the conflicting interests and objectives of the stakeholders involved. In this article, we examine whether it is possible to develop time‐window policies that enhance environmental sustainability and distribution efficiencies, while meeting the objectives of the municipalities. We develop a framework for balancing retailer (costs), municipality (satisfaction), and environmental (emissions) objectives, using data envelopment analysis, under different urban time‐window policies. The approach is illustrated by a case study of three Dutch retail organizations, with a large number of stores affected by such time windows. On the basis of an evaluation of 99 different time‐window policies, our results show that harmonizing time windows between neighboring cities leads to the best overall performance. The currently used time‐window policy appears to perform reasonably well, but can be improved on all dimensions . However, harmonizing time‐window policies may be difficult to realize in practice.     

Ant Colony System for a Dynamic Vehicle Routing Problem

An aboundant literature on vehicle routing problems is available. However, most of the work deals with static problems, where all data are known in advance, i.e. before the optimization has started. The technological advances of the last few years give rise to a new class of problems, namely the dynamic vehicle routing problems, where new orders are received as time progresses and must be dynamically incorporated into an evolving schedule. In this paper a dynamic vehicle routing problem is examined and a solving strategy, based on the Ant Colony System paradigm, is proposed. Some new public domain benchmark problems are defined, and the algorithm we propose is tested on them. Finally, the method we present is applied to a realistic case study, set up in the city of Lugano (Switzerland).     

New Methods for Resolving Conflicting Requests with Examples from Medical Residency Scheduling

In scheduling medical residents, the objective is often to maximize resident satisfaction across the space of feasible schedules, relative to the many hard constraints that ensure appropriate patient coverage, adequate training opportunities, etc. A common metric of resident satisfaction is the number of time‐off requests that are granted. Simply maximizing this total, however, may lead to undesirable schedules since some requests have higher priority than others. For example, it might be better to grant one resident's request for a family member's wedding in place of two residents’ requests to attend a rugby game. Another approach is to assign a weight to each request and maximize the total weight of granted requests, but determining weights that accurately represent residents’ and schedulers’ preferences can be quite challenging. Instead, we propose to identify the exhaustive collection of maximally feasible and minimally infeasible sets of requests which can then be used by schedulers to select their preferred solution. Specifically, we have developed two algorithms, which we call Sequential Request Selection Via Cuts (Sequential RSVC) and Simultaneous Request Selection Via Cuts (Simultaneous RSVC), to identify these sets by solving two sequences of optimization problems. We present these algorithms along with computational results based on a real‐world problem of scheduling residents at the University of Michigan C.S. Mott Pediatric Emergency Department. Although we focus our exposition on the problem of resident scheduling, our approach is applicable to a broad class of problems with soft constraints.     

Minimization of maximum lateness under linear deterioration

This paper considers a single-machine scheduling problem to minimize the maximum lateness. The processing time of each job is a linear function of the time when the job starts processing. This problem is known to be -hard in the literature. In this paper, we design a branch-and-bound algorithm for deriving exact solutions by incorporating several properties concerning dominance relations and lower bounds. These properties produce synergic effects in accelerating the solution finding process such that the algorithm can solve problems of 100 jobs within 1 min on average. To compose approximate solutions, we revise a heuristic algorithm available in the literature and propose several hybrid variants. Numerical results evince that the proposed approaches are very effective in successfully reporting optimal solutions for most of the test cases.     

基于愿景满意度函数的多属性群决策方法

针对定性和定量属性相混合的多属性群决策问题，提出基于愿景满意度函数的多属性群决策方法。该方法从损失和收益的角度考虑问题，通过计算标准化的愿景值和属性值之间的距离，建立考虑专家不同风险态度的愿景满意度函数，求得专家各自的满意度，最后应用简单加权算子集结专家的排序结果。通过案例分析和算法对比说明了该算法可适用于不同风险态度的专家进行决策，而风险态度和愿景值的分析结果表明当属性不确定性较大时，专家看重损失或者收益取决于专家的风险态度和愿景值的高低，该方法可为参与决策的双方提供有价值的参考意见。