带时间窗车辆路径问题的差分进化混合算法

研究了带时间窗的车辆路径问题(Vehicle Routing Problem with Time Windows,VRPTW),建立了数学模型,并设计了求解VRPTW的离散差分进化混合算法。算法采用随机车辆配载方法构造初始解,并通过构造新的变异和交叉算子进行改进。进一步,利用插入可行邻域和2-Opt可行邻域两种搜索可行解的邻域结构,引入禁忌搜索进一步进行局部搜索以提高算法的寻优能力。实验结果表明该算法是求解VRPTW的一种有效方法。     

带时间窗车辆路径问题的文化基因算法

针对物流配送中带时间窗的车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）,建立了数学模型,并设计了求解VRPTW的文化基因算法。种群搜索采用遗传算法的进化模式,局部搜索采用禁忌搜索机制,并结合可行邻域结构避免对不可行解的搜索,以提高搜索效率。与单纯的遗传算法和禁忌搜索算法进行对比实验,表明该算法是求解VRPTW的一种有效方法。     

开放式车辆路径问题的混合算法

为研究开放式车辆路径问题(Open Vehicle Routing Problem,OVRP),建立了数学模型.针对遗传算法(Genetic Algorithm,GA)与禁忌搜索算法(Tabu Search Algorithm,TSA)的不足,提出了一个采用GA和TSA相结合的混合算法求解OVRP.混合算法中以GA为主,把TSA用在GA的变异操作中,增强算法的爬山能力.通过仿真,将提出的混合算法与文献中其它算法比较,结果表明它可以快速、有效求得最优解或近似解.     

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

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

一种基于Voronoi图求解车辆路径问题的混合启发式算法

针对由多个配送中心和多个客户点组成的物流网络中的车辆路径问题,提出了一种基于“集群第一,路线第二”的路径优化策略,即首先使用Voronoi分割对配送区域进行划分,然后引入综合插入算法和变邻域搜索算法的混合启发式算法求解配送区域内车辆路径问题。通过算例和应用系统的分析与验证表明,该混合算法既能获取质量较优解,同时也具有较好的实时性,能较好地满足实际应用需求。     

混合模因算法在求解带装箱约束的车辆路径问题中的应用

带有回程取货约束的车辆路径问题(Vehicle Routing Problem with Backhauls,VRPB)和二维装箱问题(two-dimensional Bin Packing Problem,2L-BPP)是两个经典的组合优化问题,在融合两者的基础上,本文提出了一种新的组合最优化问题,即2L-VRPB.在该问题中,车队的最优路径规划和货物的最优装载设计需要同时进行考虑,该问题的优化目标是在满足所有客户的送货和取货需求的前提下,为车队中的车辆制定尽可能最优的行驶路线和货物装载方案,使得车队的总的服务成本最低.该问题在实际生活中有着广泛的应用场景,例如在设备维修和零售行业的货物运输中可经常遇到此类情形,但是文献中关于此类问题的研究论文仍然较少.为了求解2L-VRPB问题,我们提出了一种具有自适应性机制的混合模因算法(HMA),该算法采用改进的模因算法(IMA)来规划最优路径,并通过增强的组合装箱算法(MultiPack)来设计货物的最优装载方案.在实验环节,通过在VRPB问题的Goetschalckx&Jacobs-Blecha测试算例和2L-VRPB问题的Gendreau测试算例上设计对比实验,我们验证了混合模因算法在求解VRPB和2L-VRPB问题时的鲁棒性和有效性.     

混合启发式算法在汽车调度中的应用

将蚁群优化和变邻域下降搜索VND相结合,形成一种混合启发式算法ACS_VND,应用于客运公司的汽车调度,求解车辆需求数和最佳路径。该算法充分利用了2种不同算法的优点。实验结果表明,算法ACS_VND能在较短时间内获得比单个算法更好的车辆调度路径。     

需求可拆分校车路径问题的元启发式算法

校车路径规划中,允许站点乘车需求拆分通常能有效地降低校车服务成本。将该问题定义为需求可拆分校车路径问题(SDSBRP)进行求解。由于校车服务中要顾及学生最大乘车时间,且优化目标要兼顾所需校车数量和校车行驶距离,经典SDVRP算法难以直接应用于SDSBRP。因此分析了该问题的解特征,首次构建双目标SDSBRP数学模型,并首次设计针对该问题的元启发式求解算法。该算法首先构造初始可行解,然后在模拟退火算法框架下,引入站点需求拆分的邻域搜索算子进行迭代搜索,逐步改善解的质量。邻域搜索中,设计了多目标问题的邻域接受准则来引导邻域解的搜索方向,并引入破坏重建机制来增加解的多样性。使用已有的测试案例集和改造的测试案例进行算法测试,实验结果表明所提算法收敛性好,能够显著降低校车服务成本。     

一种求解带时间窗车辆路径问题的混合差分进化算法

