Solving a vehicle routing problem by balancing the vehicles time utilization

Various vehicle routing problems (VRP) appear in the literature due to their important applications in the area of transportation and distribution.A VRP is characterized by the constraints that the involved factors must satisfy and by an optimality goal.In this paper, we develop a heuristic algorithm that

• (i)partitions suitably a distribution network into subnetworks. A single depot complies with every subnetwork, where a fleet of identical vehicles will start their itinerary. The nodes of the corresponding subnetwork are demand nodes that require a onetime visit by one only vehicle.
• (ii)Determine the routes of k vehicles, k=2,3,…, for every subnetwork so to minimize the visiting time of the corresponding demand nodes. Consequently the method computes the necessary vehicle number for each subnetwork so as to complete promptly the visiting requirement of all the demand nodes of the whole network. The main strategy of the algorithm for designing the vehicle routes consists of balancing the time utilization of the used vehicles. The paper is integrated by an application of the presented algorithm to the center of the city of Thessaloniki.

     

Upper and lower bounds for recurrent and recursively decomposable parallel processor-networks

A “recursively decomposable network” can be partitioned into a finite number of subnetworks that are smaller “versions of itself,” where the subnetworks are themselves recursively decomposable. Several interesting notions of such networks emerge depending on the collections of parameters chosen to model the relative behavioral characteristics that make a subnetwork a version of another. Examples of such parameters are permutation time, bandwidth, latency, topology, wires, degree, and size. This paper introduces and studies the class of networks that are recursively decomposable relative to bandwidth limitations, and the subclass of “recurrent networks” that are recursively decomposable relative to topology limitations. We show that an N-node recursively decomposable into halves network with bandwidth-inefficiency function β(x) must be at least $\frac{N}{2}\sum\nolimits_{i = l}^{\lg N}{\frac{1}{{\beta(2^i)}}}$ wires. This implies that the linear array, hypercube, and completely connected networks are all exactly optimal. The above lower bound is generalized to networks that are recursively decomposable, but not necessarily into halves. We show that the bound is tight up to a constant factor by exhibiting recurrent networks matching the above lower bounds. Our lower bound results both tighten and generalize a result of Meertens: no recurrent, fixed degree network can permute in O(log N) time. © 1996 John Wiley & Sons, Inc. ©1996 John Wiley & Sons, Inc.     

Decomposition approximation of queueing-network control models with tree structures

We devise a decomposition approximation method for a general branching queueing network with service-rate controls. The decomposition method, which reduces and simplifies computation routines considerably, results from the conditions for monotone optimal control policies in induction arguments. We first isolate each branch of connected queues as a subnetwork and then link the subnetworks through branching nodes to approximate the optimal control policies for the global network. The numerical results for a wide class of cost models show that the approximated optimal policies from the decomposed problems are sufficiently close to the optimal policies of the global problem.     

递归树的若干枚举特征

递归树由Meir和Moon定义作非平面增长树的一种，且所有节点出度都是允许的．本文首先在n个节点的递归树集合和n-1个元素的排列之间建立一个新的──对应，这个对应能同时给出树叶子和排列中的路段之间的对应和树叶子数和排列中的路段数之间的密切关系．同时还研究递归树的各种枚举特征，诸如节点的分类枚举（内节点和叶子节点、偶节点和奇节点，具不同出度的节点）和通路长度枚举（接各种节点分类）．     

A generalized activity network model

In recent years activity networks for projects with both random and deterministic alternative outcomes in key nodes have been considered. The developed control algorithm chooses an optimal outcome direction at every deterministic alternative node which is reached in the course of the project's realization. At each routine decision-making node, the algorithm singles out all the subnetworks (the so-called joint variants) which correspond to all possible outcomes from that node. Decision-making results in determining the optimal joint variant and following the optimal direction up to the next decision-making node. However, such models cover a limited class of alternative networks, namely, only fully-divisible networks which can be subdivided into nonintersecting fragments. In this paper, a more generalized activity network is considered. The model can be applied to a broader spectrum of R&D projects and can be used for all types of alternative networks, for example, for non-divisible networks comprising nodes with simultaneously ‘must follow’, random ‘exclusive OR’ and deterministic ‘exclusive or’ emitters. The branching activities of the third type refer to decision-making outcomes; choosing the optimal outcome is the sole prerogative of the project's management. Such a model is a more universal activity network; we will call it GAAN—Generalized Alternative Activity Network. The problem is to determine the joint variant optimizing the mean value of the objective function subject to restricted mean values of several other criteria. We will prove that such a problem is a NP-complete one. Thus, in general, the exact solution of the problem may be obtained only by looking through all the joint variants on the basis of their proper enumeration. To enumerate the joint variants we will use the lexicographical method in combination with some techniques of discrete optimization. A numerical example will be presented. Various application areas are considered.     

