基于剩余装载能力的蚁群算法求解同时送取货车辆路径问题

建立了带车辆最大行程约束的同时送取货车辆路径问题的混合整数规划模型;采用了基于排序的蚂蚁系统和最大最小蚂蚁系统的信息素更新策略;设计了基于车辆剩余装载能力的启发信息策略,可在满足车辆负载的限制下,提高车辆的负载利用率;并在改进阶段使用了节点交换的局部搜索策略,以提高算法收敛速度.仿真结果表明本文算法能够在可接受的计算时间内得到满意解.

同时送取货车辆路径问题算法研究综述

针对同时送取货车辆路径问题的研究算法进行了评述。将该问题的求解方法分为精确算法、构造型启发式、现代启发式以及并行算法四个大类。从算法的原理、性能、适用环境,以及算法之间差异性等方面对各类算法进行了较为全面的介绍。最后,说明了VRPSDP算法研究在节点具有双重需求车辆路径问题理论研究方面的意义,并提出未来VRPSDP算法研究的两个发展方向,即适合多处理器上运行的并行现代启发式算法,以及有效的混合算法如量子行为粒子群算法。

混合优化算法求解同时送取货车辆路径问题

为了给各物流企业在车辆配送路径规划方面提供合理有效的决策支持,针对单配送中心的配送模式,研究带时间窗约束的同时送取货车辆路径问题(VRPSDPTW),建立以总配送成本最小化为目标的数学模型。根据模型的特征,提出基于模拟退火(SA)与自适应大规模邻域搜索(ALNS)相结合的混合优化算法(SA-ALNS)。采用基于时间与距离加权的插入启发式算法构造问题的初始解;引入多种删除、插入算子,以自适应选择策略进行路径优化,并通过反馈机制,逐渐调整各操作算子被选择的概率,使算法更倾向于选择寻优效果较好的算子;使用模拟退火机制的Metropolis准则控制解的更新。仿真实验中测试了56个大规模算例,对比了p-SA算法、DCS算法和VNS-BSTS等其他智能优化算法并进行统计分析,结果证明该算法在求解带时间窗约束的同时送取货车辆路径问题的可行性和优越性,研究成果极大丰富了车辆路径问题(VRP)的相关研究。

需求可分割的同时送取货车辆路径问题求解

针对企业生产原料调运过程,建立多品种货物且供需未匹配情况下需求可分割的大规模送取货车辆路径问题的数学模型,以运输成本最小化为目标。提出基于车辆运输效率的启发式算法构造初始解,并采用变邻域搜索算法对初始解进行改进。测算结果表明基于运输效率的启发式算法对实际运输费用降低20%左右,加入变邻域搜索算法后对初始解有3%左右的改进。

带时间窗的时间依赖型同时取送货车辆路径问题研究

针对带时间窗的时间依赖型同时取送货车辆路径问题(Time Dependent Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows,TDVRPSPDTW),本文建立以车辆固定成本、驾驶员成本、燃油消耗及碳排放成本之和为优化目标的数学模型;并在传统蚁群算法的基础上,利用节约启发式构造初始解初始化信息素,改进状态转移规则,引入局部搜索策略,提出一种带自适应大邻域搜索的混合蚁群算法(Ant Colony Optimization with Adaptive Large Neighborhood Search,ACO-ALNS)进行求解;最后,分别选取基准问题算例和改编生成TDVRPSPDTW算例进行实验。实验结果表明:本文提出的ACO-ALNS算法可有效解决TDVRPSPDTW的基准问题;相较于模拟退火算法和带局部搜索的蚁群算法,本文算法求解得到的总配送成本最优值平均分别改善7.56%和2.90%;另外,相比于仅考虑碳排放或配送时间的模型,本文所构建的模型综合多种因素,总配送成本平均分别降低4.38%和3.18%,可有效提高物流企业的经济效益。

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

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

面向多行程取送货车辆路径问题的混合NSGA-Ⅱ

针对多行程取送货车辆路径问题(VRP)收敛性与多样性相互制约的问题,提出一种融合自适应大邻域搜索(ALNS)算法和自适应邻域选择(ANS)的混合快速非支配排序遗传算法(NSGA-Ⅱ-ALNS-ANS)。首先,考虑初始解对算法收敛速度的影响,提出一种改进的后悔插入法以获得高质量初始解;其次,结合取送货问题特性,设计多组破坏和修复算子,以及多种邻域结构,提高算法的全局搜索能力和局部搜索能力;最后,设计基于随机采样的最佳拟合下降(BFD)算法与高效的可行解评价标准,生成路径分配方案。采用不同规模的标准公开算例进行仿真实验,与模因算法(MA)相比,所提算法的最优解质量提升了27%。实验结果表明,所提算法可快速得到满足多重约束的高质量车辆多行程路径分配方案,并在收敛性与多样性上优于对比算法。

深度强化学习Memetic算法求解取送货车辆路径问题