对带时间窗的车辆路径问题进行研究,建立以最小化车辆数量和行驶路程为目标的多目标数学模型,提出一种结合改进差分进化算法和变邻域下降搜索的基于Pareto支配的混合差分进化算法。首先重新定义了个体的生成方式。其次,结合双种群策略和变邻域下降搜索技术来平衡算法的全局探索能力和局部开发能力,并在搜索过程中用随机个体替代种群中的重复个体,维持种群的多样性。然后引入Pareto支配的概念来评价个体的优劣性,并采用擂台法则构造非支配解集。最后对18个不同规模的Solomon算例的求解结果表明,算法在行驶路程和车辆数量上的求解质量比人工蜂群算法分别平均提高了2.04%和14.95%,且与已知最优解相比,在车辆数量的求解质量上平均提高了14.53%,验证了所提算法的有效性。     

同时送取货选址路径问题及混合免疫算法

研究了同时送取货的选址路径问题(location-routing problem with simultaneous pickup and delivery,LRP-SPD),在同时送取货问题中,每个客户都有送货需求和取货需求,并且两种需求需要同时进行服务.在此条件下,建立了以仓库的选址成本、车辆启用成本及运输成本等目标和最小的选址路径模型;针对该模型的特点,设计改进了一种混合免疫优化算法(hybrid immune algorithm,HIA)对该问题进行求解,运用贪心聚类算法生成初始解,利用原始免疫算法对抗体进行评价排序,由邻域搜索操作改进原始算法的免疫操作.最后,通过使用混合免疫优化算法与原始免疫优化算法、模拟退火算法、蚁群算法分别对案例进行求解和对比分析,验证了提出模型的可行性和算法的有效性.     

An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem

In this paper, an enhanced ant colony optimization (EACO) is proposed for capacitated vehicle routing problem. The capacitated vehicle routing problem is to service customers with known demands by a homogeneous fleet of fixed capacity vehicles starting from a depot. It plays a major role in the field of logistics and belongs to NP-hard problems. Therefore, it is difficult to solve the capacitated vehicle routing problem directly when solutions increase exponentially with the number of serviced customers. The framework of this paper is to develop an enhanced ant colony optimization for the capacitated vehicle routing problem. It takes the advantages of simulated annealing and ant colony optimization for solving the capacitated vehicle routing problem. In the proposed algorithm, simulated annealing provides a good initial solution for ant colony optimization. Furthermore, an information gain based ant colony optimization is used to ameliorate the search performance. Computational results show that the proposed algorithm is superior to original ant colony optimization and simulated annealing separately reported on fourteen small-scale instances and twenty large-scale instances.     

Variable neighborhood search for location routing

In this paper we propose various neighborhood search heuristics (VNS) for solving the location routing problem with multiple capacitated depots and one uncapacitated vehicle per depot. The objective is to find depot locations and to design least cost routes for vehicles. We integrate a variable neighborhood descent as the local search in the general variable neighborhood heuristic framework to solve this problem. We propose five neighborhood structures which are either of routing or location type and use them in both shaking and local search steps. The proposed three VNS methods are tested on benchmark instances and successfully compared with other two state-of-the-art heuristics.     

A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem

This paper addresses an extension of the capacitated vehicle routing problem where customer demand is composed of two-dimensional weighted items (2L-CVRP). The objective consists in designing a set of trips minimizing the total transportation cost with a homogenous fleet of vehicles based on a depot node. Items in each vehicle trip must satisfy the two-dimensional orthogonal packing constraints. A GRASP×ELS algorithm is proposed to compute solutions of a simpler problem in which the loading constraints are transformed into resource constrained project scheduling problem (RCPSP) constraints. We denote this relaxed problem RCPSP-CVRP. The optimization framework deals with RCPSP-CVRP and lastly RCPSP-CVRP solutions are transformed into 2L-CVRP solutions by solving a dedicated packing problem. The effectiveness of our approach is demonstrated through computational experiments including both classical CVRP and 2L-CVRP instances. Numerical experiments show that the GRASP×ELS approach outperforms all previously published methods.     

Skewed general variable neighborhood search for the cumulative capacitated vehicle routing problem

The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new version of the classical capacitated vehicle routing problem, and it is equivalent to a traveling repairman problem with capacity constraints and a homogeneous vehicle fleet, which aims to minimize the total arrival time at customers. Many real‐world applications can be modeled by this problem, such as the important application resulting from the humanitarian aid following a natural disaster. In this paper, two heuristics are proposed. The first one is a constructive heuristic to generate an initial solution and the second is the skewed variable neighborhood search (SVNS) heuristic. The SVNS algorithm starts with the initial solution. At each iteration, the perturbation phase and the local search phase are used to improve the solution of the CCVRP, and the distance function in acceptance criteria phase is used to improve the exploration of faraway valleys. This algorithm is applied to a set of benchmarks, and the comparison results show that the proposed algorithms provide better solutions than those reported in the previous literature on memetic algorithms and adaptive large neighborhood search heuristics.     

