检索结果-内蒙古大学图书馆

The vehicle rescheduling problem: Model and algorithms

NETWORKS 2007年第3期50卷 211-229页

作者： Li, Jing-Quan Mirchandani, Pitu B. Borenstein, Denis Univ Arizona Dept Syst & Ind Engn Tucson AZ 85721 USA Univ Fed Rio Grande do Sul Sch Management BR-90010460 Porto Alegre RS Brazil

When a vehicle on a scheduled trip breaks down, one or more vehicles need to be rescheduled to serve the customers on that trip with minimum operating and delay costs. The problem of reassigning vehicles in real-time to this cut trip as well as to other scheduled trips with given starting and ending times, is referred to as the vehicle rescheduling problem (VRSP). This paper considers modeling, algorithmic, and computational aspects of the single-depot VRSP. The paper formulates a model for this problem and develops several fast algorithms to solve it, including parallel synchronous auction algorithms. The concept of the common feasible network (CFN) is introduced to find a good set of initial "prices" for speeding up the auction algorithm. Computational experiments on randomly generated problems are described. Computational results show that, for small problems, all of the developed algorithms demonstrate very good computational performances. For large problems, parallel CFN-based auction algorithms provide the optimal solution with much smaller computation times. (c) 2007 Wiley Periodicals, Inc.

关键词： vehicle scheduling rescheduling auction algorithm parallel processing

来源：评论

学校读者我要写书评

暂无评论

Servo relays as distributed controllable-mobility network to maintain long-term stable links for mobile robot swarms

引用

AD HOC NETWORKS 2021年 117卷

作者： Zhang, Hong Guang Jin, Guan Yu Qu, Yu Xiao Liu, Yuan An Beijing Univ Posts & Telecommun Sch Elect Engn Beijing Peoples R China

In the last decade, mobile robot swarms are widely used in wild applications, such as disaster search and rescue, battlefield communication, and so on. Due to their task-oriented feature in the wild, robot nodes usually move in groups. However, the communication of self-organized networks as a fundamental technology of mobile robot swarms is still the main bottleneck to restrict its developments. We propose servo relays as distributed controllable-mobility network (i.e., Servo-R network) to maintain long-term stable links for mobile robot swarms. In Servo-R network, servo relay is more like a slave. If one group of mobile robots needs a relay, it serves them. Otherwise, servo relay always stands alone and is ready to provide its relay service at any time. Servo-R network is an ensemble of controllable mobility and relay routing schemes. Controllable mobility scheme uses an iterated auction algorithm to assign servo relays to groups. Besides, it uses the virtual force and predicted location methods to realize the controllable movements of relays and base station. As a fully distributed scheme, the dynamic deployments of servo relays and base station are suitable to fight against the frequent topology changes of mobile robot swarm. According to the location information of the group's nodes, relay routing scheme uses dynamic programming to compute the group route table with the least hops. According to the received group route table, the group's nodes forward data. This is good to improve packet delivery ratio. In the various scenarios of our simulation, Servo-R outperforms four compared protocols in most cases, especially in the network connectivity and link duration.

关键词： Relay routing Controllable mobility routing auction algorithm Virtual force Search and rescue communication Battlefield communication

来源：评论

学校读者我要写书评

暂无评论

A graph space optimal transport distance as a generalization of L^p distances: application to a seismic imaging inverse problem

引用

INVERSE PROBLEMS 2019年第8期35卷

作者： Metivier, L. Brossier, R. Merigot, Q. Oudet, E. Univ Grenoble Alpes CNRS LJK Grenoble France Univ Grenoble Alpes Inst Sci Terre ISTerre Grenoble France Univ Paris Sud LMO Orsay France

