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

Learning Feature Embedding Refiner for Solving Vehicle Routing Problems

IEEE TRANSACTIONS ON neural NETWORKS AND LEARNING SYSTEMS 2024年第11期35卷 15279-15291页

作者： Li, Jingwen Ma, Yining Cao, Zhiguang Wu, Yaoxin Song, Wen Zhang, Jie Chee, Yeow Meng Sichuan Normal Univ Dept Comp Sci Chengdu 610101 Peoples R China Natl Univ Singapore Dept Ind Syst Engn & Management Coll Design & Engn Singapore 119077 Singapore Singapore Management Univ Sch Comp & Informat Syst Singapore 188065 Singapore Eindhoven Univ Technol Fac Ind Engn & Innovat Sci NL-5600 MB Eindhoven Netherlands Shandong Univ Inst Marine Sci & Technol Qingdao 266237 Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Singapore 639798 Singapore

While the encoder-decoder structure is widely used in the recent neural construction methods for learning to solve vehicle routing problems (VRPs), they are less effective in searching solutions due to deterministic feature embeddings and deterministic probability distributions. In this article, we propose the feature embedding refiner (FER) with a novel and generic encoder-refiner-decoder structure to boost the existing encoder-decoder structured deep models. It is model-agnostic that the encoder and the decoder can be from any pretrained neural construction method. Regarding the introduced refiner network, we design its architecture by combining the standard gated recurrent units (GRU) cell with two new layers, i.e., an accumulated graph attention (AGA) layer and a gated nonlinear (GNL) layer. The former extracts dynamic graph topological information of historical solutions stored in a diversified solution pool to generate aggregated pool embeddings that are further improved by the GRU, and the latter adaptively refines the feature embeddings from the encoder with the guidance of the improved pool embeddings. To this end, our FER allows current neural construction methods to not only iteratively refine the feature embeddings for boarder search range but also dynamically update the probability distributions for more diverse search. We apply FER to two prevailing neural construction methods including attention model (AM) and policy optimization with multiple optima (POMO) to solve the traveling salesman problem (TSP) and the capacitated VRP (CVRP). Experimental results show that our method achieves lower gaps and better generalization than the original ones and also exhibits competitive performance to the state-of-the-art neural improvement methods.

关键词： Probability distribution Decoding Search problems Vehicle routing Routing Logic gates Costs Encoder-decoder structure neural combinatorial optimization reinforcement learning vehicle routing problems (VRPs)

来源：评论

学校读者我要写书评

暂无评论

Machine Learning to Solve Vehicle Routing Problems: A Survey

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2024年第6期25卷 4754-4772页

作者： Bogyrbayeva, Aigerim Meraliyev, Meraryslan Mustakhov, Taukekhan Dauletbayev, Bissenbay SDU Univ Dept Comp Sci Kaskelen 040900 Kazakhstan

This paper provides a systematic overview of machine learning methods applied to solve NP-hard Vehicle Routing Problems (VRPs). Recently, there has been great interest from both the machine learning and operations research communities in solving VRPs either through pure learning methods or by combining them with traditional handcrafted heuristics. We present a taxonomy of studies on learning paradigms, solution structures, underlying models, and algorithms. Detailed results of state-of-the-art methods are presented, demonstrating their competitiveness with traditional approaches. The survey highlights the advantages of the machine learning-based models that aim to exploit the symmetry of VRP solutions. The paper outlines future research directions to incorporate learning-based solutions to address the challenges of modern transportation systems.

关键词： Routing Machine learning Computational modeling Surveys Vehicle routing Transportation Logistics Reinforcement learning supervised learning neural combinatorial optimization vehicle routing

来源：评论

学校读者我要写书评

暂无评论

D2A: Operating a Service Function Chain Platform With Data-Driven Scheduling Policies

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2022年第3期19卷 2839-2853页

作者： Kraemer, Patrick Diederich, Philip Kraemer, Corinna Pries, Rastin Kellerer, Wolfgang Blenk, Andreas Tech Univ Munich Chair Commun Networks D-80333 Munich Germany Deutsch Sparkassenverlag GmbH D-70563 Stuttgart Germany Nokia Bell Labs Nokia Strategy & Technol D-81541 Munich Germany Siemens AG Corp Technol D-80333 Munich Germany

Realizing Service Function Chaining with a micro-service-based architecture results in an increased number of computationally cheap Virtual Network Functions (VNFs). Pinning cheap VNFs to dedicated CPU cores can waste resources since not every VNF fully utilizes its core. Thus, cheap VNFs should share CPU cores to improve resource utilization. However, sharing cores can result in degraded performance due to interference between VNFs, even in mildly loaded scenarios. We propose D(2)A, a system that combines neural combinatorial optimization, Machine Learning (ML)-based Digital Twins (DTs), and Game Theory to optimize VNF assignments. Measurements in a testbed show that D(2)A increases throughput by up to 46% and reduces latency by up to 93%, compared to three baseline algorithms. Using an ML-based DT to model VNF interference increases throughput by up to 11%, and reduces latency by up to 90% compared to an analytical model of the system.

