时变网络条件下带时间窗的食品冷链配送定位—运输路径优化问题

为解决食品冷链配送系统优化问题,针对易腐品特性,结合配送网络时变特征进行行程时间分析,根据服务时间窗设计满意度函数,建立时变条件下的仿真模型;采用"预优化阶段+实时优化阶段"两阶段求解策略,利用分解法进行问题分解,设计最小包络聚类分析方法与混合遗传算法求解。仿真计算验证了模型和算法的有效性与研究的实用价值。     

求解带硬时间窗的多目标车辆路径问题的多种混合蝙蝠算法

针对多目标车辆路径问题的研究,考虑了车载量限制和硬时间窗的约束条件,以最小派车数和最小车辆行驶距离为目标建立了数学模型。在分析基本蝙蝠算法求解离散问题局限性的基础上,混合蝙蝠法加入交叉算子和重组算子,提高算法性能。利用遗传算法的特点,构建出三种混合蝙蝠算法,算例测试结果表明,混合蝙蝠算法是解决离散型问题的一种有效方法。与基本蝙蝠算法相比,混合蝙蝠算法具有较高的计算效率和持续优化能力,其中单点重组精英遗传混合蝙蝠算法解决算例寻优能力最佳。 关键词：混合蝙蝠算法;车辆路径问题;多目标;硬时间窗     

求解带硬时间窗车辆路径问题的时差插入启发式算法

针对已有求解带硬时间窗车辆路径问题时插入启发式算法结构复杂、参数多、求解效率不高的缺点,提出了求解该问题的时差插入启发式算法。该算法引入时差的概念,将时差作为启发规则的评价指标。相比已有求解该问题的经典启发式算法,该算法有参数个数少、算法结构简单等特点。应用标准测试算例测试表明,所提算法的求解质量优于Solomon的插入启发式算法和Potvin的平行插入启发式算法。     

A branch-and-cut algorithm for the hub location and routing problem

We study the hub location and routing problem where we decide on the location of hubs, the allocation of nodes to hubs, and the routing among the nodes allocated to the same hubs, with the aim of minimizing the total transportation cost. Each hub has one vehicle that visits all the nodes assigned to it on a cycle. We propose a mixed integer programming formulation for this problem and strengthen it with valid inequalities. We devise separation routines for these inequalities and develop a branch-and-cut algorithm which is tested on CAB and AP instances from the literature. The results show that the formulation is strong and the branch-and-cut algorithm is able to solve instances with up to 50 nodes.     

不确定条件下速度时变VRPTW问题

构建了不确定条件下速度时变的VRPTW问题模型(UTDVRPTW),设计了一种改进的双重进化人工蜂群算法求解该模型.在需要两点进行操作的搜索过程中,采用一点随机选取,另一点通过遍历可行解,以其中最优解确定位置的半随机式搜索策略改进插入点算子和逆转序列算子,分别在两对以及三对城市间距离之和的解空间维度上交叉搜索,并应用到局部搜索中构成双重进化过程.实验结果验证了所提出算法的有效性以及解决UTDVRPTW的可行性.     

Neural versus traditional approaches to the location of interacting hub facilities

In this paper we consider the optimal location of interacting hub facilities. Using the well-known quadratic integer programming formulation of the uncapacitated, single allocation, p-hub median problem (USApHMP), we demonstrate a mapping onto a Hopfield neural network which guarantees feasibility of the final solution. We also propose a novel modification to the Hopfield network which enables escape from local minima, thus improving final solution quality. A practical application of the USApHMP—a postal delivery network—is used to demonstrate that the quality of these Hopfield network solutions compares favorably to those obtained using both exact methods and simulated annealing. Well-known data sets from the literature are also tested using the Hopfield network approaches, and provide further evidence that optimal or near-optimal solutions can consistently be obtained. The speed advantages which can be attained when implementing neural networks in hardware make the Hopfield neural network a very attractive potential alternative to the existing solution techniques.     

旁域更新智能水滴算法软时间窗车辆路径优化

利用智能水滴算法（IWD）特点,设计了基于IWD算法的车辆路径优化算法框架。针对标准IWD算法在泥土更新上过于单一的缺点,设计了旁域更新的泥土含量更新机制,考虑整个河道的泥土信息变化,增加了其他水滴到达目标节点的概率;提出了车辆路径IWD算法的编码方式,基于改进的旁域更新IWD算法设计了软时间窗车辆路径优化算法;通过实验仿真,对比旁域IWD算法与标准算法及粒子群算法的车辆路径优化结果,显示该算法相比对比算法具有更高的收敛精度和更快的收敛时间。     

