模糊需求与时间窗的车辆路径问题及混合遗传算法求解

针对带模糊需求与模糊时间窗的车辆路径问题,以总行驶距离、车辆使用数最小化,以及平均客户满意度最大化为目标,构建基于可信性测度理论的多目标模糊机会约束模型。为提高种群的多样性,改进了交叉算子,在引入局部优化算法及擂台法则的基础上,设计了适合求解多目标车辆路径问题的混合遗传算法。通过VRPTW标准算例实验,表明算法能够有效地求解带时间窗的车辆路径问题,以及模型的合理性,同时显示了决策者偏好值对决策目标的影响。研究成果可为求解带模糊需求与时间窗的车辆路径问题提供一种思路,也可为实际配送路径规划提供指导。     

一个求解带有时间窗口约束的车辆路径问题的启发式算法

对适用于旅行商问题的最近距离搜索启发式算法进行修正,构造出评价函数,并依此提出一个求解有时间窗约束的车辆路径问题的启发式算法。求解具体算例表明,此算法是有效的。     

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

针对目前蚁群算法在求解有时间窗的车辆路径问题上存在的缺陷,提出一种搜索效率较高的混合蚁群算法,阐述了混合蚁群算法的基本原理,给出了求解有时间窗的车辆路径问题的具体步骤.计算机实验结果表明,混合蚁群算法在求解有时间窗的车辆路径问题上是有效的.     

随机递归算法求解车辆路径问题

车辆路径问题(VRP)是组合优化中一个典型的NP难题,对于中等规模以上的问题,目前大多采用禁忌搜索、遗传算法和模拟退火等亚启发式算法,在吸取这些算法精髓的基础上,提出了一种新的并且简洁而高效的启发式算法.计算结果表明,在27个国际标准算例中应用该算法取得了2个解优于当前最优解,其余相当接近当前最优解.需要指出的是所有这些结果是在该算法应用同一组参数得到的.     

带时间窗的开放式满载车辆路径问题建模及其求解算法

为满足某些企业的满载运输需求, 针对运输任务对车辆具有独占性的特点, 分析得到总运输费用的大小取决于车辆的空车运行费用, 在此基础上, 将带时间窗的开放式满载车辆路径问题转化为带时间窗的多车场开放式车辆路径问题, 建立了相应的数学模型, 并设计了改进的自适应遗传算法进行开环路径求解, 并把算法应用于某木材厂的周运输计划的制定, 算法在很短时间内求得了运输方案, 比木材厂原运输方案减少了车辆数, 并节省了运输费用. 实验证明, 算法是可行和有效的.     

求解带软时间窗的车辆路径问题的改进遗传算法

带软时让窗的车辆路径问题(VRPSTW)是在基本的车辆路径问题(VRP)上增加了时间窗约束条件的一种更化形式，是一个典型的NP-难问题。通过引用一种新的编码方法、交叉和变异概率的自适应机制，构造一个改进的遗传算法来求解VRPSTW，并将求解结果与其他遗传算法比较。比较结果显示，该算法具有较好的性能。     

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

随机旅行时间的车辆路径问题在实际中经常会出现，然而由于问题本身的难度以及人们重视不足，目前对该问题的研究还很少．文章在Laporte等的研究基础上，提出了一个考虑车辆容量的机会约束模型，并构造了求解该模型的遗传算法．     

两阶段启发式算法求解带时间窗的多中心车辆路径问题

车辆路径问题(VRP)是物流研究领域中一个具有重要理论价值和现实意义的问题. 带时间窗的多中心车辆路径优化问题(MDVRPTW)是单中心带时间窗的VRP(VRPTW)的一个扩展, 其非常复杂, 难于求解. 本文提出一个两阶段的启发式算法来求解MDVRPTW. 该算法首先通过基于聚集度的启发式分类算法将MDVRPTW简化为多个VRPTW; 然后采用蚁群算法对每个VRPTW进行求解. 为了提高蚁群算法的效率, 提出了两个改进策略: 交叉算子和自适应的ant-weight信息素增量更新策略. 最后, 通过若干经典的MDVRPTW对该算法进行了验证, 结果显示结合基于聚集度的启发式分类算法和改进的蚁群算法是一个求解MDVRPTW的有力工具.     

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

针对带时间窗车辆路径问题（vehicle routing problem with time windows, VRPTW）, 提出了混合种群增量学习算法（hybrid population-based incremental learning algorithm, HPBIL）, 用于同时最小化车辆数和总行驶距离. 在HPBIL中, 通过改进标准的PBIL概率模型以提高算法的全局探索能力, 同时设计了基于插入法和两点邻域交换法的两阶段局部搜索来增强算法的局部开发能力. 仿真实验和算法比较验证了HPBIL的有效性和鲁棒性.     

模糊需求信息条件下的车辆路径问题研究

在对模糊需求信息条件下的车辆路径问题进行简单描述的基础上，通过引入决策者主观偏好的概念，提出了解决该问题的一种基于模糊可能性的混合遗传算法．同时，在最小化车辆使用数与车辆行驶距离的目标下，通过随机模拟方法研究了决策者的主观偏好对最终决策目标的影响作用，并通过与其它计算方法的比较证明了基于模糊可能性的混合遗传算法的优越性．     

车辆路径问题(VRP)的蚂蚁搜索算法

车辆路径问题(vehicle routing problem，VRP)是组合优化中一个典型的NP难题，理论上，目前仅能保证一些相对小规模的问题可求得最优解．基于近些年出现的新型智能优化思想：人工蚂蚁系统，给出了一种可快速求解VRP的蚂蚁搜索算法．通过定义基本的人工蚂蚁状态转移概率，并结合局部搜索策略，用迭代次数控制算法的运行时间，从而使该方法具有实用意义和可操作性．经一系列数据测试和验证，并与若干已有的经典算法相比较．获得了较好的结果．     

