Scatter search for a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries in Brazil

In this paper, we consider a real-life heterogeneous fleet vehicle routing problem with time windows and split deliveries that occurs in a major Brazilian retail group. A single depot attends 519 stores of the group distributed in 11 Brazilian states. To find good solutions to this problem, we propose heuristics as initial solutions and a scatter search (SS) approach. Next, the produced solutions are compared with the routes actually covered by the company. Our results show that the total distribution cost can be reduced significantly when such methods are used. Experimental testing with benchmark instances is used to assess the merit of our proposed procedure. (C) 2008 Published by Elsevier B.V.

Virtual landmarking for locality aware peer IDs

In Peer-to-Peer (P2P) networks, it is often desirable to assign node IDs which preserve locality relationships in the underlying topology. Node locality can be embedded into node IDs by utilizing a one dimensional mapping by a Hilbert space filling curve on a vector of network distances from each node to a subset of reference landmark nodes within the network. However this approach is fundamentally limited because while robustness and accuracy might be expected to improve with the number of landmarks, the effectiveness of 1 dimensional Hilbert Curve mapping falls for the curse of dimensionality. This work proposes an approach to solve this issue using Landmark Multidimensional Scaling (LMDS) to reduce a large set of landmarks to a smaller set of virtual landmarks. This smaller set of landmarks has been postulated to represent the intrinsic dimensionality of the network space and therefore a space filling curve applied to these virtual landmarks is expected to produce a better mapping of the node ID space. The proposed approach, the Virtual Landmarks Hilbert Curve (VLHC), is particularly suitable for decentralised systems like P2P networks. In the experimental simulations the effectiveness of the methods is measured by means of the locality preservation derived from node IDs in terms of latency to nearest neighbours. A variety of realistic network topologies are simulated and this work provides strong evidence to suggest that VLHC performs better than either Hilbert Curves or LMDS use independently of each other.

Methodological issues in applying Location Models to Rural areas

Location Models are usedfor planning the location of multiple service centers in order to serve a geographicallydistributed population. A cornerstone of such models is the measure of distancebetween the service center and a set of demand points, viz, the location of thepopulation (customers, pupils, patients and so on). Theoretical as well asempirical evidence support the current practice of using the Euclidian distancein metropolitan areas. In this paper, we argue and provide empirical evidencethat such a measure is misleading once the Location Models are applied to ruralareas with heterogeneous transport networks. This paper stems from the problemof finding an optimal allocation of a pre-specified number of hospitals in alarge Swedish region with a low population density. We conclude that the Euclidianand the network distances based on a homogenous network (equal travel costs inthe whole network) give approximately the same optimums. However networkdistances calculated from a heterogeneous network (different travel costs indifferent parts of the network) give widely different optimums when the numberof hospitals increases.  In terms ofaccessibility we find that the recent closure of hospitals and the in-optimallocation of the remaining ones has increased the average travel distance by 75%for the population. Finally, aggregation the population misplaces the hospitalsby on average 10 km.

Distance measure and the p-median problem in rural areas

The p-median model is used to locate P facilities to serve a geographically distributed population. Conventionally, it is assumed that the population patronize the nearest facility and that the distance between the resident and the facility may be measured by the Euclidean distance. Carling, Han, and Håkansson (2012) compared two network distances with the Euclidean in a rural region witha sparse, heterogeneous network and a non-symmetric distribution of thepopulation. For a coarse network and P small, they found, in contrast to the literature, the Euclidean distance to be problematic. In this paper we extend their work by use of a refined network and study systematically the case when P is of varying size (2-100 facilities). We find that the network distance give as gooda solution as the travel-time network. The Euclidean distance gives solutions some 2-7 per cent worse than the network distances, and the solutions deteriorate with increasing P. Our conclusions extend to intra-urban location problems.

Planification et dimensionnement des réseaux optiques de longues distances