关键词： Behavioral sciences Noise measurement Kernel Interference Task analysis Scheduling Throughput Reinforcement learning network virtualization game theory neural combinatorial optimization digital twin graph neural networks service function chaining

来源：评论

学校读者我要写书评

暂无评论

neural Order-First Split-Second Algorithm for the Capacitated Vehicle Routing Problem 5th

Neural Order-First Split-Second Algorithm for the Capacitate...

引用

4th International Conference on optimization and Learning (OLA)

作者： Yaddaden, Ali Harispe, Sebastien Vasquez, Michel Univ Montpellier IMT Mines Ales EuroMov Digital Hlth Mot Ales France

ISBN: (纸本)9783031220388;9783031220395

Modern machine learning, including deep learning models and reinforcement learning techniques, have proven effective for solving difficult combinatorial optimization problems without relying on handcrafted heuristics. In this work, we present NOFSS, a neural Order-First Split-Second deep reinforcement learning approach for the Capacity Constrained Vehicle Routing Problem (CVRP). NOFSS consists of a hybridization between a deep neural network model and a dynamic programming shortest path algorithm (Split). Our results, based on intensive experiments with several neural network model architectures, show that such a two-step hybridization enables learning of implicit algorithms (i.e. policies) producing competitive solutions for the CVRP.

关键词： neural combinatorial optimization Capacitated vehicle routing problem Order-first split-second Deep reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

Learning Heuristics for combinatorial optimization Problems on K-Partite Hypergraphs 21st

Learning Heuristics for Combinatorial Optimization Problems ...

引用

21st International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR)

作者： Zouitine, Mehdi Berjaoui, Ahmad Lagnoux, Agnes Pellegrini, Clement Rachelson, Emmanuel IRT St Exupery Toulouse France Univ Toulouse Inst Math Toulouse CNRS UMR5219 Toulouse France UT2J F-31058 Toulouse France UT3 Toulouse France ISAE SUPAERO Toulouse France

ISBN: (纸本)9783031606014;9783031605994

Recently, deep neural networks have demonstrated remarkable performance in addressing combinatorial optimization challenges. The expressive power of graph neural networks combined with Reinforcement Learning (RL) enabled learning heuristics that rival or even surpass conventional methods. Such advancements have paved the way for neural combinatorial optimization (NCO), an emerging paradigm that enables end-to-end heuristic learning without the reliance on expert knowledge. In this paper, we propose an NCO approach to learn heuristics for the vast family of combinatorial optimization Problems (COPs) defined on K-partite hypergraphs, including multi-dimensional assignment or scheduling problems. Central to our approach is the ability to represent sophisticated functions on K-partite hypergraphs, using a novel family of neural networks. We show that our heuristic competes with other ones in comparable settings and that our method can also be applied to more complex real-life assignment and scheduling problems.

关键词： Learning Based-Heuristics neural combinatorial optimization Graph neural Networks Deep Reinforcement Learning

来源：评论

学校读者我要写书评

暂无评论

Graph Representation for Learning the Traveling Salesman Problem 13th

Graph Representation for Learning the Traveling Salesman Pro...

引用

13th Mexican Conference on Pattern Recognition (MCPR)

作者： Gutierrez, Omar Zamora, Erik Menchaca, Ricardo Inst Politecn Nacl CIC Av Juan Dios Batiz S-NGustavo A Madero Mexico City 07738 Mexico

ISBN: (纸本)9783030770044;9783030770037

Training deep learning models for solving the Travelling Salesman Problem (TSP) directly on large instances is computationally challenging. An approach to tackle large-scale TSPs is through identifying elements in the model or training procedure that promotes out-of-distribution (OoD) generalization, i.e., generalization to samples larger than those seen in training. The state-of-the-art TSP solvers based on Graph neural Networks (GNNs) follow different strategies to represent the TSP instances as input graphs. In this paper, we conduct experiments comparing different graph representations finding features that lead to a better OoD generalization.

关键词： neural combinatorial optimization Traveling salesman Graph neural networks NP-Hard

来源：评论

学校读者我要写书评

暂无评论

Graph Q-learning Assisted Ant Colony optimization for Vehicle Routing Problems with Time Windows

Graph Q-learning Assisted Ant Colony Optimization for Vehicl...

引用

Genetic and Evolutionary Computation Conference (GECCO)

作者： Yue, Peng Liu, Shiqing Jin, Yaochu Northeastern Univ Shenyang Liaoning Peoples R China Bielefeld Univ Bielefeld Germany

ISBN: (纸本)9798400701207

Vehicle routing problem with time windows (VRPTW) is a typical class of constrained path planning problems in the field of combinatorial optimization. VRPTW considers a delivery task for a given set of customers with time windows, and the target is to find optimal routes for a group of vehicles that can minimize the total transportation cost. The traditional heuristics suffer from several limitations when solving VRPTW, such as poor scalability, sensitivity to hyperparameters and difficulty in handling complex constraints. Recent advance in machine learning makes it possible to enhance heuristic approaches via learned knowledge. In this paper, we propose a graph Q-learning assisted ant colony optimization algorithm named GQL-ACO to solve VRPTW. Compared to vanilla ant colony optimization (ACO), our proposed method first employs the learned heuristic values by using graph Q learning, instead of handcrafted ones, to define the hyperparameters of ACO. Second, we design a collaborative search strategy by combining ACO and Q-learning effectively, which can adaptively adjust the hyperparameters of ACO based on the search experiences.

