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

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

时变车辆路径问题的启发式算法

标准的带时间窗车辆路径问题一般假定车辆的行驶速度保持恒定,然而在实际应用中车辆的行驶速度通常是时变的,因此近年来时变车辆路径问题正日益成为该领域的研究热点.本文对时变车辆路径问题的求解策略进行了研究,并设计了一种两阶段启发式算法对问题进行求解,算法的第一阶段提出了一种"最先过期用户优先"的启发式算法求得初始解,第二阶段利用模拟退火算法对初始解进行了改进.实验结果表明该算法可以有效地求解时变车辆路径问题.     

基于SWEEP方法的改进车辆路径协作策略研究

针对需求随机的车辆路径优化问题,提出了一种基于SWEEP方法的改进车辆路径协作策略,构造了基于该策略的车辆任务量分配模型、设计了求解该模型的启发式算法。该策略采用SWEEP规则对基本车未完成任务的客户重新进行路径优化,然后利用SWEEP车服务这些客户,以缩短客户的服务时间、减少运输成本。应用此方法对24个不同规模的车辆路径优化问题进行了计算机仿真,结果表明,该任务分配模型和算法具有较强的适用性,改进的SWEEP协作策略能够有效地解决解随机车辆路径问题。     

基于模糊时间窗的车辆调度干扰管理研究

为解决由顾客需求变动引发的物流配送干扰问题,最大化满足顾客需求并兼顾企业利益,提出基于模糊时间窗的车辆调度干扰管理方法.采用干扰管理思想对由客户需求变动引起的实时车辆调度问题进行研究,在深入分析现实中客户服务时间要求特征的基础上,把客户满意度水平定义为模糊时间窗的隶属度函数,并提出了车辆调度干扰恢复问题转换策略,构建了基于模糊时间窗的客户需求变动干扰管理救援模型,实现从顾客、驾驶员和供应商3方面对干扰影响程度的度量.为寻求最优解,设计模糊遗传算法,并改进了基于客户点的编码方式.在算法中用模糊优化程序处理问题的模糊特征,通过对客户服务时间的局部调整来确定最佳服务时间.实例结果表明了时间窗模糊化处理、扰动恢复模型及算法在应用中的有效性.     

考虑交叉口负面影响的有轨电车时刻表优化

现代有轨电车运行过程中,交叉口公交信号优先策略能够保证列车顺利通过交叉口,但会对交叉口其它社会车辆产生负面影响.本文考虑信号优先策略对交叉口产生的负面影响,提出了综合优化列车旅行时间和交叉口负面影响的有轨电车时刻表优化模型,针对模型的非线性特点,设计模拟退火算法和基于事件驱动的仿真法相结合的组合算法进行求解.以沈阳浑南现代有轨电车5号线为实例,结果表明,模型求解的时刻表方案相对于总旅行时间最小的时刻表方案,其旅行时间增加了1.2%,但交叉口的负面影响费用相对减少了66.4%.由此说明,本文提出的现在有轨电车时刻表优化方法,在保证列车旅行时间尽量小的同时极大降低了对交叉口社会车辆的负面影响.     

基于广义随机Petri网的城市道路公交优先建模与性能研究

针对当前城市道路网存在的交通拥堵问题,根据城市地面交通的特点和公交优先的原则,利用广义随机Petri网通过将变迁分为时间变迁和瞬时变迁,结合禁止弧和赋予各弧不同的优先权, 构建公交优先策略模型,为实施公交优先策略提供理论依据.     

停机位分配问题的顶点着色模型及算法

给出了停机位分配问题顶点着色模型及其分解算法.通过改良一种时间冲突算法,构建了航班使用停机位的时间冲突集合.以"先到先服务"原则为基础,把停机位分配问题转化为顶点着色问题,并建立了相应模型.利用笔者独创的分解算法,停机位的作业能力可得到改善.算法的计算复杂度为O(n2).该算法的特点在于:1)将顶点、颜色划分为若干个不同等级的集合;2)将顶点按照所属集合的等级、度进行分解,得到顶点的分解序列.在用一种颜色ck(1≤k≤K;K是可用颜色数)给顶点着色时,优先给这样一个顶点着色:该顶点能被着ck色,且其分解序列号最大.最后将该算法应用于一个算例,得到了最优解.     

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

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

