A mathematical model of deterministic wormhole routing in hypercube multicomputers using virtual channels

Although several analytical models have been proposed in the literature for binary n-cubes with deterministic routing, most of them have not included the effects of virtual channel multiplexing on network performance. The only mathematical model for deterministic wormhole routing in hypercubes with virtual channels was proposed in [Y. Boura, Design and Analysis of Routing Schemes and Routers for Wormhole-routed Mesh Architectures, Ph.D. Thesis, Department of Computer Science and Engineering, Pennsylvania State University, 1995] which uses complex combinatorial analysis with a computation time of O(N=2ⁿ) for an n-dimensional hypercube. This paper proposes a new and simple analytical model to compute message latency in binary n-cubes with virtual channels. It is very simple and easy to understand which uses an average case analysis and requires a computation time of O(n) for an n-dimensional hypercube. Results from simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various network sizes and under different operating conditions.     

Heuristics for multi-attribute vehicle routing problems: A survey and synthesis

The attributes of vehicle routing problems are additional characteristics or constraints that aim to better take into account the specificities of real applications. The variants thus formed are supported by a well-developed literature, including a large variety of heuristics. This article first reviews the main classes of attributes, providing a survey of heuristics and meta-heuristics for Multi-Attribute Vehicle Routing Problems (MAVRP). It then takes a closer look at the concepts of 64 remarkable meta-heuristics, selected objectively for their outstanding performance on 15 classic MAVRP with different attributes. This cross-analysis leads to the identification of “winning strategies” in designing effective heuristics for MAVRP. This is an important step in the development of general and efficient solution methods for dealing with the large range of vehicle routing variants.     

Routing of 2-D switching networks by their embedding into cubes

The proposed all-optical 2-D switching networks are (i) M×N-gon prism switches (M2, N3) and (ii) 3-D grids of any geometry N3. For the routing we assume (1) the projection of the spatial architectures onto plane graphs (2) the embedding of the latter guest graphs into (in)complete host hypercubes (N=4) and generally, into N-cube networks (N3) and (3) routing by means of the cube algorithms of the host. By the embedding mainly faulty cubes (synonyms: injured cubes, incomplete cubes) arise which complicate the routing and analysis. The application of N-cube networks (i) extend the hypercube principles to any N3 (ii) increase the number of plane host graphs and (iii) reduce the incompleteness of the host cubes. Several different embeddings of the intersection graphs (IGs) of 2-D switching networks and several different routings are explained for N=4 and 6 by various examples. By the expansion of the grids (enlargement) internal waveguides (WGs) and internal switches are introduced which interact with the switches of the original 3-D grid without increasing the number of stages (NS). The embeddings by expansion apply to interconnection networks whereas dilation-2 embeddings (dilation ≡ distance of the nearest-neighbour nodes of the guest graph at the host) are rather suitable for the emulation of algorithms. Concepts for fault-tolerant routing and algorithm mapping are briefly explained.     

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.     

Probabilistically induced domain decomposition methods for elliptic boundary-value problems

Monte Carlo as well as quasi-Monte Carlo methods are used to generate only few interfacial values in two-dimensional domains where boundary-value elliptic problems are formulated. This allows for a domain decomposition of the domain. A continuous approximation of the solution is obtained interpolating on such interfaces, and then used as boundary data to split the original problem into fully decoupled subproblems. The numerical treatment can then be continued, implementing any deterministic algorithm on each subdomain. Both, Monte Carlo (or quasi-Monte Carlo) simulations and the domain decomposition strategy allow for exploiting parallel architectures. Scalability and natural fault tolerance are peculiarities of the present algorithm. Examples concern Helmholtz and Poisson equations, whose probabilistic treatment presents additional complications with respect to the case of homogeneous elliptic problems without any potential term and source.     

Planning and approximation models for delivery route based services with price-sensitive demands

Classical vehicle routing problems typically do not consider the impact of delivery price on the demand for delivery services. Existing models seek the minimum sum of tour lengths in order to serve the demands of a given set of customers. This paper proposes approximation models to estimate the impacts of price on delivery services when demand for delivery service is price dependent. Such models can serve as useful tools in the planning phase for delivery service providers and can assist in understanding the economics of delivery services. These models seek to maximize profit from delivery service, where price determines demand for deliveries as well as the total revenue generated by satisfying demand. We consider a variant of the model in which each customer’s delivery volume is price sensitive, as well as the case in which customer delivery volumes are fixed, but the total number of customers who select the delivery service provider is price sensitive. A third model variant allows the delivery service provider to select a subset of delivery requests at the offered price in order to maximize profit.     

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.     

Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts

We describe a solution procedure for a special case of the periodic vehicle routing problem (PVRP). Operation managers at an auto parts manufacturer in the north of Spain described the optimization problem to the authors. The manufacturer must pick up parts (raw material) from geographically dispersed locations. The parts are picked up periodically at scheduled times. The problem consists of assigning a pickup schedule to each of its supplier’s locations and also establishing daily routes in order to minimize total transportation costs. The time horizon under consideration may be as long as 90 days. The resulting PVRP is such that the critical decision is the assignment of locations to schedules, because once this is done, the daily routing of vehicles is relatively straightforward. Through extensive computational experiments, we show that the metaheuristic procedure described in this paper is capable of finding high-quality solutions within a reasonable amount of computer time. Our main contribution is the development of a procedure that is more effective at handling PVRP instances with long planning horizons when compared to those proposed in the literature.     

Equilibria for networks with malicious users

We consider the problem of characterizing user equilibria and optimal solutions for selfish routing in a given network. We extend the known models by considering malicious behavior. While selfish users follow a strategy that minimizes their individual cost, a malicious user will use his flow through the network in an effort to cause the maximum possible damage to the overall cost. We define a generalized model, present characterizations of flows at equilibrium and prove bounds for the ratio of the social cost of a flow at equilibrium over the cost when centralized coordination among users is allowed. An extended abstract of this work appeared in the Proceedings of the 14th Annual International Symposium on Algorithms and Computation (ISAAC) 2003. G. Karakostas’ research was supported by an NSERC Discovery research grant and MITACS. Part of this research was done when Viglas was a postdoctoral fellow at the University of Toronto, Canada.     

On computing average cost optimal policies with application to routing to parallel queues

The Approximating Sequence Method for computation of average cost optimal stationary policies in denumerahle state Markov decision chains, introduced in Sennott (1994), is reviewed. New methods for verifying the assumptions are given. These are useful for models with multidimensional state spaces that satisfy certain mild structural properties. The results are applied to four problems in the optimal routing of packets to parallel queues. Numerical results are given for one of the models.