多车型电动汽车车辆路径问题的分支定价算法研究

随着环境意识的日益提升和电动汽车的逐渐普及,考虑到物流企业中不同类型的电动汽车的电池最大容量、电池充电率、电量单位消耗率、最大载重量、固定成本和可变成本不同,本文研究含时间窗的多车型电动汽车车辆路径问题,建立了一个混合整数规划模型,并利用分支定价算法求其最优解.为了加快算法的求解速度,本文提出生成下界值的方法以对车辆类型进行预处理操作,并制定了生成整数解上界的策略以压缩解空间.然后,通过用多组算例验证了模型和算法结果的准确性,同时也证明了本文提出的加速过程能有效地提高算法的求解速率.最后,通过不同规模的算例分析了车辆可变成本的变化对结果的影响.     

有能力约束车辆路径问题的量子进化算法

针对有能力约束车辆路径问题,构造一种具有量子旋转门和灾变操作的量子进化算法.算法采用0-1矩阵编码方式, 通过量子旋转门实现进化,引入灾变操作保证解空间的多样性,采用最邻近插入法结合2-Opt法再优化线路内次序.选取基准实例进行实验仿真, 通过与文献中其它算法进行性能比较,表明文中提出的量子进化算法是一个有效求解有能力约束车辆问题的方法.     

装卸混合车辆路径问题的模拟退火算法研究

提出了更具一般性的装卸混合车辆路径问题，建立了该问题的基于直观描述的数学模型．通过设计一种新的解的表示方法构造了求解该问题的模拟退火算法，并进行了实验计算．计算结果表明，用设计的模拟退火算法求解装卸混合车辆路径问题，不仅可以取得很好的计算结果，而且计算效率较高，收敛速度较快，计算结果也较稳定．通过对双向配送策略与单向配送策略计算结果的比较，说明了采用双向配送策略求解装卸混合车辆路径问题对于配送企业节省配送车辆、减少配送里程，从而降低配送成本、提高经济效益的重要意义．     

带时间窗车辆路径问题的量子蚁群算法

带时间窗的车辆路径问题(VRPTW)是VRP的一种重要扩展类型, 是组合优化中的一个NP难题, 针对蚁群算法在求解VRPTW问题时易陷入局部最优和收敛速度慢的问题, 本文结合量子计算提出一种求解VRPTW的量子蚁群算法(QACA). 通过定义人工蚂蚁的转移概率, 增加量子比特启发式因子, 以及用量子旋转门实现信息素更新, 从而提高算法的全局搜索能力, 有效避免了算法陷入局部最优. 经一系列VRPTW的仿真实验表明, 量子蚁群算法较蚁群算法在求解VRPTW问题上具有更好的性能, 通过与其他算法的比较, 进一步说明量子蚁群算法是可行有效的.     

车辆路径问题的改进分支切割法

对容量约束车辆路径问题建立了数学模型并提出了一种改进的分支切割算法.算法结合启发式规则, 采用梳子不等式和连接不等式产生切割面,设置参数控制分支客户组合的大小和分支方向,通过不断调整问题下界来删除多余节点. 提出了切割面更新策略,设置切割面利用系数和切割面库, 通过动态更新来淘汰利用率低的切割面,保存利用率高的切割面. 采用多组CVRP算例进行计算,并与其它算法优化CVRP的实验结果作了比较, 对运算结果进行了分析,给出了推荐的参数取值方案,说明了提出的分支切割算法对容量约束车辆路径问题的有效性.     

分散搜索算法求解带货物权重的车辆路径问题

研究了由一个分销中心、多个零售商组成的分销网络中运输单产品考虑货物权重的车辆路径问题(weighted vehicle routing problem,WVRP).问题的目标是设计合理的路线最小化由于行驶距离,运输载重量及使用车辆而产生的总费用.针对问题的特点,设计了求解WVRP问题的分散搜索算法(scatter search algo-rithm,SS),该算法基于客户进行编码,以基于最优划分过程的随机初始化作为多样性产生方法,通过对不同解包括的弧组合来生成新解,并用最近邻法对解进行改进.分别采用了随机数据与标准数据对算法进行测试,并与其他求解该问题的算法进行了比较,说明了算法的有效性.     

一类随机需求VRP的混合粒子群算法研究

针对一类随机需求车辆路径问题(stochastic vehicle routing problem,SVRP),结合现实生活中长期客户服务记录所隐含的统计性知识构建新的统计学模型,并将种群搜索与轨迹搜索算法相结合提出了一种新的混合粒子群优化算法。该算法通过引入导引式局部搜索,来减小粒子群搜索陷入局优的可能性以获得更优化解。仿真计算证明混合粒子群优化算法的有效性。同时,该算法也拓展了VRP的算法空间。     

求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法

模糊需求车辆路径问题(CVRPFD)是对带容量约束车辆路径问题(CVRP)的扩展,属于经典的NP难题,其求解与需求确定CVRP区别较大,较为复杂,具有很强的理论和现实意义.基于先预优化后重调度的思想,提出一种新的两阶段变邻域禁忌搜索算法(VNTS)对其求解:在预优化阶段,基于可信性理论构建模糊机会约束优化模型处理客户点模糊需求,设计VNTS求解预优化方案;在重调度阶段,设计随机模拟算法模拟客户点实际需求,提出一种新的点重调度策略对预优化方案进行调整.算例实验表明两阶段变邻域禁忌搜索算法是一种求解CVRPFD的有力工具,点重调度策略调整效果较佳.