Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 1320

Search results for: vehicle routing

1320 A Coordinate-Based Heuristic Route Search Algorithm for Delivery Truck Routing Problem

Authors: Ahmed Tarek, Ahmed Alveed

Abstract:

Vehicle routing problem is a well-known re-search avenue in computing. Modern vehicle routing is more focused with the GPS-based coordinate system, as the state-of-the-art vehicle, and trucking systems are equipped with digital navigation. In this paper, a new two dimensional coordinate-based algorithm for addressing the vehicle routing problem for a supply chain network is proposed and explored, and the algorithm is compared with other available, and recently devised heuristics. For the algorithms discussed, which includes the pro-posed coordinate-based search heuristic as well, the advantages and the disadvantages associated with the heuristics are explored. The proposed algorithm is studied from the stand point of a small supermarket chain delivery network that supplies to its stores in four different states around the East Coast area, and is trying to optimize its trucking delivery cost. Minimizing the delivery cost for the supply network of a supermarket chain is important to ensure its business success.

Keywords: coordinate-based optimal routing, Hamiltonian Circuit, heuristic algorithm, traveling salesman problem, vehicle routing problem

Procedia PDF Downloads 57
1319 Survey: Topology Hiding in Multipath Routing Protocol in MANET

Authors: Akshay Suhas Phalke, Manohar S. Chaudhari

Abstract:

In this paper, we have discussed the multipath routing with its variants. Our purpose is to discuss the different types of the multipath routing mechanism. Here we also put the taxonomy of the multipath routing. Multipath routing is used for the alternate path routing, reliable transmission of data and for better utilization of network resources. We also discussed the multipath routing for topology hiding such as TOHIP. In multipath routing, different parameters such as energy efficiency, packet delivery ratio, shortest path routing, fault tolerance play an important role. We have discussed a number of multipath routing protocol based on different parameters lastly.

Keywords: multi-path routing, WSN, topology, fault detection, trust

Procedia PDF Downloads 219
1318 Symbiotic Organism Search (SOS) for Solving the Capacitated Vehicle Routing Problem

Authors: Eki Ruskartina, Vincent F. Yu, Budi Santosa, A. A. N. Perwira Redi

Abstract:

This paper introduces symbiotic organism search (SOS) for solving capacitated vehicle routing problem (CVRP). SOS is a new approach in metaheuristics fields and never been used to solve discrete problems. A sophisticated decoding method to deal with a discrete problem setting in CVRP is applied using the basic symbiotic organism search (SOS) framework. The performance of the algorithm was evaluated on a set of benchmark instances and compared results with best known solution. The computational results show that the proposed algorithm can produce good solution as a preliminary testing. These results indicated that the proposed SOS can be applied as an alternative to solve the capacitated vehicle routing problem.

Keywords: symbiotic organism search, capacitated vehicle routing problem, metaheuristic

Procedia PDF Downloads 527
1317 A Metaheuristic Approach for the Pollution-Routing Problem

Authors: P. Parthiban, Sonu Rajak, R. Dhanalakshmi

Abstract:

This paper presents an Ant Colony Optimization (ACO) approach, combined with a Speed Optimization Algorithm (SOA) to solve the Vehicle Routing Problem (VRP) with environmental considerations, which is well known as Pollution-Routing Problem (PRP). It consists of routing a number of vehicles to serve a set of customers, and determining fuel consumption, driver wages and their speed on each route segment, while respecting the capacity constraints and time windows. Since VRP is NP-hard problem, so PRP also a NP-hard problem, which requires metaheuristics to solve this type of problems. The proposed solution method consists of two stages. Stage one is to solve a Vehicle Routing Problem with Time Window (VRPTW) using ACO and in the second stage, a SOA is run on the resulting VRPTW solution. Given a vehicle route, the SOA consists of finding the optimal speed on each arc of the route to minimize an objective function comprising fuel consumption costs and driver wages. The proposed algorithm tested on benchmark problem, the preliminary results show that the proposed algorithm can provide good solutions within reasonable computational time.

Keywords: ant colony optimization, CO2 emissions, speed optimization, vehicle routing

Procedia PDF Downloads 271
1316 An Ant Colony Optimization Approach for the Pollution Routing Problem

Authors: P. Parthiban, Sonu Rajak, N. Kannan, R. Dhanalakshmi

Abstract:

