动态车辆路径问题的优化方法

设计了在动态环境下进行车辆路径优化的导向局域搜索算法.算法在产生初始解以后的动态求解过程中,不再做车辆之间的顾客调整,而只应用2-opt局域搜索算子更新车辆服务顾客的顺序,即针对每辆车辆的旅行路线求解一个旅行商问题.建立了在动态环境下车辆执行运输任务过程的仿真模型.仿真过程中,应用算法根据交通路网实际情况实时优化车辆路径,并采用4种接受准则判别是否接受新的车辆路径.仿真结果表明:算法具有实时、高效的特点,满足动态车辆路径问题的求解要求.     

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

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

禁忌搜索算法求解带时间窗和多配送人员的车辆路径问题

【目的】为了求解带时间窗和多配送人员的车辆路径问题,建立了该车辆路径问题的数学模型,并采用禁忌搜索算法进行求解。【方法】首先松弛车辆载重和顾客时间窗约束,在目标函数里面引入相应的惩罚成本;接着,使用贪婪算法生成初始解;最后,设计禁忌搜索算法求解该问题。在禁忌搜索中,使用了插入、删除、移动、交换等算子搜索邻域解空间,并使用扰动算子进一步加大搜索范围。为了验证禁忌搜索算法的有效性,对修改的Solomon标准测试问题进行求解,并与CPLEX的优化结果进行比较。【结果】在小规模算例求解中证实了禁忌搜索算法的准确性,在标准规模算例求解中证实了该算法的高效性。【结论】所提出的禁忌搜索算法能够有效解决带时间窗和多配送人员的车辆路径问题。     

铁路行包配送车辆路径问题模型及算法

铁路行包配送车辆路径问题属于同时具有送货和集货需求的车辆路径问题.结合该问题特点,建立数学优化模型.求解算法中采用基于最近邻居的启发式方法产生尽可能好的初始解,并通过构造合理的邻域结构,引入适合的罚函数评价解的质量,随机选取禁忌长度的禁忌搜索算法优化初始解.以5台车辆、21个配送点的实例进行仿真计算,计算结果表明,模型及算法有效可行.     

同时收发运输路径问题的禁忌搜索算法

研究同时收发的运输路径问题,要求运输工具到每个客户收取和发送一次完成,并且在运输工具容量的限制下,寻求每个运输工具的运输路径,使总运费为最少.提出两阶段的求解过程:先用启发式算法得到初始解,然后用层次禁忌搜索算法得到改进解.计算实验表明,同样规模的问题,算法所需时间比直接使用禁忌搜索算法要少.     

基于改进的禁忌搜索算法求解带2维装箱约束的低碳车辆路径问题

同时考虑2维装箱和车辆路径2个NP难问题,以碳排放量为目标函数,对低碳环境下带2维装箱约束的车辆路径问题进行研究.求解思路是以禁忌搜索算法(Tabu Search,TS)为主要框架,然后基于贪心的思想采用4种启发式装箱策略生成初始解,并通过改进编码解码方式以及使用动态增长的禁忌长度对TS算法进行改进; 由给出算例的计算结果可知,改进的禁忌搜索算法对于求解该类问题具有一定的优越性.     

定位-车辆路径问题的两阶段混合启发式算法

定位-车辆路径问题(LRP)集成了设施定位分配和车辆路径决策,属于NP-hard难题.为有效求解实际大规模的具有设施容量约束和车辆容量约束的LRP问题,设计了基于禁忌搜索及双种群蚁群算法的两阶段混合启发式算法.算法第1阶段采用禁忌搜索算法确定设施定位及客户分配,算法第2阶段采用双种群蚁群算法优化车辆路径,蚁群间的通信与协调通过信息素共享来实现.通过仿真试验并与其他启发式算法进行对比,结果表明,该算法是可行和有效的.     

具有同时送货和取货需求的车辆路径问题的蚁群禁忌混合优化算法

在分析具有同时送货和取货需求的车辆路径问题(VRPSDP)的基础上,建立VRPSDP数学模型,提出一种新的求解VRPSDP问题的蚁群禁忌混合优化算法(ACO-TS),并通过实验验证该算法的有效性和可行性.新算法首先采用蚁群算法产生阶段最优解,然后利用禁忌搜索算法对阶段最优解进一步优化.实验表明,新算法能够高效解决VRPSDP问题,并且具有较好的优化效果.     

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

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

有时间窗的车辆路径问题及改进禁忌搜索算法

基于改进的禁忌搜索算法求解有时间窗的车辆路径问题,建立了该问题的通用数学模型.改进算法中,在随机构造的多个可行解中挑选较好的解作为初始解,采用2-opt方法生成邻域,并构造了动态禁忌表,使禁忌表的大小和结构随搜索过程发生改变,提高了整体寻优能力.仿真实验证明了算法的可行性、有效性和优越性.     

基于Backbone的空间收缩与划分算法

搜索空间的规模和复杂程度是决定问题求解难度的重要因素,而解空间的信息往往可以引导搜索找到最优解。在已知JSP空间结构的基础上,提出一种空间收缩与划分算法。算法利用搜索算法获得的较优解,结合组合优化问题解的backbone的概念,将搜索空间收缩并划分为一个或多个优解域,在优解域内再进行小规模问题的优化。该算法不必在求解前或求解过程中进行大量的统计分析工作,可以利用求解信息对解空间的地形进行估计,提高求解速度和解的质量。实验结果也证明了算法的有效性。     

基于图搜索与数值优化方法的分层轨迹规划方法

