带服务优先级车辆路径问题的扫描禁忌搜索算法

提出了一种带服务优先级车辆路径问题的模型(Vehicle Routing Problem with Precedence Constraints,VRPPC),和一种扫描—禁忌搜索算法(sweep-Taboo Search Algorithm,S-TSA).然后,运用S-TSA对郑煤物资供销有限公司的带有服务优先级的危险物资配送进行优化求解,并与扫描遗传算法(sweep-Genetic Algorithm,SGA),禁忌搜索算法(Taboo Search Algorithm,TSA),人工鱼群算法(Artificial Fish Algorithm,AFA)进行比较研究,研究结果显示:扫描禁忌搜索算法能在满足服务优先级的前提下,使配送费用最少.     

有时间窗的车辆路径问题的局部下降搜索算法

介绍了一个求解有时间窗的车辆路径问题(vehicle routing problem with time windows,VRPTW)的启发式算法——基于λ-交换的局部下降搜索算法(Local search descent method based on λ-interchange).VRPTW是指合理安排车辆行驶路线,为一组预先设定有时间限制的客户运送货物,在不违反时间要求和车辆容量限制的条件下使得成本最小.它是一个典型的NP-难题,可以通过启发式算法获得近优解来解决.通过两个实验验证,显示了局部下降搜索算法的优良性能,取得了很好的效果,可以作为进一步研究复杂算法的基础.     

An Iterated Local Search heuristic for the Heterogeneous Fleet Vehicle Routing Problem

This paper deals with the Heterogeneous Fleet Vehicle Routing Problem (HFVRP). The HFVRP is $\mathcal{NP}$ -hard since it is a generalization of the classical Vehicle Routing Problem (VRP), in which clients are served by a heterogeneous fleet of vehicles with distinct capacities and costs. The objective is to design a set of routes in such a way that the sum of the costs is minimized. The proposed algorithm is based on the Iterated Local Search (ILS) metaheuristic which uses a Variable Neighborhood Descent procedure, with a random neighborhood ordering (RVND), in the local search phase. To the best of our knowledge, this is the first ILS approach for the HFVRP. The developed heuristic was tested on well-known benchmark instances involving 20, 50, 75 and 100 customers. These test-problems also include dependent and/or fixed costs according to the vehicle type. The results obtained are quite competitive when compared to other algorithms found in the literature.     

求解车辆路径问题的免疫算法

将免疫算法用于求解车辆路径问题,并根据车辆路径问题的具体情况提出了一种基于分组匹配的亲和力计算方法.实验结果表明,免疫算法能有效地应用于车辆路径问题.     

A Neural-Tabu Search Heuristic for the Real Time Vehicle Routing Problem

The Real Time Vehicle Routing Problem RTVRP is a dynamic routing problem where requests are generated dynamically during the operation horizon without any previous knowledge. Received requests need to be answered as fast as possible and then assigned to a vehicle to be served. Due to timing constraints of the RTVRP, a solving approach should give the best compromise between the cost of the provided solution and the computation time needed to find it. In this paper, we present a neural-tabu search solving scheme for the RTVRP. The developed approach is composed by two phases; The first part consists of learning and reproducing previous routing decisions using a feed forward neural network with a particular structure. The second phase is based on a tabu search heuristic that takes its initial solution from the assignment provided by the neural module. If the reaction time is still available, the tabu search module will continue ameliorating the final solution. To evaluate the proposed approach a set of problems are simulated and solved. The obtained results are compared to those given by the First Come First Served FCFS and Nearest Neighbor NN policies and also to the optimal solutions provided by the GNU Linear Programming Kit GLPK.      

A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem

In this paper, we propose a hybrid Granular Tabu Search algorithm to solve the Multi-Depot Vehicle Routing Problem (MDVRP). We are given on input a set of identical vehicles (each having a capacity and a maximum duration), a set of depots, and a set of customers with deterministic demands and service times. The problem consists of determining the routes to be performed to fulfill the demand of the customers by satisfying, for each route, the associated capacity and maximum duration constraints. The objective is to minimize the sum of the traveling costs related to the performed routes. The proposed algorithm is based on a heuristic framework previously introduced by the authors for the solution of the Capacitated Location Routing Problem (CLRP). The algorithm applies a hybrid Granular Tabu Search procedure, which considers different neighborhoods and diversification strategies, to improve the initial solution obtained by a hybrid procedure. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several best solutions obtained by the previously published methods and new best solutions.     