Two new algorithms for UMTS access network topology design

Present work introduces two network design algorithms for planning UMTS (Universal Mobile Telecommunication System) access networks. The task is to determine the cost-optimal number and location of the Radio Network Controller nodes and their connections to the Radio Base Stations (RBS) in a tree topology according to a number of planning constraints. First, a global algorithm to this general problem is proposed, which combines a metaheuristic technique with the solution of a specific b-matching problem. It is shown how a relatively complex algorithm can be performed within each step of a metaheuristic method still in reasonable time. Then, another method is introduced that is able to plan single RBS-trees. It can also be applied to make improvements on each tree created by the first algorithm. This approach applies iterative local improvements using branch-and-bound with Lagrangian lower bound. Eventually, it is demonstrated through a number of test cases that these algorithms are able to reduce the total cost of UMTS access networks, also compared to previous results.     

Analysis of recursive batched interpolation search

For an ordered file of records with uniformly distributed key values, we examine an existing batched searching algorithm based on recursive use of interpolation searches. The algorithm, called Recursive Batched Interpolation Search (RBIS) in this paper, uses a divide-and-conquer technique for batched searching. The expected-case complexity of the algorithm is shown to beO(m loglog (2n/m) +m), wheren is the size of the file andm is the size of the query batch. Simulations are performed to demonstrate the savings of batched searching using RBIS. Also, simulations are performed to compare alternative batched searching algorithms which are based on either interpolation search or binary search. When the file's key values are uniformly distributed, the simulation results confirm that interpolation-search based algorithms are superior to binary-search based algorithms. However, when the file's key values are not uniformly distributed, a straight-forward batched interpolation search deteriorates quickly as the batch size increases, but algorithm RBIS still outperforms binary-search based algorithms when the batch size passes a threshold value.     

Natural synchronization in power-grids with anti-correlated units

Synchronization between spatially distributed nodes of a power-grid is a crucial requirement for its proper operation. Using a Kuramoto-like network as a realistic physical model for the distribution of electrical power in a power-grid, we obtain coupling strengths and topological characteristics that favor the synchronous state of those technological networks. Power-grids are highly heterogeneous. They are composed of different classes of nodes and each node behaves differently. We show in this work that if a power-grid is extensive and nodes are highly connected, the coupling strength that leads to synchronization depends mainly on the eigenvalues of the Laplacian matrix, as it happens in homogeneous networks composed of equal nodes. On the other hand, if a power-grid is sparsely connected, the coupling strength that leads to synchronization is also strongly related to the correlation coefficient of the network, which means that a high number of connections between similar nodes (two power plants or two consumer centers) disfavor the synchronizability of the power-grid. We apply our results to the Brazilian power-grid system.     

Improving solution of discrete competitive facility location problems

We consider discrete competitive facility location problems in this paper. Such problems could be viewed as a search of nodes in a network, composed of candidate and customer demand nodes, which connections correspond to attractiveness between customers and facilities located at the candidate nodes. The number of customers is usually very large. For some models of customer behavior exact solution approaches could be used. However, for other models and/or when the size of problem is too high to solve exactly, heuristic algorithms may be used. The solution of discrete competitive facility location problems using genetic algorithms is considered in this paper. The new strategies for dynamic adjustment of some parameters of genetic algorithm, such as probabilities for the crossover and mutation operations are proposed and applied to improve the canonical genetic algorithm. The algorithm is also specially adopted to solve discrete competitive facility location problems by proposing a strategy for selection of the most promising values of the variables in the mutation procedure. The developed genetic algorithm is demonstrated by solving instances of competitive facility location problems for an entering firm.     

Kürzeste Wege in gemischten Netzen