考虑载重影响耗电率的电动车车辆路径问题

随着新能源和绿色物流等政策的出台,电动车逐渐成为物流配送的主要运输工具.考虑到电动车的电池容量、充电时间、耗电率和充电站位置等因素,研究载重影响耗电率的电动车车辆路径问题,建立以总成本最小化为目标的混合整数规划模型.结合禁忌搜索算法的思想,设计改进的自适应大邻域搜索算法对其求解,在该算法中,开发多种基于模型特性的破坏算子和修复算子以提高求解效率.通过算例求解验证模型和算法的有效性,为物流企业电动车配送方案的规划提供一定的决策依据.     

有时间窗约束车辆路径问题的改进遗传算法

将遗传算法与禁忌搜索结合起来,设计了一种改进的遗传算法求解有时间窗约束车辆路径问题。采用启发式插入算法产生较优良的遗传操作初始种群,通过改进的逆转变异算子更多继承父代的优良性能,以提高遗传算法的计算效率。引入海明距评估遗传进化中种群的多样性。当种群多样性低到一定程度时转入禁忌搜索,以避免遗传算法早熟的缺陷,最终实现全局优化。通过算例验证了该算法的优越性。     

负载平衡路由：一种新的ACO路由策略*

通过改进ACO算法达到一种能实现通信网络负载平衡的群体智能路由策略。采用的主要方法为：将蚁群划分为若干个子群,不同子群的蚂蚁释放不同类型的信息素。通过不同类型信息素之间的相互制约作用,以及链路负载的测量,提出了三种策略实现负载平衡路由。在模拟网络上进行了不同策略的对比实验,以及与已有的群体智能路由算法的运行测试比较。实验结果表明,本文的路由策略具有较好的效果和一定的优势。     

不确定车辆数的有时间窗车辆选径问题的混合算法

针对标准遗传算法在求解车辆选径问题中出现的早熟、收敛、易陷入局部极值点的问题，提出了一种由遗传算法结合模拟退火算法的混合算法求解车辆选径问题，并与遗传算法进行了比较。该算法利用了模拟退火算法具有的较强的局部搜索能力的特性，有效地克服了传统遗传算法的“早熟收敛”问题。实验结果表明，该算法具有计算效率高、收敛速度快和求解质量优的特点，是解决车辆选径问题的有效方法。     

Artificial intelligence heuristics in solving vehicle routing problems with time window constraints

This paper describes the authors’ research on various heuristics in solving vehicle routing problem with time window constraints (VRPTW) to near optimal solutions. VRPTW is NP-hard problem and best solved to near optimum by heuristics. In the vehicle routing problem, a set of geographically dispersed customers with known demands and predefined time windows are to be served by a fleet of vehicles with limited capacity. The optimized routines for each vehicle are scheduled as to achieve the minimal total cost without violating the capacity and time window constraints. In this paper, we explore different hybridizations of artificial intelligence based techniques including simulated annealing, tabu search and genetic algorithm for better performance in VRPTW. All the implemented hybrid heuristics are applied to solve the Solomon's 56 VRPTW with 100-customer instances, and yield 23 solutions competitive to the best solutions published in literature according to the authors’ best knowledge.     

Site dependent vehicle routing problem with soft time window: Modeling and solution approach

This paper presents two meta-heuristic algorithms, an ant colony system with local searches and a tabu search algorithm, for Site-Dependent Vehicle Routing Problem with Soft Time Window (SDVRPSTW). In the SDVRPSTW a fleet of vehicles must deliver goods to their allowable set of customers, preferably in their time windows while the capacity constraints of the vehicles must be respected. Based on our best knowledge, this problem which challenges the distribution task of public services and private organizations in an urban context with heavy traffic has not yet been considered in practical aspects, especially where the vehicles entrance to some areas needs traffic license. Hence, in addition to present an Integer Linear Programming (ILP) model, we present the two mentioned algorithms to handle the problem in large scale instances. Furthermore, the algorithms efficiency and their optimality are analyzed by experimental results both in small and large dimensions.     

A variable neighborhood descent with ant colony optimization to solve a bilevel problem with station location and vehicle routing

Applied Intelligence - Electric vehicles are becoming popular in transport systems due to subsidies provided by the governments and the reduction of environmental issues. A bilevel optimization...     

