Abstract: This paper aims to demonstrate how various algorithms can be implemented within swarms of autonomous robots to provide continuous inspection within underground pipeline networks. Current methods of fault detection within pipes are costly, time consuming and inefficient. As such, solutions tend toward a more reactive approach, repairing faults, as opposed to proactively seeking leaks and blockages. The paper presents an efficient inspection method, showing that autonomous swarm robotics is a viable way of monitoring underground infrastructure. Tailored adaptations of various Vehicle Routing Problems (VRP) and path-planning algorithms provide a customised inspection procedure for complicated networks of underground pipes. The performance of multiple algorithms is compared to determine their effectiveness and feasibility. Notable inspirations come from ant colonies and stigmergy, graph theory, the k-Chinese Postman Problem ( -CPP) and traffic theory. Unlike most swarm behaviours which rely on fast communication between agents, underground pipe networks are a highly challenging communication environment with extremely limited communication ranges. This is due to the extreme variability in the pipe conditions and relatively high attenuation of acoustic and radio waves with which robots would usually communicate. This paper illustrates how to optimise the inspection process and how to increase the frequency with which the robots pass each other, without compromising the routes they are able to take to cover the whole network.
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.
Abstract: In this paper, we consider the vehicle routing problem
with mixed fleet of conventional and heterogenous electric vehicles
and time dependent charging costs, denoted VRP-HFCC, 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 different insertion methods. All
heuristics are tested on real data instances.
Abstract: There are many classical algorithms for finding
routing in FPGA. But Using DNA computing we can solve the routes
efficiently and fast. The run time complexity of DNA algorithms is
much less than other classical algorithms which are used for solving
routing in FPGA. The research in DNA computing is in a primary
level. High information density of DNA molecules and massive
parallelism involved in the DNA reactions make DNA computing a
powerful tool. It has been proved by many research accomplishments
that any procedure that can be programmed in a silicon computer can
be realized as a DNA computing procedure. In this paper we have
proposed two tier approaches for the FPGA routing solution. First,
geometric FPGA detailed routing task is solved by transforming it
into a Boolean satisfiability equation with the property that any
assignment of input variables that satisfies the equation specifies a
valid routing. Satisfying assignment for particular route will result in
a valid routing and absence of a satisfying assignment implies that
the layout is un-routable. In second step, DNA search algorithm is
applied on this Boolean equation for solving routing alternatives
utilizing the properties of DNA computation. The simulated results
are satisfactory and give the indication of applicability of DNA
computing for solving the FPGA Routing problem.
Abstract: A key element of many distribution systems is the
routing and scheduling of vehicles servicing a set of customers. A
wide variety of exact and approximate algorithms have been
proposed for solving the vehicle routing problems (VRP). Exact
algorithms can only solve relatively small problems of VRP, which is
classified as NP-Hard. Several approximate algorithms have proven
successful in finding a feasible solution not necessarily optimum.
Although different parts of the problem are stochastic in nature; yet,
limited work relevant to the application of discrete event system
simulation has addressed the problem. Presented here is optimization
using simulation of VRP; where, a simplified problem has been
developed in the ExtendSimTM simulation environment; where,
ExtendSimTM evolutionary optimizer is used to minimize the total
transportation cost of the problem. Results obtained from the model
are very satisfactory. Further complexities of the problem are
proposed for consideration in the future.
Abstract: The paper proposes and validates a new method of solving instances of the vehicle routing problem (VRP). The approach is based on a multiple agent system paradigm. The paper contains the VRP formulation, an overview of the multiple agent environment used and a description of the proposed implementation. The approach is validated experimentally. The experiment plan and the discussion of experiment results follow.