随机需求多车辆路径问题的重优化算法

针对随机需求的多车辆路径问题(MVRPSD),提出了一种简单有效的重优化新算法.该算法先用预优化策略给出一个预优化的单车辆路径,然后重复使用rollout算法对该路径进行进一步优化,将其划分为满足约束条件的多条子路径,不仅能满足实际需求,而且极大提高了优化性能.与现行方法对比实验结果表明,本算法可以对多车辆路径更为合理的优化,明显减少行驶费用,是求解随机需求的多车辆路径问题的一种有效算法.     

路径长度受限的随机需求VRP的两阶段模拟退火方法

路径长度受限的随机需求下的车辆路径问题(PSVRP)是一种普遍存在而求解困难的运筹学问题.在满足路径长度限制、只允许服务失败一次和不允许部分服务的策略下设计了一个两阶段模拟退火算法,根据模拟退火的理论容易知道算法求到的近似最优解是以概率1收敛的.对随机生成的中等规模和大规模问题做了数值试验,试验结果表明该算法有效.     

多中心半开放式同时送取货的车辆路径问题研究

研究了带软时间窗约束的多配送中心半开放式同时送取货的车辆路径问题,所有客户点均存在送取两种需求,并采用同一辆车同时提供送取服务.车辆服务完路线上所有客户点后,不一定返回起始配送中心,可就近返回任意配送中心.在此条件下,构建了以车辆运输成本、车辆租赁成本、时间窗惩罚成本等总和最小为目标的优化模型.根据问题特征,设计了自适应精英遗传算法对该问题进行求解,引入自适应机制,根据个体的适应度动态地调节交叉和变异概率,采用精英保留策略将优秀个体进行遗传保留,不仅增强了算法的全局优化能力,还均衡了算法的局部搜索能力.通过案例仿真,验证了模型和算法的可行性和有效性.研究成果丰富了车辆路径问题的相关研究,为物流企业提供了一种决策参考.     

路径长度受限的随机需求VRP的模型和算法

路径长度受限的随机需求VRP在生产、生活中有着广泛的应用。给出了路径长度受限的随机需求VRP问题的线性整数规划模型,在不允许部分服务和仅能服务失败一次的策略下设计了一个启发式算法。该算法以离散优化中广泛应用的扫描算法为基础生成服务的一个初始可行方案,然后利用模拟退火算法改进得到近似最优解。对需求为二项分布的50个结点、1个服务中心的问题进行了数值试验,数值结果表明该算法对求解路径长度受限的随机需求VRP是有效的。     

求解集送货可拆分车辆路径问题的启发式算法

为了节约运输成本、提高物流服务效率,对集送货可拆分的车辆路径问题进行了研究.该问题允许一个任务点被访问多次,也允许同一车辆访问同一任务点多于一次.针对问题的特点设计三阶段启发式算法,拆分部分任务点的集送货需求,并使车辆行驶距离之和最小.数值实验结果表明,新的算法可以得到合理的车辆路径,尤其适用于送货需求总量大于集货需求总量的情形.     

基于GIS与约束条件下的最优路径规划研究

根据无人地面车辆自主导航的需求,提出一种给定任务点的约束条件下的最优路径实现方法. 首先基于地理信息系统（GIS）平台构建为车辆行驶提供先验信息的GIS数据库,并设计研究基于计算几何的路段匹配算法,同时结合A*算法进行全局路径规划. 然后根据无人地面车辆的运动特性和对路口识别的需求提出了新的路口模型,同时为保证无人地面车辆行驶轨迹的平滑性和对路口识别的精确性,对路口轨迹和U-turn轨迹进行了算法设计. 最后提出了动态重规划的行驶策略. 实际跑车实验证明了该设计算法的有效性.      

随机需求车辆路径问题的禁忌搜索算法研究

研究了随机需求车辆路径问题,并将禁忌搜索算法用于解决该问题.实验结果证明,禁忌搜索算法可以有效地求得随机需求车辆路径问题的优化解,是求解随机需求车辆路径问题的一个较好方案.     

考虑时空相关随机行驶时间的车辆路径问题模型与算法

本文对一类在真实道路网络中考虑时空相关的随机行驶时间的车辆路径问题进行了研究. 首先我们建立了该问题的两阶段随机规划模型. 然后我们将用于候选解寻优的智能优化算法与用于产生评价解的随机场景的情景生成技术相结合,提出一种智能随机优化方法求解该问题. 为了有效地进行解的寻优,本文结合可变邻域下降算法提出了一种混合粒子群优化算法.最后通过一系列基于北京市区道路网络的算例实验,我们验证了所提出的混合粒子群优化算法的有效性.实验结果还表明,考虑实际交通环境中道路网络上车辆行驶时间的时空相关性,会影响最优车辆路径决策方案.     

退火单亲遗传算法求解随机需求VRP问题

为了有效求解随机需求的车辆路径问题,在单亲遗传算法中加入模拟退火选择操作,构建了退火单亲遗传算法;并实现了以虚拟自然数代表中心点,可直接利用求解随机需求VRP问题的有效遗传算子。在选择操作中,采用三复本锦标选择的方式,保持了种群的多样性。计算结果表明,该方法可有效求解随机需求车辆路径问题,算法的搜索效率、收敛概率均得到大幅度提高,取得了比一般遗传算法更优的结果。     

基于顾客时间满意度的车辆路径问题

考虑到普通带时间窗约束的车辆路径问题(vehicle routing problem with time windows,VRPTW)模型不能真正反映顾客对时间的偏好,故在车辆路径优化模型的基础上,结合顾客时间满意度函数,同时放松需求点经过即被服务的约束限制,允许多次经过同一需求点的情况发生,而需求点只能被同一辆车服务一次,建立了基于顾客时间满意度的车辆配送(vehicle routing problem with satisfaction,VRPWS)模型,并利用模拟退火算法编程求解.为验证VRPWS模型的有效性进行了数值实验.实验结果表明:与传统的带软时间窗约束的车辆路径优化(vehicle routing problems with soft time window,VRPSTW)模型和VRPTW相比,VRPWS模型配送效益提升了170.0%和3.2%.分析结果表明该工作在一定程度上有助于物流企业在配送过程中提高顾客满意度和降低运输成本.