车辆路径问题的禁忌搜索算法研究

论文在对车辆路径问题进行简单描述的基础上,通过设计一种新的解的表示方法构造了求解该问题的一种新的禁忌搜索算法,并进行了实验计算。计算结果表明,用本文设计的禁忌搜索算法求解车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定。     

一类随机动态车辆路径问题的策略分析

动态车辆路径问题是物流学中的一个重要研究领域.本文根据组合优化、排队论和几何概率方面的知识,分析了需求密集情况下的一类随机动态车辆路径问题的下界,并研究了一种运作策略的渐近性.     

大规模邻域搜索算法求解时变车辆调度问题

对时变网络车辆调度问题提出一种满足先入先出准则的时变处理方法,并建立相应的数学模型,提出一种基于大规模邻域搜索技术的智能优化算法进行求解,算法顶层采用动态规划算法搜索环状交换邻域以得到每辆车的最佳服务顾客集合;底层设计动态搜索算法用以安排每辆车的最佳服务路线.在此基础上提出顶层加入虚拟顾客和底层嵌入insert两类改进策略.通过实验仿真比较,验证了所提算法的有效性.     

求解带时间窗的客户需求可分条件下的车辆路径问题

物流运输中的车辆路径问题历来是一个重要的理论和实际问题,在同时考虑客户需求可分以及客户方和配送中心时间窗限制的前提下,重新构造了问题模型,并结合蚂蚁算法中转移概率的改进和最大-最小蚂蚁系统,设计了问题求解过程和分割点选取规则,计算结果显示出算法的可行性。另外还与客户需求不可分的情况进行了对比,从而说明在大规模物流运输需求下,可分能带来更好的效果。     

车辆路径问题的模型及算法研究综述

本文在文献[1,2,3,4]的基础上,首先,介绍了车辆路径问题的分类和限制条件;然后,全面综述了国内外关于车辆路径问题的模型及算法研究现状,重点探讨了车辆路径问题的模型构造、求解算法及其适用范围;最后,展望了其研究的前景。     

动态车辆路径问题排队模型分析

分析了一类动态车辆路径问题,其中顾客需求以泊松流形式出现,现场服务时间服从一般分布.提出解决该问题的两种策略:顺序服务策略和中点改进策略,利用排队论、几何概率论等领域的知识分别求出了这两种策略的系统时间,并通过仿真数据实验验证了这两种策略的有效性.     

顾客时间窗变化的多车场车辆调度干扰管理模型研究

为解决物流配送过程中某顾客时间窗变化而导致的物流配送难以按照原计划实现的难题,运用干扰管理方法,针对多车场带时间窗的物流配送车辆路径问题,提出包含顾客配送时间总偏离度、配送总成本、新路径方案与初始路径计划偏差量、最长行驶时间违反总量4个因素的扰动程度度量方法;以顾客时间窗变化这类干扰事件发生时的问题状态为基础,以系统整体扰动最小化为目标,建立问题的目标规划数学模型;针对这一复杂模型,提出基于特定邻域结构及其寻优概率的变邻域搜索算法;最后在标准算例上使用变邻域搜索算法与其他文献算法进行比较分析,结果表明该变邻域搜索算法对于干扰事件发生后的车辆路线重排结果在系统整体扰动程度方面明显优于其他文献的算法.     

碳排放影响下的动态配送车辆路径优化研究

本文考虑碳排放对动态配送车辆路径的影响,研究了客户需求点增减、客户需求量变化及配送路线交通中断三种情形下的配送车辆路径优化问题。首先,通过构建虚拟客户点,将动态车辆路径优化问题转化为静态车辆路径优化问题。其次,构建了基于改进遗传算法的动态车辆路径优化模型。最后,对比分析了考虑碳排放影响前后的动态车辆路径优化。研究结果表明：在满足时间窗要求的情况下,虽然考虑碳排放的动态车辆路径的总行驶距离增加了3.59 km,但碳排放成本和总配送成本分别下降了7.45%和1%;同时与静态车辆路径相比,在动态车辆路径问题中考虑碳排放可以使碳排放成本及总配送成本下降的更多,因此在动态车辆路径问题中考虑碳排放更具有价值意义。     

多车场带时间窗车辆路径问题的变邻域搜索算法

多车场带时间窗车辆路径问题是车辆路径问题集合中的一个极为复杂、且仍未得到较好解决的问题。针对这一问题,建立了它的整数规划数学模型,提出了一种改进型变邻域搜索算法。该算法在初始解的构造阶段采用聚类方法完成客户的分配,运用混合算子进行局部搜索,通过后优化过程增强寻优效果,引入模拟退火模型对新解的接受进行控制。最后,在Cordeau提出的标准用例上对改进型变邻域算法进行了实验,实验结果更新了大部分目前该问题的最优解,并在算法的稳定性和求解时间上体现出一定优势。实验表明,该算法是一种求解多车场带时间窗车辆路径问题的有效方法。     

低碳环境下的车辆路径问题及禁忌搜索算法研究

