车辆路径问题的改进遗传算法

提出一种基于遗传算法的求解车辆路径问题的新算法,避免传统遗传算法处理不可行约束条件中惩罚项系数选取不当所出现的问题.同时,通过现实例子分析该算法的优劣性,实验结果表明该算法是一种有效的算法.     

A variable neighborhood search for the capacitated arc routing problem with intermediate facilities

The capacitated arc routing problem (CARP) focuses on servicing edges of an undirected network graph. A wide spectrum of applications like mail delivery, waste collection or street maintenance outlines the relevance of this problem. A realistic variant of the CARP arises from the need of intermediate facilities (IFs) to load up or unload the service vehicle and from tour length restrictions. The proposed Variable Neighborhood Search (VNS) is a simple and robust solution technique which tackles the basic problem as well as its extensions. The VNS shows excellent results on four different benchmark sets. Particularly, for all 120 instances the best known solution could be found and in 71 cases a new best solution was achieved.     

冷原子介质中基于相干诱导高反射带和高透射带的全光路由控制

以相干诱导光子带隙结构为工作基础,提出了一种可对两个弱光信号的传播路径同时进行动态调控的新型全光路由控制方案。利用描述光波在空间周期介质中相干散射的传输矩阵理论,结合描述单频激光与多能级原子共振相互作用的密度矩阵方程,计算了作为控制媒介的相干驱动超冷原子系综的稳态反射光谱和稳态透射光谱。结果表明,通过改变两个较强相干激光的空间模式、强度和频率等参数,可在探测跃迁共振频率附近建立反射率约为95%或者透射率约为95%的两个特殊频带。对这样的相干诱导高反射带和高透射带进行了实时动态调控,可根据需要引导两个不同频率的弱光信号进入指定的网络通道。该方案很好地满足了在量子信息处理领域对弱光信号进行全光路由控制时的低损耗和低形变要求。     

基于社团结构的负载传输优化策略研究

研究表明网络社团结构特征对负载传输有影响,明显社团结构特征会降低网络的承载能力.由于最短路由策略在选择路由时有一定的随机性,本文提出了一种基于社团结构的负载传输策略,减少最短路由经过的社团数量,从而降低社团边缘节点的介数.实验结果显示,该策略在保证最短路由小世界特性的同时,提升了网络的承载能力,社团划分得越准确传输优化策略效果越显著. 关键词： 优化路由策略 社团结构 复杂网络 负载传输     

Requiem for the Miller–Tucker–Zemlin subtour elimination constraints?

The Miller–Tucker–Zemlin (MTZ) Subtour Elimination Constraints (SECs) and the improved version by Desrochers and Laporte (DL) have been and are still in regular use to model a variety of routing problems. This paper presents a systematic way of deriving inequalities that are more complicated than the MTZ and DL inequalities and that, in a certain way, “generalize” the underlying idea of the original inequalities. We present a polyhedral approach that studies and analyses the convex hull of feasible sets for small dimensions. This approach allows us to generate generalizations of the MTZ and DL inequalities, which are “good” in the sense that they define facets of these small polyhedra. It is well known that DL inequalities imply a subset of Dantzig–Fulkerson–Johnson (DFJ) SECs for two-node subsets. Through the approach presented, we describe a generalization of these inequalities which imply DFJ SECs for three-node subsets and show that generalizations for larger subsets are unlikely to exist. Our study presents a similar analysis with generalizations of MTZ inequalities and their relation with the lifted circuit inequalities for three node subsets.     

Implicit depot assignments and rotations in vehicle routing heuristics