Zusammenfassung Zur Ermittlung kürzester Wege in Netzen, die aus einander überlagernden Teilnetzen bestehen (wie z.B. Verkehrsnetze aus mehreren Netzen verschiedener Verkehrsbetriebe), wird der Algorithmus vonDijkstra erweitert. Bei der Wegsuche wird für den Fall des Übergangs von einem Teilnetz auf ein anderes ein Zuschlag zur Weglänge erhoben, der damit nicht nur die Länge, sondern auch den Verlauf des kürzesten Weges mitbestimmt. Es wird auf Erweiterungsmöglichkeiten hingewiesen, die auch zur Steuerung benutzt werden können, etwa zum Ausschluß von Wegen durch ein bestimmtes Teilnetz in einem vorgegebenen Entfernungsbereich vom Ausgangsknoten.

---

Summary In order to determine shortest paths in networks consisting of subnetworks superposing each other (like traffic networks composed of several networks of different transport undertakings),Dijkstra's algorithm is extended. During the route search, in case of changing from one subnetwork to another, an increase is added to the path length, thereby being a contributory determinant not only for the length, but also for the course of the shortest path. Capabilities of extension are referred to which can also be used for the purpose of control, e.g. to exclude paths through a certain subnetwork within a given distance range from the source.

     

A survivable design of last mile communication networks using multi-objective genetic algorithms

In this paper, we are interested in the survivable network design problem (SNDP) for last mile communication networks called (L-SNDP). Given a connected, weighted, undirected graph \(\mathrm{{G}} = (\mathrm{V, E})\); a set of infrastructure nodes and a set of customers C including two customer types where customers in the subset C1 require a single connection (type-1) and customers in the subset C2 need to be redundantly connected (type-2). The aim is to seek a sub-graph of G with the smallest weight in which all customers are connected to infrastructure nodes and the connections are protected against failures. This is a NP-hard problem and it has been solved only with the objective of minimizing the network cost. In this paper, we introduce a new multi-objective approach to solve L-SNDP called ML-SNDP. These objectives are to minimize the network cost (total cost) and to minimize the maximal amount of sharing links between connections. Results of computational experiments reported show the efficiency of our proposal.     

Random sequential bisection and its associated binary tree

Summary Random sequential bisection is a process to divide a given interval into two, four, eight, ... parts at random. Each division point is uniformly distributed on the interval and conditionally independent of the others. To study the asymptotic behavior of the lengths of subintervals in random seqential bisection, the associated binary tree is introduced. The number of internal or external nodes of the tree is asymptotically normal. The levels of the lowest and the highest external nodes are bounded with probability one or with probability increasing to one as the number of nodes increases to infinity. The associated binary tree is closely related to random binary tree which arises in computer algorithms, such as binary search tree and quicksort, and one-dimensional packing or the parking problem.     

Adaptive cluster synchronization in directed networks with nonidentical nonlinear dynamics

In this article, the problem of cluster synchronization in the complex networks with nonidentical nonlinear dynamics is considered. By Lyapunov functional and M‐matrix theory, some sufficient conditions for cluster synchronization are obtained. Moreover, the least number of nodes which should be pinned is given. It is shown that when the root nodes of all the clusters are pinning‐controlled, cluster synchronization with adaptive coupling strength can be achieved. Different from the constraints of many literatures, the assumption is that each row sum for all diagonal submatrices of the Laplacian matrix is equal to zero. Finally, a numerical simulation in the network with three scale‐free subnetwork is provided to demonstrate the effectiveness of the theoretical results. © 2016 Wiley Periodicals, Inc. Complexity 21: 380–387, 2016     

Steiner problem in Halin networks

The Steiner problem in networks is concerned with the determination of a minimum cost subnetwork connecting some (not necessarily all) vertices of an underlying network. The decision version of the Steiner problem is known to be NP-complete. However, if the underlying network is outerplanar or series-parallel, linear time algorithms have been developed.In this paper a linear time algorithm for the Steiner problem in Halin networks is presented. This result provides another example where the recursive structure of the underlying network leads to an efficient algorithm. Furthermore, the result is of interest from the network design point of view, since Halin networks are nontrivial generalizations of tree and ring networks.     

Discrete time controllable processes with bounded drift and their application in queueing systems

Recursive algorithms are considered for construction of optimal policies for some special classes of controllable stochastic processes, which are called discrete-time controllable semi-regenerative processes. By means of these processes many controllable queueing systems can be modelled. Numerical examples are given for the investigation of optimal policies in such systems.     