基于节能减排的新视角,本文研究了低碳环境下由第三方提供运输服务的车辆路径问题,在安排车辆路径时,同时考虑了能耗、碳排放和租车费用,而这些费用不仅与距离有关,也与客户点的需求量和车辆速度有关。提出了考虑车辆运量和速度的能耗计算方法,建立了非满载运输方式下的低碳路径模型——LCRP。设计了基于路径划分的禁忌搜索算法RS-TS对问题进行求解,该算法引入了一种新颖的路径编码与解码算法WSS,采用了三种邻域搜索方法。通过基准测试实例验证了算法能有效地找到满意解,并揭示了距离、能耗、行驶时间等参数之间的关系,实验分析表明采用低碳路径安排更加经济环保且选择中低的交通速度更有利于节约能耗和降低碳排放。     

Ant Colony System for a Dynamic Vehicle Routing Problem

An aboundant literature on vehicle routing problems is available. However, most of the work deals with static problems, where all data are known in advance, i.e. before the optimization has started. The technological advances of the last few years give rise to a new class of problems, namely the dynamic vehicle routing problems, where new orders are received as time progresses and must be dynamically incorporated into an evolving schedule. In this paper a dynamic vehicle routing problem is examined and a solving strategy, based on the Ant Colony System paradigm, is proposed. Some new public domain benchmark problems are defined, and the algorithm we propose is tested on them. Finally, the method we present is applied to a realistic case study, set up in the city of Lugano (Switzerland).     

基于需求预测的两级动态配送路径优化研究

针对传统响应式配送难以应对海量动态客户需求的困境,在此提出基于需求预测的两级动态配送路径优化方法。利用历史数据从需求预测、需求聚类和需求配额三个维度,处理电商物流配送过程中的动态需求;建立基于需求预测的单阶段和多阶段两级车辆配送路径优化模型,并针对问题特性利用分支定界算法与CW-禁忌搜索算法生成两个阶段的最优配送路径。最后结合实验案例对模型与算法的有效性进行验证,试验结果表明本文设计方法具有较好的动态场景适应度和客户响应能力。     

A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, ), which is an improvement over the existing 1.5-approximation.     

随机旅行时间局内车辆路径问题的模型及其算法

人们在生活中会经常遇到随机旅行时间的局内车辆路径问题,如现实物流配送中的交通堵塞现象.文章在Laporte等的研究基础上,提出了一个考虑堵塞点动态产生、一个个遇到,堵塞时间为随机变量的模型,并构造了求解该模型的算法.     

有时间窗车辆路径问题的模型及其改进模拟退火算法研究

论文在对有时间窗车辆路径问题进行描述的基础上,建立了该问题的基于直观描述的数学模型.论文还根据有时间窗车辆路径问题的特点构造了求解该问题的改进模拟退火算法,并进行了实验计算.计算结果表明,用本文设计的改进模拟退火算法求解有时间窗车辆路径问题,不仅可以取得很好的计算结果,而且算法的计算效率较高,收敛速度较快,计算结果也较稳定.     

考虑区域限制的卡车搭载无人机车辆路径问题研究

无人机参与配送是解决末端物流难题的重要途径之一。卡车搭载无人机协同配送模式,克服了无人机载重量小、续航时间短的弊端,成为无人机参与末端物流配送的重要形式之一。在疫区、灾区进行应急配送时,经常遇到由于道路毁坏或封锁、区域污染,导致部分路段车辆或无人机无法通行的情况。在非应急配送中,也可能存在车辆限行和空域禁飞等区域限制措施。区域限制给卡车搭载无人机物流配送路径优化问题带来了很大挑战。论文构建了区域限制条件下卡车搭载无人机车辆路径问题的混合整数线性规划模型,提出了一种结合最短路算法和禁忌搜索算法的混合算法,基于标准算例库设计测试集并进行测试实验,实验结果表明混合算法具有较好的计算性能。     

考虑三维装箱约束的车辆路径问题研究

针对实际物流配送问题的特点,建立考虑三维装箱约束的车辆路径问题模型,提出求解该问题的引导式局部搜索算法。采用改进的模糊遗传算法求解车辆路径问题,提出一种新的模糊逻辑控制器,并采用引导式局部搜索算法求解三维装箱问题。通过计算标准算例检验算法性能,试验结果表明引导式局部搜索算法能够在较短时间内得到质量较高的近似最优解。     

车辆路径问题的三阶段求解方法研究

针对由车辆路径问题规模的增大带采求解空间组合爆炸这一难点,从缩减解答空间入手,以节省求解时空为突破口,综合运用知识工程、模糊聚类分析、状态空间搜索理论和运筹学整数规划理论,提出一种求解车辆路径问题的三阶段求解方法.第一阶段分析物流配送过程的主要影响因素,根据相关因素对客户进行初步划分,然后采用模糊聚类分析方法将各配送区域中的客户进行细分;第二阶段采用带控制策略的深度优先搜索算法生成备选的车辆路径方案集合;第三阶段建立整数规划求解模型,并根据邻域规则将求得的解映射为实际问题中的行车方案.最后运用算例验证上述方法的有效性.