A hybrid genetic algorithm for the multi-depot vehicle routing problem

The distribution of finished products from depots to customers is a practical and challenging problem in logistics management. Better routing and scheduling decisions can result in higher level of customer satisfaction because more customers can be served in a shorter time. The distribution problem is generally formulated as the vehicle routing problem (VRP). Nevertheless, there is a rigid assumption that there is only one depot. In cases, for instance, where a logistics company has more than one depot, the VRP is not suitable. To resolve this limitation, this paper focuses on the VRP with multiple depots, or multi-depot VRP (MDVRP). The MDVRP is NP-hard, which means that an efficient algorithm for solving the problem to optimality is unavailable. To deal with the problem efficiently, two hybrid genetic algorithms (HGAs) are developed in this paper. The major difference between the HGAs is that the initial solutions are generated randomly in HGA1. The Clarke and Wright saving method and the nearest neighbor heuristic are incorporated into HGA2 for the initialization procedure. A computational study is carried out to compare the algorithms with different problem sizes. It is proved that the performance of HGA2 is superior to that of HGA1 in terms of the total delivery time.

Distributed routing algorithms for interconnected FDDI LANS

The Fibre Distributed Data Interface (FDDI) represents the new generation of local area networks (LANs). These high speed LANs are capable of supporting up to 500 users over a 100 km distance. User traffic is expected to be as diverse as file transfers, packet voice and video. As the proliferation of FDDI LANs continues, the need to interconnect these LANs arises. FDDI LAN interconnection can be achieved in a variety of different ways. Some of the most commonly used today are public data networks, dial up lines and private circuits. For applications that can potentially generate large quantities of traffic, such as an FDDI LAN, it is cost effective to use a private circuit leased from the public carrier. In order to send traffic from one LAN to another across the leased line, a routing algorithm is required. Much research has been done on the Bellman-Ford algorithm and many implementations of it exist in computer networks. However, due to its instability and problems with routing table loops it is an unsatisfactory algorithm for interconnected FDDI LANs. A new algorithm, termed ISIS which is being standardized by the ISO provides a far better solution. ISIS will be implemented in many manufacturers routing devices. In order to make the work as practical as possible, this algorithm will be used as the basis for all the new algorithms presented. The ISIS algorithm can be improved by exploiting information that is dropped by that algorithm during the calculation process. A new algorithm, called Down Stream Path Splits (DSPS), uses this information and requires only minor modification to some of the ISIS routing procedures. DSPS provides a higher network performance, with very little additional processing and storage requirements. A second algorithm, also based on the ISIS algorithm, generates a massive increase in network performance. This is achieved by selecting alternative paths through the network in times of heavy congestion. This algorithm may select the alternative path at either the originating node, or any node along the path. It requires more processing and memory storage than DSPS, but generates a higher network power. The final algorithm combines the DSPS algorithm with the alternative path algorithm. This is the most flexible and powerful of the algorithms developed. However, it is somewhat complex and requires a fairly large storage area at each node. The performance of the new routing algorithms is tested in a comprehensive model of interconnected LANs. This model incorporates the transport through physical layers and generates random topologies for routing algorithm performance comparisons. Using this model it is possible to determine which algorithm provides the best performance without introducing significant complexity and storage requirements.

The SECURE study:long-term safety of Ranibizumab 0.5 mg in neovascular age-related macular degeneration

