Search

In an increasingly interconnected world, the efficient and economical transportation of individuals and commodities has emerged as a cornerstone of modern society. Optimizing transportation plans has a huge potential for journey planning, congestion reduction, supply chain management, and data exchanges. These strategies hold immense relevance not onlyin the realm of engineering and transportation, but also in other fields, such as physics, computer science, economics, and several subject areas in mathematics. The present thesis aims to elucidate the optimization of transportation strategies, with a particular focus on two classical problems, finding short paths in large networks and solving optimal transport problems with flow-rate constraints.The so-called shortest path problem seeks an optimal path of transporting one unit of mass between pairs of vertices on graphs. We present a novel formulation of the problem as an l1-regularized regression, often referred to as lasso (Least Absolute Shrinkage and Selection Operator). Based on this formulation, we draw a connection specifically between trees that grow as active edge-sets in the least angle regression (LARS) algorithm of the lasso problem, and respective shortest-path trees that emerge using the bi-directional Dijkstra algorithm. Then, to overcome the dimensionality challenge in large graphs, we explore the alternating direction method of multipliers (ADMM) in the lasso formulation. The resulting derivativeproximal algorithm speeds up the search for the short paths, trading off optimality (i.e., finding shortest paths) that may not be absolutely essential in a variety applications.The basic transport problem is motivated by the need to transport resources/mass between end-point distributions (supply and demand). We consider the classical Monge-Kantorovich optimal transport problem with a quadratic cost functional to penalize distance of transport, with an added constraint that transported mass is required to pass through constriction points while abiding by specified allowable flow-rate; constriction points may be conceptualized as toll stations with limited throughput. Our contributions in this topic are as follows: (1) we provide a precise Monge formulation for the optimal transport problem with flux constraint at constriction sites along the path that is amenable to generalization in higher dimensions. We work out in detail the case of transport in one dimension by proving existence and uniqueness of solutions. Under suitable regularity assumptions we give an explicit construction of the transport plan; (2) we provide a Kantorovich-type reformulation of the problem by introducing a marginal probability density for the time that mass-elements cross toll stations –a probability density that is to be determined so as to meet given flow-rate constraints. Interestingly, the Kantorovich-type formalism leads to multi-marginal optimal transport problem that is readily solvable by using linear programming. Moreover, existence and uniqueness of solutions are also established in this setting. Then, (3) we propose an entropic penalty term to regularize and reduce the computational cost of resulting multi-marginal problems. Entropic regularization of standard optimal transport leads to an efficient algorithm, the Sinkhorn algorithm, which applies in the present case as well. Leveraging the splittable nature of the cost in our formulation, we proposed a Gluing Sinkhorn algorithm for the multi-marginal optimal transport problem, which reduces the computational cost to a level comparable to that in standard two-marginal problems.

This paper considers SUB_GOALs by using basic A* algorithm and Subgoal Graphs in a hybrid approach to execute optimal route. SUB_GOALs identified with pre-searching from basic A* at break points and Subgoal Graphs at corners of obstacles are added to SUB_TABLE to expedite the final searching in the hybrid approach. Map to work on is divided to subregions with decision-making process by using line-of-sight to avoid redundant searching. In the final searching layer, all feasible SUB_GOALs gained from decision-making process in the same subregion are connected to find final solutions of routes. Solutions achieved in the divided subregions are evaluated and combined to discover the final optimal route. The proposed hybrid approach is applied to three different scenarios in various dimensions of maps. In these three scenarios, the shortest route without hitting obstacles is calculated as 46.67, 57.76 and 124.7 units, respectively, and compared with other search algorithms. Simulation results of route planning are demonstrated to exhibit the effectiveness of the proposed hybrid approach.

