Routing trains through a railway station based on a node packing model

In this paper, we describe the problem of routing trains through a railway station. This routing problem is a subproblem of the automatic generation of timetables for the Dutch railway system. The problem of routing trains through a railway station is the problem of assigning each of the involved trains to a route through the railway station, given the detailed layout of the railway network within the station and given the arrival and departure times of the trains. When solving this routing problem, several aspects such as capacity, safety, and customer service have to be taken into account. In this paper, we describe this routing problem in terms of a weighted node packing problem. Furthermore, we describe an algorithm for solving this routing problem to optimality. The algorithm is based on preprocessing, valid inequalities, and a branch-and-cut approach. The preprocessing techniques aim at identifying superfluous nodes which can be removed from the problem instance. The characteristics of the preprocessing techniques with respect to propagation are investigated. We also present the results of a computational study in which the model, the preprocessing techniques and the algorithm are tested based on data related to the railway stations Arnhem, Hoorn and Utrecht CS in the Netherlands.     

GIS technology as an environment for testing an advanced mathematical model for optimization of road maintenance

In the paper, we consider a Chinese postman problem and show how integration of an advanced mathematical model with GIS technology can be beneficial providing a powerful tool for developing, testing and applying sophisticated heuristics for arc routing problems. We give details of an implementation of several recently developed heuristics for the Chinese postman problem with priority nodes that are integrated with GIS software. In the end, we show how a GIS visualization can be helpful in finding and presenting the results.     

Epistemic irrelevance in credal nets: The case of imprecise Markov trees

We focus on credal nets, which are graphical models that generalise Bayesian nets to imprecise probability. We replace the notion of strong independence commonly used in credal nets with the weaker notion of epistemic irrelevance, which is arguably more suited for a behavioural theory of probability. Focusing on directed trees, we show how to combine the given local uncertainty models in the nodes of the graph into a global model, and we use this to construct and justify an exact message-passing algorithm that computes updated beliefs for a variable in the tree. The algorithm, which is linear in the number of nodes, is formulated entirely in terms of coherent lower previsions, and is shown to satisfy a number of rationality requirements. We supply examples of the algorithm’s operation, and report an application to on-line character recognition that illustrates the advantages of our approach for prediction. We comment on the perspectives, opened by the availability, for the first time, of a truly efficient algorithm based on epistemic irrelevance.     

Autonomous localization based energy saving mechanism in indoor MANETs using ACO

The biggest challenge in MANETs is to find most efficient routing due to the changing topology and energy constrained battery operated computing devices. It has been found that Ant Colony Optimization (ACO) is a special kind of optimization technique having characterization of Swarm Intelligence (SI) which is highly suitable for finding the adaptive routing for such a type of volatile network. The proposed ACO routing algorithm uses position information and energy parameters as a routing metric to improve the performance and lifetime of network. Typical routing protocols have fixed transmission power irrespective of the distance between the nodes. Considering limiting factors, like small size, limited computational power and energy source, the proposed solution excludes use of GPS for identifying the distance between nodes for indoor MANETs. The distance between nodes can be determined by using Received Signal Strength Indicator (RSSI) measurements. Thus, an intelligent ACO routing algorithm with location information and energy metric is developed to adaptively adjust the transmission power and distribute the load to avoid critical nodes. Proposed Autonomous Localization based Eligible Energetic Path_with_Ant Colony Optimization (ALEEP_with_ACO) algorithm ensures that nodes in the network are not drained out of the energy beyond their threshold, as the load is shared with other nodes, when the energy of a node in the shortest path has reached its threshold. Hence, the total energy expenditure is reduced, thus prolonging the lifetime of network devices and the network. We simulated our proposal and compared it with the classical approach of AODV and other biological routing approaches. The results achieved show that ALEEP_with_ACO presents the best Packet Delivery Ratio (PDR), throughput and less packet drop specially under high mobility scenarios.     

Routing multiterminal nets on a hexagonal grid