Objective - To evaluate long-term safety of intravitreal ranibizumab 0.5-mg injections in neovascular age-related macular degeneration (nAMD). Design - Twenty-four–month, open-label, multicenter, phase IV extension study. Participants - Two hundred thirty-four patients previously treated with ranibizumab for 12 months in the EXCITE/SUSTAIN study. Methods - Ranibizumab 0.5 mg administered at the investigator's discretion as per the European summary of product characteristics 2007 (SmPC, i.e., ranibizumab was administered if a patient experienced a best-corrected visual acuity [BCVA] loss of >5 Early Treatment Diabetic Retinopathy Study letters measured against the highest visual acuity [VA] value obtained in SECURE or previous studies [EXCITE and SUSTAIN], attributable to the presence or progression of active nAMD in the investigator's opinion). Main Outcome Measures - Incidence of ocular or nonocular adverse events (AEs) and serious AEs, mean change in BCVA from baseline over time, and the number of injections. Results - Of 234 enrolled patients, 210 (89.7%) completed the study. Patients received 6.1 (mean) ranibizumab injections over 24 months. Approximately 42% of patients had 7 or more visits at which ranibizumab was not administered, although they had experienced a VA loss of more than 5 letters, indicating either an undertreatment or that factors other than VA loss were considered for retreatment decision by the investigator. The most frequent ocular AEs (study eye) were retinal hemorrhage (12.8%; 1 event related to study drug), cataract (11.5%; 1 event related to treatment procedure), and increased intraocular pressure (6.4%; 1 event related to study drug). Cataract reported as serious due to hospitalization for cataract surgery occurred in 2.6% of patients; none was suspected to be related to study drug or procedure. Main nonocular AEs were hypertension and nasopharyngitis (9.0% each). Arterial thromboembolic events were reported in 5.6% of the patients. Five (2.1%) deaths occurred during the study, none related to the study drug or procedure. At month 24, mean BCVA declined by 4.3 letters from the SECURE baseline. Conclusions - The SECURE study showed that ranibizumab administered as per a VA-guided flexible dosing regimen recommended in the European ranibizumab SmPC at the investigator's discretion was well tolerated over 2 years. No new safety signals were identified in patients who received ranibizumab for a total of 3 years. On average, patients lost BCVA from the SECURE study baseline, which may be the result of disease progression or possible undertreatment.

Secure key distribution over a 500 km long link using a Raman ultra-long fiber laser

In traditional communication systems the transmission medium is considered as a given characteristic of the channel, which does not depend on the properties of the transmitter and the receiver. Recent experimental demonstrations of the feasibility of extending the laser cavity over the whole communication link connecting the two parties, forming an ultra-long fiber laser (UFL), have raised groundbreaking possibilities in communication and particularly in secure communications. Here, a 500 km long secure key distribution link based on Raman gain UFL is demonstrated. An error-free distribution of a random key with an average rate of 100 bps between the users is demonstrated and the key is shown to be unrecoverable to an eavesdropper employing either time or frequency domain passive attacks. In traditional communication systems the transmission medium is considered as a given characteristic of the channel, which does not depend on the properties of the transmitter and the receiver. Recent demonstrations of the feasibility of extending the laser cavity over the whole communication link connecting the two parties, forming an ultra-long fiber laser (UFL), have raised groundbreaking possibilities in communication. Here, a 500 km long secure key distribution link based on Raman gain UFL is demonstrated. © 2014 by WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim.

A new three phase method (SDP method) for the multi-objective vehicle routing problem with simultaneous delvery and pickup (VRPSDP)

Transportation service operators are witnessing a growing demand for bi-directional movement of goods. Given this, the following thesis considers an extension to the vehicle routing problem (VRP) known as the delivery and pickup transportation problem (DPP), where delivery and pickup demands may occupy the same route. The problem is formulated here as the vehicle routing problem with simultaneous delivery and pickup (VRPSDP), which requires the concurrent service of the demands at the customer location. This formulation provides the greatest opportunity for cost savings for both the service provider and recipient. The aims of this research are to propose a new theoretical design to solve the multi-objective VRPSDP, provide software support for the suggested design and validate the method through a set of experiments. A new real-life based multi-objective VRPSDP is studied here, which requires the minimisation of the often conflicting objectives: operated vehicle fleet size, total routing distance and the maximum variation between route distances (workload variation). The former two objectives are commonly encountered in the domain and the latter is introduced here because it is essential for real-life routing problems. The VRPSDP is defined as a hard combinatorial optimisation problem, therefore an approximation method, Simultaneous Delivery and Pickup method (SDPmethod) is proposed to solve it. The SDPmethod consists of three phases. The first phase constructs a set of diverse partial solutions, where one is expected to form part of the near-optimal solution. The second phase determines assignment possibilities for each sub-problem. The third phase solves the sub-problems using a parallel genetic algorithm. The suggested genetic algorithm is improved by the introduction of a set of tools: genetic operator switching mechanism via diversity thresholds, accuracy analysis tool and a new fitness evaluation mechanism. This three phase method is proposed to address the shortcoming that exists in the domain, where an initial solution is built only then to be completely dismantled and redesigned in the optimisation phase. In addition, a new routing heuristic, RouteAlg, is proposed to solve the VRPSDP sub-problem, the travelling salesman problem with simultaneous delivery and pickup (TSPSDP). The experimental studies are conducted using the well known benchmark Salhi and Nagy (1999) test problems, where the SDPmethod and RouteAlg solutions are compared with the prominent works in the VRPSDP domain. The SDPmethod has demonstrated to be an effective method for solving the multi-objective VRPSDP and the RouteAlg for the TSPSDP.