Optimal transport distance is an appealing tool to measure the discrepancy between datasets in the frame of inverse problems, for its ability to perform global comparisons and its convexity with respect to shifted patterns in the compared quantities. However, solving inverse problems might require to compare signed quantities, while the optimal transport theory has been developed for the comparison of probability measures. In this study we propose to circumvent this difficulty by applying optimal transport to the comparison of the graph of the data rather than the data itself. We investigate this approach in the frame of seismic imaging, where each channel of the oscillatory data is interpreted as a discrete point cloud. We demonstrate that the corresponding misfit function can be computed through the solution of series of linear sum assignment problem (LSAP), while, based on the adjoint state technique, its gradient can be computed from the assignment solution of these LSAP. We illustrate how this approach yields a convex misfit function in the frame of seismic imaging using the full waveform. We show how an efficient strategy, based on a specific LSAP solver, the auction algorithm, can be designed. We illustrate the interest of the approach on a realistic 2D visco-acoustic seismic imaging problem. The proposed strategy relaxes the constraint on the accuracy of the initial model, outperforming the conventional least-squares approach and a previously proposed optimal transport based approach. The computational time increases by only a few percents compared with the least-squares approach, opening the way to applications to 3D field data in the near future.

关键词： seismic imaging optimal transport full waveform inversion linear assignment problem auction algorithm

来源：评论

学校读者我要写书评

暂无评论

A decentralized beam selection for mmWave beamspace multi-user MIMO system

引用

AEU-INTERNATIONAL JOURNAL OF ELECTRONICS AND COMMUNICATIONS 2019年 111卷

作者： Pal, Rahul Sarawadekar, K. P. Srinivas, K., V Banaras Hindu Univ Indian Inst Technol Varanasi Uttar Pradesh India

A millimeter beamspace multi-user multi-input-multi-output system is a key enabling technology of 5G to fulfil the demand for high data rate. But, it suffers from high RF complexity. However, RF Complexity can be reduced by the beam selection algorithm. Hence, few beam selection algorithms were proposed with a centralized approach. In this paper, a decentralized beam selection algorithm for millimeter wave beamspace multi-user MIMO is discussed. Unlike the centralized beam selection algorithm, the decentralized beam selection algorithm doesn't require a central unit or access point to select beams. The users themselves play an active role to select beams by sharing the local information with the neighbour users. This is also the requirement of a dynamic network. The performance thoroughly confides on the network cooperation to select beams in an efficient manner. The proposed decentralized beam selection algorithm enables the access point to be free from handling of a large channel matrix. Therefore, this low complexity beam selection algorithm is a better alternative. The performance and complexity of the proposed beam selection algorithm are examined in the following section. (C) 2019 Elsevier GmbH. All rights reserved.

关键词： mmWaves MU-MIMO Discrete lens array Beamspace Precoding auction algorithm Distributed auction algorithm

来源：评论

学校读者我要写书评

暂无评论

Enhancing Unmanned Aerial Vehicle Task Assignment with the Adaptive Sampling-Based Task Rationality Review algorithm

引用

DRONES 2024年第9期8卷

作者： Sun, Cheng Yao, Yuwen Zheng, Enhui China Jiliang Univ Sch Mech & Elect Engn Hangzhou 310018 Peoples R China

As the application areas of unmanned aerial vehicles (UAVs) continue to expand, the importance of UAV task allocation becomes increasingly evident. A highly effective and efficient UAV task assignment method can significantly enhance the quality of task completion. However, traditional heuristic algorithms often perform poorly in complex and dynamic environments, and existing auction-based algorithms typically fail to ensure optimal assignment results. Therefore, this paper proposes a more rigorous and comprehensive mathematical model for UAV task assignment. By introducing task path decision variables, we achieve a mathematical description of UAV task paths and propose collaborative action constraints. To balance the benefits and efficiency of task assignment, we introduce a novel method: the Adaptive Sampling-Based Task Rationality Review algorithm (ASTRRA). In the ASTRRA, to address the issue of high-value tasks being easily overlooked when the sampling probability decreases, we propose an adaptive sampling strategy. This strategy increases the sampling probability of high-value targets, ensuring a balance between computational efficiency and maximizing task value. To handle the coherence issues in UAV task paths, we propose a task review and classification method. This method involves reviewing issues in UAV task paths and conducting classified independent auctions, thereby improving the overall task assignment value. Additionally, to resolve the crossover problems between UAV task paths, we introduce a crossover path exchange strategy, further optimizing the task assignment scheme and enhancing the overall value. Experimental results demonstrate that the ASTRRA exhibits excellent performance across various task scales and dynamic scenarios, showing strong robustness and effectively improving task assignment outcomes.

