A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints

We present a metaheuristic methodology for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints (2L-CVRP). 2L-CVRP is a generalisation of the Capacitated Vehicle Routing Problem, in which customer demand is formed by a set of two-dimensional, rectangular, weighted items. The purpose of this problem is to produce the minimum cost routes, starting and terminating at a central depot, to satisfy the customer demand. Furthermore, the transported items must be feasibly packed into the loading surfaces of the vehicles. We propose a metaheuristic algorithm which incorporates the rationale of Tabu Search and Guided Local Search. The loading aspects of the problem are tackled using a collection of packing heuristics. To accelerate the search process, we reduce the neighbourhoods explored, and employ a memory structure to record the loading feasibility information. Extensive experiments were conducted to calibrate the algorithmic parameters. The effectiveness of the proposed metaheuristic algorithm was tested on benchmark instances and led to several new best solutions.     

Dynamic routing in open queueing networks: Brownian models,cut constraints and resource pooling

We present an introductory review of recent work on the control of open queueing networks. We assume that customers of different types arrive at a network and pass through the system via one of several possible routes; the set of routes available to a customer depends on its type. A route through the network is an ordered set of service stations: a customer queues for service at each station on its route and then leaves the system. The two methods of control we consider are the routing of customers through the network, and the sequencing of service at the stations, and our aim is to minimize the number of customers in the system. We concentrate especially on the insights which can be obtained from heavy traffic analysis, and in particular from Harrison's Brownian network models. Our main conclusion is that in many respects dynamic routingsimplifies the behaviour of networks, and that under good control policies it may well be possible to model the aggregate behaviour of a network quite straightforwardly.Supported by SERC grant GR/F 94194.     

Inventory constrained maritime routing and scheduling for multi-commodity liquid bulk,Part I: Applications and model

This paper formulates a model for finding a minimum cost routing in a network for a heterogeneous fleet of ships engaged in pickup and delivery of several liquid bulk products. The problem is frequently encountered by maritime chemical transport companies, including oil companies serving an archipelago of islands. The products are assumed to require dedicated compartments in the ship. The problem is to decide how much of each product should be carried by each ship from supply ports to demand ports, subject to the inventory level of each product in each port being maintained between certain levels that are set by the production rates, the consumption rates, and the storage capacities of the various products in each port. This important and challenging inventory constrained multi-ship pickup–delivery problem is formulated as a mixed-integer nonlinear program. We show that the model can be reformulated as an equivalent mixed-integer linear program with special structure. Over 100 test problems are randomly generated and solved using CPLEX 7.5. The results of our numerical experiments illuminate where problem structure can be exploited in order to solve larger instances of the model. Part II of the sequel will deal with new algorithms that take advantage of model properties.     

An application of Special Ordered Sets to a periodic milk collection problem

We present an OR-based approach to support a milk collection problem in a special branch of dairy industry. The annual growth of the sector and the continuous imbalance between milk supply and demand, has urged the sector to look for a different approach to their daily milk collection problem. Specific details of the problem environment (i.e., the continuous production on supply level and the delivery conditions on demand level) gave rise to choose for a short- to medium-term planning approach. The proposed decision support system has to be considered as an efficient tool for generating stable milk collection plans which in turn also serves as an effective starting point for the vehicle routing problem. From a computational point of view it turned out that the application of Special Ordered Sets type 1 (SOS1) was very useful. Although it appears from literature that the computational advantage of SOS1 is restricted to supplementary model conditions, this study shows that these conditions are not necessarily needed.     

基于三维矩阵重构争论有向图的域间路由振荡检测算法

边界网关协议(Border G atew ay P rotoco l,BGP)是当前In ternet域间路由协议的事实标准,基于策略的路由选择过程使它不再是严格意义上的距离矢量协议,也不再具有距离矢量协议的收敛性.V aradhan指出,自治系统各自为政的策略配置方式会导致全局策略冲突,引起永久性的路由振荡.针对该问题,G riffin利用稳定路径问题(S tab le Path P rob lem,SPP)模型形式化的抽象出BGP协议行为,并以此为基础提出了一种分布式的策略冲突检测算法,尽管该算法完全避免了传统方法的缺陷,但仍然存在泄漏策略信息和对BGP协议改动太大以及浪费网络资源的问题.本文提出了一种基于安全多方计算的检测路由策略冲突的方法,用于在怀疑BGP路由发生振荡时,动态的检测系统中是否存在策略冲突.该方法采纳了G riffin的理论基础,同时由于巧妙的运用了安全多方计算协议,可以完全解决G riffin算法的问题,具有很好的实用性.     

Route stability in vehicle routing decisions: a bi-objective approach using metaheuristics

In this paper, we argue that vehicle routing solutions are often tactical decisions, that should not be changed too often or too much. For marketing or other reasons, vehicle routing solutions should be stable, i.e. a new solution (when e.g. new customers require service) should be as similar as possible to a solution already in use. Simultaneously however, this new solution should still have a good quality in the traditional sense (e.g. small total travel cost). In this paper, we develop a way to measure the difference between two vehicle routing solutions. We use this distance measure to create a metaheuristic approach that will find solutions that are “close” (in the solution space) to a given baseline solution and at the same time have a high quality in the sense that their total distance traveled is small. By using this approach, the dispatcher is offered a choice of Pareto-optimal solutions, allowing him to make a trade-off between changing his existing solution and allowing a longer travel distance. Some experiments are performed to show the effectiveness of the approach.     

Product form in networks of queues with batch arrivals and batch services

A product form equilibrium distribution is derived for a class of queueing networks in either discrete or continuous time, in which multiple customers arrive simultaneously and batches of customers complete service simultaneously.     

The bi-objective Pollution-Routing Problem

The bi-objective Pollution-Routing Problem is an extension of the Pollution-Routing Problem (PRP) which consists of routing a number of vehicles to serve a set of customers, and determining their speed on each route segment. The two objective functions pertaining to minimization of fuel consumption and driving time are conflicting and are thus considered separately. This paper presents an adaptive large neighborhood search algorithm (ALNS), combined with a speed optimization procedure, to solve the bi-objective PRP. Using the ALNS as the search engine, four a posteriori methods, namely the weighting method, the weighting method with normalization, the epsilon-constraint method and a new hybrid method (HM), are tested using a scalarization of the two objective functions. The HM combines adaptive weighting with the epsilon-constraint method. To evaluate the effectiveness of the algorithm, new sets of instances based on real geographic data are generated, and a library of bi-criteria PRP instances is compiled. Results of extensive computational experiments with the four methods are presented and compared with one another by means of the hypervolume and epsilon indicators. The results show that HM is highly effective in finding good-quality non-dominated solutions on PRP instances with 100 nodes.     

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

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