Channel routing is a vital task in the layout design of VLSI circuits. Multiterminal channel routing is different from two-terminal one. While the later is quite understood, the former still poses the difficulty. In this paper, we investigate the multiterminal channel routing problem in a hexagonal model, whose grid is composed of horizontal tracks, right tracks (with slope +60°), and left tracks (with slope −60°). We present an efficient algorithm for routing multiterminal nets on a channel of width d + 3, where d is the problem density. Furthermore, we can wire the layout produced by the router using four layers and there are no overlaps among different layers. This improves the previous known results [15, 19].     

部分联合运输策略下的物流车辆路径优化问题研究

论文分析了物流车辆路径优化问题的特点,提出了企业自营物流和第三方物流协同运输的部分联合运输策略。根据客户需求节点的特点进行了节点分类,建立了以车辆调用成本、车辆运输成本、第三方物流运输成本之和最小为目标的整数线性规划模型。根据部分联合运输策略下各类客户需求点运输方式特点,构造了一种新的变维数矩阵编码结构,并对传统算法中概率选择操作方式进行修改,提出了一种新的智能优化算法并与枚举法和遗传算法的运算结果进行了算法性能对比分析。结果显示,本文提出的逆选择操作蚁群算法具有较快的运算速度和较高的稳定性,是求解此类问题的一种有效算法。     

A new branching strategy for time constrained routing problems with application to backhauling

In this paper, we explore a new branching strategy for branch-and-bound approaches based on column generation for the vehicle routing problems with time windows. This strategy involves branching on resource variables (time or capacity) rather than on network flow variables. We also examine criteria for selecting network nodes for branching. To test the effectiveness of the branching strategy, we conduct computational experiments on time window constrained vehicle routing problems where backhauling is permitted only after all the shipments to clients have been made. The branching method proved very effective. In cases where time was the more binding constraint, time-based branching succeeded in decreasing the number of nodes explored by two thirds and the total computation time by more than half when compared to flow-based branching. The computational results also show that the overall algorithm was successful in optimally solving problems with up to 100 customers. It produced an average cost decrease of almost 7% when backhauling was permitted as compared to the cost involved when the client and the distributor routes were distinct.     

An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem

We study a selective and periodic inventory routing problem (SPIRP) and develop an Adaptive Large Neighborhood Search (ALNS) algorithm for its solution. The problem concerns a biodiesel production facility collecting used vegetable oil from sources, such as restaurants, catering companies and hotels that produce waste vegetable oil in considerable amounts. The facility reuses the collected waste oil as raw material to produce biodiesel. It has to meet certain raw material requirements either from daily collection, or from its inventory, or by purchasing virgin oil. SPIRP involves decisions about which of the present source nodes to include in the collection program, and which periodic (weekly) routing schedule to repeat over an infinite planning horizon. The objective is to minimize the total collection, inventory and purchasing costs while meeting the raw material requirements and operational constraints. A single-commodity flow-based mixed integer linear programming (MILP) model was proposed for this problem in an earlier study. The model was solved with 25 source nodes on a 7-day cyclic planning horizon. In order to tackle larger instances, we develop an ALNS algorithm that is based on a rich neighborhood structure with 11 distinct moves tailored to this problem. We demonstrate the performance of the ALNS, and compare it with the MILP model on test instances containing up to 100 source nodes.     

Routing optimization in packet switching communication networks

For routing assignments a special model and an optimization algorithm are proposed. The efficiency of the routing assignments is evaluated by the average value of the total cost of delays for all packets in the network. It is the objective function. The main idea is that traffic, which is transmitted from the source node to the destination node, can be split between two or more logical paths. The minimum of the objective function can be found by varying the traffic on every path and simultaneously from all the source nodes to the destination nodes. If this approach is applied, then the objective function is nonseparable and nonlinear. Because its shape is unknown in advance, an adaptive nonlinear optimization algorithm is proposed. For evaluating its efficiency a special set of test functions has been used.     

