矩形的三角形划分问题研究

给出了矩形的三角形划分问题的定义,该问题是三角形Packing问题的一个特例,证明了该问题是NP完全的,并给出了该问题有解的一个必要条件。     

机器人足球比赛最优拦截问题建模与求解

针对机器人足球比赛拦截问题,构建了时间最短的性能指标和拦截成功的约束问题,将机器人足球比赛的拦截问题转化成一个带等式约束的规划问题求解;进一步考虑小车加速度修正该模型,获得细化的最优拦截模型,说明该模型易于扩展和修正;采用MATLAB对该问题进行求解,验证了该方法的可行性。     

P-中心选址问题的一种降阶回溯算法

运筹学研究领域中的应急服务设施选址问题有许多求解模型,选取了P-中心模型进行研究,首先研究了该问题的数学性质,并给出了证明,利用这些数学性质能对问题进行降阶从而缩小问题的规模;然后在此基础上设计一个基于上界和下界的回溯算法来求解该问题;最后通过一个示例分析进一步阐述了该算法的原理,并证明了该算法能在较短时间内求得问题的最优解。     

有时间窗车辆路径问题的混合智能算法

有时间窗的车辆路径问题属于组合优化领域中的NP-hard问题。在对该问题进行分析的基础上,为之建立了数学模型,提出了一种求解该问题的混合智能算法。该算法通过使用蚁群算法和遗传算法交替优化,并且及时交换信息,弥补了蚁群算法和遗传算法各自的不足,达到了优势互补的效果,增强了算法的寻优能力,避免了停滞现象。实验结果表明,该算法能有效解决有时间窗的车辆路径问题。     

基于有时间窗车辆路径问题的混合蚁群算法

有时间窗的车辆路径问题是目前组合优化领域研究的热点问题,其归属于NP-hard问题.在对该问题进行分析的基础上,为之建立了数学模型,提出了一种求解该问题的混合蚁群算法.该算法通过在蚁群算法中引AA-interchange变异算子,增强了算法的局部搜索能力,避免了早熟现象.实验结果表明,该算法能有效解决有时间窗的车辆路径问题.     

带广义紧前约束的资源受限项目计划问题求解

介绍带广义紧前约束资源受限项目计划问题的约束条件和数学模型,对该问题的网络拓扑和时间约束条件进行了分析,对该问题求解的相关定义、定理、预处理过程进行了介绍,提出该问题的蚁群禁忌优化算法.     

十五数码问题研究及实现

十五数码问题是人工智能领域中的一个典型问题。本文对该问题进行了详细分析,并用启发式搜索解决了该问题,同时比较了3种不同评估函数的效率。     

最大圈分解问题的研究进展

最大圈分解问题最早由Erds和Pósa提出,随后研究人员在图论领域和理论计算机科学领域中对其进行了广泛的探索。最近研究发现,该问题在计算生物学上特别是在构建进化树与分析基因组的研究方面有重要的应用。主要介绍了该问题的研究现状。首先讨论了该问题在图论方面的研究进展;随后对该问题的近似算法、参数算法、参数复杂性与不可近似性进行了分析和讨论;最后给出了该问题的进一步研究方向。     

节点加权的Steiner树问题的降阶回溯算法

节点加权的Steiner树问题是组合优化中一个经典的NP-hard问题,现有算法研究该问题时存在时间复杂性高或无法得到最优解的缺点。针对现有算法的不足,提出了一个基于降阶技术的回溯算法。首先研究该问题的数学性质,利用数学性质对该问题进行降阶以缩小问题的规模;接着提出上界子算法和下界子算法,利用上下界子算法对该问题的解空间树进行剪枝,提高搜索效率;最后利用上下界子算法和数学性质设计了一个回溯算法求解该问题。示例分析以及实验的结果表明,该算法不仅时间复杂性较低而且可以得到问题的最优解。     

增加约束条件的线性规划问题递推算法研究

首先描述线性规划问题中约束条件增加时的递推求解问题,此问题在线性规划问题中具有广泛的实际背景;然后提出一个基于凸空间思想的快速求解此类问题的递推算法,该算法能快速判断其矛盾约束、冗余约束以及新问题的递推最优解;最后给出了该问题的一个算例,实验仿真结果表明了该方法的有效性.     

A hybrid algorithm for a class of vehicle routing problems

In this work we propose a hybrid algorithm for a class of Vehicle Routing Problems with homogeneous fleet. A sequence of Set Partitioning (SP) models, with columns corresponding to routes found by a metaheuristic approach, are solved, not necessarily to optimality, using a Mixed Integer Programming (MIP) solver, that may interact with the metaheuristic during its execution. Moreover, we developed a reactive mechanism that dynamically controls the dimension of the SP models when dealing with large size instances. The algorithm was extensively tested on benchmark instances of the following Vechicle Routing Problem (VRP) variants: (i) Capacitated VRP; (ii) Asymmetric VRP; (iii) Open VRP; (iv) VRP with Simultaneous Pickup and Delivery; (v) VRP with Mixed Pickup and Delivery; (vi) Multi-depot VRP; (vii) Multi-depot VRP with Mixed Pickup and Delivery. The results obtained were quite competitive with those found by heuristics devoted to specific variants. A number of new best solutions were obtained.     

深度强化学习求解车辆路径问题的研究综述