This paper deals with the Vehicle Routing Problem (VRP) with environmental considerations which is called Pollution Routing Problem (PRP). The objective is to minimize the operational and environmental costs. It consists of routing a number of vehicles to serve a set of customers, and determining fuel consumption, driver wages and their speed on each route segment, while respecting the capacity constraints and time windows. In this context, we presented an Ant Colony Optimization (ACO) approach, combined with a Speed Optimization Algorithm (SOA) to solve the PRP. The proposed solution method consists of two stages. Stage one is to solve a Vehicle Routing Problem with Time Window (VRPTW) using ACO and in the second stage a SOA is run on the resulting VRPTW solutions. Given a vehicle route, the SOA consists of finding the optimal speed on each arc of the route in order to minimize an objective function comprising fuel consumption costs and driver wages. The proposed algorithm tested on benchmark problem, the preliminary results show that the proposed algorithm is able to provide good solutions.

Keywords: ant colony optimization, CO2 emissions, combinatorial optimization, speed optimization, vehicle routing

Procedia PDF Downloads 197
1315 Improving the Global Competitiveness of SMEs by Logistics Transportation Management: Case Study Chicken Meat Supply Chain

Authors: P. Vanichkobchinda

Abstract:

The Logistics Transportation techniques, Open Vehicle Routing (OVR) is an approach toward transportation cost reduction, especially for long distance pickup and delivery nodes. The outstanding characteristic of OVR is that the route starting node and ending node are not necessary the same as in typical vehicle routing problems. This advantage enables the routing to flow continuously and the vehicle does not always return to its home base. This research aims to develop a heuristic for the open vehicle routing problem with pickup and delivery under time window and loading capacity constraints to minimize the total distance. The proposed heuristic is developed based on the Insertion method, which is a simple method and suitable for the rapid calculation that allows insertion of the new additional transportation requirements along the original paths. According to the heuristic analysis, cost comparisons between the proposed heuristic and companies are using method, nearest neighbor method show that the insertion heuristic. Moreover, the proposed heuristic gave superior solutions in all types of test problems. In conclusion, the proposed heuristic can effectively and efficiently solve the open vehicle routing. The research indicates that the improvement of new transport's calculation and the open vehicle routing with "Insertion Heuristic" represent a better outcome with 34.3 percent in average. in cost savings. Moreover, the proposed heuristic gave superior solutions in all types of test problems. In conclusion, the proposed heuristic can effectively and efficiently solve the open vehicle routing.

Keywords: business competitiveness, cost reduction, SMEs, logistics transportation, VRP

Procedia PDF Downloads 615
1314 A Polynomial Time Clustering Algorithm for Solving the Assignment Problem in the Vehicle Routing Problem

Authors: Lydia Wahid, Mona F. Ahmed, Nevin Darwish

Abstract:

The vehicle routing problem (VRP) consists of a group of customers that needs to be served. Each customer has a certain demand of goods. A central depot having a fleet of vehicles is responsible for supplying the customers with their demands. The problem is composed of two subproblems: The first subproblem is an assignment problem where the number of vehicles that will be used as well as the customers assigned to each vehicle are determined. The second subproblem is the routing problem in which for each vehicle having a number of customers assigned to it, the order of visits of the customers is determined. Optimal number of vehicles, as well as optimal total distance, should be achieved. In this paper, an approach for solving the first subproblem (the assignment problem) is presented. In the approach, a clustering algorithm is proposed for finding the optimal number of vehicles by grouping the customers into clusters where each cluster is visited by one vehicle. Finding the optimal number of clusters is NP-hard. This work presents a polynomial time clustering algorithm for finding the optimal number of clusters and solving the assignment problem.

Keywords: vehicle routing problems, clustering algorithms, Clarke and Wright Saving Method, agglomerative hierarchical clustering

Procedia PDF Downloads 263
1313 Adaptive Routing in NoC-Based Heterogeneous MPSoCs

Authors: M. K. Benhaoua, A. E. H. Benyamina, T. Djeradi, P. Boulet

Abstract:

In this paper, we propose adaptive routing that considers the routing of communications in order to optimize the overall performance. The routing technique uses a newly proposed Algorithm to route communications between the tasks. The routing we propose of the communications leads to a better optimization of several performance metrics (time and energy consumption). Experimental results show that the proposed routing approach provides significant performance improvements when compared to those using static routing.

Keywords: multi-processor systems-on-chip (mpsocs), network-on-chip (noc), heterogeneous architectures, adaptive routin

Procedia PDF Downloads 294
1312 Fuzzy Vehicle Routing Problem for Extreme Environment