Rectilinear group Steiner trees and applications in VLSI design

 Given a set of disjoint groups of points in the plane, the rectilinear group Steiner tree problem is the problem of finding a shortest interconnection (under the rectilinear metric) which includes at least one point from each group. This is an important generalization of the well-known rectilinear Steiner tree problem which has direct applications in VLSI design: in the detailed routing phase the logical units typically allow the nets to connect to several electrically equivalent ports. We present a first (tailored) exact algorithm for solving the rectilinear group Steiner tree problem (and related variants of the problem). The algorithm essentially constructs a subgraph of the corresponding Hanan grid on which existing algorithms for solving the Steiner tree problem in graphs are applied. The reductions of the Hanan grid are performed by applying point deletions and by generating full Steiner trees on the remaining points. Experimental results for real-world VLSI instances with up to 100 groups are presented. Received: November 7, 2000 / Accepted: December 19, 2001 Published online: September 5, 2002     

移位交换网的最优路由算法

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式     

A Lagrangean relaxation and decomposition algorithm for the video placement and routing problem

Video on demand (VoD) is a technology used to provide a number of programs to a number of users on request. In developing a VoD system, a fundamental problem is load balancing, which is further characterized by optimally placing videos to a number of predefined servers and routing the user program requests to available resources. In this paper, an exact solution algorithm is described to solve the video placement and routing problem. The algorithm is based on Lagrangean relaxation and decomposition. The novelty of the approach can be described as the use of integer programs to obtain feasible solutions in the algorithm. Computational experimentation reveals that for randomly generated problems with up to 100 nodes and 250 videos, the use of such integer programs help greatly in obtaining good quality solutions (typically within 5% of the optimal solution), even in the very early iterations of the algorithm.     

Heuristic solution approaches for the cumulative capacitated vehicle routing problem

Cumulative capacitated vehicle routing problem (CCVRP) is an extension of the well-known capacitated vehicle routing problem, where the objective is minimization of sum of the arrival times at nodes instead of minimizing the total tour cost. This type of routing problem arises when a priority is given to customer needs or dispatching vital goods supply after a natural disaster. This paper focuses on comparing the performances of neighbourhood and population-based approaches for the new problem CCVRP. Genetic algorithm (GA), an evolutionary algorithm using particle swarm optimization mechanism with GA operators, and tabu search (TS) are compared in terms of required CPU time and obtained objective values. In addition, a nearest neighbourhood-based initial solution technique is also proposed within the paper. To the best of authors’ knowledge, this paper constitutes a base for comparisons along with GA, and TS for further possible publications on the new problem CCVRP.     

Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model

In this paper, we address a variant of the vehicle routing problem called the vehicle routing problem with time windows and multiple routes. It considers that a given vehicle can be assigned to more than one route per planning period. We propose a new exact algorithm for this problem. Our algorithm is iterative and it relies on a pseudo-polynomial network flow model whose nodes represent time instants, and whose arcs represent feasible vehicle routes. This algorithm was tested on a set of benchmark instances from the literature. The computational results show that our method is able to solve more instances than the only other exact method described so far in the literature, and it clearly outperforms this method in terms of computing time.     

Optimal multicast route packing

This paper considers the hop-constrained multicast route packing problem with a bandwidth reservation to build QoS-guaranteed multicast routing trees with a minimum installation cost. Given a set of multicast sessions, each of which has a hop limit constraint and a bandwidth requirement, the problem is to determine the set of multicast routing trees in an arc-capacitated network with the objective of minimizing the cost. For the problem, we propose a branch-and-cut-and-price algorithm, which can be viewed as a branch-and-bound method incorporating both the strong cutting plane algorithm and the column generation method. We implemented and tested the proposed algorithm on randomly generated problem instances with sizes up to 30 nodes, 570 arcs, and 10 multicast sessions. The test results show that the algorithm can obtain the optimal solution to practically sized problem instances within a reasonable time limit in most cases.     

Routing through a generalized switchbox

We present an algorithm for the routing problem for two-terminal nets in generalized switchboxes. A generalized switchbox is any subset R of the planar rectangular grid with no nontrivial holes, i.e., every finite face has exactly four incident vertices. A net is a pair of nodes of nonmaximal degree on the boundary of R. A solution is a set of edge-disjoint paths, one for each net. Our algorithm solves standard generalized switchbox routing problems in time O(n(log n)²) where n is the number of vertices of R, i.e., it either finds a solution or indicates that there is none. A problem is standard if deg(ν) + ter(ν) is even for all vertices ν where deg(ν) is the degree of ν and ter(ν) is the number of nets which have ν as a terminal. For nonstandard problems we can find a solution in time O(n(log n)² + |U|²) where U is the set of vertices ν with deg(ν) + ter(ν) is odd.     