基于第三方带软时间窗约束的车辆路径问题研究

在分析电商企业的“自建物流+第三方物流”配送模式的基础上,对自建物流成本和第三方物流成本分别展开研究,并在自建物流成本中设计了软时间窗惩罚函数.建立了基于第三方带软时间窗约束的车辆路径模型,设计了基于自然数序列的改进遗传算法对模型进行求解,改进交叉与变异操作来保护优秀基因,提出了种群扩张机制.最后,算例结果表明模型可以有效减少物流配送成本,提高配送效率,改进遗传算法还在提高计算时间方面有显著的成效.     

基于强基因模式组织算法的VRPTW研究

提出一种强基因模式组织算法,给出了强基因模式、连续模式以及对称模式的定义,使用节约法提取强基因模式.设计了选择、变异和模式重组算子,同时建立了以运输成本为目标、具有时间窗等约束的车辆路径问题模型.将该算法与改进的遗传算法、改进的差分进化算法和节约法对模型进行仿真实验.结果表明,强基因模式的应用及模式重组算子大大缩小了解的搜索空间,提高了算法的收敛速度和解的精度,其性能优于其他3种算法.     

Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows

This paper presents an adaptive memetic algorithm to solve the vehicle routing problem with time windows (VRPTW). It is a well-known NP-hard discrete optimization problem with two objectives—to minimize the number of vehicles serving a set of geographically dispersed customers, and to minimize the total distance traveled in the routing plan. Although memetic algorithms have been proven to be extremely efficient in solving the VRPTW, their main drawback is an unclear tuning of their numerous parameters. Here, we introduce the adaptive memetic algorithm (AMA-VRPTW) for minimizing the total travel distance. In AMA-VRPTW, a population of solutions evolves with time. The parameters of the algorithm, including the selection scheme, population size and the number of child solutions generated for each pair of parents, are adjusted dynamically during the search. We propose a new adaptive selection scheme to balance the exploration and exploitation of the solution space. Extensive experimental study performed on the well-known Solomon’s and Gehring and Homberger’s benchmark sets confirms the efficacy and convergence capabilities of the proposed AMA-VRPTW. We show that it is very competitive compared with other state-of-the-art techniques. Finally, the influence of the proposed adaptive schemes on the AMA-VRPTW behavior and performance is investigated in a thorough sensitivity analysis. This analysis is complemented with the two-tailed Wilcoxon test for verifying the statistical significance of the results.     

A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand

Home Health Care (HHC) companies are widespread in European countries, and aim to serve patients at home to help them recover from illness and injury in a personal environment. Since transportation costs are among the biggest sources of expenditure in company activities, it is of great significance to optimize this in the Home Health Care industry. From the perspective of optimizing the cost of transportation, this paper studies the Vehicle Routing Scheduling problem as it applies to HHC companies. According to a survey of the HHC companies, during the process of delivering medication drugs, the quantity of drugs required for each patient is non-deterministic when the company makes planned routes. This paper considers uncertain demand as a fuzzy variable, which is closer to a potential real life scenario. A Home Health Care Scheduling Problem with fuzzy demand is considered and a fuzzy chance constraint model is designed. We propose a hybrid genetic algorithm integrated with stochastic simulation methods to solve the proposed model. Firstly, the problem is reduced to the classical vehicle routing problem within a time window. Experimental results for Solomon’s and Homberger’s benchmark instances show that the proposed algorithm performs efficiently. Then other experiments on the fuzzy version model are undertaken with the variable value of the Dispatcher Preference Index (DPI) parameter between [0, 1]. Finally, the influence of DPI on the final objective and the indicators of the problem are discussed using stochastic simulation, and the best value of DPI is obtained. This research will help HHC companies to make appropriate decisions when arranging their vehicle scheduling routes.     

考虑灵活充电策略的带时间窗物流配送路径优化研究

电动汽车作为一种新型绿色交通运输工具,目前被广泛的应用于多种物流场景中.然而,电池容量有限、充电时间长以及配套设施不健全等问题制约着其在物流配送领域中的有效推广.为此,针对电动汽车的物流配送路径优化问题,引入一种部分充电策略,提出了考虑部分充电策略的带时间窗电动汽车物流配送路径优化问题,建立了该问题的整数规划模型,并设计混合模拟退火算法对其求解.最后,利用一个研究算例对模型和算法进行了测试和数值分析,验证了其有效性.