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

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

基于Petri网和模拟退火遗传算法的并行测试研究

针对自动测试系统中并行测试任务调度复杂、难以优化的问题，提出了一种Petri网技术和模拟退火遗传算法相结合的任务调度优化算法。首先为并行测试系统建立时间Petri网模型，然后将激发的变迁序列集作为并行测试任务调度路径。为了得到最优路径，引入模拟退火遗传（GASA）算法进行搜索。在搜索过程中，将能激发的变迁序列作为染色体，进行选择、交叉和变异。为了防止算法出现收敛过早，陷入局部最优解的现象，还要对个体进行模拟退火操作，最后得到测试完成时间最短的任务调度序列。     

求解多隔室车辆路径问题的改进粒子群优化算法

针对同时配送多种不能混装货物的多隔室车辆路径问题,建立了最小化车辆行驶成本的数学模型,并提出一种改进粒子群优化算法进行求解。该算法借鉴传统粒子群优化算法与模拟退火算法的思想,以粒子群算法为主框架,在粒子更新过程中引入模拟退火中的Metropolis准则,以一定概率接受劣解,使粒子在寻优过程中能够概率性地跳出局部最优。通过对经典车辆路径问题算例进行改编实验,并与已有文献、基本粒子群优化算法、基本人工蜂群算法分别进行对比分析表明,所提算法不但求解多隔室车辆路径问题有效,而且在求解质量上具有明显优势。     

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

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

时间依赖型同时取送货VRP及超启发式算法

为有效地协调正逆向物流,更好地体现城市物流配送速度时变的特点,降低物流配送成本,以时间依赖型同时取送货车辆路径问题为对象,建立其数学规划模型;设计了基于禁忌搜索的超启发式算法对其进行求解。在算法高层,设计了基于禁忌搜索评分制的选择策略及模拟退火的接收准则,实时监控底层启发式算子的性能并选择最优算子。通过基准实例测试及实验对比分析,表明了该算法能快速地找到满意解,所设计高层策略能保证算法跳出局部最优并快速收敛,从而证明了所提算法求解该问题的有效性。     

基于混合模拟退火算法求解电表配送车辆路径问题

为了使电能表集中配送业务中的车辆路径选择最优化,提出一种混合模拟退火算法。针对单相电能表集中检定后的配送需求,综合考虑各车型的固定成本、可变配送成本和配送里程,以总成本最小为目标,建立了具有固定车辆数的多车型车辆路径优化模型。基于多车型路径划分算法生成初始可行解,通过引入基于概率的多算子邻域搜索,采用禁忌搜索中的禁忌表对模拟退火算法进行改进,给出求解算法。以计量中心配送业务为实例,验证了模型的实用性和算法的有效性。     

[供应链调度]装卸一体化车辆路径问题的自适应并行遗传算法

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

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

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

考虑动态度和时间窗的两级车辆路径问题

为应对由客户的动态需求、大型货车的限行政策及配送时间窗的限制给供应商制定科学配送计划带来的严峻挑战,设计考虑动态度和时间窗的两级车辆路径优化方法。该方法基于客户动态增量概率阈值及动态度构建响应增量需求的车辆路径更新策略;将连续两级车辆路径优化问题映射为由配送中心到中转站和由中转站到客户的两个子网络的带时间窗的车辆路径问题(VRPTW),并在并行模拟退火算法框架下融合Or-opt, 2-opt, 2-opt^*,Swap/shift 4种邻域搜索策略求解VRPTW。用数据案例对模型及算法进行验证,表明所提策略及方法能较好地满足供应商对客户动态需求的响应,且具有良好的鲁棒性。     

混合粒子群优化算法求解多车辆拖动货物问题

为确定码头卜集装箱运输到目标位置的顺序和运输的车辆,提出了多车辆拖动货物问题,该问题需要考虑空间约束对车辆调度过程的影响.针对该问题,建立了整数规划数学模型,证明了该问题为NP完全难题,提出了四种解的编码方式,并利用模拟退火算法与粒子群优化算法结合的混合粒子群优化算法进行求解.将计算结果与模拟退火算法、粒子群优化算法进行了比较,结果表明,使用混合粒子群优化算法并采用先到先服务规则的两部分编码方法计算得到的解最好.