Vehicle routing variants with multiple depots and mixed fleet present intricate combinatorial aspects related to sequencing choices, vehicle type choices, depot choices, and depots positioning. This paper introduces a dynamic programming methodology for efficiently evaluating compound neighborhoods combining sequence-based moves with an optimal choice of vehicle and depot, and an optimal determination of the first customer to be visited in the route, called rotation. The assignment choices, making the richness of the problem, are thus no more addressed in the solution structure, but implicitly determined during each move evaluation. Two meta-heuristics relying on these concepts, an iterated local search and a hybrid genetic algorithm, are presented. Extensive computational experiments demonstrate the remarkable performance of these methods on classic benchmark instances for multi-depot vehicle routing problems with and without fleet mix, as well as the notable contribution of the implicit depot choice and positioning methods to the search performance. New state-of-the-art results are obtained for multi-depot vehicle routing problems (MDVRP), and multi-depot vehicle fleet mix problems (MDVFMP) with unconstrained fleet size. The proposed concepts are fairly general, and widely applicable to many other vehicle routing variants.     

A survey of recent research on location-routing problems

The design of distribution systems raises hard combinatorial optimization problems. For instance, facility location problems must be solved at the strategic decision level to place factories and warehouses, while vehicle routes must be built at the tactical or operational levels to supply customers. In fact, location and routing decisions are interdependent and studies have shown that the overall system cost may be excessive if they are tackled separately. The location-routing problem (LRP) integrates the two kinds of decisions. Given a set of potential depots with opening costs, a fleet of identical vehicles and a set of customers with known demands, the classical LRP consists in opening a subset of depots, assigning customers to them and determining vehicle routes, to minimize a total cost including the cost of open depots, the fixed costs of vehicles used, and the total cost of the routes. Since the last comprehensive survey on the LRP, published by Nagy and Salhi (2007), the number of articles devoted to this problem has grown quickly, calling a review of new research works. This paper analyzes the recent literature (72 articles) on the standard LRP and new extensions such as several distribution echelons, multiple objectives or uncertain data. Results of state-of-the-art metaheuristics are also compared on standard sets of instances for the classical LRP, the two-echelon LRP and the truck and trailer problem.     

An iterated local search algorithm for the vehicle routing problem with backhauls

The Vehicle Routing Problem with Backhauls (VRPB) is an extension of the VRP that deals with two types of customers: the consumers (linehaul) that request goods from the depot and the suppliers (backhaul) that send goods to the depot. In this paper, we propose a simple yet effective iterated local search algorithm for the VRPB. Its main component is an oscillating local search heuristic that has two main features. First, it explores a broad neighborhood structure at each iteration. This is efficiently done using a data structure that stores information about the set of neighboring solutions. Second, the heuristic performs constant transitions between feasible and infeasible portions of the solution space. These transitions are regulated by a dynamic adjustment of the penalty applied to infeasible solutions. An extensive statistical analysis was carried out in order to identify the most important components of the algorithm and to properly tune the values of their parameters. The results of the computational experiments carried out show that this algorithm is very competitive in comparison to the best metaheuristic algorithms for the VRPB. Additionally, new best solutions have been found for two instances in one of the benchmark sets. These results show that the performance of existing metaheuristic algorithms can be considerably improved by carrying out a thorough statistical analysis of their components. In particular, it shows that by expanding the exploration area and improving the efficiency of the local search heuristic, it is possible to develop simpler and faster metaheuristic algorithms without compromising the quality of the solutions obtained.     

Constant-factor approximations for Capacitated Arc Routing without triangle inequality

Given an undirected graph with edge costs and edge demands, the Capacitated Arc Routing problem (CARP) asks for minimum-cost routes for equal-capacity vehicles so as to satisfy all demands. Constant-factor polynomial-time approximation algorithms were proposed for CARP with triangle inequality, while CARP was claimed to be NP-hard to approximate within any constant factor in general. Correcting this claim, we show that any factor  α$\alpha$ approximation for CARP with triangle inequality yields a factor  α$\alpha$ approximation for the general CARP.     

神经网络在平面布线 中的应 用

Hopfield给出N个节点完全图K，中求最短Hamilton圈的神经网络方法，若将无自环图看做K，的子图，不难求出Hamilton图的Hamilton圈.不过当节点数增多时，解神经网络动态方程常得到次优解，和Hamilton圈差一两条边，称为准Hamilton圈.利用Hamilton圈和准Hamilton圈，可以画出一个平面图的平面化图，或者将一个非平面图分解为平面化子图，以便平面布线.