Path quality and computational time have formed together a well-known trade-off problem for path planning techniques. Due to this trade-off, contributions were usually considering improving only one of the two aspects, either increasing the swiftness as in real-time robotic path planning algorithms or enhancing the path quality as in shortest path query algorithms. Producing a path planning technique that targets both aspects is a challenging problem for robotic systems. However, this paper proposes a novel path planning framework that controls the motion of robotic systems and aims to overcome this traditional trade-off challenge, by targeting both, decreasing the computational time, and improving the path quality represented by the path length and smoothness. The shortest path is obtained by minimizing a novel objective function inspired by the artificial potential field methodology. To accelerate the execution, the Particle Swarm Optimization (PSO) technique is adopted to obtain the optimal solution in a real-time hop-by-hop manner imitating the procedures performed by computer network routing protocols. Testbed experimental results have proven the effectiveness of the proposed technique and showed superior performance over other meta-heuristic optimization techniques and over classical path planning approaches such as A*, D*, and PRM.

PT XYZ is one of freight forwarding companies in Indonesia, which is located in the city of Bandung. This company has managerial functions related to Collecting, Processing, Transporting, Delivery, and Reporting. However, the fact is in the process of Transporting this company still uses a zoning system which is a shipping system that still divides tertiary areas and each of these areas uses one vehicle. One problem that arises is that companies want effective and efficient performance in the distribution system of goods with the minimum total transportation costs. However, the company does not know yet whether the company's shipping routes have been effective and efficient or not. The company has tertiary network distribution route that are 2 routes with a total distance of 143.4 Km and a total transportation cost of Rp 5,681,484 /month. This research aims to determine the optimal goods distribution route using the Ant Colony Optimization Algorithm method, which is the method of finding the shortest path following ant behavior in taking food to its nest. Based on the results of the research, it is obtained a total distance of 109.2 Km because it becomes 1 route and total transportation costs Rp 3,337,992 /month, then it is obtained optimal results with a difference in distance is 34.2 Km and a total transportation cost of Rp 2,343,492 /month using one vehicle. Keywords: Optimization, Distribution, Ant Colony Optimization Algorithm

Previous studies on pipe auto-routing algorithms generally used such algorithms as A∗, Dijkstra, Genetic Algorithm, Particle Swarm Optimization, and Ant Colony Optimization, to satisfy the relevant constraints of its own field and improve the output quality. On the other hand, this study aimed to significantly improve path-finding speed by applying the Jump Point Search (JPS) algorithm, which requires lower search cost than the abovementioned algorithms, for pipe routing. The existing JPS, however, is limited to two-dimensional spaces and can only find the shortest path. Thus, it requires several improvements to be applied to pipe routing. Pipe routing is performed in a three-dimensional space, and the path of piping must be parallel to the axis to minimize its interference with other facilities. In addition, the number of elbows must be reduced to the maximum from an economic perspective, and preferred spaces in the path must also be included. The existing JPS was improved for the pipe routing problem such that it can consider the above-mentioned problem. The fast path-finding speed of the proposed algorithm was verified by comparing it with the conventional A∗ algorithm in terms of resolution.

Valuation algebras abstract a large number of formalisms for automated reasoning and enable the definition of generic inference procedures. Many of these formalisms provide some notion of solution. Typical examples are satisfying assignments in constraint systems, models in logics or solutions to linear equation systems. Dynamic programming algorithms rely on low treewidth decompositions and can be understood as particular cases of a single algorithmic scheme for finding solutions in a valuation algebra. The most encompassing description of this algorithmic scheme to date has been proposed by Pouly and Kohlas together with sufficient conditions for its correctness. Unfortunately, the formalization relies on a theorem for which we provide a counterexample. In spite of that, the mainline of Pouly and Kohlas' theory is correct, although some of the necessary conditions have to be revised. In this paper we analyze the impact that the counterexample has on the theory, and rebuild the theory providing correct sufficient conditions for the algorithms. Furthermore, we also provide necessary conditions for the algorithms, allowing for a sharper characterization of when the algorithmic scheme can be applied. The contribution of the paper is not limited to correcting Pouly and Kohlas' theory. First, we generalize their results from discrete tuples to tuple systems. This allows us to cover some classical algorithms, such as sparse Cholesky factorization, as well as more recently proposed algorithms, such as SNOWBALL (sparse all-pairs shortest path problems), as particular cases of the generic valuation-based algorithms presented here. For the particular case of valuation algebras induced by selective semirings, Pouly and Kohlas presented an algorithm for finding all solutions without requiring any additional condition for correctness. We characterize a necessary and a sufficient condition for it. Furthermore, we also introduce a new algorithm that requires no necessary condition., This work has been supported by projects COR (TIN2012-38876-C02-01), Collectiveware (TIN2015-66863-C2-1-R), GEAR (CSIC - 201350E112), by the Generalitat of Catalunya grant 2014-SGR-118 and also by the Secretaria d'Universitats i Recerca de la Generalitat de Catalunya and the European Social Funds (AGAUR 2019FI B1 00094).