带时间窗约束的同时取送货车辆路径问题(VRPSPDTW)是NP难问题,属于约束较复杂的车辆路径问题,在现代物流中有广泛应用。提出深度强化学习Memetic算法求解该问题,将Memetic算法求解VRPSPDTW问题中的大邻域搜索过程建模成马尔可夫决策过程,构建编码器-解码器架构的深度神经网络模型完成大邻域搜索中的移除操作。编码器对当前解中各结点的个体特征和位置特征进行信息交互,解码器输出需要移除的结点,设计了非自回归和自回归两种网络结构,采用强化学习算法训练神经网络模型。设计了混合策略,将人工设计的启发式策略与深度强化学习到的策略相结合,以提高寻优能力。实验结果显示提出的算法具有更强的跳出局部最优的能力,能在有效的时间内获得比对比算法更优的解,特别是在大规模问题上。最后,对提出算法的新组件进行了消融实验,证明了算法的有效性。

考虑软时间窗的同时送取货随机旅行时间车辆路径问题

考虑车辆总旅行时间约束和车辆载重限制以及客户对服务时间窗的要求,研究带有软时间窗的同时送取货随机旅行时间车辆路径问题(STT‒VRPSPD),建立机会约束规划模型。将禁忌搜索算法与分散搜索算法相结合,构建混合分散禁忌搜索(HSTS)算法,并采用C‒W节约算法生成初始解。基于经典的Dethloff算例和Solomon时间窗生成方法,分别生成包括50个客户、200个客户各20组算例,算例测试结果验证了混合分散禁忌搜索算法的有效性。

改进野马算法求解低碳开放式送取货选址路径问题

目的针对当前物流背景下普遍出现的送货公司外包、退换货频繁等问题,结合现有的碳排放政策,提出低碳背景下开放式同时送取货选址−路径模型(Low-Carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem,LOLRPSPD),并通过改进野马算法进行求解。方法首先设计一种新的解码方式,使得原离散问题可以采用连续算法求解。之后,运用哈尔顿序列生成初始解,改进非线性进化概率因子,使用模拟二进制交叉,增加变异操作,以及精英保留、设置连续失败重新初始化等步骤,改进野马算法。最后,通过6组不同大小的算例将改进野马算法与原始野马算法、模拟退火算法、粒子群算法、遗传算法进行对比。结果针对中大型算例,改进野马算法远超原始野马算法。针对小型算例,在确保准确率的同时,改进野马算法对比各经典算法也在速度上具有优势。结论提出的LOLRPSD模型具备合理性,改进的野马算法针对选址路径问题具有较好的搜索能力。

基于回溯搜索优化算法求解带时间窗和同时送取货的车辆路径问题

为了求解带时间窗和同时送取货的车辆路径问题(VRPSDPTW),首次设计了回溯搜索优化算法(BSA)求解该问题。使用随机选择法、最近邻居法、最远者优先法、剩余承载力和径向附加费节约算法产生初始种群。然后在BSA算法框架下,在交叉和变异操作中使用6种路径间搜索算子和4种路径内搜索算子更新当前局部最优解。选取文献[1]测试数据集中的6个算例,将BSA算法的计算结果与文献中已知的遗传算法、并行模拟退火算法和离散布谷鸟算法的结果进行比较,对算法性能进行测试。BSA算法获得了2个已知国际最好解,并更新了1个已知国际最好解。Friedman检验显示,在α=0.1%的显著性水平下,这4种算法不存在显著性差异。因此,所提出的BSA算法是求解VRPSDPTW的有效算法。

基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题

为求解带时间窗和同时取送货的车辆路径问题(VRPSPDTW),提出一种离散布谷鸟(DCS)算法,该算法在标准布谷鸟算法的基础上,在Lévy飞行位置更新过程中,使用路径内搜索2-opt法和路径间搜索swap/shift法改进当前巢穴;在寄生巢位置更新过程中,使用路径内搜索relocate/exchange法和路径间搜索GENE法,随机产生新巢穴。选取Wang和Chen测试数据集,对算法性能进行测试,并与遗传算法和并行模拟退火算法进行比较。测试结果显示,在9个中小型顾客规模算例中,DCS算法获取了所有的当前国际最优解,在56个大型顾客规模的算例中,DCS算法在5个算例中更新了当前国际最优解,在17个算例中获取了当前国际最优解。通过Rank值法对这3种算法进行Friedman检验和Wilcoxon秩检验,结果表明所提DCS算法的有效性。

带软时间窗的同时取送货车辆路径问题研究

考虑软时间窗下的车辆路径问题,客户点常伴有同时取送货的双重需求。针对此类问题,通过对软时间窗、车辆在途前后时间关系及二者融合问题进行刻画,同时将车辆行驶距离、车辆使用数、违反软时间窗总时间、客户满意度等纳入综合考量,构建相应混合整数非线性规划(mixed integer nonlinear programming,MINLP)模型。设计相应多目标优化求解算法,运用理想点法对目标函数进行转化,将多目标优化问题转化为单目标优化问题。结合相应算例集,运用LINGO 17.0全局求解程序求得每组算例的全局最优解。结果表明,针对带软时间窗的同时取送货车辆路径问题(vehicle routing problem with simultaneous pick-up and delivery and soft time windows,VRPSPDSTW),所建模型及算法是有效且可行的。