关键词： multi-UAV task assignment auction algorithm task rationality review

来源：评论

学校读者我要写书评

暂无评论

On the use of suboptimal matchings for scaling and ordering sparse symmetric matrices

引用

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 2015年第4期22卷 648-663页

作者： Hogg, Jonathan Scott, Jennifer STFC Rutherford Appleton Lab Dept Comp Sci Didcot OX11 0QX Oxon England

The use of matchings is a powerful technique for scaling and ordering sparse matrices prior to the solution of a linear system Ax = b. Traditional methods such as implemented by the HSL software package MC64 use the Hungarian algorithm to solve the maximum weight maximum cardinality matching problem. However, with advances in the algorithms and hardware used by direct methods for the parallelization of the factorization and solve phases, the serial Hungarian algorithm can represent an unacceptably large proportion of the total solution time for such solvers. Recently, auction algorithms and approximation algorithms have been suggested as alternatives for achieving near-optimal solutions for the maximum weight maximum cardinality matching problem. In this paper, the efficacy of auction and approximation algorithms as replacements for the Hungarian algorithm is assessed in the context of sparse symmetric direct solvers when used in problems arising from a range of practical applications. High-cardinality suboptimal matchings are shown to be as effective as optimal matchings for the purposes of scaling. However, matching-based ordering techniques require that matchings are much closer to optimality before they become effective. The auction algorithm is demonstrated to be capable of finding such matchings significantly faster than the Hungarian algorithm, but our 1/2-approximation matching approach fails to consistently achieve a sufficient cardinality. Copyright (c) 2015 The Authors Numerical Linear Algebra with Applications Published by John Wiley & Sons Ltd.

关键词： approximation algorithm auction algorithm matching sparse symmetric matrix scaling ordering

来源：评论

学校读者我要写书评

暂无评论

Computation Offloading Strategy in Mobile Edge Computing

引用

INFORMATION 2019年第6期10卷

作者： Sheng, Jinfang Hu, Jie Teng, Xiaoyu Wang, Bin Pan, Xiaoxia Cent South Univ Sch Comp Sci & Engn Changsha 410073 Hunan Peoples R China

Mobile phone applications have been rapidly growing and emerging with the Internet of Things (IoT) applications in augmented reality, virtual reality, and ultra-clear video due to the development of mobile Internet services in the last three decades. These applications demand intensive computing to support data analysis, real-time video processing, and decision-making for optimizing the user experience. Mobile smart devices play a significant role in our daily life, and such an upward trend is continuous. Nevertheless, these devices suffer from limited resources such as CPU, memory, and energy. Computation offloading is a promising technique that can promote the lifetime and performance of smart devices by offloading local computation tasks to edge servers. In light of this situation, the strategy of computation offloading has been adopted to solve this problem. In this paper, we propose a computation offloading strategy under a scenario of multi-user and multi-mobile edge servers that considers the performance of intelligent devices and server resources. The strategy contains three main stages. In the offloading decision-making stage, the basis of offloading decision-making is put forward by considering the factors of computing task size, computing requirement, computing capacity of server, and network bandwidth. In the server selection stage, the candidate servers are evaluated comprehensively by multi-objective decision-making, and the appropriate servers are selected for the computation offloading. In the task scheduling stage, a task scheduling model based on the improved auction algorithm has been proposed by considering the time requirement of the computing tasks and the computing performance of the mobile edge computing server. Extensive simulations have demonstrated that the proposed computation offloading strategy could effectively reduce service delay and the energy consumption of intelligent devices, and improve user experience.

关键词： mobile edge computation computation offloading analytic hierarchy process auction algorithm

来源：评论

学校读者我要写书评

暂无评论

Real-Time Task Reallocation for Large-scale UAV team in Dynamic environment