一类最小-最大车辆路线问题的启发式算法研究

针对个性化和多样性的需求,建立以缩短最长子线路为目标的最小-最大车辆路径问题模型, 并提出启发式算法求解。首先,采用自然数编码,使问题变得更简洁;用最佳保留选择法,以保证群体的多样性;引入爬山算法,加强局部搜索能力;其次,对遗传算法求得的精英种群再进行禁忌搜索,保证算法能够收敛到全局最优。最后,通过实例的计算,表明本算法均优于遗传算法和禁忌搜索算法,并为大规模解决实际问题提供思路。     

A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints

We present a metaheuristic methodology for the Capacitated Vehicle Routing Problem with two-dimensional loading constraints (2L-CVRP). 2L-CVRP is a generalisation of the Capacitated Vehicle Routing Problem, in which customer demand is formed by a set of two-dimensional, rectangular, weighted items. The purpose of this problem is to produce the minimum cost routes, starting and terminating at a central depot, to satisfy the customer demand. Furthermore, the transported items must be feasibly packed into the loading surfaces of the vehicles. We propose a metaheuristic algorithm which incorporates the rationale of Tabu Search and Guided Local Search. The loading aspects of the problem are tackled using a collection of packing heuristics. To accelerate the search process, we reduce the neighbourhoods explored, and employ a memory structure to record the loading feasibility information. Extensive experiments were conducted to calibrate the algorithmic parameters. The effectiveness of the proposed metaheuristic algorithm was tested on benchmark instances and led to several new best solutions.     

灰色非线性约束规划的改进引力搜索算法求解

灰色非线性约束规划是灰色系统中一个重要的优化问题.为求解灰色非线性约束规划,给出了一种改进引力搜索算法的求解方法.实验结果表明改进引力搜索算法对求解灰色非线性约束规划可行有效.     

Tabu Search heuristics for the Vehicle Routing Problem with Time Windows

This paper surveys the research on the Tabu Search heuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW can be described as the problem of designing least cost routes for a fleet of vehicles from one depot to a set of geographically scattered points. The routes must be designed in such a way that each point is visited only once by exactly one vehicle within a given time interval; all routes start and end at the depot, and the total demands of all points on one particular route must not exceed the capacity of the vehicle. In addition to describing basic features of each method, experimental results for Solomon’s benchmark test problems are presented and analyzed. This work was partially supported by the Emil Aaltonen Foundation, Liikesivistysrahasto Foundation, the Canadian Natural Science and Engineering Research Council and the TOP program funded by the Research Council of Norway. This support is gratefully acknowledged.     

快件揽收实时车辆路径问题的一种贪婪算法

快递运营中，调派车辆前往随机发生的快件发件人处上门揽收快件，是一个实时编排行车路径的动态决策过程．本文针对该问题，采用了揽收所有快件的最后时刻最早和行车路径最短的目标，结合车辆揽收快件数平衡的要求，给出一种贪婪算法；然后，对Solomon设计的100个点规模的VRPTW算例做计算试验，分析了车辆数对目标的影响．     

求解车辆路径问题的离散蝙蝠算法

根据车辆路径问题的数学模型,分析了它的具体特征,从而对BA的操作算子又进行了重新定义,设计了求解VRP问题的离散蝙蝠算法,并通过实例测试将离散蝙蝠算法与其他算法进行比较,验证了该算法求解VRP问题的有效性与可行性.     

A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows

The aim of this paper is to propose an algorithm based on the philosophy of the Variable Neighborhood Search (VNS) to solve Multi Depot Vehicle Routing Problems with Time Windows. The paper has two main contributions. First, from a technical point of view, it presents the first application of a VNS for this problem and several design issues of VNS algorithms are discussed. Second, from a problem oriented point of view the computational results show that the approach is competitive with an existing Tabu Search algorithm with respect to both solution quality and computation times.     

改进蚁群算法优化周期性车辆路径问题

周期性车辆路径问题(PVRP)是标准车辆路径问题(VRP)的扩展,PVRP将配送期由单一配送期延伸到T(T＞1)期,因此,PVRP需要优化每个配送期的顾客组合和配送路径。由于PVRP是一个内嵌VRP的问题,其比标准VRP问题更加复杂,难于求解。本文采用蚁群算法对PVRP进行求解,并提出采用两种改进措施——多维信息素的运用和基于扫描法的局部优化方法来提高算法的性能。最后,通过9个经典PVRP算例对该算法进行了数据实验,结果表明本文提出的改进蚁群算法求解PVRP问题是可行有效的,同时也表明两种改进措施可以显著提高算法的性能。     