Advances in robotic motion and computer vision have contributed to the increased use of automated and unmanned vehicles in complex and dynamic environments for various applications. Unmanned surface vehicles (USVs) have attracted a lot of attention from scientists to consolidate the wide use of USVs in maritime transportation. However, most of the traditional path planning approaches include single-objective approaches that mainly find the shortest path. Dynamic and complex environments impose the need for multi-objective path planning where an optimal path should be found to satisfy contradicting objective terms. To this end, a swarm intelligence graph-based pathfinding algorithm (SIGPA) has been proposed in the recent literature. This study aims to enhance the performance of SIGPA algorithm by integrating fuzzy logic in order to cope with the multiple objectives and generate quality solutions. A comparative evaluation is conducted among SIGPA and the two most popular fuzzy inference systems, Mamdani (SIGPAF-M) and Takagi–Sugeno–Kang (SIGPAF-TSK). The results showed that depending on the needs of the application, each methodology can contribute respectively. SIGPA remains a reliable approach for real-time applications due to low computational effort, SIGPAF-M generates better paths, and SIGPAF-TSK reaches a better trade-off among solution quality and computation time.

Distance transform, a central operation in image and video analysis, involves finding the shortest path between feature and non-feature entries of a binary image. The process may be implemented using chamfer-based sequential algorithms that apply small-neighborhood masks to estimate the Euclidean metric. Success of these algorithms depends on the cost function used to optimize chamfer weights. And, for years, mean absolute error and mean squared error have been used for optimization. However, studies have revealed weaknesses of these cost functions—sensitivity against outliers, lack of symmetry, and biasedness—which limit their application. In this work, we have proposed a robust and a more accurate cost function, symmetric mean absolute percentage error, which attempts to address some weaknesses. The proposed function averages the absolute percentage errors in a set of measurements and offers interesting mathematical properties (smoothness, differentiability, boundedness, and robustness) that allow easy interpretation and analysis of the results. Numerical results show that chamfer masks designed under our optimization criterion generate lower errors. The present work has also proposed an automatic algorithm that converts coefficients of the designed real-valued masks into integers, which are preferable in most practical computing devices. Lastly, we have modified the chamfer algorithm to improve its speed and then embedded the proposed weights into the algorithm to compute distance maps of real images. Results show that the proposed algorithm is faster and uses fewer number of operations compared with those consumed by the classical chamfer algorithm. Our results may be useful in robotics to address the matching problem.

Given the growth, complexity, and size of the Internet, new methodologies are needed to support cost-effective resource provisioning. This paper provides a cost-based polynomial-time heuristic algorithm for resource provisioning optimization called multi-layered market algorithm (MMA). The MMA is solvable for multi-layered, multi-technology, and practical-sized networks, where the traffic is modeled as a combination of constant bit-rate and variable bit-rate (VBR) traffic streams. A VBR stream is modeled either by a Gaussian process or by a Poisson Pareto burst process (PPBP) which under certain parameter values is long-range dependent – a known characteristic of the Internet traffic streams. The consideration of VBR traffic models in a multi-layered network optimization is a key novel aspect of MMA. The MMA considers a range of transport technologies operating in layers and traffic sharing schemes. The MMA implements flow-size-based routing where flows according to their sizes are routed independently. As routing affects resource requirement, such considerations are important for resource provisioning by the given cost models. The complexity resulting from these considerations, including layering and PPBP traffic, requires a simplified design philosophy which in this paper, is based on adopting the shortest path routing in each layer. This is achieved by MMA which is based on an iterative algorithm, and resource provisioning that is performed link-by-link in all layers. As a benchmark for MMA, we provide an integer linear programming (ILP) formulation for a multi-layered network optimization problem with fixed end-to-end demands. The MMA is validated by comparing its solutions to those ILP results in different variants of a six-node network, and its software is verified using double-entry bookkeeping – a method commonly used in accounting systems. The MMA runs on a platform called network mark-up language, which enables visualization and further validation of the results.