关键词： Ant Colony optimization Deep Q-Learning Graph neural Network neural combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Fragmentation-Aware VNF Placement: A Deep Reinforcement Learning Approach 59

Fragmentation-Aware VNF Placement: A Deep Reinforcement Lear...

引用

59th Annual IEEE International Conference on Communications (IEEE ICC)

作者： Mohamed, Ramy Avgeris, Marios Leivadeas, Aris Lambadaris, Ioannis Carleton Univ Dept Syst & Comp Engn Ottawa ON Canada Ecole Technol Super Dept Software & IT Engn Montreal PQ Canada

ISBN: (纸本)9781728190549

In this paper we address the challenge of efficiently deploying Virtual Network Functions (VNFs) in network infrastructures. This is particularly crucial when facing resource fragmentation, where available resources are not fully utilized due to the fluctuating allocation and deallocation of virtual network requests. Traditional optimization techniques often fall short in managing the dynamic complexities of VNF placement. To overcome this, we introduce a novel online VNF placement strategy using Deep Reinforcement Learning (DRL) combined with a Reward Constrained Policy optimization (RCPO). This method leverages the flexibility of DRL and the constraint integration capacity of RCPO, ensuring compliance with performance and resource limitations while minimizing resource fragmentation. The results demonstrate that our DRL-based method surpasses existing methods, resulting in more effective resource management and less resource fragmentation.

关键词： Resource Fragmentation neural combinatorial optimization Reinforcement Learning 5G NFV SFC VNF Placement

来源：评论

学校读者我要写书评

暂无评论

Deep Reinforcement Learning Based Container Cluster Placement Strategy in Edge Computing Environment

Deep Reinforcement Learning Based Container Cluster Placemen...

引用

IEEE Global Communications Conference (GLOBECOM)

作者： Chen, Zhuo Zhu, Bowen Chongqing Univ Technol Coll Comp Sci & Engn Chongqing Peoples R China

ISBN: (纸本)9781665435406

Container-based virtualization technology has been increasingly used in edge clouds recently due to its advantages of lighter resource occupation, faster startup capability, and better resource utilization efficiency. For a task request, it is usually necessary to interconnect multiple containers to build a Container Cluster (CC), and then deploy it to edge service nodes with relatively limited resources. However, the increasingly complex and time-varying nature of tasks brings great challenges to optimally deploying CC on edge nodes. From the perspective of edge service provider, this paper regards the charges for various resources occupied by providing services as revenue, and regards the service efficiency and energy consumption generated by providing services as cost, then formulate an integer optimization model to describe the optimal deployment of CC on distributed edge nodes. Different from the heuristic-based methods adopted in existing works, we introduce Graph Convolutional Network (GCN) to extract features from the logical topological link relationships among containers in CCs and use them as the input of the solution framework to improve the solution quality. Compared with other related algorithms, the results show that the method proposed in this paper can obtain better solution quality and maintain acceptable solution efficiency under the same edge cloud environment. The improved system revenue for edge service provider can be further obtained.

关键词： Edge computing Network virtualization Cloud container cluster neural combinatorial optimization Graph convolutional network

来源：评论

学校读者我要写书评

暂无评论

Online VNF Placement using Deep Reinforcement Learning and Reward Constrained Policy optimization

Online VNF Placement using Deep Reinforcement Learning and R...

引用

IEEE International Mediterranean Conference on Communications and Networking (IEEE MeditCom)

作者： Mohamed, Ramy Avgeris, Marios Leivadeas, Aris Lambadaris, Ioannis Carleton Univ Dept Syst & Comp Engn Ottawa ON Canada Ecole Technol Super Dept Software & IT Engn Montreal PQ Canada

ISBN: (纸本)9798350309492;9798350309485

Appropriate deployment of Virtual Network Functions (VNFs) within the network infrastructure to optimize resource utilization, while fulfilling performance criteria, is critical to Network Function Virtualization (NFV). However, traditional optimization methods frequently struggle to deal with the dynamic and complex nature of the VNF placement problem. Therefore, this study proposes an online VNF placement approach that addresses these problems by leveraging Deep Reinforcement Learning (DRL) and Reward Constrained Policy optimization (RCPO). This technique combines DRL's adaptability with RCPO's constraint incorporation capabilities, ensuring that the learned policies satisfy performance and resource restrictions while optimizing the overall VNF placement. Hence, the VNF placement problem is formulated as a constrained optimization problem and adapted to the DRL setting. We demonstrate that our proposed framework outperforms certain state-of-the-art VNF placement techniques when it comes to resource utilization and constraint satisfaction.

关键词： neural combinatorial optimization Reinforcement Learning 5G NFV SFC VNF Placement

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：