一类新的车辆路径问题及其两阶段算法

本文结合汽车零部件第三方物流业的实际背景,提出了一类新的车辆路径问题,它是一种带时间窗约束的分车运输同时收发车辆路径问题(简称SVRPSPDTW).接着给出了问题的模型,并提出求解问题的启发式算法：两阶段算法. 最后在改进的Solomn的算例的基础上,进行了数值试验.     

混合启发式算法求解多配送人员车辆路径问题

为解决带时间窗和多配送人员的车辆路径问题,本文采用混合启发式算法对其进行求解。该算法主要由整数规划重组、局部搜索算法和模拟退火算法三部分组成。在算法中,整数规划重组有效提高了解的质量,局部搜索算法和模拟退火算法保证了算法搜索的深入性和广泛性。通过与CPLEX和禁忌搜索算法进行对比,证实了混合启发式算法实用价值更高,求解效果更好。     

基于引力搜索和粒子群混合优化算法的证券投资组合问题研究

本文研究考虑交易成本的投资组合模型,分别以风险价值(VAR)和夏普比率(SR)作为投资组合的风险评价指标和效益评价指标。为有效求解此模型,本文在引力搜索和粒子群算法的基础上提出了一种混合优化算法(IN-GSA-PSO),将粒子群算法的群体最佳位置和个体最佳位置与引力搜索算法的加速度算子有机结合,使混合优化算法充分发挥单一算法的开采能力和探索能力。通过对算法相关参数的合理设置,算法能够达到全局搜索和局部搜索的平衡,快速收敛到模型的最优解。本文选取上证50股2014年下半年126个交易日的数据,运用Matlab软件进行仿真实验,实验结果显示,考虑交易成本的投资组合模型可使投资者得到更高的收益率。研究同时表明,基于PSO和GSA的混合算法在求解投资组合模型时比单一算法具有更好的性能,能够得到满意的优化结果。     

求解带时间窗车辆路径问题的混合Memetic算法

为提高带时间窗车辆路径问题的求解精度和求解效率,设计了一种混合Memetic算法。采用基于时间窗升序排列的混合插入法构造初始种群,提高解质量的同时兼顾多样性,扩大搜索空间;任意选择组成父代种群,以维持搜索空间;运用简化的变邻域搜索进行局部开发,引入邻域半径减少策略提高开发效率,约束放松机制开放局部空间;以弧为对象,增加种群向当前最优解和全局最优解的后学习过程。实验结果表明,所提出的算法具有较好的寻优精度和稳定性,能搜索到更好的路径长度结果,更新了现有研究在最短路径长度的目标函数上的下限。     

A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows

Vehicle routing problem with time windows (VRPTW) involves the routing of a set of vehicles with limited capacity from a central depot to a set of geographically dispersed customers with known demands and predefined time windows. The problem is solved by optimizing routes for the vehicles so as to meet all given constraints as well as to minimize the objectives of traveling distance and number of vehicles. This paper proposes a hybrid multiobjective evolutionary algorithm (HMOEA) that incorporates various heuristics for local exploitation in the evolutionary search and the concept of Pareto's optimality for solving multiobjective optimization in VRPTW. The proposed HMOEA is featured with specialized genetic operators and variable-length chromosome representation to accommodate the sequence-oriented optimization in VRPTW. Unlike existing VRPTW approaches that often aggregate multiple criteria and constraints into a compromise function, the proposed HMOEA optimizes all routing constraints and objectives simultaneously, which improves the routing solutions in many aspects, such as lower routing cost, wider scattering area and better convergence trace. The HMOEA is applied to solve the benchmark Solomon's 56 VRPTW 100-customer instances, which yields 20 routing solutions better than or competitive as compared to the best solutions published in literature.     

一种部分约束满足车辆路线问题及其求解算法

描述了一类过度约束车辆路线问题，其中可用车辆数较少而时间窗口等其它约束又不允许放松，因而导致不存在满足所有约束的可行解。此时问题求解可以转化为一类部分约束满足问题来处理，相应的优化目标是最小化未访问顾客的损失和。本给出了求解这类特殊问题的一种禁忌搜索算法设计，并通过规模不同的几个算例与其它常用方法进行了比较。最后分析了模型和算法的实用意义。