We study a multicommodity, multiperiod, resource-constrained pickup-and-delivery problem inspired by the short-term planning of maintenance services at offshore wind farms. To begin a maintenance service, different types of relatively scarce servicemen need to be delivered (transported) to the service locations. We develop resource-exceeding route (RER) inequalities, which are inspired by knapsack cover inequalities, to model the scarcity of servicemen. In addition to a traditional separation approach, we present a column-dependent constraints approach so as to include the RER inequalities in the mathematical formulation. An alternative pricing strategy is developed to correctly include the column-dependent constraints. The resulting approach is broadly applicable to any routing problem that involves a set of scarce resources. We present a branch-and-price-and-cut algorithm to compare both approaches that include RER inequalities. The branch-and-price-and-cut algorithm relies on efficiently solving a new variant of the elementary resource-constrained shortest-path problem, using a tailored pulse algorithm developed specifically to solve it. Computational experiments show that the RER inequalities significantly tighten the root node relaxations. The column-dependent constraints approach then searches the branch-and-bound tree more effectively and appears to be competitive with the traditional separation procedure. Both approaches are able to solve instances of up to 92 nodes over 21 periods to optimality.

New cities exploit the smartness of the IoT-based architecture to run their vital and organizational processes. The smart response of pandemic emergency response services needs optimizing methodologies of caring and limit infection without direct connection with patients. In this paper, a hybrid Computational Intelligence (CI) algorithm called Moth-Flame Optimization and Marine Predators Algorithms (MOMPA) is proposed for planning the COVID-19 pandemic medical robot's path without collisions. MOMPA is validated on several benchmarks and compared with many CI algorithms. The results of the Friedman Ranked Mean test indicate the proposed algorithm can find the shortest collision-free path in almost all test cases. In addition, the proposed algorithm reaches an almost %100 success ratio for solving all test cases without constraint violation of the regarded problem. After the validation experiment, the proposed algorithm is applied to smart medical emergency handling in Egypt's New Galala mountainous city. Both experimental and statistical results ensure the prosperity of the proposed algorithm. Also, it ensures that MOMPA can efficiently find the shortest path to the emergency location without any collisions.

The One-to-one Pickup and Delivery Problem with Shortest-path Transport along Real-life Paths (OPDPSTRP) is presented in this paper. It is a variation of the One-to-one Pickup and Delivery Problem (OPDP), which is common in daily life, such as the Passenger Train Operation Plans (PTOP) and partial Taxi-sharing Problem. Unlike the classical OPDP, in the OPDPSTRP, (1) each demand must be transported along the shortest path according to passengers/shippers requirements, and (2) each vehicle should travel along a real-life path. First, six route structure rules are proposed for the OPDPSTRP, and a kind of Mixed-Integer Programming (MIP) models is formulated for it. Second, A Variable Neighborhood Descent (VND), a Variable Neighborhood Research (VNS), a Multi-Start VND (MS_VND) and a Multi-Start VNS (MS_VNS) with five neighborhood operators has been developed to solve the problem. Finally, The Gurobi solver, the VND, the VNS, the MS_VND and the MS_VNS have been compared with each other by 84 random instances partitioned in small size connected graphs, medium size connected graphs and large size connected graphs. From the test results we found that solutions generated by these approaches are often comparable with those found by the Gurobi solver, and the solutions found by these approaches are better than the solutions found by the Gurobi solver when solving instances with larger numbers of demands. In almost all instances, the MS_VND significantly outperforms the VND and the VNS in terms of solution quality, and outperforms the MS_VNS both in terms of solution quality and CPU time. In the instances with large numbers of demands, the MS_VND is still able to generate good feasible solutions in a reasonable CPU time, which is of vital practical significance for real-life instances.

