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

Online Vehicle Routing With neural combinatorial optimization and Deep Reinforcement Learning

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2019年第10期20卷 3806-3817页

作者： Yu, James J. Q. Yu, Wen Gu, Jiatao Southern Univ Sci & Technol Dept Comp Sci & Engn Shenzhen 518055 Peoples R China Natl Polytech Inst CINVESTAV IPN Dept Automat Control Mexico City 07360 DF Mexico Univ Hong Kong Dept Elect & Elect Engn Hong Kong Peoples R China

Online vehicle routing is an important task of the modern transportation service provider. Contributed by the ever-increasing real-time demand on the transportation system, especially small-parcel last-mile delivery requests, vehicle route generation is becoming more computationally complex than before. The existing routing algorithms are mostly based on mathematical programming, which requires huge computation time in city-size transportation networks. To develop routes with minimal time, in this paper, we propose a novel deep reinforcement learning-based neural combinatorial optimization strategy. Specifically, we transform the online routing problem to a vehicle tour generation problem, and propose a structural graph embedded pointer network to develop these tours iteratively. Furthermore, since constructing supervised training data for the neural network is impractical due to the high computation complexity, we propose a deep reinforcement learning mechanism with an unsupervised auxiliary network to train the model parameters. A multisampling scheme is also devised to further improve the system performance. Since the parameter training process is offline, the proposed strategy can achieve a superior online route generation speed. To assess the proposed strategy, we conduct comprehensive case studies with a real-world transportation network. The simulation results show that the proposed strategy can significantly outperform conventional strategies with limited computation time in both static and dynamic logistic systems. In addition, the influence of control parameters on the system performance is investigated.

关键词： Online vehicle routing logistic system neural combinatorial optimization deep reinforcement learning intelligent transportation

来源：评论

学校读者我要写书评

暂无评论

Multi-Objective neural Evolutionary Algorithm for combinatorial optimization Problems

引用

IEEE TRANSACTIONS ON neural NETWORKS AND LEARNING SYSTEMS 2023年第4期34卷 2133-2143页

作者： Shao, Yinan Lin, Jerry Chun-Wei Srivastava, Gautam Guo, Dongdong Zhang, Hongchun Yi, Hu Jolfaei, Alireza Alibaba Inc Hangzhou 310052 Peoples R China Western Norway Univ Appl Sci N-5063 Bergen Norway Brandon Univ Dept Math & Comp Sci Brandon MB R7A 6A9 Canada China Med Univ Res Ctr Interneural Comp Taichung 40402 Taiwan Asia Univ Coll Informat & Elect Engn Taichung 413 Taiwan Macquarie Univ Dept Comp Sydney NSW 2109 Australia

There has been a recent surge of success in optimizing deep reinforcement learning (DRL) models with neural evolutionary algorithms. This type of method is inspired by biological evolution and uses different genetic operations to evolve neural networks. Previous neural evolutionary algorithms mainly focused on single-objective optimization problems (SOPs). In this article, we present an end-to-end multi-objective neural evolutionary algorithm based on decomposition and dominance (MONEADD) for combinatorial optimization problems. The proposed MONEADD is an end-to-end algorithm that utilizes genetic operations and rewards signals to evolve neural networks for different combinatorial optimization problems without further engineering. To accelerate convergence, a set of nondominated neural networks is maintained based on the notion of dominance and decomposition in each generation. In inference time, the trained model can be directly utilized to solve similar problems efficiently, while the conventional heuristic methods need to learn from scratch for every given test problem. To further enhance the model performance in inference time, three multi-objective search strategies are introduced in this work. Our experimental results clearly show that the proposed MONEADD has a competitive and robust performance on a bi-objective of the classic travel salesman problem (TSP), as well as Knapsack problem up to 200 instances. We also empirically show that the designed MONEADD has good scalability when distributed on multiple graphics processing units (GPUs).

关键词： optimization Evolutionary computation Heuristic algorithms Search problems neural networks Genetics Urban areas Attention mechanism deep reinforcement learning (DRL) multi-objective learning neural combinatorial optimization neural evolutionary algorithm

来源：评论

学校读者我要写书评

暂无评论

A neural combinatorial Approach for School Bus Routing System optimization

A Neural Combinatorial Approach for School Bus Routing Syste...

引用

作者： Qian, Leren Northeastern University

学位级别：Ph.D., Doctor of Philosophy

Maintaining a fleet of buses to transport students to school is a major expense for school districts. An efficient bus routing system can greatly reduce the time and cost associated with transportation, while also ensuring the safety and comfort of students. Optimizing large-scale school bus routing problems (SBRP) is challenging due to the huge number of variables and constraints involved. It is thus treated by decomposing into several subproblems, involving bus stop selection, bus route generation, school bell time adjustment, and bus scheduling. All subproblems of the SBRP are known to be NP-hard. Among all the sub-problems of SBRP, the school bell time adjustment sub-problem has drawn little research attention. Nonetheless, change in the school bell time (start and end time) can be a cost-efficient and practical approach to improve the school bus transportation system. Given a set of bus routes assigned to schools, in this dissertation we develop a multicriteria optimization model that determines the bell times in each school, the assignment of routes to buses, and the schedule of the buses under a single load assumption for both heterogeneous and homogeneous fleet scenarios. The three criteria we consider are (1) minimizing the number of buses, (2) minimizing the total miles of travel distances, and (3) maximizing the preference of all constituents for schools’ bell times. We first introduce an end-to-end neural combinatorial method to efficiently deal with the school bus scheduling problem. Borrowing the idea from the Transformer architecture, an attention model trained using reinforcement learning is applied to the bus scheduling problem by taking the embedded graph information as input, to predict the optimal routing permutation. As a result, a pre-trained model would be available for solving multiple instances simultaneously in parallel. In addition, we design the scheme for generating benchmark datasets for the bus scheduling problem. Then, a 2-stage Tabu