Authors: G. Sirbiladze, B. Ghvaberidze, B. Matsaberidze

Abstract:

A fuzzy vehicle routing problem is considered in the possibilistic environment. A new criterion, maximization of expectation of reliability for movement on closed routes is constructed. The objective of the research is to implement a two-stage scheme for solution of this problem. Based on the algorithm of preferences on the first stage, the sample of so-called “promising” routes will be selected. On the second stage, for the selected promising routes new bi-criteria problem will be solved - minimization of total traveled distance and maximization of reliability of routes. The problem will be stated as a fuzzy-partitioning problem. Two possible solutions of this scheme are considered.

Keywords: vehicle routing problem, fuzzy partitioning problem, multiple-criteria optimization, possibility theory

Procedia PDF Downloads 460
1311 Robust Optimisation Model and Simulation-Particle Swarm Optimisation Approach for Vehicle Routing Problem with Stochastic Demands

Authors: Mohanad Al-Behadili, Djamila Ouelhadj

Abstract:

In this paper, a specific type of vehicle routing problem under stochastic demand (SVRP) is considered. This problem is of great importance because it models for many of the real world vehicle routing applications. This paper used a robust optimisation model to solve the problem along with the novel Simulation-Particle Swarm Optimisation (Sim-PSO) approach. The proposed Sim-PSO approach is based on the hybridization of the Monte Carlo simulation technique with the PSO algorithm. A comparative study between the proposed model and the Sim-PSO approach against other solution methods in the literature has been given in this paper. This comparison including the Analysis of Variance (ANOVA) to show the ability of the model and solution method in solving the complicated SVRP. The experimental results show that the proposed model and Sim-PSO approach has a significant impact on the obtained solution by providing better quality solutions comparing with well-known algorithms in the literature.

Keywords: stochastic vehicle routing problem, robust optimisation model, Monte Carlo simulation, particle swarm optimisation

Procedia PDF Downloads 201
1310 Probability Fuzzy Aggregation Operators in Vehicle Routing Problem

Authors: Anna Sikharulidze, Gia Sirbiladze

Abstract:

For the evaluation of unreliability levels of movement on the closed routes in the vehicle routing problem, the fuzzy operators family is constructed. The interactions between routing factors in extreme conditions on the roads are considered. A multi-criteria decision-making model (MCDM) is constructed. Constructed aggregations are based on the Choquet integral and the associated probability class of a fuzzy measure. Propositions on the correctness of the extension are proved. Connections between the operators and the compositions of dual triangular norms are described. The conjugate connections between the constructed operators are shown. Operators reflect interactions among all the combinations of the factors in the fuzzy MCDM process. Several variants of constructed operators are used in the decision-making problem regarding the assessment of unreliability and possibility levels of movement on closed routes.

Keywords: vehicle routing problem, associated probabilities of a fuzzy measure, choquet integral, fuzzy aggregation operator

Procedia PDF Downloads 227
1309 Routing Metrics and Protocols for Wireless Mesh Networks

Authors: Samira Kalantary, Zohre Saatzade

Abstract:

Wireless Mesh Networks (WMNs) are low-cost access networks built on cooperative routing over a backbone composed of stationary wireless routers. WMNs must deal with the highly unstable wireless medium. Thus, routing metrics and protocols are evolving by designing algorithms that consider link quality to choose the best routes. In this work, we analyse the state of the art in WMN metrics and propose taxonomy for WMN routing protocols. Performance measurements of a wireless mesh network deployed using various routing metrics are presented and corroborate our analysis.

Keywords: wireless mesh networks, routing protocols, routing metrics, bioinformatics

Procedia PDF Downloads 341
1308 Optimal Delivery of Two Similar Products to N Ordered Customers

Authors: Epaminondas G. Kyriakidis, Theodosis D. Dimitrakos, Constantinos C. Karamatsoukis

Abstract:

The vehicle routing problem (VRP) is a well-known problem in Operations Research and has been widely studied during the last fifty-five years. The context of the VRP is that of delivering products located at a central depot to customers who are scattered in a geographical area and have placed orders for these products. A vehicle or a fleet of vehicles start their routes from the depot and visit the customers in order to satisfy their demands. Special attention has been given to the capacitated VRP in which the vehicles have limited carrying capacity of the goods that must be delivered. In the present work, we present a specific capacitated stochastic vehicle routing problem which has realistic applications to distributions of materials to shops or to healthcare facilities or to military units. A vehicle starts its route from a depot loaded with items of two similar but not identical products. We name these products, product 1 and product 2. The vehicle must deliver the products to N customers according to a predefined sequence. This means that first customer 1 must be serviced, then customer 2 must be serviced, then customer 3 must be serviced and so on. The vehicle has a finite capacity and after servicing all customers it returns to the depot. It is assumed that each customer prefers either product 1 or product 2 with known probabilities. The actual preference of each customer becomes known when the vehicle visits the customer. It is also assumed that the quantity that each customer demands is a random variable with known distribution. The actual demand is revealed upon the vehicle’s arrival at customer’s site. The demand of each customer cannot exceed the vehicle capacity and the vehicle is allowed during its route to return to the depot to restock with quantities of both products. The travel costs between consecutive customers and the travel costs between the customers and the depot are known. If there is shortage for the desired product, it is permitted to deliver the other product at a reduced price. The objective is to find the optimal routing strategy, i.e. the routing strategy that minimizes the expected total cost among all possible strategies. It is possible to find the optimal routing strategy using a suitable stochastic dynamic programming algorithm. It is also possible to prove that the optimal routing strategy has a specific threshold-type structure, i.e. it is characterized by critical numbers. This structural result enables us to construct an efficient special-purpose dynamic programming algorithm that operates only over those routing strategies having this structure. The findings of the present study lead us to the conclusion that the dynamic programming method may be a very useful tool for the solution of specific vehicle routing problems. A problem for future research could be the study of a similar stochastic vehicle routing problem in which the vehicle instead of delivering, it collects products from ordered customers.

Keywords: collection of similar products, dynamic programming, stochastic demands, stochastic preferences, vehicle routing problem

Procedia PDF Downloads 182
1307 Artificial Bee Colony Based Modified Energy Efficient Predictive Routing in MANET

Authors: Akhil Dubey, Rajnesh Singh

Abstract:

In modern days there occur many rapid modifications in field of ad hoc network. These modifications create many revolutionary changes in the routing. Predictive energy efficient routing is inspired on the bee’s behavior of swarm intelligence. Predictive routing improves the efficiency of routing in the energetic point of view. The main aim of this routing is the minimum energy consumption during communication and maximized intermediate node’s remaining battery power. This routing is based on food searching behavior of bees. There are two types of bees for the exploration phase the scout bees and for the evolution phase forager bees use by this routing. This routing algorithm computes the energy consumption, fitness ratio and goodness of the path. In this paper we review the literature related with predictive routing, presenting modified routing and simulation result of this algorithm comparison with artificial bee colony based routing schemes in MANET and see the results of path fitness and probability of fitness.

Keywords: mobile ad hoc network, artificial bee colony, PEEBR, modified predictive routing

Procedia PDF Downloads 294
1306 Dynamic Route Optimization in Vehicle Adhoc Networks: A Heuristics Routing Protocol

Authors: Rafi Ullah, Shah Muhammad Emaduddin, Taha Jilani

Abstract:

Vehicle Adhoc Networks (VANET) belongs to a special class of Mobile Adhoc Network (MANET) with high mobility. Network is created by road side vehicles equipped with communication devices like GPS and Wifi etc. Since the environment is highly dynamic due to difference in speed and high mobility of vehicles and weak stability of the network connection, it is a challenging task to design an efficient routing protocol for such an unstable environment. Our proposed algorithm uses heuristic for the calculation of optimal path for routing the packet efficiently in collaboration with several other parameters like geographical location, speed, priority, the distance among the vehicles, communication range, and networks congestion. We have incorporated probabilistic, heuristic and machine learning based approach inconsistency with the relay function of the memory buffer to keep the packet moving towards the destination. These parameters when used in collaboration provide us a very strong and admissible heuristics. We have mathematically proved that the proposed technique is efficient for the routing of packets, especially in a medical emergency situation. These networks can be used for medical emergency, security, entertainment and routing purposes.

Keywords: heuristics routing, intelligent routing, VANET, route optimization

Procedia PDF Downloads 90
1305 A Survey of Novel Opportunistic Routing Protocols in Mobile Ad Hoc Networks

Authors: R. Poonkuzhali, M. Y. Sanavullah, M. R. Gurupriya

Abstract:

Opportunistic routing is used, where the network has the features like dynamic topology changes and intermittent network connectivity. In Delay Tolerant network or Disruption tolerant network opportunistic forwarding technique is widely used. The key idea of opportunistic routing is selecting forwarding nodes to forward data and coordination among these nodes to avoid duplicate transmissions. This paper gives the analysis of pros and cons of various opportunistic routing techniques used in MANET.