Ad hoc network state aware routing protocol

The environment of a mobile ad hoc network may vary greatly depending on nodes' mobility, traffic load and resource conditions. In this paper we categorize the environment of an ad hoc network into three main states: an ideal state, wherein the network is relatively stable with sufficient resources; a congested state, wherein some nodes, regions or the network is experiencing congestion; and an energy critical state, wherein the energy capacity of nodes in the network is critically low. Each of these states requires unique routing schemes, but existing ad hoc routing protocols are only effective in one of these states. This implies that when the network enters into any other states, these protocols run into a sub optimal mode, degrading the performance of the network. We propose an Ad hoc Network State Aware Routing Protocol (ANSAR) which conditionally switches between earliest arrival scheme and a joint Load-Energy aware scheme depending on the current state of the network. Comparing to existing schemes, it yields higher efficiency and reliability as shown in our simulation results. © 2007 IEEE.

Ultralong fiber lasers with coding in free-spectral range for secure key Distribution

We present experimental results on a 50km fiber laser switching among four different values of the free-spectral range for possible applications in secure key-distribution. © 2014 OSA.

Long-range, high bit-rate secure key distribution link utilizing Raman Ultra-long fiber laser (UFL)

The distribution of the secret key is the weakest link of many data encryption systems. Quantum key distribution (QKD) schemes provide attractive solutions [1], however their implementation remains challenging and their range and bit-rate are limited. Moreover, practical QKD systems, employ real-life components and are, therefore, vulnerable to diverse attack schemes [2]. Ultra-Long fiber lasers (UFLs) have been drawing much attention recently because of their fundamentally different properties compared to conventional lasers as well as their unique applications [3]. Here, we demonstrate a 100Bps, practically secure key distribution, over a 500km link, employing Raman gain UFL. Fig. 1(a) depicts a schematic of the UFL system. Each user has an identical set of two wavelength selective mirrors centered at l0 and l 1. In order to exchange a key-bit, each user independently choose one of these mirrors and introduces it as a laser reflector at their end. If both users choose identical mirrors, a clear signal develops and the bits in these cases are discarded. However if they choose complementary mirrors, (1, 0 or 0, 1 states), the UFL remains below lasing threshold and no signal evolves. In these cases, an eavesdropper can only detect noise and is unable to determine the mirror choice of the users, where the choice of mirrors represent a single key bit (e.g. Alice's choice of mirror is the key-bit). These bits are kept and added to the key. The absence of signal in the secure states faxilitates fast measurements to distinguish between the non-secure and the secure states and to determine the key-bit in the later case, Sequentially reapeating the single bit exchange protocol generate the entire keys of any desirable length. © 2013 IEEE.

Efficient algorithm for routing optimization via statistical mechanics

Many practical routing algorithms are heuristic, adhoc and centralized, rendering generic and optimal path configurations difficult to obtain. Here we study a scenario whereby selected nodes in a given network communicate with fixed routers and employ statistical physics methods to obtain optimal routing solutions subject to a generic cost. A distributive message-passing algorithm capable of optimizing the path configuration in real instances is devised, based on the analytical derivation, and is greatly simplified by expanding the cost function around the optimized flow. Good algorithmic convergence is observed in most of the parameter regimes. By applying the algorithm, we study and compare the pros and cons of balanced traffic configurations to that of consolidated traffic, which provides important implications to practical communication and transportation networks. Interesting macroscopic phenomena are observed from the optimized states as an interplay between the communication density and the cost functions used. © 2013 IEEE.

Chain routing:a new routing framework for the Internet based on complete orders

A new framework to perform routing at the autonomous system (AS) level is proposed here. This mechanism, called chain routing framework (CRF), uses complete orders as its main topological unit. Since complete orders are acyclic digraphs that possess a known topology, it is possible to use these acyclic structures to route consistently packets between a group of ASs. The adoption of complete orders also allows easy identification and avoidance of persistent route oscillations, eliminates the possibility of developing transient loops in paths and provides a structure that facilitates the implementation of traffic engineering. Moreover, by combining CRF with other mechanisms that implement complete orders in time, the authors propose that it is possible to design a new routing protocol, which can be more reliable and stable than the border gateway protocol. © 2011 The Institution of Engineering and Technology.