Considering that the vehicle routing problem （VRP） with many extended features is widely used in actual life, such as multi-depot, heterogeneous types of vehicles, customer service priority and time windows etc., a ...Considering that the vehicle routing problem （VRP） with many extended features is widely used in actual life, such as multi-depot, heterogeneous types of vehicles, customer service priority and time windows etc., a mathematical model for multi-depot heterogeneous vehicle routing problem with soft time windows （MDHVRPSTW） is established. An improved ant colony optimization （IACO） is proposed for solving this model. First, MDHVRPSTW is transferred into different groups according to the nearest principle, and then the initial route is constructed by the scanning algorithm （SA）. Secondly, genetic operators are introduced, and crossover probability and mutation probability are adaptively adjusted in order to improve the global search ability of the algorithm. Moreover, the smooth mechanism is used to improve the performance of the ant colony optimization （ACO）. Finally, the 3-opt strategy is used to improve the local search ability. The proposed IACO was tested on three new instances that were generated randomly. The experimental results show that IACO is superior to the other three existing algorithms in terms of convergence speed and solution quality. Thus, the proposed method is effective and feasible, and the proposed model is meaningful.展开更多
为了克服蚁群算法(Ant Colony Optimization,ACO)搜索初期信息匮乏、信息素累积时间长、求解速度慢的缺点,结合具有快速全局搜索能力的遗传算法(genetic algorithm,GA),同时引入混沌搜索和平滑机制,采用混沌搜索产生初始种群可以克服生...为了克服蚁群算法(Ant Colony Optimization,ACO)搜索初期信息匮乏、信息素累积时间长、求解速度慢的缺点,结合具有快速全局搜索能力的遗传算法(genetic algorithm,GA),同时引入混沌搜索和平滑机制,采用混沌搜索产生初始种群可以克服生成大量非可行解的缺陷,加速染色体向最优解收敛,平滑机制有助于对搜索空间进行更有效的搜索,构成混沌蚁群优化算法(Chaos Ant Colony Optimization,CACO)。建立物流配送中心选址(logistic distribution center location)与车辆路径问题(vehicle routing problem,VRP)的数学模型,分别应用CACO和GA求解,对50客户规模的问题模型仿真,结果表明CACO优于GA。展开更多
针对带软时间窗的开放式关联运输调度问题(Open Incident Vehicle Routing Problem with Soft Time Windows,OIVRPSTW),联系实际应用中连锁店超市中货物供应的车辆路径问题,介绍了粒子群算法的基本原理,采用一种非线性动态自适应调节惯...针对带软时间窗的开放式关联运输调度问题(Open Incident Vehicle Routing Problem with Soft Time Windows,OIVRPSTW),联系实际应用中连锁店超市中货物供应的车辆路径问题,介绍了粒子群算法的基本原理,采用一种非线性动态自适应调节惯性权重因子的方法,使得惯性系数会随着粒子目标值的变化而自动改变,结合混沌搜索产生初始种群的方法,设计了一种混沌粒子群优化算法。同时也设计了引入了模拟退火机制的混沌遗传算法,自适应地调整交叉概率和变异概率。并用这两种算法来对OIVRPSTW求解,然后与基本的遗传算法求解此模型的结果相比较。实例证明用混沌搜索产生初始种群的方法在求解此类开放式关联运输调度问题是可行的,能取得令人满意的效果。展开更多
针对带硬时间窗的水果运输调度问题(Fruits in Vehicle Routing Problem with Hard Time Windows,FVRPHTW),联系实际应用中水果易腐的特性及运输途中的路况因素,采用蚁群算法、模拟退火算法和禁忌搜索算法来对FVRPHTW求解,并分析3种算...针对带硬时间窗的水果运输调度问题(Fruits in Vehicle Routing Problem with Hard Time Windows,FVRPHTW),联系实际应用中水果易腐的特性及运输途中的路况因素,采用蚁群算法、模拟退火算法和禁忌搜索算法来对FVRPHTW求解,并分析3种算法的优缺点。实例证明,这些算法对求解水果运输调度问题是可行的,模拟退火算法略优于其他两种算法。展开更多
基金The National Natural Science Foundation of China(No.61074147)the Natural Science Foundation of Guangdong Province(No.S2011010005059)+2 种基金the Foundation of Enterprise-University-Research Institute Cooperation from Guangdong Province and Ministry of Education of China(No.2012B091000171,2011B090400460)the Science and Technology Program of Guangdong Province(No.2012B050600028)the Science and Technology Program of Huadu District,Guangzhou(No.HD14ZD001)
文摘Considering that the vehicle routing problem （VRP） with many extended features is widely used in actual life, such as multi-depot, heterogeneous types of vehicles, customer service priority and time windows etc., a mathematical model for multi-depot heterogeneous vehicle routing problem with soft time windows （MDHVRPSTW） is established. An improved ant colony optimization （IACO） is proposed for solving this model. First, MDHVRPSTW is transferred into different groups according to the nearest principle, and then the initial route is constructed by the scanning algorithm （SA）. Secondly, genetic operators are introduced, and crossover probability and mutation probability are adaptively adjusted in order to improve the global search ability of the algorithm. Moreover, the smooth mechanism is used to improve the performance of the ant colony optimization （ACO）. Finally, the 3-opt strategy is used to improve the local search ability. The proposed IACO was tested on three new instances that were generated randomly. The experimental results show that IACO is superior to the other three existing algorithms in terms of convergence speed and solution quality. Thus, the proposed method is effective and feasible, and the proposed model is meaningful.
文摘为了克服蚁群算法(Ant Colony Optimization,ACO)搜索初期信息匮乏、信息素累积时间长、求解速度慢的缺点,结合具有快速全局搜索能力的遗传算法(genetic algorithm,GA),同时引入混沌搜索和平滑机制,采用混沌搜索产生初始种群可以克服生成大量非可行解的缺陷,加速染色体向最优解收敛,平滑机制有助于对搜索空间进行更有效的搜索,构成混沌蚁群优化算法(Chaos Ant Colony Optimization,CACO)。建立物流配送中心选址(logistic distribution center location)与车辆路径问题(vehicle routing problem,VRP)的数学模型,分别应用CACO和GA求解,对50客户规模的问题模型仿真,结果表明CACO优于GA。
文摘针对带软时间窗的开放式关联运输调度问题(Open Incident Vehicle Routing Problem with Soft Time Windows,OIVRPSTW),联系实际应用中连锁店超市中货物供应的车辆路径问题,介绍了粒子群算法的基本原理,采用一种非线性动态自适应调节惯性权重因子的方法,使得惯性系数会随着粒子目标值的变化而自动改变,结合混沌搜索产生初始种群的方法,设计了一种混沌粒子群优化算法。同时也设计了引入了模拟退火机制的混沌遗传算法,自适应地调整交叉概率和变异概率。并用这两种算法来对OIVRPSTW求解,然后与基本的遗传算法求解此模型的结果相比较。实例证明用混沌搜索产生初始种群的方法在求解此类开放式关联运输调度问题是可行的,能取得令人满意的效果。
文摘针对带硬时间窗的水果运输调度问题(Fruits in Vehicle Routing Problem with Hard Time Windows,FVRPHTW),联系实际应用中水果易腐的特性及运输途中的路况因素,采用蚁群算法、模拟退火算法和禁忌搜索算法来对FVRPHTW求解,并分析3种算法的优缺点。实例证明,这些算法对求解水果运输调度问题是可行的,模拟退火算法略优于其他两种算法。