Keywords: ETX, opportunistic routing, PSR, throughput

Procedia PDF Downloads 413
1304 Analysis of Two Methods to Estimation Stochastic Demand in the Vehicle Routing Problem

Authors: Fatemeh Torfi

Abstract:

Estimation of stochastic demand in physical distribution in general and efficient transport routs management in particular is emerging as a crucial factor in urban planning domain. It is particularly important in some municipalities such as Tehran where a sound demand management calls for a realistic analysis of the routing system. The methodology involved critically investigating a fuzzy least-squares linear regression approach (FLLRs) to estimate the stochastic demands in the vehicle routing problem (VRP) bearing in mind the customer's preferences order. A FLLR method is proposed in solving the VRP with stochastic demands. Approximate-distance fuzzy least-squares (ADFL) estimator ADFL estimator is applied to original data taken from a case study. The SSR values of the ADFL estimator and real demand are obtained and then compared to SSR values of the nominal demand and real demand. Empirical results showed that the proposed methods can be viable in solving problems under circumstances of having vague and imprecise performance ratings. The results further proved that application of the ADFL was realistic and efficient estimator to face the stochastic demand challenges in vehicle routing system management and solve relevant problems.

Keywords: fuzzy least-squares, stochastic, location, routing problems

Procedia PDF Downloads 351
1303 An Application of Integrated Multi-Objective Particles Swarm Optimization and Genetic Algorithm Metaheuristic through Fuzzy Logic for Optimization of Vehicle Routing Problems in Sugar Industry

Authors: Mukhtiar Singh, Sumeet Nagar

Abstract:

Vehicle routing problem (VRP) is a combinatorial optimization and nonlinear programming problem aiming to optimize decisions regarding given set of routes for a fleet of vehicles in order to provide cost-effective and efficient delivery of both services and goods to the intended customers. This paper proposes the application of integrated particle swarm optimization (PSO) and genetic optimization algorithm (GA) to address the Vehicle routing problem in sugarcane industry in India. Suger industry is very prominent agro-based industry in India due to its impacts on rural livelihood and estimated to be employing around 5 lakhs workers directly in sugar mills. Due to various inadequacies, inefficiencies and inappropriateness associated with the current vehicle routing model it costs huge money loss to the industry which needs to be addressed in proper context. The proposed algorithm utilizes the crossover operation that originally appears in genetic algorithm (GA) to improve its flexibility and manipulation more readily and avoid being trapped in local optimum, and simultaneously for improving the convergence speed of the algorithm, level set theory is also added to it. We employ the hybrid approach to an example of VRP and compare its result with those generated by PSO, GA, and parallel PSO algorithms. The experimental comparison results indicate that the performance of hybrid algorithm is superior to others, and it will become an effective approach for solving discrete combinatory problems.

Keywords: fuzzy logic, genetic algorithm, particle swarm optimization, vehicle routing problem

Procedia PDF Downloads 307
1302 A Stochastic Vehicle Routing Problem with Ordered Customers and Collection of Two Similar Products

Authors: Epaminondas G. Kyriakidis, Theodosis D. Dimitrakos, Constantinos C. Karamatsoukis

Abstract:

The vehicle routing problem (VRP) is a well-known problem in Operations Research and has been widely studied during the last fifty-five years. The context of the VRP is that of delivering or collecting products to or from customers who are scattered in a geographical area and have placed orders for these products. A vehicle or a fleet of vehicles start their routes from a depot and visit the customers in order to satisfy their demands. Special attention has been given to the capacitated VRP in which the vehicles have limited carrying capacity for the goods that are delivered or collected. In the present work, we present a specific capacitated stochastic vehicle routing problem which has many realistic applications. We develop and analyze a mathematical model for a specific vehicle routing problem in which a vehicle starts its route from a depot and visits N customers according to a particular sequence in order to collect from them two similar but not identical products. We name these products, product 1 and product 2. Each customer possesses items either of product 1 or product 2 with known probabilities. The number of the items of product 1 or product 2 that each customer possesses is a discrete random variable with known distribution. The actual quantity and the actual type of product that each customer possesses are revealed only when the vehicle arrives at the customer’s site. It is assumed that the vehicle has two compartments. We name these compartments, compartment 1 and compartment 2. It is assumed that compartment 1 is suitable for loading product 1 and compartment 2 is suitable for loading product 2. However, it is permitted to load items of product 1 into compartment 2 and items of product 2 into compartment 1. These actions cause costs that are due to extra labor. The vehicle is allowed during its route to return to the depot to unload the items of both products. The travel costs between consecutive customers and the travel costs between the customers and the depot are known. The objective is to find the optimal routing strategy, i.e. the routing strategy that minimizes the total expected cost among all possible strategies for servicing all customers. It is possible to develop a suitable dynamic programming algorithm for the determination of the optimal routing strategy. It is also possible to prove that the optimal routing strategy has a specific threshold-type strategy. Specifically, it is shown that for each customer the optimal actions are characterized by some critical integers. This structural result enables us to design a special-purpose dynamic programming algorithm that operates only over these strategies having this structural property. Extensive numerical results provide strong evidence that the special-purpose dynamic programming algorithm is considerably more efficient than the initial dynamic programming algorithm. Furthermore, if we consider the same problem without the assumption that the customers are ordered, numerical experiments indicate that the optimal routing strategy can be computed if N is smaller or equal to eight.