Significance Why do humans move the way they do? Here, we obtain a physiologically based theory of the speeds and paths with which humans navigate their environment. We measure the metabolic energy cost of walking with turning and show that minimizing this cost explains diverse phenomena involving navigating around obstacles, walking in complex paths, and turning. We explain why humans slow down while turning, avoid sharp turns, do not always use the shortest path, and other naturalistic locomotor phenomena., Navigating our physical environment requires changing directions and turning. Despite its ecological importance, we do not have a unified theoretical account of non-straight-line human movement. Here, we present a unified optimality criterion that predicts disparate non-straight-line walking phenomena, with straight-line walking as a special case. We first characterized the metabolic cost of turning, deriving the cost landscape as a function of turning radius and rate. We then generalized this cost landscape to arbitrarily complex trajectories, allowing the velocity direction to deviate from body orientation (holonomic walking). We used this generalized optimality criterion to mathematically predict movement patterns in multiple contexts of varying complexity: walking on prescribed paths, turning in place, navigating an angled corridor, navigating freely with end-point constraints, walking through doors, and navigating around obstacles. In these tasks, humans moved at speeds and paths predicted by our optimality criterion, slowing down to turn and never using sharp turns. We show that the shortest path between two points is, counterintuitively, often not energy-optimal, and, indeed, humans do not use the shortest path in such cases. Thus, we have obtained a unified theoretical account that predicts human walking paths and speeds in diverse contexts. Our model focuses on walking in healthy adults; future work could generalize this model to other human populations, other animals, and other locomotor tasks.

International audience; Edge-aware filtering is an important pre-processing step in many computer vision applications. In literature, there exist several versions of collaborative edge-aware filters based on spanning trees and shortest path heuristics which work well in practice. For instance, Tree Filter (TF) which is recently proposed based on a minimum spanning tree (MST) heuristic yields promising results in many filtering applications. However, links between the tree-based filters and shortest path-based filters are faintly explored. In this article, we introduce an edge-aware generalization of the TF, termed as UMST filter based on the union of all MSTs. The major contribution of this paper is establishing theoretical links between filters based on MSTs and filters based on geodesics via power watershed framework. More precisely, we show that Union of Minimum Spanning Trees (UMST) filter can be obtained as the limit of Shortest Path Filters (SPFs). Intuitively, TF can be viewed as an approximate limit of the SPFs. We propose and provide a detailed analysis of two different implementations of the UMST filter based on shortest paths. Further, we establish empirically with the help of denoising experiments that TF is an approximate limit by showing that TF and one of our approximations yield similar results.

