有里程和软时间窗约束的开放式多车场集送货一体化车辆路径问题研究

基于现代物流业的现实状况和实际需求,研究了一个带有里程和软时间窗约束的开放式多车场集送货一体化车辆路径问题。给出一个遗传算法对该问题进行求解。在该算法中,为了提高其性能,并全面考虑所有约束,论文采取如下措施:(1)在初始种群形成之前,将各个任务的送货点按时间窗进行排序;(2)在所有任务的一个序列中用里程约束来控制车场的插入,并对软时间窗约束采取加入惩罚的方式解决。最后论文举例对该遗传算法进行说明,并对进一步的研究工作进行了展望。

基于共同配送策略的农村电商集送货一体化车辆路径问题

研究农村电商物流配送问题,综合考虑区域内多配送中心、客户居住地较分散、同时具有集货和送货双重需求、集货量与需求量都比较小等因素,引入共同配送策略,以总配送费用最少为目标构建基于共同配送策略的集送货一体化车辆路径问题数学模型,并根据模型特点设计一种改进蚁群算法求解。最后,采用案例证明共同配送策略能从全局优化的角度统筹规划区域内物流资源,能有效缩短车辆总行驶距离、减少车辆使用数量、降低总配送费用。

双需求集货送货一体化车辆路径问题的数学模型及算法

本文研究了具有总时间和车容量约束的双需求集货送货一体化车辆路径问题,在综合考虑运输费用和车辆出行固定费用的前提下,建立了该问题的整数线性规划模型,并分别给出了求解该模型的精确算法和基于节约准则的启发式算法。最后通过一个具体实例验证了算法的有效性。

多车型集配货一体化车辆路径问题研究

针对客户存在收货和发货双重需求的物流配送问题,讨论具有多种车型的集配货一体化车辆路径问题。在综合考虑各车型的固定成本和可变配送成本的前提下,以总成本最小为目标,以尽可能提高车辆满载率、减少出行次数为思路,构建多车型集配货一体化车辆路径优化模型。基于最小插入费用法设计初始可行解生成算法,通过引入基于概率的多算子邻域操作、最优解记忆装置、多准则终止原则对模拟退火算法进行改进,给出求解思路。设计算例并对多车型单/双向集配货模型的求解结果进行比较,以验证模型的实用性和算法的有效性。研究结果表明:使用改进后的模拟退火算法对构建的多车型集配货一体化车辆路径问题模型求解更直接简便,对多车型集配货一体化车辆路径优化后能有效降低配送成本。

集货送货一体化的物流配送车辆路线问题的标号算法

本文结合实际情况,对具有时间窗约束的集货送货一体化的车辆路线问题进行了研究,针对该问题的特点,采用修正的多属性标号算法对该问题进行求解,并通过C++编程语言实现了该算法,最后用一个示例表明本文的算法是有效的。

基于遗传算法的集送一体化的车辆路径问题

有时间窗的集送货一体化的车辆路径问题(VRPPDTW)是对经典的车辆路径问题(VRP)的扩展,是一类重要的组合优化问题,但是目前对该问题的研究非常有限。论文采用了新的染色体编码方法,设计了遗传算法对该问题进行求解。在求解过程中,对集送一体化、多种配送车辆类型的问题进行了有效处理,同时考虑了车辆载重量和时间窗等约束。最后的实验结果表明,该算法可以求得这类车辆路径问题的最优解或次优解。

电动汽车集散货一体化车辆路径问题

针对电动汽车特性,考虑里程约束和时间窗约束,建立以最小化总费用为目标的电动汽车集散货一体化车辆路径问题模型.模型考虑了车辆可在行驶途中多次前往充电站补充电量.因此,避免由于电量不足导致的车辆半路抛锚及电池过度放电.应用遗传算法求解模型,得到包含配送计划、行车时间及充电计划在内的配送方案.并基于Dijkstra算法求解任意两个邻接节点之间最短路径问题,在路网上为车辆规划行车路线.结合北京市城区路网的算例验证模型和方法的有效性和实用性.

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