基于模拟植物生长算法的车辆调度问题

基于配送企业车辆资源的限制和客户需求时间窗的要求,在考虑外包车辆和配送入员加班的情况下,对带时间窗的车辆调度问题进行扩展研究.根据客户需求的随机性特点构建以最小化车辆配送总成本为目标的机会约束规划模型,并设计求解该问题的模拟植物生长算法.结合车辆调度具体实例,将模拟植物生长算法与遗传算法进行比较,结果表明该算法不仅可以获得最优解,而且提高了求解效率,是一种有效的方法.     

动态需求的多车型车辆调度问题及云遗传算法

根据动态信息产生的时间点不同提出时间轴概念,利用时间轴将动态车辆调度问题转化为一系列的静态车辆调度问题,建立考虑车载率和油耗的综合费用为优化目标的车辆调度模型.利用云模型云滴的随机性和稳定倾向性改进自适应遗传算法中交叉率和变异率设置方式,设计云自适应遗传算法对车辆调度问题进行实时再优化.最后,结合算例对模型和算法的有效性进行验证.     

Improved Ant Colony System for VRPSPD with Maximum Distance Constraint

This article investigates the reverse logistics vehicle routing problem with a single depot, simultaneous distribution and collection of the goods by a homogeneous fleet of vehicles under the restrictions of maximum capacities and maximum distance. A mixed integer programming model is established. To solve the model, an Ant Colony System (ACS) approach combined with the pheromone updating strategy of ASRank and MMAS ant algorithm is proposed. In such approach, the vehicle residual loading capacity is introduced into the heuristic function considering the complex feature of fluctuating vehicle load. Moreover, the initial load is designed to be a random value correlated to the delivery and pick-up demands of the rest clients. The experimental study indicates that the proposed approach could improve the vehicle load rate and avoid the added total distance caused by the fluctuating load and the maximum capacity constraint. It could reach the satisfied solutions with high convergence speed in an acceptable computational time.     

求解复杂TSP问题的随机扰动蚁群算法

针对基本蚁群算法 ,设计出一种新颖的随机扰动蚁群算法 ,并将其应用于求解复杂 TSP问题 .该算法包含了两个重要方面 :一是提出了采用倒指数曲线来描述的扰动因子 ;二是设计出了相应的随机选择策略和扰动策略 .数值模拟表明 :该算法可以有效地克服基本蚁群算法的计算时间较长和容易出现停滞现象的缺陷 ,具有更好的全局搜索能力 .此外 ,还对该算法中参数的取值范围及选取方法进行了研究和探讨.     

带时间窗和调货特性的多品类取送货优化算法

为了满足快时尚品连锁门店多品类的销售需求,综合考虑载重限制、多货品、门店相互调货以及服务时间窗等因素,研究了同时取送货车辆路径问题.为了有效降低库存管理和运输成本,通常鼓励门店间的货品相互调配,且需要控制用车数.为此,以最小化车辆数为第一优化目标,最小化转运成本(运输成本和仓库处理成本)为第二优化目标,构建了混合整数规...     

基于蚁群并行算法的电气接线路径优化及仿真

继电控制系统中元件的连接关系可以使用网络拓扑图描述，元件间的接线路径优化类似于旅行商(TSP)问题，属于NP完备的组合优化问题。本文将ACS蚁群算法引入接线路径优化，建立了适用于继电系统接线路径优化的计算模型，并在MPI(消息传递界面)的基础上实现了算法的并行化。通过对算法初始参数进行仿真分析，确定了各参数的最佳取值范围，实验结果证明，在参数选择适当的情况下，ACS蚁群算法具有很好的全局搜索能力和较快的收敛速度。     

行为综合功能流水线中的资源约束LB-ACO算法