Construction algorithms for polynomial lattice rules for multivariate integration

We introduce a new construction algorithm for digital nets for integration in certain weighted tensor product Hilbert spaces. The first weighted Hilbert space we consider is based on Walsh functions. Dick and Pillichshammer calculated the worst-case error for integration using digital nets for this space. Here we extend this result to a special construction method for digital nets based on polynomials over finite fields. This result allows us to find polynomials which yield a small worst-case error by computer search. We prove an upper bound on the worst-case error for digital nets obtained by such a search algorithm which shows that the convergence rate is best possible and that strong tractability holds under some condition on the weights.

We extend the results for the weighted Hilbert space based on Walsh functions to weighted Sobolev spaces. In this case we use randomly digitally shifted digital nets. The construction principle is the same as before, only the worst-case error is slightly different. Again digital nets obtained from our search algorithm yield a worst-case error achieving the optimal rate of convergence and as before strong tractability holds under some condition on the weights. These results show that such a construction of digital nets yields the until now best known results of this kind and that our construction methods are comparable to the construction methods known for lattice rules.

We conclude the article with numerical results comparing the expected worst-case error for randomly digitally shifted digital nets with those for randomly shifted lattice rules.

     

An adaptive memory algorithm for the split delivery vehicle routing problem

The split delivery vehicle routing problem (SDVRP) relaxes routing restrictions forcing unique deliveries to customers and allows multiple vehicles to satisfy customer demand. Split deliveries are used to reduce total fleet cost to meet those customer demands. We provide a detailed survey of the SDVRP literature and define a new constructive algorithm for the SDVRP based on a novel concept called the route angle control measure. We extend this constructive approach to an iterative approach using adaptive memory concepts, and then add a variable neighborhood descent process. These three new approaches are compared to exact and heuristic approaches by solving the available SDVRP benchmark problem sets. Our approaches are found to compare favorably with existing approaches and we find 16 new best solutions for a recent 21 problem benchmark set.     

Constructions of general polynomial lattice rules based on the weighted star discrepancy

In this paper we study construction algorithms for polynomial lattice rules modulo arbitrary polynomials. Polynomial lattice rules are a special class of digital nets which yield well distributed point sets in the unit cube for numerical integration.Niederreiter obtained an existence result for polynomial lattice rules modulo arbitrary polynomials for which the underlying point set has a small star discrepancy and recently Dick, Leobacher and Pillichshammer introduced construction algorithms for polynomial lattice rules modulo an irreducible polynomial for which the underlying point set has a small (weighted) star discrepancy.In this work we provide construction algorithms for polynomial lattice rules modulo arbitrary polynomials, thereby generalizing the previously obtained results. More precisely we use a component-by-component algorithm and a Korobov-type algorithm. We show how the search space of the Korobov-type algorithm can be reduced without sacrificing the convergence rate, hence this algorithm is particularly fast. Our findings are based on a detailed analysis of quantities closely related to the (weighted) star discrepancy.     

基于交通流的多模糊时间窗车辆路径优化

研究了基于交通流的多模糊时间窗车辆路径问题,考虑了实际中不断变化的交通流以及客户具有多个模糊时间窗的情况,以最小化配送总成本和最大化客户满意度为目标,构建基于交通流的多模糊时间窗车辆路径模型。根据伊藤算法的基本原理,设计了求解该模型的改进伊藤算法,结合仿真算例进行了模拟计算,并与蚁群算法的计算结果进行了对比分析,结果表明,利用改进伊藤算法求解基于交通流的多模糊时间窗车辆路径问题,迭代次数小,效率更高,能够在较短的时间内收敛到全局最优解,可以有效的求解多模糊时间窗车辆路径问题。