Real-Time Task Reallocation for Large-scale UAV team in Dyna...

引用

2016 IEEE Chinese Guidance, Navigation and Control Conference (IEEE CGNCC2016)

作者： Fei Yan Zhuang Shao Zhou Zhou Xiaoping Zhu National Key Laboratory of Special and Technology on UAV Northwestern Polytechnical University College of Aeronautics Northwestern Polytechnical University UAV Research Institute Northwestern Polytechnical University

ISBN: (纸本)9781467383196

To solve the problem of cooperative task reallocation for large-scale unmanned aerial vehicle(UAV)team under complex dynamic environment,a method based on man in-loop consensus auction principle is ***,Delaunay diagram is used for environment ***,the shortest paths of UAVs to targets are obtained by using Warshall-Floyd algorithm,thus task allocation and path planning are ***,with man in-loop and consensus-based auction approach,the task reallocation under several sudden changes of environment is *** results show that,the proposed method can provide a feasible task reallocation in 1.2s for a large-scale UAV team,which proves the real-time performance of this method.

关键词： auction algorithm cooperative task allocation large-scale UAV team man in-loop

来源：评论

学校读者我要写书评

暂无评论

Research on blockchain-based microgrid power trading method 23

Research on blockchain-based microgrid power trading method

引用

Proceedings of the 2023 6th International Conference on Artificial Intelligence and Pattern Recognition

作者： Sheping Zhai Haonan Nie Xianjing Lu Rui Yang Department of computing Xi'an University of Posts&Telecommunications China

ISBN: (纸本)9798400707674

The current microgrid electricity market suffers from inefficient, risky, and time-consuming transaction processes. However, with the introduction of blockchain technology with decentralized and open and transparent features, automated electricity trading with high security, high efficiency, and audit traceability can be achieved, thus providing a new market model with potential for microgrids. In this paper, we propose a blockchain-based approach to microgrid electricity trading, which utilizes blockchain technology, anonymous message flow and other technical means to achieve privacy and security guarantees for transactions. Smart contracts are utilized for the exchange of power ownership and tokens between the power purchaser and the power seller to ensure that the rights and interests of both parties are protected. The design of the auction rules achieves the balance of interests between the power purchaser and the power seller. Experiments show that the blockchain-based microgrid trading method proposed in this paper can conduct multilateral bidding transactions, effectively improve the utilization of electricity within the microgrid, and ensure the economic efficiency and safe operation of the microgrid.

关键词： Blockchain auction algorithm microgrid smart contract

来源：评论

学校读者我要写书评

暂无评论

Multi-Robot Assignment algorithm for Tasks with Set Precedence Constraints

Multi-Robot Assignment Algorithm for Tasks with Set Preceden...

引用

2011 IEEE International Conference on Robotics and Automation(2011年IEEE世界机器人与自动化大会 ICRA 2011)

作者： Lingzhi Luo Nilanjan Chakraborty Katia Sycara Robotics Institute School of Computer ScienceCarnegie Mellon University5000 Forbes AvePittsburghPA 15213

In this paper, we present task allocation (assignment) algorithms for a multi-robot system where the tasks are divided into disjoint groups and there are precedence constraints between the task groups. Existing auction-based algorithms assume the task independence and hence can not be used directly to solve the class of multi-robot task assignment problems that we consider. In our model, each robot can do a fixed number of tasks and obtains a benefit (or incurs a cost) for each task. The tasks are divided into groups and each robot can do only one task from each group. These constraints arise when the robots have to do a set of tasks that have precedence constraints and each task takes the same time to be completed. We extend the auction algorithm to provide an almost optimal solution to the task assignment problem with set precedence constraints (the theoretical guarantees are the same as that of the original auction algorithm for unconstrained tasks). In other words, we guarantee that we will get a solution within a factor of O(nt ε) of the optimal solution, where nt is the total number of tasks and e is a parameter that we choose. We first present our algorithm using a shared memory model and then indicate how consensus algorithms can be used to make the algorithm totally distributed.

关键词： Multi-robot assignment Task allocation auction algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：