求解车辆路径问题的改进微粒群优化算法

微粒群优化算法是求解连续函数极值的一个有效方法。研究了用该算法求解车辆路径的问题。设计了求解车辆路径问题的一种新的实数编码方案,将车辆路径问题转化成准连续优化问题,并采用罚函数法处理约束条件。应用该微粒群优化算法求解了多个车辆路径问题的算例,并与遗传算法和双种群遗传算法进行了比较。计算结果表明,该算法可以更有效地求得车辆路径问题的优化解,是解决车辆路径问题的有效方法。     

求解车辆路径问题的混合遗传算法

针对物流配送中具有容量限制的车辆路径问题,设计了一种结合2-OPT子路径优化的混合遗传算法.在该算法中,提出了一种新的双层染色体编码方案.该染色体编码方案能确保子路径为满足车辆容量约束的可行路径,并且该编码方案只需根据客户编号生成染色体,无需预先知道有容量限制的车辆路径问题所需的最小车辆数,更适于求解实际中的车辆路径优化问题.采用2-OPT算法作为遗传算法的变异算子以优化子路径,从而提高算法的收敛速度.基于典型基准测试实例的计算结果表明,该算法是求解有容量限制的车辆路径问题的有效方法.     

基于NSGA Ⅱ的物流配送中车辆路径问题研究

车辆路径问题已经被证明属于NP—Hard问题。针对这一问题建立了多目标优化的数学模型;构造了带精英策略的快速非支配排序遗传算法,以求解车辆路径问题的数学模型,针对物流配送路径优化,将该算法从解决连续问题扩展为解决离散问题;进行了算法设计,提出了离散问题的快速非支配排序和锦标赛选择结合的子代选择方法,并修正了以往的初始群体生成、交叉和变异的方法。通过实例比较证明,该算法可以更好地解决物流配送路径优化的多目标问题,较快找到更优解,避免早熟收敛并改进算法性能,达到较高的搜索效率。     

多配送中心大区域配送路径优化

针对多配送中心大区域物流配送的复杂问题,首先构建了相应的数理模型,然后选取蚁群算法作为该模型的求解算法.经过系统分析,结合Visual Basic编程技术实现了配送模型的优化求解,完成了物流配送路径优化系统的开发.最后以晋、冀、鲁、豫4省部分城市和京津地区的实际路径数据为例验证了该模型的有效性,展示了软件系统的实用性、高效性和可扩展性.     

多配送中心大区域配送路径优化

针对多配送中心大区域物流配送的复杂问题,首先构建了相应的数理模型,然后选取蚁群算法作为该模型的求解算法。经过系统分析,结合Visual Basic编程技术实现了配送模型的优化求解,完成了物流配送路径优化系统的开发。最后以晋、冀、鲁、豫4省部分城市和京津地区的实际路径数据为例验证了该模型的有效性,展示了软件系统的实用性、高效性和可扩展性。     

多车场车辆路径问题的新型聚类蚁群算法

在对多车场带时间窗的车辆路径问题进行详细阐述的基础上,以车辆运输总费用最少为目标函数,建立了问题的数学模型。提出了先采用聚类蚁群算法将多车场带时间窗的车辆路径问题分解为若干个单车场车辆路径问题,然后对各单车场问题应用改进蚁群算法进行优化的求解思路。最后通过一个实例将这种新型聚类蚁群算法与就近分配禁忌搜索算法和K-均值算法的优化能力进行了对比。试验结果表明,该算法对优化多车场带时间窗的车辆路径问题的求解结果是相当令人满意的。     

多车场车辆路径问题的新型聚类蚁群算法

在对多车场带时间窗的车辆路径问题进行详细阐述的基础上,以车辆运输总费用最少为目标函数,建立了问题的数学模型.提出了先采用聚类蚁群算法将多车场带时间窗的车辆路径问题分解为若干个单车场车辆路径问题,然后对各单车场问题应用改进蚁群算法进行优化的求解思路.最后通过一个实例将这种新型聚类蚁群算法与就近分配禁忌搜索算法和K-均值算法的优化能力进行了对比.试验结果表明,该算法对优化多车场带时间窗的车辆路径问题的求解结果是相当令人满意的.     

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

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

基于核心路径禁忌算法的开放式车辆路径问题研究

描述了开放式车辆路径问题,提出了核心路径的概念和原理,并设计了解决有能力约束和距离约束的开放式车辆路径问题的禁忌算法.该算法基于核心路径原理,应用改进的广义插入法产生初始解和进行邻域操作,设计了3种邻域,利用能力约束控制单条路径配送点数,采用惩罚函数处理距离约束.应用该算法求解了多个开放式车辆路径问题算例,并与参考文献中的算例进行了比较.经分析表明,该算法可以更有效地求得开放式车辆路径问题的优化解,是解决有能力约束和距离约束车辆路径问题的有效方法.     

低碳动态开放式选址—路径问题

合理的配送中心选址及路径优化有助于降低物流碳排放,本文针对物流配送过程面临的不确定交通网络现实,研究不确定道路网络对选址—路径问题碳排放的影响,提出应用概率函数及交通因子表示路径不确定的随机性及不确定程度,将其转化为速度函数,结合第三方物流配送的特点,建立了基于速度及车辆类型的动态低碳开放式选址—路径模型,并设计了量子进化算法与局部搜索算法相结合的智能优化算法进行求解。为了分析路网对碳排放的影响,采用随机及确定性概率交通状况进行仿真实验对比,结果表明,当路网不确定发生概率随机时,其成本增加量高于0.1确定性概率,但低于0.5、0.9确定性概率;交通不确定对碳排放量的影响程度高于成本;随着交通不确定固定概率的增大,碳排量的增加与顾客数目的相关性呈下降趋势。通过与其他智能算法进行对比,表明本算法是求解该问题的一种有效算法。     

