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

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

基于粒子群优化的有反向物流的车辆路径问题

在对具有时间窗、考虑反向物流的车辆路径问题进行简单描述的基础上,基于最小费用的角度构建了该问题的多目标数学模型.该决策模型综合考虑了正向和反向物流,有助于提高车辆的装载率.针对该问题提出了一种改进的粒子群算法,并用计算机进行实现,并获得很好的效果.     

混合变邻域搜索算法求解大规模电动车辆路径优化问题

基于真实的物流场景,研究了带时间窗的多车型和多循环电动车辆路径问题。建立了一个基于路径的混合整数线性规划模型,可精确求解小规模算例。提出了将变邻域搜索算法和标签算法相结合的混合启发式算法,用以求解大规模情形。该算法提出了一种带随机因子的启发式算法构造初始解,并对时间窗和里程约束进行了松弛,使用邻域算子进行变邻域搜索,使用标签算法精确求解了固定商户配送顺序下的路径最优充电决策问题。测试结果表明：混合变邻域搜索算法可在极短时间内找到最优解,能大幅度降低物流成本。     

求解多车型车辆路径问题的变邻域搜索算法

多车型车辆路径问题（FSMVRP）是车辆类型不同的车辆路径问题（VRP）,基于变邻域搜索,提出一种启发式算法VNS_FSM求解FSMVRP。该算法设计了实现变邻域搜索中的＂抖动＂和局部优化过程的邻域结构组合,同时,还提出了一种新的车型调整策略。在通用的基准测试问题的实验验证了VNS_FSM算法的有效性,并给出问题G_07-G_12的正确解。实验结果表明,VNS_FSM算法能够获得大多数测试问题的已知最好解。与已有算法相比,VNS_FSM算法性能相当或更优。     

时间依赖型多时间窗车辆路径问题研究

针对一类考虑城市交通拥堵情况的时间依赖型多时间窗车辆路径问题(time-dependent vehicle routing problem with multiple time windows,TD_VRPMTW),提出一种混合离散灰狼算法(hybrid discrete grey wolf optimizer,HDGWO)进行求解。在HDGWO中,设计了新的灰狼个体更新公式,采用基于客户排列的整数编码方式,使算法可直接在离散问题解空间中执行基于标准灰狼算法个体更新机理的全局搜索;设计了基于问题性质的种群初始化策略,用于生成具有高质量和多样性的初始种群;引入头狼信息交流公式,用于探索头狼形成的优质解空间;构造具有多种局部搜索操作的自适应变邻域局部搜索策略,用于增强算法的局部搜索能力。结果表明：HDGWO可有效求解TD_VRPMTW。     

基于碳排放与速度优化的带时间窗车辆路径问题

研究了考虑碳排放和速度优化的带时间窗车辆路径问题,引入了基于速度的碳排放计算方法,以油耗、碳排旅行时间费用最小化为目标,将速度作为决策变量,建立了混合整数规划模型. 提出了两阶段启发式算法,第一阶段采用改进的禁忌搜索算法优化配送网络中的速度,第二阶段设计了弧段速度优化算法用于优化路径弧段上的速寻求对最优解的进一步改进. 数值实验分析表明: ①两阶段启发式算法能快速有效地找到满意解; ②采用优度的路径安排比固定速度的路径安排能减少更多的碳排放和总费用; ③碳排放和旅行时间之间存在替换关系,减少碳排放会导致旅行时间的增加; ④传统的车辆路径安排中存在很大的碳排放改进空间,由于油耗和碳排放是相关的,减少碳排放有利于节约总费用.     

多时间窗车辆调度问题的建模与求解

传统的单时间窗车辆调度问题模型无法描述用户空闲时间分段可选的情况,为此需要建立多时间窗车辆调度问题模型.对多时间窗车辆调度问题进行研究,建立了问题的数学模型,并基于模拟退火算法设计了一种两阶段启发式算法进行求解.该算法首先利用扫描算法求得初始解,然后利用模拟退火算法对初始解进行改进.实验结果表明该算法可以有效地求解多时间窗车辆调度问题.     

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

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

车辆路径问题的粒子群算法研究

车辆路径优化问题是一类具有重要实用价值的组合NP问题．粒子群算法(panicle swarm optimization)是一种新出现的群智能(swarm intellingece)优化方法，将其应用于车辆路径优化问题，构造车辆路径问题的粒子表达方法，建立了此问题的粒子群算法，并与遗传算法作了对比试验．结果表明，粒子群算法可以快速、有效求得车辆路径问题的优化解，是求解车辆路径问题的一个较好方案。     