带时间窗的同时取送货车辆路径问题求解算法

为了整合物流配送过程的退货与送货服务,依据实际情况建立带时间窗的同时取送货车辆路径规划模型,设计一种基于K-means聚类处理的Q-Leaning自启发式蚁群算法解决此类问题。根据配送服务的特性,在基本的K-means算法上作相应的改进,同时提高蚁群算法的局部搜索能力,完成两算法的合理衔接。选用相关文献数据和标准算例进行实验,验证所提算法具有较好的性能,可以解决所描述的此类问题。

改进烟花算法求解同时送取货选址路径问题

针对同时送取货的选址路径问题(Location-routing Problem with Simultaneous Pickup and Delivery,LRPSPD),设计一种改进烟花算法(Improved Firework Algorithm,IFWA)求解。首先,考虑仓库建设、车辆启用、车辆路径等成本因素,建立最小成本的LRPSPD模型,该模型强调需求点的送货需求和取货需求只能由一辆车同时进行服务。其次,设计一种改进烟花算法,该算法结合贪心聚类算法生成初始解,由烟花爆炸算子操作生成邻域解,利用变异操作协助产生新种群。最后,通过使用混合免疫算法、模拟退火算法求解相同算例,对结果进行分析比较,验证模型的可行性和改进算法的有效性。

带时间窗的同时取送货车辆路径问题建模及模因求解算法

为解决逆向物流背景下的带时间窗的同时取送货车辆路径问题(VRPSPDTW),根据实际情况建立了相应的车辆路径问题模型,并采用模因算法进行求解。在模型的求解过程中使用引导弹射搜索(GES)生成初始种群,在种群进化的过程中采用边界组合交叉(EAX)产生子代,并采用多种邻域结构对子代进行修复、教育,以提高解的质量和算法的搜索效率。通过在Wang和Chen测试数据集上与遗传算法(GA)、并行模拟退火(p-SA)算法、离散布谷鸟(DCS)算法进行比较,实验结果显示:在小规模算例进行求解时,所提算法全部取得了当前最优解;对标准规模算例进行求解时,所提算法使70%的算例更新或获取了当前最优解,获得的最优求解算例结果与当前最优解相比有超过5%的提升,充分验证了所提算法求解VRPSPDTW的良好性能。

同时取送货车辆路径问题的改进粒子群优化算法

同时取送货车辆路径问题(VRPSDP)是指车辆在服务过程中,对顾客同时进行取货和送货服务,针对这类问题,提出一种改进的粒子群优化算法。通过惯性权重的更新和路径链接更新策略有效地扩大算法的搜索空间,从而改进了算法的性能。另外,采用邻域搜索扩大策略(ENS)加快了算法的搜索速度。最后,应用所提出的改进的粒子群优化算法求解了两类同时取送货的车辆路径问题的算例。结果表明,该算法与经典的求解结果相比较,取得了比较好的计算结果,表明该算法是求解同时取送货车辆路径问题的有效工具。

同时取送货车辆路径问题的改进人工鱼群算法

该文在建立同时送取货车辆路径问题数学模型基础上,针对车辆负载波动性的特点,构造相应的人工鱼群算法的四元个体模型;利用动态设置视野范围、邻域搜索方法改进人工鱼群算法的觅食和追尾操作行为,仿真算例证明改进人工鱼群算法能快速收敛得到较优解,具有较强工程应用价值。

基于实时信息的取送货动态车辆路径问题研究

为适应点对点、实时城市配送对动态响应和快速决策提出的新要求,研究了多种实时信息作用和影响下的取送货动态车辆路径问题.采用将动态问题转化为一系列静态问题的建模方法,建立了基于实时信息的取送货动态车辆路径模型;设计了动态算法框架,运用构造算法获得初始可行解,运用禁忌搜索算法改善初始可行解质量.实验表明,本文的模型和算法能有效解决基于实时信息的取送货动态车辆路径问题,将初始可行解的质量(实时物流配送成本)改善了34%.

多车次同时送取货物车辆路径问题的量子蚁群算法

研究了配送车辆载重量和工作时间有限,考虑货物装卸时间的多车次同时送货和取货的车辆路径问题(multi-trip vehicle routing problem with simultaneous deliveries and pickups,MTVRPSDP),建立了以配送车辆启动成本和车辆行驶成本之和最小为目标的线性整数规划模型.将量子计算和基本蚁群算法相结合提出了求解MTVRPSDP的量子蚁群算法,该算法应用量子比特启发式因子改进了人工蚂蚁的转移概率,从而提高了算法的全局搜索能力和稳定性,有效改进了算法陷入局部最优的缺陷.算例分析表明:MTVRPSDP的线性整数规划模型在实际应用中是可行和有效的,而且相比于基本蚁群算法和文献中所给其他算法的计算结果,利用量子蚁群算法和MTVRPSDP的线性整数规划模型能够得到较好的满意解,安排的车辆配送路线更加经济合理.