考虑紧急度的救灾车辆路径问题建模与优化

为了减少救灾物资配送的延误时间和救灾车辆的总运输时间，引入紧急度的概念，建立了基于紧急度的救灾物资车辆路径问题模型，并设计了一种改进遗传算法对该模型进行求解。首先，采用多种策略生成初始种群；然后，提出一种基于紧急度的任务再分配算法作为局部搜索算子，该算法依据紧急度为延误安置点重新安排配送车辆或调整配送顺序从而减少延误时间，对无延误的车辆优化其路线从而减少总运输时间，以达到延误时间和总运输时间两者最优。在17个数据集上与先来先服务（FCFS）算法、按紧急度排序（URGS）算法和遗传算法（GA）三种算法进行了对比。实验结果表明，具有基于紧急度的任务再分配策略的遗传算法（TRUD-GA）与GA相比，平均延误时间减少25.0%，平均运输时间减少1.9%，与FCFS、URGS算法相比改进则更加明显。     

面向防汛物资动态变化的运输车辆调度优化算法研究

为解决防汛救灾过程中受灾需求变化下的防汛物资调度问题,提出一种面向防汛物资动态变化的运输车辆调度优化算法(SOA_TV).在SOA_TV算法中,考虑车辆限载、调度车辆数量、移动距离等约束,建立防汛物资运力调度优化模型.依据已知受灾信息和仓储信息,确定受灾最小所需车辆数,获得待运输物资集合,并按照最近邻原则初始化车辆集合.引入车辆移动距离阈值,通过边权计算构建二分图,并进行矩阵转换,获得一个低维度的矩阵.最后,考虑需求不变化和动态变化两种情况下的物资分配,根据仓库点之间的运输距离和车辆负载情况更新边权值,多次执行KM算法直到获得目标模型的近似最优解.实验结果表明:在多种实验场景中,SOA_TV都能寻找到一个较优解.相比于GA和ABC,SOA_TV虽然略微降低了车辆移动总距离,但其运算时间获得大幅度削减,可在极短的时间内计算获得较优的车辆分配方案.相较于Hungarian,SOA_TV可降低运行时间和车辆移动总距离.     

灾后应急成品粮物流网络库存控制模型仿真

为解决各物流节点库存的不合理分配,构建基于库存价值不变的最优库存控制模型。基于连续型需求的随机库存订货模型确保物流网络库存成本最小、社会效益最大,采用"先进先出"原则解决成品粮贬值问题,合理控制成品粮物流网络库存量;根据救灾区域的成品粮物流网络分布情况与各等级物流节点救灾能力,分配成品粮物流网络节点库存,实现灾后应急成品粮物流网络库存最优控制。仿真结果表明,上述模型可实现高救灾保障、低救灾成本的成品粮物流网络库存控制,满足对灾后应急成品粮的供应需求。     

Variable neighbourhood search and tabu search for a discrete time/cost trade-off problem to minimize the maximal cash flow gap

This paper addresses a project scheduling problem (PSP) where the activities can be performed with several discrete modes and with four different payment patterns. Cash outflows depend on the activities’ execution modes, while cash inflows are determined by the payment pattern. Under project deadline constraints, the objective is to minimize the maximal cash flow gap, which is defined as the greatest gap between the accumulative cash inflows and outflows over the course of the project. Based on the definition of the problem, the optimization models are constructed using the activity-based method. Due to the NP-hardness of the problem, the mixed and nested versions of variable neighbourhood search (VNS), tabu search (TS), and variable neighbourhood search with tabu search (VNS-TS) are developed. Based on the characteristics of the problem, two improvement measures are proposed and embedded into the algorithms. Through a computational experiment conducted on a data set generated randomly, the performance of the developed algorithms, the contributions of the improvement measures, and the effects of the key parameters on the objective function are analysed. Based on the computational results, the following conclusions are drawn: Among the algorithms developed, the nested version of the VNS-TS is the most promising algorithm, especially for larger problems. The maximal cash flow gap decreases with the increase of the advance payment proportion, payment number, payment proportion, or project deadline. Among the four payment patterns, the expense based and progress based payment patterns may be more favourable for contractors to decrease the gap. The research in this paper has practical implications for contractors to smooth their cash flows and academic implications for project scheduling research due to the introduction of a new objective.     

Heuristics for the capacitated modular hub location problem