开放式车辆路径问题的蚁群优化算法

研究了开放式车辆路径问题,该问题中车辆在服务完最后一个顾客点后不需要回到车场,若要求回到车场,则必须沿原路返回.提出了一种混合蚁群优化算法,该算法主体是一个在超立方框架下执行的MAX-MIN蚂蚁系统,算法混合了禁忌搜索算法作为局部优化算法,同时算法集成了一个后优化过程来进一步优化最优解.基于标准测试问题,最后给出了算法同文献中其它算法的性能比较结果,计算结果表明本文提出的算法是一个有效的求解开放式车辆路径问题的方法.     

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

将粒子群算法(PSO)应用于带时间窗车辆路径优化问题(VRPTW),构造车辆路径问题的粒子表达方法,建立了此问题的粒子群算法,并与遗传算法作了比较.实验结果表明,粒子群算法可以快速、有效求得带时间窗车辆路径问题的优化解,是求解带时间窗车辆路径问题的一个较好方案.     

求解非线性双层规划问题的混合变邻域粒子群算法

针对非线性双层规划难以获得全局最优的问题,汲取粒子群算法的快速搜索能力及变邻域搜索算法的全局搜索优势,提出了求解非线性双层规划问题的混合变邻域粒子群算法.首先利用Kuhn-Tucker条件,将非线性双层规划转化为一个单层规划问题,然后由粒子群算法得到一个较优的群体,通过审敛因子判断陷入局部最优的粒子,并进一步利用变邻域搜索算法的全局搜索能力对陷入局部最优的粒子进行优化,从而得到全局最优.测试函数的仿真实验对比分析证明了该算法的有效性.     

考虑工作量均衡的成品油二次配送车辆路径问题

为避免工作量分配不均,研究了考虑工作量均衡的成品油二次配送车辆路径问题。以总配送成本极小化和不同车辆路径长度之差极小化为目标,建立了双目标混合整数规划模型;并设计了变邻域禁忌搜索启发式算法。利用改进的Solomon＿I1插入算法求出使总配送成本尽量小的初始解;再利用变邻域禁忌搜索算法改进初始解,得到近似最优解。模拟计算结果显示,通过变邻域禁忌搜索算法改进后的解,总配送成本仅增加6.2%,车辆路径长度差值降低了45%,验证了算法的有效性。     

时变路网下考虑时空距离的同时配集货车辆路径优化

针对道路行驶速度时变且软时间窗条件下的同时配集货车辆路径问题,以车辆派遣成本、时间窗惩罚成本以及车辆运输成本之和最小化为目标建立路径优化模型。根据问题特征设计了考虑时空距离的混合变邻域搜索遗传算法,采用时空距离对客户进行聚类生成初始解,提高算法求解质量;将变邻域搜索算法的深度搜索能力运用到遗传算法的局部搜索策略中,增强算法的局部搜索能力;提出自适应邻域搜索次数策略以及模拟退火的新解接受机制,平衡种群进化所需的广度和深度。通过多组不同规模的算例验证了本文模型及算法的有效性,研究成果不仅深化和拓展同时配集货车辆路径问题的相关研究,也为物流企业优化车辆调度方案提供理论依据。     

存在车辆租赁及共享且有时间窗的多配送中心开环VRP

针对企业自身运力有限以及旗下多个配送中心在各决策周期运力不均衡的情况,提出了一类具有多个配送中心、需要进行车辆租赁和车辆共享、有时间窗限制、开环的VRP, 建立了相应的混合整数规划模型.通过引入一个虚拟配送中心,将多配送中心VRP 转化为单配送中心VRP, 并设计了一种结合扫描算法和C-W节约算法、对车辆路径和车辆调度统筹优化的混合遗传算法.最后,以重庆天友乳业物流分公司的业务数据对该模型的可行性和有效性进行了验证, 结果表明本文所提方法与该企业现有的配送方案相比,在配送总里程、配送总成本和车辆在途时间等方面均有明显改进.此外,进行了模型参数的灵敏度分析和算法的收敛性分析, 结果表明该算法具有较好的性能.     

不确定车辆数的有时间窗车辆路径问题的遗传算法

给出了不确定车辆数的有时间窗车辆路径问题(VRPTW)的数学模型,提出一种基于客户的编码表示方式,可以表示出不同的车辆数,实现VRPTW的路径长度和车辆数的同时优化,并用计算实例进行了验证,同时对计算中涉及的一些问题进行了讨论.