An efficient variable neighborhood search heuristic for very large scale vehicle routing problems

In this paper, we present an efficient variable neighborhood search heuristic for the capacitated vehicle routing problem. The objective is to design least cost routes for a fleet of identically capacitated vehicles to service geographically scattered customers with known demands. The variable neighborhood search procedure is used to guide a set of standard improvement heuristics. In addition, a strategy reminiscent of the guided local search metaheuristic is used to help escape local minima. The developed solution method is specifically aimed at solving very large scale real-life vehicle routing problems. To speed up the method and cut down memory usage, new implementation concepts are used. Computational experiments on 32 existing large scale benchmarks, as well as on 20 new very large scale problem instances, demonstrate that the proposed method is fast, competitive and able to find high-quality solutions for problem instances with up to 20,000 customers within reasonable CPU times.     

Active guided evolution strategies for large-scale vehicle routing problems with time windows

We present a new and effective metaheuristic algorithm, active guided evolution strategies, for the vehicle routing problem with time windows. The algorithm combines the strengths of the well-known guided local search and evolution strategies metaheuristics into an iterative two-stage procedure. More precisely, guided local search is used to regulate a composite local search in the first stage and the neighborhood of the evolution strategies algorithm in the second stage. The vehicle routing problem with time windows is a classical problem in operations research, where the objective is to design least cost routes for a fleet of identical capacitated vehicles to service geographically scattered customers within pre-specified time windows. The presented algorithm is specifically designed for large-scale problems. The computational experiments were carried out on an extended set of 302 benchmark problems. The results demonstrate that the suggested method is highly competitive, providing the best-known solutions to 86% of all test instances within reasonable computing times. The power of the algorithm is confirmed by the results obtained on 23 capacitated vehicle routing problems from the literature.     

Location arc routing problem with inventory constraints

Dust suppression of hauling roads in open pit mines is done by periodically spraying water from a water truck. The objective of this paper is to present and compare two methods for locating water depots along the road network so that penalty costs for the lack of humidity in roads and routing costs are minimized. Because the demands are located on the arcs of the network and the arcs require service more than once in a time horizon, this problem belongs to the periodic capacitated arc routing domain. We compare two methods for finding the initial depot location. We then use an exchange algorithm to modify the initial location and an adaptive large neighborhood search algorithm to modify the initial routing of vehicles. This method is the first one used for depot location in periodic arc routing problems.     

A deterministic tabu search algorithm for the capacitated arc routing problem

The capacitated arc routing problem (CARP) is a difficult optimisation problem in vehicle routing with applications where a service must be provided by a set of vehicles on specified roads. A heuristic algorithm based on tabu search is proposed and tested on various sets of benchmark instances. The computational results show that the proposed algorithm produces high quality results within a reasonable computing time. Some new best solutions are reported for a set of test problems used in the literature.     

OVRP_GELS: solving open vehicle routing problem using the gravitational emulation local search algorithm

In open vehicle routing problem (OVRP), after delivering service to the last customer, the vehicle does not necessarily return to the initial depot. This type of problem originally defined about thirty years ago and still is an open issue. In real life, the OVRP is similar to the delivering newspapers and consignments. The problem of service delivering to a set of customers is a particular open VRP with an identical fleet for transporting vehicles that do not necessarily return to the initial depot. Contractors which are not the employee of the delivery company use their own vehicles and do not return to the depot. Solving the OVRP means to optimize the number of vehicles, the traveling distance and the traveling time of a vehicle. In time, several algorithms such as tabu search, deterministic annealing and neighborhood search were used for solving the OVRP. In this paper, a new combinatorial algorithm named OVRP_GELS based on gravitational emulation local search algorithm for solving the OVRP is proposed. We also used record-to-record algorithm to improve the results of the GELS. Several numerical experiments show a good performance of the proposed method for solving the OVRP when compared with existing techniques.

     

多中心联合配送模式下集货需求随机的VRPSDP问题

针对多中心联合配送模式下集货需求随机的同时配集货车辆路径问题(MDVRPSDDSPJD), 构建了两阶段MDVRPSDDSPJD模型. 预优化阶段基于随机机会约束机制以及车载量约束为客户分配车辆, 生成预优化方案; 重优化阶段采用失败点重优化策略对服务失败点重新规划路径. 根据问题特征, 设计了自适应变邻域文化基因算法(Adaptive memetic algorithm and variable neighborhood search, AMAVNS), 针对文化基因算法易早熟、局部搜索能力弱等缺陷, 将变邻域搜索算法的深度搜索能力运用到文化基因算法的局部搜索策略中, 增强算法的局部搜索能力; 提出自适应邻域搜索次数策略和自适应劣解接受机制平衡种群进化所需的广度和深度. 通过多组算例验证了提出模型及算法的有效性. 研究成果不仅深化和拓展了VRP (Vehicle routing problem)相关理论研究, 也为物流企业制定车辆调度计划提供一种科学合理的方法.