We present two results on slime mold computations. In wet-lab experiments (Nature'00) by Nakagaki et al. the slime mold Physarum polycephalum demonstrated its ability to solve shortest path problems. Biologists proposed a mathematical model, a system of differential equations, for the slime's adaption process (J. Theoretical Biology'07). It was shown that the process convergences to the shortest path (J. Theoretical Biology'12) for all graphs. We show that the dynamics actually converges for a much wider class of problems, namely undirected linear programs with a non-negative cost vector. Combinatorial optimization researchers took the dynamics describing slime behavior as an inspiration for an optimization method and showed that its discretization can $\varepsilon$-approximately solve linear programs with positive cost vector (ITCS'16). Their analysis requires a feasible starting point, a step size depending linearly on $\varepsilon$, and a number of steps with quartic dependence on $\mathrm{opt}/(\varepsilon\Phi)$, where $\Phi$ is the difference between the smallest cost of a non-optimal basic feasible solution and the optimal cost ($\mathrm{opt}$). We give a refined analysis showing that the dynamics initialized with any strongly dominating point converges to the set of optimal solutions. Moreover, we strengthen the convergence rate bounds and prove that the step size is independent of $\varepsilon$, and the number of steps depends logarithmically on $1/\varepsilon$ and quadratically on $\mathrm{opt}/\Phi$.

Internet of Things (IoT) is a new concept in the information and communication technology studies which indicates that any creature (human, animal, or object) can send and receive data through communication networks, such as the internet or intranet platform. Wireless sensors have limited energy resources due to the use of batteries to supply energy, and since it is usually not possible to replace the batteries of these sensors. In addition, the lifespan of the wireless sensor network is limited and short. Therefore, reducing the energy consumption of sensors in IoT networks for increasing network lifespan is one of the fundamental challenges and issues in these networks. In this paper, a routing protocol is proposed and simulated based on an ant colony optimization algorithm’s performance. The clustering is performed with a routing method based on energy level criteria, collision reduction, distance from the cluster-head to the destination, and neighborhood energy in the proposed method. The cluster head is selected based on the maximum residual energy, minimum distance with other clusters, and consumed energy. This energy is minimized to reach the base station. The node with more energy than the threshold is selected as the new cluster head. Then, four conditions are applied for routing: the shortest path, the leading path, the shortest distance to the source node and the destination node, and routing. Results show that after about 50 cycles of transferring information, only the average of 19.4% of the initial energy is consumed in the network nodes. Therefore, obtained results illustrate that the proposed method helps to retain the energy more than 40% comparing the available methods.

In a hybrid road network with multiple paths to same location having prior geographical knowledge, successful navigation for mobile robots is one of the main challenges. Path planning is one of the most important issues in the navigation process which enables the selection and identification of a suitable path for the robot to traverse in the workspace area. Path-planning for mapped roads can be considered as the process of navigating a mobile robot around a configured road map, which provides optimized path by considering roughness of roads. In this paper, we propose a novel navigation algorithm for outdoor environments, which permits robots to travel from one static node to another along a planned path. It utilizes Normal probability weight distribution (NPWD) to assign weights between two nodes dynamically. Heuristics based shortest path (HSP) algorithm is employed to solve complex optimization problems concerned with real-world scenarios. The experiments performed on categorized road databases show significant improvement in timings and complexity of system. Our results justify the effectiveness for the implementation of driver-assist system.

The unpredictable increase in electrical demand affects the quality of theenergy throughout the network. A solution to the problem is the increase of distributedgeneration units which burn fossil fuels.While this is an immediate solution to theproblem the ecosystem gets affected by the emission of CO2.A promising solutionis the integration of Distributed Renewable Energy Sources (DRES) to the conventionalelectrical system, thus, introducing the concept of smart microgrids (SMG) that requirea safe, reliable and technically planned two-way communication system. This documentpresents a heuristic based on planning capable of providing a bidirectional communicationnear optimal route map, following the structure of an hybrid Fiber-Wireless (FiWi) with thepurpose of obtaining information of electrical parameters that help us to manage the useof energy by integrating conventional electrical system to SMG. A FiWi network is basedon the integration of wireless access and optical networks. This integration increases thecoverage and reliability at a lower cost. The optimization model is based on clusteringtechniques, through the construction of balanced conglomerates. The method is used forthe development of the clusters along with the Nearest-Neighbor Spanning Tree Algorithm(N-NST). Additionally, Optimal Delay Balancing (ODB) model will be used to minimizethe end to end delay of each grouping. In addition, the heuristic observes real designparameters such as: capacity and coverage. Using the Dijkstra algorithm, the routes arebuilt following the minimum shorter path. Therefore, this paper presents a heuristic able to plan the deployment of smart meters (SMs) through a tree-like hierarchical topology for theintegration of SMG at the lowest cost.

Aukcijski algoritmi, temeljeni na principu klasične aukcije, djeluju suprotno klasičnim algoritmima mrežne optimizacije jer u svakoj iteraciji ne poboljšavaju nužno ni primarnu ni dualnu funkciju cilja, no na kraju nalaze optimalnu vrijednost. Zasnovani su na metodama nediferencijabilne optimizacije. U početku opisujemo aukcijski algoritam za klasični problem dodjeljivanja, te se bavimo raznim pitanjima kao što su \(\epsilon\)-skaliranje, problem nedopustivosti, obrnuti algoritam i slično. Razlog tomu je što se problem toka minimalnog troška lako može pretvoriti u problem dodjeljivanja, te su ta pitanja zajednička svim vrstama promatranih problema. Stoga, kasnije u radu, promatramo adaptaciju algoritma za problem maksimalnog toka, transportni problem, problem najkraćih putova i problem toka minimalnog troška. Za problem toka minimalnog troška uvodimo generički algoritam, te kao njegov specijalni slučaj, razvijamo metodu \(\epsilon\)-relaksacije. Auction algorithms, based on real auction, work counter to classical network optimization algorithms because in each iteration they don’t necessarily improve the primal or dual cost, although in the end they find an optimal primal solution. They are based on methods of nondifferentiable optimization. Initially, we describe the auction algorithm for classical assignment problem and we deal with various issues such as \(\epsilon\)-scaling, dealing with infeasibility, reverse auction etc.. The reason is that the minimum cost flow problem can be easily transformed to an assignment problem, so these issues are common to all types of observed problems. Therefore, later in the paper, we observe the algorithm adaptation for the max-flow problem, transportation problem, shortest path problem and minimum cost flow problem. For minimum cost flow problem we introduce generic algorithm and develop \(\epsilon\)-relaxation method as a special case of the generic algorithm.

Software defined networking (SDN) provides a framework to dynamically adjust and re-program the data plane with the use of flow rules. The realization of highly adaptive SDNs with the ability to respond to changing demands or recover after a network failure in a short period of time, hinges on efficient updates of flow rules. We model the time to deploy a set of flow rules by the update time at the bottleneck switch, and formulate the problem of selecting paths to minimize the deployment time under feasibility constraints as a mixed integer linear program (MILP). To reduce the computation time of determining flow rules, we propose efficient heuristics designed to approximate the minimum-deployment-time solution by relaxing the MILP or selecting the paths sequentially. Through extensive simulations we show that our algorithms outperform current, shortest path-based solutions by reducing the total network configuration time up to 55% while having similar packet loss, in the considered scenarios. We also demonstrate that in a networked environment with a certain fraction of failed links, our algorithms are able to reduce the average time to reestablish disrupted flows by 40%.

In this work multiple depot vehicle routing problem is considered in case of variable travel times between nodes on a metropolis network. This variant of the classic multiple depot vehicle routing problem is motivated by the fact that in urban contexts variable traffic conditions play an essential role and can not be ignored in order to perform a realistic optimization. Time-travel matrices corresponding to each period of planning horizon were formed by solving the traffic assignment problem in conjunction with shortest path problem. Routing problem instances include from 20 to 100 customers randomly chosen from a road network of Saint-Petersburg. The results demonstrate that taking into account traffic flow information can reduce route time by 8-37% depending on number of customers in the problem instance.

The shortest path finding algorithm is used in many problems on graphs and networks. This article will introduce the algorithm to find the shortest path between two vertices on the extended graph. Next, the algorithm finds the shortest path between the pairs of vertices on the extended graph with multiple weights is developed. Then, the shortest path finding algorithms is used to find the maximum flow on the multicommodity multicost extended network is developed in the article[12].

This study describes an optimization method called Simulated Annealing. The Simulated Annealing method is widely used in various combinatorial optimization tasks. Simulated Annealing is a stochastic optimization method that can be used to minimize the specified cost function given a combinatorial system with multiple degrees of freedom. In this study the application of the Simulated Annealing method to a well - known task of combinatorial analysis, Travelling Salesman Problem, is demonstrated and an experiment aimed to find the shortest tour distances between educational institutions of Rēzekne Municipality is performed. It gives possibilities to analyze and search optimal schools' network in Rēzekne Municipality.

International audience; We study a combinatorial optimization problem for conflict-free routing in a Network-on-Chip. Based on time division multiplexing and cyclic emission, the problem consists in finding a set of K shortest paths, such that packets will never conflict through the network but can use shared communication links in an efficient way. The model allows to avoid collisions and deadlocks in irregular network topologies, while minimizing latency. A time-expanded graph approach is retained for the solution process. First, we present a mixed integer linear programming model for the problem. Second, a set of shortest paths operators are combined within three iterated local search schemes able to quickly generate admissible solutions for the problem. To evaluate the method, experiments are conducted on a set of five real-life problem instances, and on many artificial unstructured random instances derived from them. We detail the problem of traffic instance generation, that also illustrates the designer’s task of flow decomposition between communicating components. Intensive simulations illustrate the accuracy of the solution method.

Through the course of a construction project, resources are required to constantly travel on the site from one point to another to support construction activities. Path planning for resources is an important part of site logistics and is required for various tasks such as site layout planning or safety planning, but the effect of different approaches on the precision of the paths is still not investigated sufficiently. The objective of this paper is to compare the complexity and precision of direct, grid based, and visibility graph approaches in determining the distance travelled by resources through a number of case examples.

Authors are in long term developing e-learning supports for some parts of Operation Research course. The original purpose was to prepare e-learning supports for students of FBE Mendelu, mainly for part-time form students, who have subscribed Economic mathematical methods course (EMM). Considering decreasing number of lessons on part-time form of study (16 hours in a semester, in comparison to 56 hours in full-time form of study), was for part-time form students even more difficult to fulfill exam requirements. As a help for students there was stage by stage prepared several of programs, they allow self-contained practicing of some linear programming methods. Programs did allow to users step-by-step verify their solution, i.e. whether their calculation are in accordance with algorithm described in lectures. Advantage for the students consists in fact, that each mistake (numerical or algorithmic) they were able to uncover, what contributes to increase of self-study effectiveness and from that resulting higher study motivation. Resulting from existing experience, authors decided to request for a new FRVS grant for academic year 2012, focused on e-learning support of selected graph theory problems. Within this project there was developed a tool allowing to make and according to the user needs interactively modify created graphs. On this graph it is possible individually, step by step (in compliance with on lectures presented algorithm) to practice solving of selected graph theory and network analysis problems (e.g. minimal spanning tree, shortest path in a graph, testing for cycles in a graph, critical path method etc.). Project is realized as modular and was realized in Delphi developing tool. Described algorithms are saved in dynamic linked libraries. There for it is very easy to add here new (newly programmed) algorithms. Project results (i.e. project experience obtained from e-learning supports) will be available for all FBE Mendelu members interested in this problematic.

This study considers the Budgeted Flow Expansion (BFE) problem on transportation network. The problem input includes a given budget and a transportation network, i.e. a directed graph with edges’ capacities. In addition, each edge is associated with possible expansion capacity and the expansion cost. For instance, given a transportation network connecting two cities and possible options of expanding existing roads and/or constructing new roads, the objective is to efficiently utilize a given budget to maximize the flow between the cities. The BFE problem is NP-hard (non-deterministic polynomial-time hard) for the general case where the expansion options are all-or-nothing, i.e., expand by utilizing the entire expansion capacity or do not expand at all. Nonetheless, this study considers a special case in which any integral amount of expansion capacity can be utilized; for this case a polynomial algorithm is proposed. The algorithm iteratively expands the flow by one unit as long as the resultant cost is within the budget constraint. In each iteration, the maximum flow is found using the known Ford-Fulkerson algorithm. Based on the residual network, combined with the possible expansion of edges, the cheapest path for expanding the flow is selected. The method described can be used as an efficient tool for decision makers to attain the best improvements of transportation networks when a limited budget is available. The methodology and algorithms can be applied to a real-world road network including the exhibition and interpretation of the unique features used and the benefits expected.