关键词： Deep reinforcement learning neural combinatorial optimization School bell optimization School bus routing Tabu search

来源：评论

学校读者我要写书评

暂无评论

Reinforcement Learning for Efficient Drone-Assisted Vehicle Routing

引用

APPLIED SCIENCES-BASEL 2025年第4期15卷 2007-2007页

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

Many exact algorithms, heuristics, and metaheuristics have been proposed to solve the Vehicle Routing Problem with Drones, which involves using a fleet of trucks and drones to fulfil customer orders in last-mile delivery. In this study, the problem is formulated using the Markov Decision Process, and a Reinforcement Learning (RL) based solution is proposed. The proposed RL model is based on an attention-encoder and a recurrent neural network-decoder architecture. This approach enhances coordination by determining which vehicles should visit specific customers and where vehicles can rendezvous, effectively leveraging drones and reducing the overall completion time. The RL model has demonstrated competitive performance compared to benchmark algorithms through extensive experiments.

关键词： reinforcement learning neural combinatorial optimization vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Deep reinforcement learning for machine scheduling: Methodology, the state-of-the-art, and future directions

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2025年 200卷

作者： Khadivi, Maziyar Charter, Todd Yaghoubi, Marjan Jalayer, Masoud Ahang, Maryam Shojaeinasab, Ardeshir Najjaran, Homayoun Univ Victoria Dept Mech Engn Victoria BC V8P 5C2 Canada Univ Victoria Dept Elect & Comp Engn Victoria BC V8P 5C2 Canada Univ Turku Dept Mech & Mat Engn Turku 20014 Finland

Machine scheduling aims to optimally assign jobs to a single or a group of machines while meeting manufacturing rules as well as job specifications. Optimizing the machine schedules leads to significant reduction in operational costs, adherence to customer demand, and rise in production efficiency. Despite its benefits for the industry, machine scheduling remains a challenging combinatorial optimization problem to be solved, inherently due to its Non-deterministic Polynomial-time (NP) hard nature. Deep Reinforcement Learning (DRL) has been regarded as a foundation for "artificial general intelligence"with promising results in tasks such as gaming and robotics. Researchers have also aimed to leverage the application of DRL, attributed to extraction of knowledge from data, across variety of machine scheduling problems since 1995. This paper presents a comprehensive review and comparison of the methodology, application, and the advantages and limitations of different DRL-based approaches. Further, the study categorizes the DRL methods based on the integrated computational components including conventional neural networks, encoder-decoder architectures, graph neural networks and metaheuristic algorithms. Our literature review concludes that the DRL-based approaches surpass the performance of exact solvers, heuristics, and tabular reinforcement learning algorithms in either computation speed, generating near-global optimal solutions, or both. They have been applied to static or dynamic scheduling of different machine environments, which consist of single machine, parallel machine, flow shop, job shop, and open shop, with different job characteristics. Nonetheless, the existing DRLbased schedulers face limitations not only in considering complex operational constraints, and configurable multi-objective optimization but also in dealing with generalization, scalability, intepretability, and robustness. Therefore, addressing these challenges shapes future work in this field.

关键词： Machine scheduling Deep reinforcement learning neural combinatorial optimization Graph neural networks Production scheduling Artificial intelligence

来源：评论

学校读者我要写书评

暂无评论

Improving generalization of neural Vehicle Routing Problem solvers through the lens of model architecture

引用

neural NETWORKS 2025年 187卷 107380页

作者： Xiao, Yubin Wang, Di Wu, Xuan Wu, Yuesong Li, Boyang Du, Wei Wang, Liupu Zhou, You Jilin Univ Coll Comp Sci & Technol Minist Educ Key Lab Symbol Computat & Knowledge Engn Changchun 130012 Peoples R China Nanyang Technol Univ Joint NTU UBC Res Ctr Excellence Act Living Elderl Singapore 639956 Singapore Nanyang Technol Univ WeBank NTU Joint Res Inst Fintech Singapore 639956 Singapore Nanyang Technol Univ Coll Comp & Data Sci Singapore 639956 Singapore

neural models produce promising results when solving Vehicle Routing Problems (VRPs), but may often fall short in generalization. Recent attempts to enhance model generalization often incur unnecessarily large training cost or cannot be directly applied to other models solving different VRP variants. To address these issues, we take a novel perspective on model architecture in this study. Specifically, we propose a plug- and-play Entropy-based Scaling Factor (ESF) and a Distribution-Specific (DS) decoder to enhance the size and distribution generalization, respectively. ESF adjusts the attention weight pattern of the model towards familiar ones discovered during training when solving VRPs of varying sizes. The DS decoder explicitly models VRPs of multiple training distribution patterns through multiple auxiliary light decoders, expanding the model representation space to encompass a broader range of distributional scenarios. We conduct extensive experiments on both synthetic and widely recognized real-world benchmarking datasets and compare the performance with seven baseline models. The results demonstrate the effectiveness of using ESF and DS decoder to obtain a more generalizable model and showcase their applicability to solve different VRP variants, i.e., traveling salesman problem and capacitated VRP. Notably, our proposed generic components require minimal computational resources, and can be effortlessly integrated into conventional generalization strategies to further elevate model generalization.

关键词： Vehicle Routing Problem Generalization Model architecture neural combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：