Le projet de recherche porte sur l'étude des problèmes de conception et de planification d'un réseau optique de longue distance, aussi appelé réseau de coeur (OWAN-Optical Wide Area Network en anglais). Il s'agit d'un réseau qui transporte des flots agrégés en mode commutation de circuits. Un réseau OWAN relie différents sites à l'aide de fibres optiques connectées par des commutateurs/routeurs optiques et/ou électriques. Un réseau OWAN est maillé à l'échelle d'un pays ou d’un continent et permet le transit des données à très haut débit. Dans une première partie du projet de thèse, nous nous intéressons au problème de conception de réseaux optiques agiles. Le problème d'agilité est motivé par la croissance de la demande en bande passante et par la nature dynamique du trafic. Les équipements déployés par les opérateurs de réseaux doivent disposer d'outils de configuration plus performants et plus flexibles pour gérer au mieux la complexité des connexions entre les clients et tenir compte de la nature évolutive du trafic. Souvent, le problème de conception d'un réseau consiste à prévoir la bande passante nécessaire pour écouler un trafic donné. Ici, nous cherchons en plus à choisir la meilleure configuration nodale ayant un niveau d'agilité capable de garantir une affectation optimale des ressources du réseau. Nous étudierons également deux autres types de problèmes auxquels un opérateur de réseau est confronté. Le premier problème est l'affectation de ressources du réseau. Une fois que l'architecture du réseau en termes d'équipements est choisie, la question qui reste est de savoir : comment dimensionner et optimiser cette architecture pour qu'elle rencontre le meilleur niveau possible d'agilité pour satisfaire toute la demande. La définition de la topologie de routage est un problème d'optimisation complexe. Elle consiste à définir un ensemble de chemins optiques logiques, choisir les routes physiques suivies par ces derniers, ainsi que les longueurs d'onde qu'ils utilisent, de manière à optimiser la qualité de la solution obtenue par rapport à un ensemble de métriques pour mesurer la performance du réseau. De plus, nous devons définir la meilleure stratégie de dimensionnement du réseau de façon à ce qu'elle soit adaptée à la nature dynamique du trafic. Le second problème est celui d'optimiser les coûts d'investissement en capital(CAPEX) et d'opération (OPEX) de l'architecture de transport proposée. Dans le cas du type d'architecture de dimensionnement considérée dans cette thèse, le CAPEX inclut les coûts de routage, d'installation et de mise en service de tous les équipements de type réseau installés aux extrémités des connexions et dans les noeuds intermédiaires. Les coûts d'opération OPEX correspondent à tous les frais liés à l'exploitation du réseau de transport. Étant donné la nature symétrique et le nombre exponentiel de variables dans la plupart des formulations mathématiques développées pour ces types de problèmes, nous avons particulièrement exploré des approches de résolution de type génération de colonnes et algorithme glouton qui s'adaptent bien à la résolution des grands problèmes d'optimisation. Une étude comparative de plusieurs stratégies d'allocation de ressources et d'algorithmes de résolution, sur différents jeux de données et de réseaux de transport de type OWAN démontre que le meilleur coût réseau est obtenu dans deux cas : une stratégie de dimensionnement anticipative combinée avec une méthode de résolution de type génération de colonnes dans les cas où nous autorisons/interdisons le dérangement des connexions déjà établies. Aussi, une bonne répartition de l'utilisation des ressources du réseau est observée avec les scénarios utilisant une stratégie de dimensionnement myope combinée à une approche d'allocation de ressources avec une résolution utilisant les techniques de génération de colonnes. Les résultats obtenus à l'issue de ces travaux ont également démontré que des gains considérables sont possibles pour les coûts d'investissement en capital et d'opération. En effet, une répartition intelligente et hétérogène de ressources d’un réseau sur l'ensemble des noeuds permet de réaliser une réduction substantielle des coûts du réseau par rapport à une solution d'allocation de ressources classique qui adopte une architecture homogène utilisant la même configuration nodale dans tous les noeuds. En effet, nous avons démontré qu'il est possible de réduire le nombre de commutateurs photoniques tout en satisfaisant la demande de trafic et en gardant le coût global d'allocation de ressources de réseau inchangé par rapport à l'architecture classique. Cela implique une réduction substantielle des coûts CAPEX et OPEX. Dans nos expériences de calcul, les résultats démontrent que la réduction de coûts peut atteindre jusqu'à 65% dans certaines jeux de données et de réseau.

Distances, rencontres, communications : les défis de la concorde dans l'Empire carolingien

