Electric vehicle (EV) adoption in long-distance logistics faces challenges such as range anxiety and uneven distribution of charging stations. Two pivotal questions emerge: How can EVs be efficiently routed in a charg...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
Electric vehicle (EV) adoption in long-distance logistics faces challenges such as range anxiety and uneven distribution of charging stations. Two pivotal questions emerge: How can EVs be efficiently routed in a charging network considering range limits, charging speeds and prices? And, can the existing charging infrastructure sustain the increasing demand for EVs in long-distance logistics? This paper addresses these questions by introducing a novel theoretical and computational framework to study the EV networkflow problems. We present an EV networkflow model that incorporates range constraints and nonlinear charging rates, and identify conditions under which polynomial-time solutions can be obtained for optimal single EV routing, maximum flow, and minimum-cost flow problems. Our findings provide insights for optimizing EV routing in logistics, ensuring an efficient and sustainable future.
In this paper, the problem of planning the allocation of crops to arable lands, taking into account crop rotations principles and diversification strategies promoted by sustainable agriculture is addressed. Optimizati...
详细信息
In this paper, the problem of planning the allocation of crops to arable lands, taking into account crop rotations principles and diversification strategies promoted by sustainable agriculture is addressed. Optimization models for solving multi-period planning problems are proposed, able to decide how to allocate crops in each growing season in order to maximize the total expected profit. The allocation decisions are made considering the crop rotation benefits across seasons and the sustainable requirements stated by current regulations. A complexity analysis is performed, and polynomial special cases are presented. Integer Linear Programming models are proposed, for a case study related to structured professional Italian farms specialized in arable crops, following sustainability rules coming from public regulations and private initiatives, i.e., the Common Agricultural Policy by the European Union and "La Carta del Mulino"by the Barilla Group. Numerical experiments conducted on real data show the effectiveness of the proposed solution approaches.
The goal of this paper is to study different algorithms for planning a large scale pedestrian evacuation process. A pedestrian (walking) mode of evacuation is an efficient mode of transportation that is often overlook...
详细信息
The goal of this paper is to study different algorithms for planning a large scale pedestrian evacuation process. A pedestrian (walking) mode of evacuation is an efficient mode of transportation that is often overlooked in the literature. Fairness in the evacuation process is another aspect that is rarely studied. In this paper, we study efficiency and fairness of pedestrian mode of emergency evacuation. We model the evacuation problem as a dynamic networkflow problem, which captures the time-dependency of the network attributes such as edge and vertex capacities and edge travel times. To evaluate the efficiency of the algorithms, we consider the clearance time of the network. To investigate fairness, we consider the Gini coefficient and Lorenz curve that are popular indexes in economy to measure wealth distribution in a society. We compute the Gini coefficient and Lorenz curve to measure the fairness in travel time distribution of the evacuees in the emergency evacuation process. We develop a new algorithm called PEPA (Pedestrian Evacuation Planning Algorithm) to find the minimum clearance time of the network. PEPA is compared to two commonly studied graph algorithms in the literature, shortest path and maximum flowalgorithms. We compared the algorithms in terms of computation time of the algorithm, clearance time of the network and Gini coefficient. Our results show that PEPA beats both shortest path and maximum flow in terms of efficiency and fairness, although it is slightly slower in terms of computation time. To implement PEPA, shortest path and maximum flowalgorithms, we develop a new software named PEMSS (Pedestrian Evacuation Modeler, Solver, and Simulator). PEMSS is written in the Java programming language and is capable of reading and showing maps in open street map XML format.
This paper presents the use of a modified collective behavior strategy of ant colonies to find approximate sets in the multi-objective optimization problem. The currently used methods search for non-dominated solution...
详细信息
ISBN:
(纸本)9781450357401
This paper presents the use of a modified collective behavior strategy of ant colonies to find approximate sets in the multi-objective optimization problem. The currently used methods search for non-dominated solutions, which takes place directly on the basis of definitions in the previously generated finite set of admissible ratings, searching in the space of goals by analyzing active constraints, solving optimization tasks in terms of all subsequent individual optimization criteria and adopting optimization criteria in order to form a substitute criterion of optimization in the form of a combination of linear criteria with appropriately selected weighting factors. However, these methods are ineffective in many cases. Therefore, the authors of the article propose a new approach based on the use of rough sets flow graphs to control the strategy of communicating artificial ants in distributed cognitive environments. The use of this approach allows to maximize the number of generated solutions and finding non-dominated solutions for the multiple objectives.
This article records our contribution to the international debate on the use of modern technologies in the learning process. Our theme is the development of online games that support the learning processes of Vocation...
详细信息
ISBN:
(纸本)9783319751757;9783319751740
This article records our contribution to the international debate on the use of modern technologies in the learning process. Our theme is the development of online games that support the learning processes of Vocational Education and Training. The medium we used for this implementation concerns an online platform that includes polymorphic games. The learning content of the platform refers to topics related to web-based algorithms, techniques and data flow methods, such as the Bellman-Ford, Dijkstra, Floyd, and Johnson algorithms. Each digital scenario has a specific goal. The completion of each scenario will familiarize the student/ user with the process of the particular algorithm and how each algorithm is implemented in a networking environment. Our main goal of developing the platform is to use all the available modern technologies to create a strong overall learning experience through gaming that will also broaden the students' knowledge of networkalgorithms.
A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique called continuous scaling. The main measure of progress is that within a strongly ...
详细信息
A strongly polynomial algorithm is given for the generalized flow maximization problem. It uses a new variant of the scaling technique called continuous scaling. The main measure of progress is that within a strongly polynomial number of steps, an arc can be identified that must be tight in every dual optimal solution and thus can be contracted. As a consequence of the result, we also obtain a strongly polynomial algorithm for the linear feasibility problem with at most two nonzero entries per column in the constraint matrix.
A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective Sigma(ij is an element of Epsilon) C-ij (f(ij)) over feasible flows f, where on every arc ij of the network, C-ij is a c...
详细信息
A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective Sigma(ij is an element of Epsilon) C-ij (f(ij)) over feasible flows f, where on every arc ij of the network, C-ij is a convex function. We give a strongly polynomial algorithm for the case when all C-ij's are convex quadratic functions, settling an open problem raised, e.g., by Hochbaum [Math. Oper. Res., 19 (1994), pp. 390-409]. We also give strongly polynomial algorithms for computing market equilibria in Fisher markets with linear utilities and with spending constraint utilities that can be formulated in this framework (see Shmyrev [J. Appl. Ind. Math., 3 (2009), pp. 505-518], Birnbaum, Devanur, and Xiao [Proceedings of the 12th ACM Conference on Electronic Commerce, 2011, pp. 127-136]). For the latter class this resolves an open question raised by Vazirani [Math. Oper. Res., 35 (2010), pp. 458-478]. The running time is O(m(4) log m) for quadratic costs, O(n(4)+n(2)(m+n log n) log n) for Fisher's markets with linear utilities, and O(mn(3) + m(2)(m + n log n) logm) for spending constraint utilities. All these algorithms are presented in a common framework that addresses the general problem setting. Whereas it is impossible to give a strongly polynomial algorithm for the general problem even in an approximate sense (see Hochbaum [Math. Oper. Res., 19 (1994), pp. 390-409]), we show that assuming the existence of certain black-box oracles, one can give an algorithm using a strongly polynomial number of arithmetic operations and oracle calls only. The particular algorithms can be derived by implementing these oracles in the respective settings.
Rapid advances in image acquisition and storage technology underline the need for real-time algorithms that are capable of solving large-scale image processing and computer-vision problems. The minimum s-t cut problem...
详细信息
Rapid advances in image acquisition and storage technology underline the need for real-time algorithms that are capable of solving large-scale image processing and computer-vision problems. The minimum s-t cut problem, which is a classical combinatorial optimization problem, is a prominent building block in many vision and imaging algorithms such as video segmentation, co-segmentation, stereo vision, multi-view reconstruction, and surface fitting to name a few. That is why finding a real-time algorithm which optimally solves this problem is of great importance. In this paper, we introduce to computer vision the Hochbaum's pseudoflow (HPF) algorithm, which optimally solves the minimum s-t cut problem. We compare the performance of HPF, in terms of execution times and memory utilization, with three leading published algorithms: (1) Goldberg's and Tarjan's Push-Relabel;(2) Boykov's and Kolmogorov's augmenting paths;and (3) Goldberg's partial augment-relabel. While the common practice in computer-vision is to use either BK or PRF algorithms for solving the problem, our results demonstrate that, in general, HPF algorithm is more efficient and utilizes less memory than these three algorithms. This strongly suggests that HPF is a great option for many real-time computer-vision problems that require solving the minimum s-t cut problem.
Software-defined networking (SDN) increases the network programmability, promoting an effective development of networked systems of cloud scale. As the scale of the networks and systems is growing larger and larger wi...
详细信息
ISBN:
(纸本)9781479982189
Software-defined networking (SDN) increases the network programmability, promoting an effective development of networked systems of cloud scale. As the scale of the networks and systems is growing larger and larger with time, programmability of the systems and networks is researched intensively. Many emulators are proposed and implemented to emulate large and complex networks inside a single computer, or a cluster of computers in the research lab. However, the emulators lack the ability to represent large systems such as data center networks or content delivery networks. Many of the networkalgorithms and design choices can also be tested for their functionality and efficiency in a simulator environment. While network emulators and simulators exist, a generic networkflow simulator that is easy to program a variety of highly distributed and gigantic systems is still lacking. This paper presents xSDN, an expressive simulator for dynamic networkflows. Adhering to the principles of software-defined networking paradigm from the design, xSDN focuses to be lean, light-weight, easy to learn and configure, and efficient, that can simulate networks of a scale of million nodes within a few seconds.
We study an extension of the well-known generalized maximum flow problem in which the outflow of an edge is a strictly increasing convex function of its inflow. In contrast to the traditional generalized maximum flow ...
详细信息
We study an extension of the well-known generalized maximum flow problem in which the outflow of an edge is a strictly increasing convex function of its inflow. In contrast to the traditional generalized maximum flow problem, in which the outflow of an edge depends linearly on its inflow and which is solvable in polynomial time, we show that, for convex outflow functions, the problem becomes strongly NP-hard to solve even on bipartite acyclic graphs and weakly NP-hard on series-parallel graphs, Both results hold even if the outflow functions are convex quadratic. Furthermore, we present (exponentialtime) exact algorithms for computing optimal flows on acyclic and series parallel graphs and optimal preflows on general graphs. We also show that a flow decomposition similar to the one for traditional generalized flows is possible and present a pseudo-polynomial-time algorithm for the case of integral flows on series parallel graphs. (C) 2015 Elsevier B.V. All rights reserved.
暂无评论