Keywords: dynamic programming, similar products, stochastic demands, stochastic preferences, vehicle routing problem

Procedia PDF Downloads 176
1301 Vehicle Routing Problem Considering Alternative Roads under Triple Bottom Line Accounting

Authors: Onur Kaya, Ilknur Tukenmez

Abstract:

In this study, we consider vehicle routing problems on networks with alternative direct links between nodes, and we analyze a multi-objective problem considering the financial, environmental and social objectives in this context. In real life, there might exist several alternative direct roads between two nodes, and these roads might have differences in terms of their lengths and durations. For example, a road might be shorter than another but might require longer time due to traffic and speed limits. Similarly, some toll roads might be shorter or faster but require additional payment, leading to higher costs. We consider such alternative links in our problem and develop a mixed integer linear programming model that determines which alternative link to use between two nodes, in addition to determining the optimal routes for different vehicles, depending on the model objectives and constraints. We consider the minimum cost routing as the financial objective for the company, minimizing the CO2 emissions and gas usage as the environmental objectives, and optimizing the driver working conditions/working hours, and minimizing the risks of accidents as the social objectives. With these objective functions, we aim to determine which routes, and which alternative links should be used in addition to the speed choices on each link. We discuss the results of the developed vehicle routing models and compare their results depending on the system parameters.

Keywords: vehicle routing, alternative links between nodes, mixed integer linear programming, triple bottom line accounting

Procedia PDF Downloads 298
1300 A Low Power Consumption Routing Protocol Based on a Meta-Heuristics

Authors: Kaddi Mohammed, Benahmed Khelifa D. Benatiallah

Abstract:

A sensor network consists of a large number of sensors deployed in areas to monitor and communicate with each other through a wireless medium. The collected routing data in the network consumes most of the energy of the sensor nodes. For this purpose, multiple routing approaches have been proposed to conserve energy resource at the sensors and to overcome the challenges of its limitation. In this work, we propose a new low energy consumption routing protocol for wireless sensor networks based on a meta-heuristic methods. Our protocol is to operate more fairly energy when routing captured data to the base station.

Keywords: WSN, routing, energy, heuristic

Procedia PDF Downloads 210
1299 Performance Analysis of Ad-Hoc Network Routing Protocols

Authors: I. Baddari, A. Riahla, M. Mezghich

Abstract:

Today in the literature, we discover a lot of routing algorithms which some have been the subject of normalization. Two great classes Routing algorithms are defined, the first is the class reactive algorithms and the second that of algorithms proactive. The aim of this work is to make a comparative study between some routing algorithms. Two comparisons are considered. The first will focus on the protocols of the same class and second class on algorithms of different classes (one reactive and the other proactive). Since they are not based on analytical models, the exact evaluation of some aspects of these protocols is challenging. Simulations have to be done in order to study their performances. Our simulation is performed in NS2 (Network Simulator 2). It identified a classification of the different routing algorithms studied in a metrics such as loss of message, the time transmission, mobility, etc.

Keywords: ad-hoc network routing protocol, simulation, NS2, delay, packet loss, wideband, mobility

Procedia PDF Downloads 260
1298 Cloud-Based Dynamic Routing with Feedback in Formal Methods

Authors: Jawid Ahmad Baktash, Mursal Dawodi, Tomokazu Nagata

Abstract:

With the rapid growth of Cloud Computing, Formal Methods became a good choice for the refinement of message specification and verification for Dynamic Routing in Cloud Computing. Cloud-based Dynamic Routing is becoming increasingly popular. We propose feedback in Formal Methods for Dynamic Routing and Cloud Computing; the model and topologies show how to send messages from index zero to all others formally. The responsibility of proper verification becomes crucial with Dynamic Routing in the cloud. Formal Methods can play an essential role in the routing and development of Networks, and the testing of distributed systems. Event-B is a formal technique that consists of describing the problem rigorously and introduces solutions or details in the refinement steps. Event-B is a variant of B, designed for developing distributed systems and message passing of the dynamic routing. In Event-B and formal methods, the events consist of guarded actions occurring spontaneously rather than being invoked.

Keywords: cloud, dynamic routing, formal method, Pro-B, event-B

Procedia PDF Downloads 327
1297 Comparative Study of Ad Hoc Routing Protocols in Vehicular Ad-Hoc Networks for Smart City

Authors: Khadija Raissi, Bechir Ben Gouissem

Abstract:

In this paper, we perform the investigation of some routing protocols in Vehicular Ad-Hoc Network (VANET) context. Indeed, we study the efficiency of protocols like Dynamic Source Routing (DSR), Ad hoc On-demand Distance Vector Routing (AODV), Destination Sequenced Distance Vector (DSDV), Optimized Link State Routing convention (OLSR) and Vehicular Multi-hop algorithm for Stable Clustering (VMASC) in terms of packet delivery ratio (PDR) and throughput. The performance evaluation and comparison between the studied protocols shows that the VMASC is the best protocols regarding fast data transmission and link stability in VANETs. The validation of all results is done by the NS3 simulator.

Keywords: VANET, smart city, AODV, OLSR, DSR, OLSR, VMASC, routing protocols, NS3

Procedia PDF Downloads 206
1296 Care: A Cluster Based Approach for Reliable and Efficient Routing Protocol in Wireless Sensor Networks

Authors: K. Prasanth, S. Hafeezullah Khan, B. Haribalakrishnan, D. Arun, S. Jayapriya, S. Dhivya, N. Vijayarangan

Abstract:

The main goal of our approach is to find the optimum positions for the sensor nodes, reinforcing the communications in points where certain lack of connectivity is found. Routing is the major problem in sensor network’s data transfer between nodes. We are going to provide an efficient routing technique to make data signal transfer to reach the base station soon without any interruption. Clustering and routing are the two important key factors to be considered in case of WSN. To carry out the communication from the nodes to their cluster head, we propose a parameterizable protocol so that the developer can indicate if the routing has to be sensitive to either the link quality of the nodes or the their battery levels.

Keywords: clusters, routing, wireless sensor networks, three phases, sensor networks

Procedia PDF Downloads 393
1295 Support for Planning of Mobile Personnel Tasks by Solving Time-Dependent Routing Problems

Authors: Wlodzimierz Ogryczak, Tomasz Sliwinski, Jaroslaw Hurkala, Mariusz Kaleta, Bartosz Kozlowski, Piotr Palka

Abstract:

Implementation concepts of a decision support system for planning and management of mobile personnel tasks (sales representatives and others) are discussed. Large-scale periodic time-dependent vehicle routing and scheduling problems with complex constraints are solved for this purpose. Complex nonuniform constraints with respect to frequency, time windows, working time, etc. are taken into account with additional fast adaptive procedures for operational rescheduling of plans in the presence of various disturbances. Five individual solution quality indicators with respect to a single personnel person are considered. This paper deals with modeling issues corresponding to the problem and general solution concepts. The research was supported by the European Union through the European Regional Development Fund under the Operational Programme ‘Innovative Economy’ for the years 2007-2013; Priority 1 Research and development of modern technologies under the project POIG.01.03.01-14-076/12: 'Decision Support System for Large-Scale Periodic Vehicle Routing and Scheduling Problems with Complex Constraints.'

Keywords: mobile personnel management, multiple criteria, time dependent, time windows, vehicle routing and scheduling

Procedia PDF Downloads 253
1294 A Hybrid Algorithm Based on Greedy Randomized Adaptive Search Procedure and Chemical Reaction Optimization for the Vehicle Routing Problem with Hard Time Windows

Authors: Imen Boudali, Marwa Ragmoun

Abstract:

The Vehicle Routing Problem with Hard Time Windows (VRPHTW) is a basic distribution management problem that models many real-world problems. The objective of the problem is to deliver a set of customers with known demands on minimum-cost vehicle routes while satisfying vehicle capacity and hard time windows for customers. In this paper, we propose to deal with our optimization problem by using a new hybrid stochastic algorithm based on two metaheuristics: Chemical Reaction Optimization (CRO) and Greedy Randomized Adaptive Search Procedure (GRASP). The first method is inspired by the natural process of chemical reactions enabling the transformation of unstable substances with excessive energy to stable ones. During this process, the molecules interact with each other through a series of elementary reactions to reach minimum energy for their existence. This property is embedded in CRO to solve the VRPHTW. In order to enhance the population diversity throughout the search process, we integrated the GRASP in our method. Simulation results on the base of Solomon’s benchmark instances show the very satisfactory performances of the proposed approach.

Keywords: Benchmark Problems, Combinatorial Optimization, Vehicle Routing Problem with Hard Time Windows, Meta-heuristics, Hybridization, GRASP, CRO

Procedia PDF Downloads 284
1293 Vehicle Routing Problem with Mixed Fleet of Conventional and Heterogenous Electric Vehicles and Time Dependent Charging Costs

Authors: Ons Sassi, Wahiba Ramdane Cherif-Khettaf, Ammar Oulamara

Abstract:

In this paper, we consider a new real-life Heterogenous Electric Vehicle Routing Problem with Time Dependant Charging Costs and a Mixed Fleet (HEVRP-TDMF), in which a set of geographically scattered customers have to be served by a mixed fleet of vehicles composed of a heterogenous fleet of Electric Vehicles (EVs), having different battery capacities and operating costs, and Conventional Vehicles (CVs). We include the possibility of charging EVs in the available charging stations during the routes in order to serve all customers. Each charging station offers charging service with a known technology of chargers and time-dependent charging costs. Charging stations are also subject to operating time windows constraints. EVs are not necessarily compatible with all available charging technologies and a partial charging is allowed. Intermittent charging at the depot is also allowed provided that constraints related to the electricity grid are satisfied. The objective is to minimize the number of employed vehicles and then minimize the total travel and charging costs. In this study, we present a Mixed Integer Programming Model and develop a Charging Routing Heuristic and a Local Search Heuristic based on the Inject-Eject routine with three different insertion strategies. All heuristics are tested on real data instances.

Keywords: charging problem, electric vehicle, heuristics, local search, optimization, routing problem

Procedia PDF Downloads 394
1292 GIS-Based Topographical Network for Minimum “Exertion” Routing

Authors: Katherine Carl Payne, Moshe Dror

Abstract:

The problem of minimum cost routing has been extensively explored in a variety of contexts. While there is a prevalence of routing applications based on least distance, time, and related attributes, exertion-based routing has remained relatively unexplored. In particular, the network structures traditionally used to construct minimum cost paths are not suited to representing exertion or finding paths of least exertion based on road gradient. In this paper, we introduce a topographical network or “topograph” that enables minimum cost routing based on the exertion metric on each arc in a given road network as it is related to changes in road gradient. We describe an algorithm for topograph construction and present the implementation of the topograph on a road network of the state of California with ~22 million nodes.

Keywords: topograph, RPE, routing, GIS

Procedia PDF Downloads 443
1291 Estimation of the Parameters of Muskingum Methods for the Prediction of the Flood Depth in the Moudjar River Catchment

Authors: Fares Laouacheria, Said Kechida, Moncef Chabi

Abstract:

The objective of the study was based on the hydrological routing modelling for the continuous monitoring of the hydrological situation in the Moudjar river catchment, especially during floods with Hydrologic Engineering Center–Hydrologic Modelling Systems (HEC-HMS). The HEC-GeoHMS was used to transform data from geographic information system (GIS) to HEC-HMS for delineating and modelling the catchment river in order to estimate the runoff volume, which is used as inputs to the hydrological routing model. Two hydrological routing models were used, namely Muskingum and Muskingum routing models, for conducting this study. In this study, a comparison between the parameters of the Muskingum and Muskingum-Cunge routing models in HEC-HMS was used for modelling flood routing in the Moudjar river catchment and determining the relationship between these parameters and the physical characteristics of the river. The results indicate that the effects of input parameters such as the weighting factor "X" and travel time "K" on the output results are more significant, where the Muskingum routing model was more sensitive to input parameters than the Muskingum-Cunge routing model. This study can contribute to understand and improve the knowledge of the mechanisms of river floods, especially in ungauged river catchments.

Keywords: HEC-HMS, hydrological modelling, Muskingum routing model, Muskingum-Cunge routing model

Procedia PDF Downloads 169