针对带时间窗的时间依赖型同时取送货车辆路径问题(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%,可有效提高物流企业的经济效益。

集配协同下多产品越库配送车辆路径问题研究

文中基于实际越库配送中零售商的多样化需求和集配过程的连续型,针对集配协同下的多产品车辆路径问题,构建以车辆固定成本、运输成本、时间窗惩罚成本和库存持有成本最小化为目标的带越库配送的车辆路径优化模型.根据问题的阶段性特征,提出一种改进的遗传算法对问题进行求解,并以车辆等待时间最小为准则设计解码方案.通过算例的对比分析,验证了改进的遗传算法有更强的寻优能力.结果表明:建立的模型能够有效降低总成本,提高运输效率.

具有同时集送货需求的车辆路径问题的自适应混合遗传算法

为满足配送货物和收集货物的需求,给出了具有同时集送货需求的车辆路径问题的混合整数规划模型,设计了求解该模型的自适应混合遗传算法。该算法以最优划分方法计算适应值,邻域搜索法作为变异算子,设计了新颖的交叉算子和群体更新策略,定义了群体多样性结构和变异概率的变化规律。通过仿真实验,并与已有优化算法比较,表明该算法是求解具有同时集送货需求的车辆路径问题和一般车辆路径问题的一个有效方法。

具有同时集送货需求的车辆路径问题的粗粒度并行遗传算法

设计了求解VRPSDP的粗粒度并行遗传算法(CGPGA),其中遗传算法以最优划分法计算适应值,邻域搜索法作为变异算子,定义了群体多样性结构。并行算法以单向环作为连接拓扑,各子群体独立进行遗传操作,迁移算子用于群体间的信息交流,采用多样性替换的方法进行个体替换。论文给出了CGPGA算法在集群系统上的重复非阻塞MPI实现。对典型VRPSDP实例进行测试的结果表明:CGPGA算法在大部分实例上超过了已知最好解,未达到已知最好解的实例与已知最好解的相对误差不超过1.5%。在计算速度方面,CGPGA算法具有接近线性甚至超线性的加速比,提高了遗传算法的求解速度。

带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法

为了同时实现总配送成本最低、车辆数最少和车辆行驶距离最短等目标,考虑车辆指派成本及运输路径成本的相对重要性,建立了带时间窗装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性,提出了一种混合离散粒子群求解算法。算法基于客户排列的直观无分段大路径解表示法,采用改进深度优先搜索分割法对问题解进行解码与评价;嵌入一种变邻域下降搜索程序并在个体粒子每次迭代时以一定概率选择执行,利用混合粒子群算法在多邻域深度搜索和在全局空间广度搜索进行寻优,同时应用模拟退火思想和比例选择性变异最差个体来改善个体搜索停滞现象。采用两个不同目标算例进行寻优测试,验证了所提算法的可行性和有效性。

求解卸装一体化的车辆路径问题的混合启发式算法

提出一种结合蚁群系统（Ant Colony System,ACS）和变邻域下降搜索（Variable Neighborhood Descent,VND）的混合启发式算法ACS_VND,求解卸装一体化车辆路径问题.利用基于插入的ACS解构造方法产生多个弱可行解,再逐个转换成强可行解,并选择其中最好的作为VND的初始解.在VND过程中使用三种不同的邻域结构：插入、交换和2-opt依次对解进行迭代优化.对55个规模为22~199的benchmark算例的求解结果表明,算法ACS_VND能在较短时间内获得52个算例的已知最好解,并且更新了其中44个算例的已知最好解,求解性能优于现有算法.

装卸一体化车辆路径问题的自适应并行遗传算法

为了同时实现总配送成本最低、车辆行驶距离最短、车辆数最小等目标,综合考虑车辆指派成本及运输路径成本,建立了装卸一体化车辆路径问题的混合整数规划模型。针对该问题搜索空间的离散性和求解算法的局部收敛性,提出了一种自适应并行遗传算法。算法以C-W节约法为基础,设计了三种基于双重需求的启发式种群初始化方法,缩小搜索空间并优化初始解;引入多样性种群和高质量种群的双种群并行策略,实现深度与广度的同步搜索;设计自适应交叉变异操作,改善高质量种群个体搜索停滞,并针对全局最优个体采用特殊变异的后优化操作以进一步提高全局优化性能。采用标准数据集作为算例进行寻优测试,验证了所提算法的可行性和有效性。

软硬时间窗共存装卸一体化车辆路径问题的混合离散粒子群优化算法

文章针对软硬时间窗共存装卸一体化车辆路径问题(vehicle routing problem with simultaneous delivery and pickup under coexistence of soft and hard time windows,VRPSDPCSHTW)建立了包含车辆固定出行成本、运输成本和惩罚成本的数学模型,提出了一种混合离散粒子群优化算法。针对基本离散粒子群算法容易早熟收敛而陷入局部最优等问题,内嵌一种变邻域下降局域搜索方法,并在一定概率下执行以加强种群搜索能力,最后通过3个算例的仿真分析进行了算法验证。

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

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

带有次序限制的装卸一体化车辆路径问题研究

研究了装卸一体化的车辆路径问题,根据问题的实际情况,增加了带有次序限制条件,并以总行驶路线最短为目标,建立了数学模型,并根据模型的特点,用改进的遗传算法进行求解。最后,通过具体实例验证了模型及算法的有效性。

求解卸装一体化车辆路径问题的改进导向局部搜索算法

针对卸装一体化车辆路径问题,提出一种变惩罚函数的导向局部搜索算法(IGLS)。在传统导向局部搜索算法的基础上加入了新的惩罚效用函数,当传统导向局部搜索算法陷入局部最优时,变换惩罚策略后重新搜索,从而扩展搜索的邻域。通过和传统导向局部搜索算法以及TS_GLS算法在不同算例上的仿真结果比较,验证了所提算法在解决卸装一体化车辆路径问题上的有效性和稳定性。

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

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

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

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