A Cooperative and Adaptive Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

In this paper we propose two cooperation schemes to compose new parallel variants of the Variable Neighborhood Search (VNS). On the one hand, a coarse-grained cooperation scheme is introduced which is well suited for being enhanced with a solution warehouse to store and manage the so far best found solutions and a self-adapting mechanism for the most important search parameters. This makes an a priori parameter tuning obsolete. On the other hand, a fine-grained scheme was designed to reproduce the successful properties of the sequential VNS. In combination with the use of parallel exploration threads all of the best solutions and 11 out of 20 new best solutions for the Multi Depot Vehicle Routing Problem with Time Windows were found.

Exact Solutions to the Symmetric and Asymmetric Vehicle Routing Problem with Simultaneous Delivery and Pick-Up

In reverse logistics networks, products (e.g., bottles or containers) have to be transported from a depot to customer locations and, after use, from customer locations back to the depot. In order to operate economically beneficial, companies prefer a simultaneous delivery and pick-up service. The resulting Vehicle Routing Problem with Simultaneous Delivery and Pick-up (VRPSDP) is an operational problem, which has to be solved daily by many companies. We present two mixed-integer linear model formulations for the VRPSDP, namely a vehicle-flow and a commodity-flow model. In order to strengthen the models, domain-reducing preprocessing techniques, and effective cutting planes are outlined. Symmetric benchmark instances known from the literature as well as new asymmetric instances derived from real-world problems are solved to optimality using CPLEX 12.1.

Importance of vegetation, topography and flow paths for water transit times of base flow in alpine headwater catchments

The mean transit time (MTT) of water in a catchment gives information about storage, flow paths, sources of water and thus also about retention and release of solutes in a catchment. To our knowledge there are only a few catchment studies on the influence of vegetation cover changes on base flow MTTs. The main changes in vegetation cover in the Swiss Alps are massive shrub encroachment and forest expansion into formerly open habitats. Four small and relatively steep headwater catchments in the Swiss Alps (Ursern Valley) were investigated to relate different vegetation cover to water transit times. Time series of water stable isotopes were used to calculate MTTs. The high temporal variation of the stable isotope signals in precipitation was strongly dampened in stream base flow samples. MTTs of the four catchments were 70 to 102 weeks. The strong dampening of the stable isotope input signal as well as stream water geochemistry points to deeper flow paths and mixing of waters of different ages at the catchments' outlets. MTTs were neither related to topographic indices nor vegetation cover. The major part of the quickly infiltrating precipitation likely percolates through fractured and partially karstified deeper rock zones, which increases the control of bedrock flow paths on MTT. Snow accumulation and the timing of its melt play an important role for stable isotope dynamics during spring and early summer. We conclude that, in mountainous headwater catchments with relatively shallow soil layers, the hydrogeological and geochemical patterns (i.e. geochemistry, porosity and hydraulic conductivity of rocks) and snow dynamics influence storage, mixing and release of water in a stronger way than vegetation cover or topography do.

Context-aware Opportunistic Routing in Mobile Ad-hoc Networks Incorporating Node Mobility

Opportunistic routing (OR) employs a list of candi- dates to improve reliability of wireless transmission. However, list-based OR features restrict the freedom of opportunism, since only the listed nodes can compete for packet forwarding. Additionally, the list is statically generated based on a single metric prior to data transmission, which is not appropriate for mobile ad-hoc networks. This paper provides a thorough perfor- mance evaluation of a new protocol - Context-aware Opportunistic Routing (COR). The contributions of COR are threefold. First, it uses various types of context information simultaneously such as link quality, geographic progress, and residual energy of nodes to make routing decisions. Second, it allows all qualified nodes to participate in packet forwarding. Third, it exploits the relative mobility of nodes to further improve performance. Simulation results show that COR can provide efficient routing in mobile environments, and it outperforms existing solutions that solely rely on a single metric by nearly 20 - 40 %.

Assessment of a robust opportunistic routing for video transmission in dynamic topologies

Mobile multimedia ad hoc services run on dynamic topologies due to node mobility or failures and wireless channel impairments. A robust routing service must adapt to topology changes with the aim of recovering or maintaining the video quality level and reducing the impact of the user's experience. In those scenarios, beacon-less Opportunistic Routing (OR) increases the robustness by supporting routing decisions in a completely distributed manner based on protocol-specific characteristics. However, the existing beacon-less OR approaches do not efficiently combine multiple metrics for forwarding selection, which cause higher packet loss rate, and consequently reduce the video quality level. In this paper, we assess the robustness and reliability of our recently developed OR protocol under node failures, called cross-layer Link quality and Geographical-aware OR protocol (LinGO). Simulation results show that LinGO achieves multimedia dissemination with QoE support and robustness in scenarios with dynamic topologies.