À l’aube du IXe siècle, les Carolingiens prétendent imposer à l’Occident l’unité dans la foi et le culte. Cet idéal domine les pensées des empereurs qui se conçoivent comme protecteurs, législateurs et juges, mais aussi vicaires du Christ et recteurs de l’Église. De telles ambitions stimulent l’élaboration d’un gouvernement original. Comme les conquêtes avaient composé une vaste mosaïque de populations, de cultures et d’intérêts, la concorde posait un grand défi. Pour y répondre, Charlemagne et Louis le Pieux ont fait des communications leur premier outil politique. Leur inventivité et leur efficience furent appréciables, mais elles n’ont pas suffi à leur gagner toutes les adhésions : la discorde s’est installée là où l’empereur ne parvenait pas à maintenir une relation forte avec les élites régionales. Les distances et les modalités des communications déterminaient la nature de leurs échanges, donc leurs limites et, de ce fait, le destin de l’Empire carolingien. L’enquête aborde un vaste éventail documentaire : actes, capitulaires, correspondances, monnaies... Elle s’intéresse particulièrement aux relations du pouvoir impérial avec les élites du sud-ouest de l’empire. Ses résultats dépendent d’un étayage complexe : dispositifs de représentation du pouvoir, conséquences politico-sociales des distances et des vitesses de déplacement, anthropologie de la rencontre et des relations à distance, étude des réseaux. Au-delà des considérations propres à l’histoire des VIIIe-IXe siècles, elle démontre l’intérêt d’aborder les réalités politiques prémodernes du point de vue des défis que présentent les distances géographiques, les rencontres et les communications.

RMAC-M: Extending the R-MAC Protocol for an Energy Efficient, Delay Tolerant Underwater Acoustic Sensor Network application with a mobile data mule node

One of the major applications of underwater acoustic sensor networks (UWASN) is ocean environment monitoring. Employing data mules is an energy efficient way of data collection from the underwater sensor nodes in such a network. A data mule node such as an autonomous underwater vehicle (AUV) periodically visits the stationary nodes to download data. By conserving the power required for data transmission over long distances to a remote data sink, this approach extends the network life time. In this paper we propose a new MAC protocol to support a single mobile data mule node to collect the data sensed by the sensor nodes in periodic runs through the network. In this approach, the nodes need to perform only short distance, single hop transmission to the data mule. The protocol design discussed in this paper is motivated to support such an application. The proposed protocol is a hybrid protocol, which employs a combination of schedule based access among the stationary nodes along with handshake based access to support mobile data mules. The new protocol, RMAC-M is developed as an extension to the energy efficient MAC protocol R-MAC by extending the slot time of R-MAC to include a contention part for a hand shake based data transfer. The mobile node makes use of a beacon to signal its presence to all the nearby nodes, which can then hand-shake with the mobile node for data transfer. Simulation results show that the new protocol provides efficient support for a mobile data mule node while preserving the advantages of R-MAC such as energy efficiency and fairness.

How do different densities in a network affect the optimal location of service centers?

The p-median problem is often used to locate p service centers by minimizing their distances to a geographically distributed demand (n). The optimal locations are sensitive to geographical context such as road network and demand points especially when they are asymmetrically distributed in the plane. Most studies focus on evaluating performances of the p-median model when p and n vary. To our knowledge this is not a very well-studied problem when the road network is alternated especially when it is applied in a real world context. The aim in this study is to analyze how the optimal location solutions vary, using the p-median model, when the density in the road network is alternated. The investigation is conducted by the means of a case study in a region in Sweden with an asymmetrically distributed population (15,000 weighted demand points), Dalecarlia. To locate 5 to 50 service centers we use the national transport administrations official road network (NVDB). The road network consists of 1.5 million nodes. To find the optimal location we start with 500 candidate nodes in the network and increase the number of candidate nodes in steps up to 67,000. To find the optimal solution we use a simulated annealing algorithm with adaptive tuning of the temperature. The results show that there is a limited improvement in the optimal solutions when nodes in the road network increase and p is low. When p is high the improvements are larger. The results also show that choice of the best network depends on p. The larger p the larger density of the network is needed. 

Does road network density matter in optimally locating facilities?

Optimal location on the transport infrastructure is the preferable requirement for many decision making processes. Most studies have focused on evaluating performances of optimally locate p facilities by minimizing their distances to a geographically distributed demand (n) when p and n vary. The optimal locations are also sensitive to geographical context such as road network, especially when they are asymmetrically distributed in the plane. The influence of alternating road network density is however not a very well-studied problem especially when it is applied in a real world context. This paper aims to investigate how the density level of the road network affects finding optimal location by solving the specific case of p-median location problem. A denser network is found needed when a higher number of facilities are to locate. The best solution will not always be obtained in the most detailed network but in a middle density level. The solutions do not further improve or improve insignificantly as the density exceeds 12,000 nodes, some solutions even deteriorate. The hierarchy of the different densities of network can be used according to location and transportation purposes and increase the efficiency of heuristic methods. The method in this study can be applied to other location-allocation problem in transportation analysis where the road network density can be differentiated. 