车辆路径问题（VRP）是组合优化问题中经典的NP难问题,广泛应用于交通、物流等领域,随着问题规模和动态因素的增多,传统算法很难快速、智能地求解复杂的VRP问题。近年来随着人工智能技术的发展,尤其是深度强化学习（DRL）在AlphaGo中的成功应用,为路径问题求解提供了全新思路。鉴于此,针对近年来利用DRL求解VRP及其变体问题的模型进行文献综述。回顾了DRL求解VRP的相关思路,并梳理基于DRL求解VRP问题的关键步骤,对基于指针网络、图神经网络、Transformer和混合模型的四类求解方法分类总结,同时对目前基于DRL求解VRP及其变体问题的模型性能进行对比分析,总结了基于DRL求解VRP问题时遇到的挑战以及未来的研究方向。     

An open source Spreadsheet Solver for Vehicle Routing Problems

The Vehicle Routing Problem (VRP) is one of the most frequently encountered optimization problems in logistics, which aims to minimize the cost of transportation operations by a fleet of vehicles operating out of a base. This paper introduces VRP Spreadsheet Solver, an open source Excel based tool for solving many variants of the Vehicle Routing Problem (VRP). Case studies of two real-world applications of the solver from the healthcare and tourism sectors that demonstrate its use are presented. The solution algorithm for the solver, and computational results on benchmark instances from the literature are provided. The solver is found to be capable of solving Capacitated VRP and Distance-Constrained VRP instances with up to 200 customers within 1 h of CPU time.     

An improved model for vehicle routing problem with time constraint based on genetic algorithm

A vehicle routing problem (VRP) with time constraint is one of the important problems in distribution and transportation. Thus the generic VRP and its practical extensions are discussed in great detail in the literatures. In the VRP, the service of a customer must start and finish within a given time interval. The objective of this problem is to minimize the cost of servicing the set of customers without being tardy or exceeding the capacity or travel time of the vehicles. In this research we concentrated on developing a GA–TSP model by improving the genetic algorithm (GA) operators and the initial population. For the computational purpose, we developed a GUI (graphic user interface)-type computer program according to the proposed method. The computational results show that the proposed method is very effective on a set of standard test problems and it can be potentially useful in solving the VRPs.     

An Overview and Experimental Study of Learning-Based Optimization Algorithms for the Vehicle Routing Problem

The vehicle routing problem (VRP) is a typical discrete combinatorial optimization problem, and many models and algorithms have been proposed to solve the VRP and its variants. Although existing approaches have contributed significantly to the development of this field, these approaches either are limited in problem size or need manual intervention in choosing parameters. To solve these difficulties, many studies have considered learning-based optimization (LBO) algorithms to solve the VRP. This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches. We performed a statistical analysis of the reviewed articles from various aspects and designed three experiments to evaluate the performance of four representative LBO algorithms. Finally, we conclude the applicable types of problems for different LBO algorithms and suggest directions in which researchers can improve LBO algorithms.      

Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm

The Vehicle Routing Problem (VRP) has been thoroughly studied in the last decades. However, the main focus has been on the deterministic version where customer demands are fixed and known in advance. Uncertainty in demand has not received enough consideration. When demands are uncertain, several problems arise in the VRP. For example, there might be unmet customers’ demands, which eventually lead to profit loss. A reliable plan and set of routes, after solving the VRP, can significantly reduce the unmet demand costs, helping in obtaining customer satisfaction. This paper investigates a variant of an uncertain VRP in which the customers’ demands are supposed to be uncertain with unknown distributions. An advanced Particle Swarm Optimization (PSO) algorithm has been proposed to solve such a VRP. A novel decoding scheme has also been developed to increase the PSO efficiency. Comprehensive computational experiments, along with comparisons with other existing algorithms, have been provided to validate the proposed algorithms.     

Testing local search move operators on the vehicle routing problem with split deliveries and time windows

The vehicle routing problem (VRP) is an important transportation problem. The literature addresses several extensions of this problem, including variants having delivery time windows associated with customers and variants allowing split deliveries to customers. The problem extension including both of these variations has received less attention in the literature. This research effort sheds further light on this problem. Specifically, this paper analyzes the effects of combinations of local search (LS) move operators commonly used on the VRP and its variants. We find when paired with a MAX-MIN Ant System constructive heuristic, Or-opt or 2-opt⁎ appear to be the ideal LS operators to employ on the VRP with split deliveries and time windows with Or-opt finding higher quality solutions and 2-opt⁎ requiring less run time.     

求解VRP的蚁群算法研究

车辆路径问题是物流配送中一个至关重要的问题。由于它是一个NP-Hard问题,启发式算法成为求解VRP的主要方法。蚁群算法是近年来发展起来的一种可以用来求解VRP的启发式算法。实验证明,该方法能够很好地解决车辆路径问题。本文详细阐述了蚁群算法的基本原理和求解VRP的蚁群算法过程。     

二次蚁群算法在运输调度问题中的应用

蚁群算法在解决车辆路径问题VRP(Vehicle Routing Problem)上表现了很大优势,但也存在全局搜索能力较低、易出现停滞等缺陷.提出的二次蚁群算法是指先用改进的自适应蚁群算法对VRP求得一个可行解,再用求解旅行商问题TSP(Traveling Salesman Problem)的蚁群算法对所得到的解进一步优化,从而得到最优解.从两个实验仿真结果的数据上看,该算法具有很强的搜索能力,克服了基本蚁群算法的某些弊端,能够有效地求解车辆路径问题.