针对行为综合功能流水线中带资源约束的调度问题,提出了一种新的功能流水线调度算法负载平衡蚁群调度算法(load-balanced ant colony scheduling,LB-ACO).该算法将蚁群算法和力向算法的受力公式相结合,在保证较低运行时间复杂度O(cn²)的前提下,可获得近似最优的流水线调度结果.通过确定蚁群算法的局部试探因子和全局试探因子的计算方法,描述了该算法的实现步骤.通过仿真实验证明了该算法的流水线调度性能.     

基于蚁群算法的序贯决策问题研究

实际工程中存在许多大规模、非线性多约束的序贯决策问题,传统算法解决起来较为困难.蚁群系统(ACS)是一个用来解决大规模多约束组合优化问题的现代启发式算法,根据序贯决策的特点设计了多层结构的蚁群系统,给出了算法的组成结构;为了节约计算内存和优化时间,详细阐述了淘汰劣质解机制的精英策略;并通过梯级水电站短期优化调度这一实际工程序贯决策问题,来验证所构造的算法,给出了优化调度的数学模型及算法的求解思路.最后,采用我国西南地区某梯级流域中三个水电站的相关数据建立了调度仿真模型,仿真结果证实了所采用算法的有效性和可行性.     

Flow shop问题的蚁群优化调度方法

提出了一种新颖的蚁群优化算法，用于解决流水作业（flowshop）的优化调度问题。算法中，流水作业调度问题以结点或弧模式有向图表示，人工蚁受有向图上信息素踪迹的指引，在图上搜索并一步步构造出问题的可行解。算法中的信息素踪迹更新过程作为蚁群间的间接通信机制，将引导整个蚁群收敛到问题的优化解。信息素踪迹更新过程中的停滞状态脱离机制以及信息素踪迹限制机制能帮助人工蚁跳出局部最优解。算法局部搜索过程中采用的基于关键路径的领域结构缩小问题的搜索空间。与其他算法在Taillard流水作业调度测试问题集上的比较试验表明，本算法性能更优，且具有更强的自适应和鲁棒性。     

基于解均匀度的车辆路径问题的自适应蚁群算法

蚁群算法是一种新型的模拟进化算法，具有许多优良的性质，可以很好地解决旅行商问题(Traveling Salesman Problem，TSP)，但同时也存在计算时间长、易出现停滞等缺陷。在分析车辆路径问题(Vehicle Roulting Problem，VRP)与TSP区别的基础上，将蚁群算法应用于VRP的求解，通过引入解均匀度、选择窗口以及吸引力等概念对算法的转移策略和更新策略进行改进，构造了具有自适应功能的蚁群算法。实验仿真结果表明所设计的算法具有很强的搜索能力，计算效率较高，能够有效地解决加速收敛与停滞现象之间的矛盾。     

基于Voronoi图和蚁群优化算法的无人作战飞机航路规划

无人作战飞机(UCVA)航路规划是一类复杂优化问题.在众多航路规划算法中,Voronoi图是一种根据战场多威胁源分布情况获取可行航路的图形算法,而蚁群优化(ACO)算法是受到蚂蚁觅食行为启发而形成的一种启发式仿生算法.根据已知威胁源生成Voronoi加权图,其中每条Voronoi边的总代价可以由威胁代价和燃油代价计算得出;然后给出了在Voronoi图条件下,用于航路规划的改进ACO算法模型和具体实现方法;最后,将Voronoi图与ACO算法相结合,并针对某UCAV多种空战态势下的航路规划问题进行了系列仿真实验.实验结果验证了所提方法在解决UCAV航路规划问题时的可行性和有效性.     

基于蚁群系统的工件排序问题的一种新算法

工件排序问题中如何使加工效率最高，一直是一个非常重要而且又非常困难的问题，特别是问题的规模很大时，目前各种算法计算就非常困难，有的甚至无法得到合理的方案，蚁群系统是近年来发展起来的解决组合优化问题的一种有效方法，根据工件排序问题的特点，建立了在不同种类的并行机上加工一批不同种类工件的优化数学模型，在蚁群算法的基础上对其进行改进，成功地把改进的蚁群算法用于工件排序问题的优化中，通过与其他算法的仿真比较，表明基于蚁群系统的算法是有效的，特别是问题规模很大时更显示其快较的收敛速度和较高的精度。