Using GIS Network Analyst to Identify Suppliers for a Produce Co-op in Waterville, ME

The idea for organizing a cooperative market on Waterville Main Street was proposed by Aime Schwartz in the fall of 2008. The Co-op would entail an open market located on Main Street to provide fresh, local produce and crafts to town locals. Through shorter delivery distances and agreements with local farmers, the co-op theoretically will offer consumers lower prices on produce than can be found in conventional grocery stores, as well as an opportunity to support local agriculture. One of the tasks involved with organizing the Co-op is to source all of the produce from among the hundreds of farmers located in Maine. The purpose of this project is to show how Geographic Information System (GIS) tools can be used to help the Co-op and other businesses a) site nearby farms that carry desired produce and products, and b) determine which farms are closest to the business site. Using GIS for this purpose will make it easier and more efficient to source produce suppliers, and reduce the workload on business planners. GIS Network Analyst is a tool that provides network-based spatial analysis, and can be used in conjunction with traditional GIS technologies to determine not only the geometric distance between points, but also distance over existing networks (like roads). We used Network Analyst to find the closest produce suppliers to the Co-op for specific produce items, and compute how far they are over existing roads. This will enable business planners to source potential suppliers by distance before contacting individual farmers, allowing for more efficient use of their time and a faster planning process.

Search for Gravitational Waves Associated with gamma-ray Bursts Detected by the Interplanetary Network

We present the results of a search for gravitational waves associated with 223 gamma-ray bursts (GRBs) detected by the InterPlanetary Network (IPN) in 2005-2010 during LIGO's fifth and sixth science runs and Virgo's first, second, and third science runs. The IPN satellites provide accurate times of the bursts and sky localizations that vary significantly from degree scale to hundreds of square degrees. We search for both a well-modeled binary coalescence signal, the favored progenitor model for short GRBs, and for generic, unmodeled gravitational wave bursts. Both searches use the event time and sky localization to improve the gravitational wave search sensitivity as compared to corresponding all-time, all-sky searches. We find no evidence of a gravitational wave signal associated with any of the IPN GRBs in the sample, nor do we find evidence for a population of weak gravitational wave signals associated with the GRBs. For all IPN-detected GRBs, for which a sufficient duration of quality gravitational wave data are available, we place lower bounds on the distance to the source in accordance with an optimistic assumption of gravitational wave emission energy of 10(-2)M(circle dot)c(2) at 150 Hz, and find a median of 13 Mpc. For the 27 short-hard GRBs we place 90% confidence exclusion distances to two source models: a binary neutron star coalescence, with a median distance of 12 Mpc, or the coalescence of a neutron star and black hole, with a median distance of 22 Mpc. Finally, we combine this search with previously published results to provide a population statement for GRB searches in first-generation LIGO and Virgo gravitational wave detectors and a resulting examination of prospects for the advanced gravitational wave detectors.

Unprecedented Trapping of Difluorooctamolybdate Anions within an α-Polonium Type Coordination Network