In this paper we study the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a modular way, as a factor of the number of flights. We propose heuristic methods to obtain high-quality solutions in short computing times. Specifically, we implement memory structures to create advanced search methods and compare them with previous heuristics on a set of benchmark instances. Memory structures have been widely implemented in the context of the tabu search methodology, usually embedded in local search algorithms. In this paper we explore an alternative design in which the constructive method is enhanced with frequency information and the local search is coupled with a path relinking post-processing. Statistical tests confirm the superiority of our proposal with respect to previous developments.     

New simple and efficient heuristics for the uncapacitated single allocation hub location problem

Hub-and-spoke networks are widely studied in the area of location theory. They arise in several contexts, including passenger airlines, postal and parcel delivery, and computer and telecommunication networks. Hub location problems usually involve three simultaneous decisions to be made: the optimal number of hub nodes, their locations and the allocation of the non-hub nodes to the hubs. In the uncapacitated single allocation hub location problem (USAHLP) hub nodes have no capacity constraints and non-hub nodes must be assigned to only one hub. In this paper, we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve this problem. With multi-start heuristics, several different initial solutions are constructed and then improved by tabu search, while in the two-stage integrated heuristic tabu search is applied to improve both the locational and allocational part of the problem. Computational experiments using typical benchmark problems (Civil Aeronautics Board (CAB) and Australian Post (AP) data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. We also report the integer optimal solutions for all 80 CAB data set instances and the 12 AP instances up to 100 nodes, as well as for the corresponding new generated AP instances with reduced fixed costs.     

Hybrid column generation and large neighborhood search for the dial-a-ride problem

Demographic change towards an ever aging population entails an increasing demand for specialized transportation systems to complement the traditional public means of transportation. Typically, users place transportation requests, specifying a pickup and a drop off location and a fleet of minibuses or taxis is used to serve these requests. The underlying optimization problem can be modeled as a dial-a-ride problem. In the dial-a-ride problem considered in this paper, total routing costs are minimized while respecting time window, maximum user ride time, maximum route duration, and vehicle capacity restrictions. We propose a hybrid column generation and large neighborhood search algorithm and compare different hybridization strategies on a set of benchmark instances from the literature.     

卡车-无人机协同救灾物资避障配送问题研究

针对洪涝灾害中存在积水障碍区的卡车-无人机协同配送的最优路径及最短配送时间问题,建立了一种整数规划模型,并提出了一种两阶段启发式算法,第一阶段将积水障碍区进行二维网格化处理并确定无人机运输救灾物资时卡车的安全等待点以及各等待点无人机运送客户的集合,第二阶段提出阶段性规划算法,结合改进A*算法与非线性收敛因子的模拟退火鲸鱼算法对卡车绕积水障碍区的配送路径进行优化,在确保卡车行使安全的前提下,将A*算法的全局寻优性及鲸鱼算法的局部搜索精确性结合。解决存在积水障碍区的救灾物资配送问题,最后通过实例验证了所提出方法可以快速安全地解决洪涝灾害中救灾物资的避障配送问题。     

An exact algorithm for the modular hub location problem with single assignments

A key feature of hub-and-spoke networks is the consolidation of flows at hub facilities. The bundling of flows allows reduction in the transportation costs, which is frequently modeled using a constant discount factor that is applied to the flow cost associated with all interhub links. In this paper, we study the modular hub location problem, which explicitly models the flow-dependent transportation costs using modular arc costs. It neither assumes a full interconnection between hub nodes nor a particular topological structure, instead it considers link activation decisions as part of the design. We propose a branch-and-bound algorithm that uses a Lagrangean relaxation to obtain lower and upper bounds at the nodes of the enumeration tree. Numerical results are reported for benchmark instances with up to 75 nodes.     

Solving the hub location problem with modular link capacities

This paper deals with a capacitated hub location problem arising in the design of telecommunications networks. The problem is different from the classical hub location problem in two ways: the cost of using an edge is not linear but stepwise and the capacity of a hub restricts the amount of traffic transiting through the hub rather than the incoming traffic. In this paper both an exact and a heuristic method are presented. They are compared and combined in a heuristic concentration approach to investigate whether it is possible to improve the results within limited computational times.     

A new stochastic approach for a reliable p-hub covering location problem

A hub location problem (HLP) is a fertile research field, in the aspect of interdisciplinary studies, such as transportation, operation research, network design, telecommunication and economics. The location of hub facilities and allocation of non-hub nodes to hubs configure the backbone of HLPs. This study presents a new mathematical model for a reliable HLP by a new stochastic approach to minimize the total transportation cost and obtain maximum flows that the network can carry, when its link capacities are subject to stochastic degradations, as in a form of daily traffic, earthquake, flood, etc. We consider the road capacity reliability as a probability that ensures the maximum network capacity is greater than or equal to the total incoming flow to the network by considering the road capacity as random variable. As a result, this paper assumes that link capacities satisfy in a Truncated Erlang $(\mathit{TErl})$ distribution function. Due to complexity of the HLP, a meta-heuristic algorithm, namely differential evolution (DE) algorithm, is applied on the problem in order to achieve near-optimal solutions. Furthermore, the performance of the proposed algorithm (i.e., DE) is evaluated by the performance of the genetic algorithm (GA) applied on the given problem. Some computational experiments are presented to illustrate the effectiveness of the presented model and proposed algorithm. Finally the conclusion is provided.     

基于改进GA的救援物资中转网点定位

针对大规模救援物资调运的多目标中转运输网点定位问题,考虑运输费用、中转网点的作业变动费用和运输时间,建立一个救援物资中转运输网点的非线性多目标混合整数规划模型。为有效求解该模型,提出一种基于矩阵编码的遗传算法,利用费用矩阵标杆的寻优导向信息提高遗传变异算子的局部搜索能力,提高全局收敛速度。通过算例分析验证该模型和算法的有效性。     

区际救援物资中转运输网点的定位—配给问题研究*

为增强大规模区际救援物资联动调运的效率,建立了救援物资中转网点的定位—配给模型,并设计了一种运用矩阵编码的遗传算法。在算法流程设计中,为提高标准遗传算法求解非线性运输问题的寻优速度和寻优效能,参照费用矩阵标杆的寻优导向信息来指导种群中每个个体局部的精细搜索空间。最后通过算例分析验证了该模型和算法的有效性。     

Hub network design problem in the presence of disruptions

The main issue in p-hub median problem is locating hub facilities and allocating spokes to those hubs in order to minimize the total transportation cost. However hub facilities may fail occasionally due to some disruptions which could lead to excessive costs. One of the most effective ways to hedge against disruptions especially intentional disruptions is designing more reliable hub networks. In this paper, we formulate the multiple allocation p-hub median problem under intentional disruptions by a bi-level model with two objective functions at the upper level and a single objective at the lower level. In this model, the leader aims at identifying the location of hubs so that minimize normal and worst-case transportation costs. Worst-case scenario is modeled in the lower level where the follower’s objective is to identify the hubs that if lost, it would mostly increase the transportation cost. We develop two multi-objective metaheuristics based on simulated annealing and tabu search to solve the problem. Computational results indicate the viability and effectiveness of the proposed algorithms for exploring the non-dominated solutions.     

Emergency facility location under random network damage: Insights from the Istanbul case

Damage to infrastructure, especially to highways and roads, adversely affects accessibility to disaster areas. Predicting accessibility to demand points from the supply points by a systematic model would lead to more effective emergency facility location decisions. To this effect, we model the spatial impact of the disaster on network links by random failures with dependency such that failure of a link induces failure of nearby links that are structurally more vulnerable. For each demand point, a set of alternative paths is generated from each potential supply point so that the shortest surviving path will be used for relief transportation after the disaster. The objective is to maximize the expected demand coverage within a specified distance over all possible network realizations. To overcome the computational difficulty caused by extremely large number of possible outcomes, we propose a tabu search heuristic that evaluates candidate solutions over a sample of network scenarios. The scenario generation algorithm that represents the proposed distance and vulnerability based failure model is the main contribution of our study. The tabu search algorithm is applied to Istanbul earthquake preparedness case with a detailed analysis comparing solutions found in no link failure, independent link failure, and dependent link failure cases. The results show that incorporating dependent link failures to the model improves the covered demand percentages significantly.     

Spatial Analysis of Single Allocation Hub Location Problems

Hubs are special facilities that serve as switching, transshipment and sorting nodes in many-to-many distribution systems. Flow is consolidated at hubs to exploit economies of scale and to reduce transportation costs between hubs. In this article, we first identify general features of optimal hub locations for single allocation hub location problems based on only the fundamental problem data (demand for travel and spatial locations). We then exploit this knowledge to develop a straightforward heuristic methodology based on spatial proximity of nodes, dispersion and measures of node importance to delineate subsets of nodes likely to contain optimal hubs. We then develop constraints for these subsets for use in mathematical programming formulations to solve hub location problems. Our methodology can also help narrow an organization’s focus to concentrate on more detailed and qualitative analyses of promising potential hub locations. Results document the value of including both demand magnitude and centrality in measuring node importance and the relevant tradeoffs in solution quality and time.     

现货市场补充作用下基于总量折扣的运输服务采购问题研究

产品需求的不确定性使得企业经常产生临时性或突发性的物流需求,物流服务现货市场采购在应对上述物流需求时发挥了重要的作用.在物流服务采购决策过程中,长期合同采购所提供的价格折扣受采购量的影响,因此对托运企业而言,如何平衡长期合同采购以及现货市场采购,从而在满足其物流需求的基础上使得总体采购成本最低,成为一个需要解决的问题.基于托运人的角度,建立以最小化运输服务采购成本及最大化整体满意度为目标,综合考虑承托双方偏好、承运方总量折扣及承运方运力接受范围等因素的运输服务混合采购决策模型,并设计多目标粒子群算法对上述模型进行求解.通过算例分析验证所提模型及算法的有效性,算例结果表明,所建立的模型可显著降低运输服务总采购成本,并有效提升整体的满意度水平,研究成果对于降低运输服务采购成本、促进承托双方的稳定合作具有一定的理论意义.     

Group search optimizer based optimal location and capacity of distributed generations

This paper presents a novel efficient population-based heuristic approach for optimal location and capacity of distributed generations (DGs) in distribution networks, with the objectives of minimization of fuel cost, power loss reduction, and voltage profile improvement. The approach employs an improved group search optimizer (iGSO) proposed in this paper by incorporating particle swarm optimization (PSO) into group search optimizer (GSO) for optimal setting of DGs. The proposed approach is executed on a networked distribution system—the IEEE 14-bus test system for different objectives. The results are also compared to those that executed by basic GSO algorithm and PSO algorithm on the same test system. The results show the effectiveness and promising applications of the proposed approach in optimal location and capacity of DGs.     

Scatter search algorithm for supplier selection and order lot sizing under multiple price discount environment

Supplier selection is one the most important elements of supply chain management. This function involves evaluation of many factors such as, cost of parts/materials, size of order, quality, and delivery performance. Therefore, this problem is categorized as multi-criteria decision making problems. Different approaches have been applied in order to assess and select the suppliers when suppliers offer discount on the unit price. In practical conditions, buyers may face a situation where different types of discount may be offered by candidate suppliers. None of the previous studies have considered different discount schemes simultaneously. In this article a mathematical model is introduced which consider different types of discount (all-unit cost, incremental discount, and total business volume discount) through multi-objective formulation for single item purchasing problem. In addition, constraints such as suppliers’ capacity and demand are taken into consideration in the model. Due to the complexity of the problem a proposed scatter search algorithm (SSA) is presented to solve this problem. Finally several sample problems have been solved by the proposed SSA and the exact (branch and bound) method. The results illustrate slight relative errors to compare with reasonable saving in computational times.     

The optimization of warehouse location and resources distribution for emergency rescue under uncertainty

China is one of the countries that suffer the most natural disasters in the world. The situation of emergency response and rescue is extremely tough. Establishing the emergency warehouse is one of the important ways to cope with rapid-onset disasters. In this paper, a mixed integer programming (MIP) model based on time cost under uncertainty is proposed, which help solve the emergency warehouse location and distribution problem. Comprehensive consideration of factors such as time cost, penalty cost for lack of resources, alternative origins of resources from both suppliers and emergency warehouses, different means of transportation and multiple resources types are involved in our study. We also introduce uncertain scenarios to describe the severity of the disaster. Particle swarm optimization (PSO) and variable neighborhood search (VNS) are designed to solve the MIP model of different scales of instances. Numerous examples have been tested to compare two heuristics with commercial solver (CPLEX). Both of two algorithms can obtain the exact solution same as CPLEX in small-scale instances while show great performance on larger instances with 10 candidate warehouses, 25 disasters and 50 scenarios.