Heuristic algorithms for the 2-period balanced Travelling Salesman Problem in Euclidean graphs

In the 2-period Travelling Salesman Problem some nodes, called double nodes, are visited in both of two periods while the remaining ones, called single nodes, are visited in either one of the periods. In this paper we study the case in which a balance constraint is also introduced. We require that the difference between the number of visited nodes in the two periods must be below a fixed threshold. Moreover, we suppose that distances between nodes are Euclidean. The problem is NP-hard, and exact methods, now available, appear inadequate. Here, we propose three heuristics. Computational experiences and a comparison between the algorithms are also given.     

Core-generating approximate minimum entropy discretization for rough set feature selection in pattern classification

Rough set feature selection (RSFS) can be used to improve classifier performance. RSFS removes redundant attributes whilst retaining important ones that preserve the classification power of the original dataset. Reducts are feature subsets selected by RSFS. Core is the intersection of all the reducts of a dataset. RSFS can only handle discrete attributes, hence, continuous attributes need to be discretized before being input to RSFS. Discretization determines the core size of a discrete dataset. However, current discretization methods do not consider the core size during discretization. Earlier work has proposed core-generating approximate minimum entropy discretization (C-GAME) algorithm which selects the maximum number of minimum entropy cuts capable of generating a non-empty core within a discrete dataset. The contributions of this paper are as follows: (1) the C-GAME algorithm is improved by adding a new type of constraint to eliminate the possibility that only a single reduct is present in a C-GAME-discrete dataset; (2) performance evaluation of C-GAME in comparison to C4.5, multi-layer perceptrons, RBF networks and k-nearest neighbours classifiers on ten datasets chosen from the UCI Machine Learning Repository; (3) performance evaluation of C-GAME in comparison to Recursive Minimum Entropy Partition (RMEP), Chimerge, Boolean Reasoning and Equal Frequency discretization algorithms on the ten datasets; (4) evaluation of the effects of C-GAME and the other four discretization methods on the sizes of reducts; (5) an upper bound is defined on the total number of reducts within a dataset; (6) the effects of different discretization algorithms on the total number of reducts are analysed; (7) performance analysis of two RSFS algorithms (a genetic algorithm and Johnson’s algorithm).     

The energy-constrained quickest path problem

This paper addresses a variant of the quickest path problem in which each arc has an additional parameter associated to it representing the energy consumed during the transmission along the arc while each node is endowed with a limited power to transmit messages. The aim of the energy-constrained quickest path problem is to obtain a quickest path whose nodes are able to support the transmission of a message of a known size. After introducing the problem and proving the main theoretical results, a polynomial algorithm is proposed to solve the problem based on computing shortest paths in a sequence of subnetworks of the original network. In the second part of the paper, the bi-objective variant of this problem is considered in which the objectives are the transmission time and the total energy used. An exact algorithm is proposed to find a complete set of efficient paths. The computational experiments carried out show the performance of both algorithms.     

Vulnerability of complex networks

We consider normalized average edge betweenness of a network as a metric of network vulnerability. We suggest that normalized average edge betweenness together with is relative difference when certain number of nodes and/or edges are removed from the network is a measure of network vulnerability, called vulnerability index. Vulnerability index is calculated for four synthetic networks: Erdős–Rényi (ER) random networks, Barabási–Albert (BA) model of scale-free networks, Watts–Strogatz (WS) model of small-world networks, and geometric random networks. Real-world networks for which vulnerability index is calculated include: two human brain networks, three urban networks, one collaboration network, and two power grid networks. We find that WS model of small-world networks and biological networks (human brain networks) are the most robust networks among all networks studied in the paper.     

An Integer Linear Programming Formulation and Branch-and-Cut Algorithm for the Capacitated m-Ring-Star Problem

We study the capacitated m-ring-star problem (CmRSP) that faces the design of minimum cost network structure that connects customers with m rings using a set of ring connections that share a distinguished node (depot), and optionally star connections that connect customers to ring nodes. Ring and star connections have some associated costs. Also, rings can include transit nodes, named Steiner nodes, to reduce the total network cost if possible. The number of customers in each ring-star (ringʼs customers and customer connected to it through star connections) have an upper bound (capacity).These kind of networks are appropriate in optical fiber urban environments. CmRSP is know to be NP-Hard. In this paper we propose an integer linear programming formulation and a branch-and-cut algorithm.