New fluorinated hybrid solids [Mo2F2O5(tr2pr)] (1), [Co3(tr2pr)2(MoO4)2F2]·7H2O (2), and [Co3(H2O)2(tr2pr)3(Mo8O26F2)]·3H2O (3) (tr2pr = 1,3-bis(1,2,4-triazol-4-yl)propane) were prepared from the reaction systems consisting of Co(OAc)2/CoF2 and MoO3/(NH4)6Mo7O24, as CoII and MoVI sources, in water (2) or in aqueous HF (1, 3) employing mild hydrothermal conditions. The tr2pr ligand serves as a conformationally flexible tetradentate donor. In complex 1, the octahedrally coordinated Mo atoms are linked in the discrete corner-sharing {Mo2(μ2-O)F2O4N4} unit in which a pair of tr-heterocycles (tr = 1,2,4-triazole) is arranged in cis-positions opposite to “molybdenyl” oxygen atoms. The anti−anti conformation type of tr2pr facilitates the tight zigzag chain packing motif. The crystal structure of the mixed-anion complex salt 2 consists of trinuclear [Co3(μ3-MoO4)2(μ2-F)2] units self-assembling in CoII-undulating chains (Co···Co 3.0709(15) and 3.3596(7) Å), which are cross-linked by tr2pr in layers. In 3, containing condensed oxyfluoromolybdate species, linear centrosymmetric [Co3(μ2-tr)6]6+ SBUs are organized at distances of 10.72−12.45 Å in an α-Po-like network using bitopic tr-linkers. The octahedral {N6} and {N3O3} environments of the central and peripheral cobalt atoms, respectively, are filled by triazole N atoms, water molecules, and coordinating [Mo8O26F2]6− anions. Acting as a tetradentate O-donor, each difluorooctamolybdate anion anchors four [Co3(μ2-tr)6]6+ units through their peripheral Co-sites, which consequently leads to a novel type of a two-nodal 4,10-c net with the Schläfli symbol {32.43.5}{34.420.516.65}. The 2D and 3D coordination networks of 2 and 3, respectively, are characterized by significant overall antiferromagnetic exchange interactions (J/k) between the CoII spin centers on the order of −8 and −4 K. The [Mo8O26F2]6− anion is investigated in detail by quantum chemical calculations.

Robust rolling stock in rapid transit network

This paper focuses on the railway rolling stock circulation problem in rapid transit networks, in which frequencies are high and distances are relatively short. Although the distances are not very large, service times are high due to the large number of intermediate stops required to allow proper passenger flow. The main complicating issue is the fact that the available capacity at depot stations is very low, and both capacity and rolling stock are shared between different train lines. This forces the introduction of empty train movements and rotation maneuvers, to ensure sufficient station capacity and rolling stock availability. However, these shunting operations may sometimes be difficult to perform and can easily malfunction, causing localized incidents that could propagate throughout the entire network due to cascading effects. This type of operation will be penalized with the goal of selectively avoiding them and ameliorating their high malfunction probabilities. Critic trains, defined as train services that come through stations that have a large number of passengers arriving at the platform during rush hours, are also introduced. We illustrate our model using computational experiments drawn from RENFE (the main Spanish operator of suburban passenger trains) in Madrid, Spain. The results of the model, achieved in approximately 1 min, have been received positively by RENFE planners

Practical network coding for two way relay channels in LTE networks

In this paper, the implementation aspects and constraints of the simplest network coding (NC) schemes for a two-way relay channel (TWRC) composed of a user equipment (mobile terminal), an LTE relay station (RS) and an LTE base station (eNB) are considered in order to assess the usefulness of the NC in more realistic scenarios. The information exchange rate gain (IERG), the energy reduction gain (ERG) and the resource utilization gain (RUG) of the NC schemes with and without subcarrier division duplexing (SDD) are obtained by computer simulations. The usefulness of the NC schemes are evaluated for varying traffic load levels, the geographical distances between the nodes, the RS transmit powers, and the maximum numbers of retransmissions. Simulation results show that the NC schemes with and without SDD, have the throughput gains 0.5% and 25%, the ERGs 7 - 12% and 16 - 25%, and the RUGs 0.5 - 3.2%, respectively. It is found that the NC can provide performance gains also for the users at the cell edge. Furthermore, the ERGs of the NC increase with the transmit power of the relay while the ERGs of the NC remain the same even when the maximum number of retransmissions is reduced.

Short-circuit and ground fault analyses and location in VSC-based DC network cables

The application of high-power voltage-source converters (VSCs) to multiterminal dc networks is attracting research interest. The development of VSC-based dc networks is constrained by the lack of operational experience, the immaturity of appropriate protective devices, and the lack of appropriate fault analysis techniques. VSCs are vulnerable to dc-cable short-circuit and ground faults due to the high discharge current from the dc-link capacitance. However, faults occurring along the interconnecting dc cables are most likely to threaten system operation. In this paper, cable faults in VSC-based dc networks are analyzed in detail with the identification and definition of the most serious stages of the fault that need to be avoided. A fault location method is proposed because this is a prerequisite for an effective design of a fault protection scheme. It is demonstrated that it is relatively easy to evaluate the distance to a short-circuit fault using voltage reference comparison. For the more difficult challenge of locating ground faults, a method of estimating both the ground resistance and the distance to the fault is proposed by analyzing the initial stage of the fault transient. Analysis of the proposed method is provided and is based on simulation results, with a range of fault resistances, distances, and operational conditions considered.