针对结构化道路场景中多约束的轨迹规划问题,提出一种路径和速度协同搜索、解耦优化的分层轨迹规划方法. 上层初始轨迹规划器考虑动态障碍物风险场与时空信息,构造时空代价地图,通过三维A*算法搜索得到安全可行的初始轨迹,保证初始轨迹解的质量. 下层运动轨迹规划器将轨迹规划解耦为路径规划和速度规划,以最小曲率、最大速度以及舒适性等为目标,采用数值优化算法构建路径和速度样条优化模型,使其在避障过程中能够充分发挥车辆的动力性能,同时保证驾乘舒适性,并以局部时空隧道思想简化约束条件,提高求解效率. 通过试验验证本文提出的方法具有较好的行驶效率、舒适性以及实时性.     

运用自动化信息系统优化的农产品物流配送路径研究

基于自动化信息技术的广泛应用,运用自动化信息系统研究了农产品物流配送路径的优化,提高配送效率和降低配送成本.首先,利用自动化的信息系统将配送车辆、配送员、物流公司、客户联系在一起,实时监控客户的需求变化,并保持信息沟通和共享,构建考虑自动化信息系统的农产品物流多配送中心成本优化模型.其次,结合A公司农产品物流企业数据,设计了一种运用GPS思想改进的混合算法进行路径的优化,得到一个最优化的配送方案,证明了该模型和算法对路径优化的科学性,也说明了改进的混合算法对于模型的最优解具有较强的全局搜索能力.最后,通过仿真实验结果证明,运用自动化信息系统对农产品物流配送路径进行优化具有可行性和合理性.在此基础上,本研究针对农产品物流配送路径优化的进一步发展提出了建议.     

收发件同步的快递服务网点选址与车辆线路规划算法研究

快递服务网点的布局需要考虑区域内客户的分布及各客户的收件、发件总量等多重因素.快递服务网点的选址及车辆线路的规划问题可以看作是将向客户发送物件的正向物流和从客户收取物件的逆向物流相结合的双向物流网络优化问题.以网点建设成本及运输成本最小为优化目标,提出一种新的综合考虑双向物流的快递物流网络模型,并设计一种改进的离散人工蜂群算法实现问题的有效求解.通过实际算例验证了提出的算法不但具有较高的求解效率,而且能够得到稳定且高质量的解.     

一种解多目标优化问题的基于分解的人工蜂群算法

在处理多目标优化问题时,如何平衡所得解集的分布性与收敛性是一个困难又重要的工作。为此,提出了解决该问题的一种基于目标空间分解的人工蜂群算法(MOABC/D)。首先采用一组方向向量将目标空间分解成一系列的子区域,并在每一个子区域至少保留一个解来保持解的分布性,其次提出一个基于分解的选择策略和2个基于信息交换的搜索策略来提高人工蜂群算法的搜索能力,并采用一个基于高斯分布的搜索策略来增强人工蜂群算法的搜索效率。为验证所提算法的性能,与8种同类算法在10个测试问题上进行比较。结果表明,本文所提算法得到的解集具有更好的收敛性能和分布性能。     

基于网络响应面的多目标优化方法

为提高多目标优化算法的收敛性以及Pareto解的分布均匀性,构建了基于网络响应面的多目标优化方法.将前馈（BP）网络以及自适应共振（ART）网络的优点相结合,充分利用各子目标每1次独立优化时获得的最优解,并将其作非占优判断后作为初始样本自适应地构建网络响应面,从而提高了Pareto解的收敛性以及多样性指标.对网络获得的每个新类进行各子目标值计算,同时对该子目标值做相似度计算,进一步剔除相似度高的样本,从而提高了Pareto解的分布性指标.通过常用的多目标优化测试函数验证该方法,并与改进的非支配排序遗传算法（NSGA-Ⅱ）以及随机权和算法作对比,结果表明该方法能明显改善多目标优化方法的各性能指标.     

遗传算法初始种群与操作参数的均匀设计

通过对遗传算法初始种群与操作参数设定问题的研究,认为初始种群的分布状态与算子操作参数的选取直接关系遗传算法的全局收敛性与搜索效率,对初始种群与各操作参数进行合理设定是应用遗传算法进行寻优计算的重要问题.同时,遗传算法的初始种群必须科学地表征解空间的信息,操作参数也必须兼顾多样性与快速性相互协调设置.基于优化设计思想提出应用均匀设计方法同时确定遗传算法的初始种群及其他操作参数的方法.利用均匀设计的等价准则提出一种简化计算的近似获得均匀初始种群的方法,仿真实例验证了这种方法的可行性、有效性.     

基于子种群的改进人工蜂群算法

针对人工蜂群算法以及现有改进算法的不足,提出了一种基于子种群的改进人工蜂群算法.此算法利用个体适应值与种群适应值平均值的比较,将种群划分为两个子种群,每个子种群采用不同的搜索方式,有效地平衡了不同搜索方式的探索和开发能力.此外,采用分段Logistic方程的初始化方法产生初始解,提高算法的收敛速度.与基本蜂群算法和其他改进蜂群算法进行比较,数值仿真结果表明,所提算法在处理复杂数值优化问题时具有更好的寻优精度和收敛速度.     

改进的两阶段算法求解差别费率车辆调度问题

针对车辆在负载和空载状态下不同的成本核算模型,提出了两阶段算法求解最小配送成本:第一阶段用改进的扫描算法求得满足问题约束条件的若干组非同质化的初始解;第二阶段采用这些解作为多样化的初始种群,并用改进的单亲遗传算法进行全局、大范围搜索,最终求得满意解.实例计算表明,算法能在较短的时间内求得理想解,满足了物流配送企业深挖内部潜力、有效控制成本的现实需要.