有时间窗的车辆路径问题的近似算法研究

为了分析不确定性因素对敏捷供需链系统的影响,文章从敏捷供需链系统重构的可能性条件和快速响应特征出发,根据敏捷供需链的运行目标,建立了基于风险因子的敏捷供需链系统风险分析模型,将敏捷供需链的不确定性因素分为系统层、协作层和实体层进行分析;以系统各层评价指标变化为风险分析的最终结果,给出一种针对敏捷供需链系统的风险进行定性与定量相结合的方法和分析流程。最后对该风险量化建模和定量分析方法进行举例验证,风险分析结果能够有助于为敏捷供需链系统的决策层提供决策依据,证明了该风险量化建模和定量分析方法适用于敏捷供需链系统的风险管理。     

车辆路径问题的混沌神经网络解法

利用混沌神经网络在解组合优化问题时具有的随机性和确定性并存的优点,对一类随机需求服从泊松分布的车辆选径问题进行了求解,提出了一种混沌神经网络求解算法,并与平均场退火算法和模拟退火算法进行了比较。结果表明,该算法具有很强的避免陷入局部极小点的能力和较强的全局搜索能力,较大地提高了优化的时间性能和求解质量,是求解车辆选径问题的有效方法。     

Demonstrating the importance of using total time balance instead of route balance on a multi-objective vehicle routing problem with time windows

‘Route balance’ is the difference between the longest and the shortest among all the route lengths. The route balance is frequently considered in a vehicle routing problem (VRP) for balancing the distance travelled among delivery vehicles. This is a common practice since in VRPs there are no time elements. However, in recent years, some research works have considered route balance in a vehicle routing problem with time windows (VRPTW). As there are more time elements in VRPTW, this paper refutes that route balance is sufficient for VRPTW by simultaneously optimising makespan and workload imbalance using ‘total time balance’ instead of route balance. On the other hand, ‘total time balance’ is the difference between the longest total time taken and the shortest total time taken among delivery vehicles. As such, makespan is the longest total time taken among vehicles. Total time taken for a vehicle is the sum of vehicle run time, waiting time and service time. In order to demonstrate the importance of using total time balance instead of route balance on VRPTW, three different multi-objective VRPTW models, namely, (1) only with general VRPTW objectives (i.e. ‘total distance travelled’ by all vehicles and ‘total number of vehicles’ used), (2) general VRPTW objectives with route balance and (3) general VRPTW objectives with total time balance are developed and solved by fitness aggregated genetic algorithm (FAGA) for 36 Solomon’s benchmark instances. By comparison of the makespan produced by the FAGA between the three cases, the importance of using total time balance instead of route balance on multi-objective VRPTW is demonstrated. Also, the makespan produced by the FAGA for the third case, i.e. general VRPTW objectives with total time balance is compared with the makespan produced by fitness aggregated differential evolution (FADE). By comparing makespan with statistical testing between FAGA and FADE, the outperformance of FAGA over FADE is verified. To check the practicality of the total time balance on multi-objective VRPTW, an instance with real time windows is also solved for the three cases by the FAGA and its makespan are compared and reported.     

改进的最大-最小蚂蚁算法在有时间窗车辆路径问题中的应用

利用最大-最小策略,最大最小蚂蚁算法减小了蚂蚁算法陷入局部陷阱的可能性。基于对最大最小信息素策略和信息素更新方式的改进,结合快速产生初始解的算法,提出了一种新方法。把该方法应用于有时间窗车辆路径问题,试验结果表明该算法是有效的。     

不确定需求和旅行时间下的车辆路径问题

针对一类不确定需求和旅行时间下的随机车辆路径问题,建立了一个随机规划模型,提出了一种带有自适应机制的改进遗传算法。该算法引入自适应选择机制,采用了新的交叉算子。选取两种不同规模的随机车辆调度问题,分别采用该算法和基于边重组的改进遗传算法进行求解,并通过对计算结果进行对比分析,分别针对自适应选择机制和新的交叉算子做了讨论。结果表明,所提算法不仅取得了更好的优化结果,而且具有更快的收敛速度。     

A decomposition-based hierarchical optimization algorithm for hot rolling batch scheduling problem

In this paper, the hot rolling batch scheduling problem is formulated as a multi-objective vehicle routing problem with double time windows model, in which the first time window deals with the surface grade constraint and the second one is for the linkage modes. In view of the complexity of the proposed model and the priority of considered objectives in practical production, a decomposition-based hierarchical optimization algorithm is proposed to solve the model. Firstly, the model is decomposed into two sub-problems: vehicle routing problem with time windows (VRPTW) and single vehicle routing problem with time windows (SVRPTW). Secondly, MACS-VRPTW is used to optimize the VRPTW sub-problem, in which the first objective is prior to the second one. Then, dynamic programming and genetic algorithm are used to optimize the SVRPTW sub-problem so as to reach a higher hot charge temperature. Experimental results based on the practical production instances have indicated that the proposed model and algorithm are effective and efficient.     

基于近似动态规划的动态车辆调度算法

针对物流配送服务业中,车辆调度问题日渐呈现任务规模大,车辆类型多、属性多,调度实时性要求越来越高等特点,提出了基于近似动态规划的动态车辆调度算法。根据当前的任务需求与车辆状态以及相应的约束条件作出相应的调度,并且对一些样本进行训练,得到了一个近似价值函数。通过该价值函数,即可对任务迅速作出相应的决策。仿真模拟实验证明了该算法的有效性和优越性。