Vehicle routing problems over time: a survey Mor, A.; Speranza, M. G.
Annals of operation research/Annals of operations research,
07/2022, Letnik:
314, Številka:
1
Journal Article
Recenzirano
Odprti dostop
In vehicle routing problems (VRPs) the decisions to be taken concern the assignment of customers to vehicles and the sequencing of the customers assigned to each vehicle. Additional decisions may ...need to be jointly taken, depending on the specific problem setting. In this paper, after discussing the different kinds of decisions taken in different classes of VRPs, the class where the decision about when the routes start from the depot has to be taken is considered and the related literature is reviewed. This class of problems, that we call VRPs over time, includes the periodic routing problems, the inventory routing problems, the vehicle routing problems with release dates, and the multi-trip vehicle routing problems.
Due to the problems of high bit error rate and delay, low bandwidth and limited energy of sensor nodes in underwater acoustic sensor network (UASN), it is particularly important to design a routing ...protocol with high reliability, strong robustness, low end-to-end delay and high energy efficiency which can flexibly be employed in dynamic network environment. Therefore, a reinforcement learning-based opportunistic routing protocol (RLOR) is proposed in this paper by combining the advantages of opportunistic routing and reinforcement learning algorithm. The RLOR is a kind of distributed routing approach, which comprehensively considers nodes' peripheral status to select the appropriate relay nodes. Additionally, a recovery mechanism is employed in RLOR to enable the packets to bypass the void area efficiently and continue to forward, which improves the delivery rate of data in some sparse networks. The simulation results show that, compared with other representative underwater routing protocols, the proposed RLOR performs well in end-to-end delay, reliability, energy efficiency and other aspects in underwater dynamic network environments.
A Sensor Equipped Aquatic (SEA) swarm is a sensor cloud that drifts with water currents and enables 4-D (space and time) monitoring of local underwater events such as contaminants, marine life, and ...intruders. The swarm is escorted on the surface by drifting sonobuoys that collect data from the underwater sensors via acoustic modems and report it in real time via radio to a monitoring center. The goal of this study is to design an efficient anycast routing algorithm for reliable underwater sensor event reporting to any surface sonobuoy. Major challenges are the ocean current and limited resources (bandwidth and energy). In this paper, these challenges are addressed, and HydroCast, which is a hydraulic-pressure-based anycast routing protocol that exploits the measured pressure levels to route data to the surface sonobuoys, is proposed. This paper makes the following contributions: a novel opportunistic routing mechanism to select the subset of forwarders that maximizes the greedy progress yet limits cochannel interference and an efficient underwater dead end recovery method that outperforms the recently proposed approaches. The proposed routing protocols are validated through extensive simulations.
The majority of work in cognitive radio networks have focused on single-hop networks with mainly challenges at the physical and MAC layers. Recently, multi-hop secondary networks have gained ...attention as a promising design to leverage the full potential of cognitive radio networks. One of the main features of routing protocols in multi-hop networks is the routing metric used to select the best route for forwarding packets. In this paper, we survey the state-of-the-art routing metrics for cognitive radio networks. We start by listing the challenges that have to be addressed in designing a good routing metric for cognitive radio networks. We then provide a taxonomy of the different metrics and a survey of the way they have been used in different routing protocols. Then we present a case study to compare different classes of metrics. After that, we discuss how to combine individual routing metrics to obtain a global one. We end the paper with a discussion of the open issues in the design of future metrics for cognitive radio networks.
Vehicular ad hoc networks (VANETs) have been widely used in intelligent transportation systems (ITSs) for purposes such as the control of unmanned aerial vehicles (UAVs) and trajectory prediction. ...However, an efficient and reliable data routing decision scheme is critical for VANETs due to the feature of self-organizing wireless multi-hop communication. Compared with wireless networks, which are unstable and have limited bandwidth, wired networks normally provide longer transmission distances, higher network speeds and greater reliability. To address this problem, this paper proposes a reliable VANET routing decision scheme based on the Manhattan mobility model, which considers the integration of roadside units (RSUs) into wireless and wired modes for data transmission and routing optimization. First, the problems of frequently moving vehicles and network connectivity are analyzed based on road networks and the motion information of vehicle nodes. Second, an improved greedy algorithm for vehicle wireless communication is used for network optimization, and a wired RSU network is also applied. In addition, routing decision analysis is carried out in accordance with the probabilistic model for various transmission ranges by checking the connectivity among vehicles and RSUs. Finally, comprehensive experiments show that our proposed method can support real-time planning and improve network transmission performance compared with other baseline protocol approaches in terms of several metrics, including package delivery ratio, time delay and wireless hops.
Wireless sensor networks (WSNs) are networks with devices that can detect, process, store, and communicate wirelessly. Each network terminal can have multiple sensing devices that can measure ...physical variations such as temperature, brightness, humidity, and vibration. However, developing and implementing WSNs poses many challenges. This review presents the challenges of WSN using different routing algorithms such as geographic routing, energy-aware routing, delay aware routing, QoS aware routing, secure aware routing, and hierarchical aware routing. Another goal is to find out which WSN component automates interference and behavior. What kind of application is in the WSN depends not only on his work but also on the question of the basis, functionality, and handling of his project. The study was carefully planned, and the systematic review of the literature was set up in a strong framework according to a pre-defined protocol. Finally, we evaluate the performance parameters of previous routing algorithms with diverse routine metrics that are energy consumption, delay, packet delivery ratio, throughput, false ratio, packet loss ratio, and network overhead.
Recently, different applications of wireless sensor networks (WSNs) in the industry fields using different data transfer protocols has been developed. As the energy of sensor nodes is limited, ...prolonging network lifetime in WSNs considered a significant occurrence. To develop network permanence, researchers had considered energy consuming in routing protocols of WSNs by using modified Low Energy Adaptive Clustering Hierarchy. This article presents a developed effective transfer protocols for autonomic WSNs. An efficient routing scheme for wireless sensor network regarded as significant components of electronic devices is proposed. An optimal election probability of a node to be cluster head has being presented. In addition, this article uses a Voronoi diagram, which decomposes the nodes into zone around each node. This diagram used in management architecture for WSNs.
Vehicular ad hoc network is a collection of vehicles and associated road-side infrastructure, which is able to provide mobile wireless communication services. This highly dynamic topology structure ...is still open to many routing and message forwarding challenges. This paper addresses the issue of message delivery from vehicle to a fixed destination, by hopping over neighboring vehicles. We propose a reinforcement-learning-based hierarchical protocol called QGrid to improve the message deliver ratio with minimum possible delay and hops. The protocol works at two levels. First, it divides the geographical area into smaller grids and finds the next optimal grid toward the destination. Second, it discovers a vehicle inside or moving toward the next optimal grid for message relaying. There is no need of routing tables as the protocol builds a Q-value table based on the traffic flow in neighbor grids, which is then used for the grid selection. The vehicle selection process can employ different strategies, like, greedy selection of nearest neighbor, or solution based on the two-order Markov chain prediction of neighbor movement. This combination makes QGrid an offline and online solution. QGrid is further improved giving higher priority to vehicles with fixed routes and better communication capabilities, like buses, when making the vehicle selection. We have carried out extensive simulation evaluation by using real-world vehicular traces to measure the performance of our proposed schemes. The simulation comparisons among QGrid with/without bus aid, and existing position-based routing protocols, show the great improvement in the delivery percentage by our proposed routing protocol.
In vehicle routing problems (VRPs) the decisions to be taken concern the assignment of customers to vehicles and the sequencing of the customers assigned to each vehicle. Additional decisions may ...need to be jointly taken, depending on the specific problem setting. In this paper, after discussing the different kinds of decisions taken in different classes of VRPs, the class where the decision about when the routes start from the depot has to be taken is considered and the related literature is reviewed. This class of problems, that we call VRPs over time, includes the periodic routing problems, the inventory routing problems, the vehicle routing problems with release dates, and the multi-trip vehicle routing problems.
Geographic routing offers a radical departure from previous topology-dependent routing paradigms through its use of physical location in the routing process. Geographic routing protocols eliminate ...dependence on topology storage and the associated costs, which also makes them more suitable to handling dynamic behavior frequently found in wireless ad-hoc networks. Geographic routing protocols have been designed for a variety of applications ranging from mobility prediction and management through to anonymous routing and from energy efficiency to QoS. Geographic routing is also part of the larger area of context-awareness due to its usage of location data to make routing decisions and thus represents an important step in the journey towards ubiquitous computing. The focus of this paper, within the area of geographic routing is on wireless ad-hoc networks and how location information can benefit routing. This paper aims to provide both a comprehensive and methodical survey of existing literature in the area of geographic routing from its inception as well as acting as an introduction to the subject.
PDF
