In this paper, a hybrid genetic algorithm （GA） is proposed for the traveling salesman problem （TSP） with pickup and delivery （TSPPD）. In our algorithm, a novel pheromone-based crossover operator is advanced that...In this paper, a hybrid genetic algorithm （GA） is proposed for the traveling salesman problem （TSP） with pickup and delivery （TSPPD）. In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.展开更多
The multitrip pickup and delivery problem with time windows and manpower planning(MTPDPTW-MP)determines a set of ambulance routes and finds staff assignment for a hospital. It involves different stakeholders with dive...The multitrip pickup and delivery problem with time windows and manpower planning(MTPDPTW-MP)determines a set of ambulance routes and finds staff assignment for a hospital. It involves different stakeholders with diverse interests and objectives. This study firstly introduces a multiobjective MTPDPTW-MP(MO-MTPDPTWMP) with three objectives to better describe the real-world scenario. A multiobjective iterated local search algorithm with adaptive neighborhood selection(MOILS-ANS) is proposed to solve the problem. MOILS-ANS can generate a diverse set of alternative solutions for decision makers to meet their requirements. To better explore the search space, problem-specific neighborhood structures and an adaptive neighborhood selection strategy are carefully designed in MOILS-ANS. Experimental results show that the proposed MOILS-ANS significantly outperforms the other two multiobjective algorithms. Besides, the nature of objective functions and the properties of the problem are analyzed. Finally, the proposed MOILS-ANS is compared with the previous single-objective algorithm and the benefits of multiobjective optimization are discussed.展开更多
The weapon transportation support scheduling problem on aircraft carrier deck is the key to restricting the sortie rate and combat capability of carrier-based aircraft.This paper studies the problem and presents a nov...The weapon transportation support scheduling problem on aircraft carrier deck is the key to restricting the sortie rate and combat capability of carrier-based aircraft.This paper studies the problem and presents a novel solution architecture.Taking the interference of the carrier-based aircraft deck layout on the weapon transportation route and precedence constraint into consideration,a mixed integer formulation is established to minimize the total objective,which is constituted of makespan,load variance and accumulative transfer time of support unit.Solution approach is developed for the model.Firstly,based on modeling the carrier aircraft parked on deck as convex obstacles,the path library of weapon transportation is constructed through visibility graph and Warshall-Floyd methods.We then propose a bi-population immune algorithm in which a population-based forward/backward scheduling technique,local search schemes and a chaotic catastrophe operator are embedded.Besides,the randomkey solution representation and serial scheduling generation scheme are adopted to conveniently obtain a better solution.The Taguchi method is additionally employed to determine key parameters of the algorithm.Finally,on a set of generated realistic instances,we demonstrate that the proposed algorithm outperforms all compared algorithms designed for similar optimization problems and can significantly improve the efficiency,and that the established model and the bi-population immune algorithm can effectively respond to the weapon support requirements of carrier-based aircraft under different sortie missions.展开更多
A new type of vehicle routing problem （VRP）, multiple vehicle routing problem integrated reverse logistics （MVRPRL）, is studied. In this problem, there is delivery or pickup （or both） and uncertain features in t...A new type of vehicle routing problem （VRP）, multiple vehicle routing problem integrated reverse logistics （MVRPRL）, is studied. In this problem, there is delivery or pickup （or both） and uncertain features in the demands of the clients. The deliveries of every client as uncertain parameters are expressed as triangular fuzzy numbers. In order to describe MVRPRL, a multi-objective fuzzy programming model with credibility measure theory is constructed. Then the simulationbased tabu search algorithm combining inter-route and intra-route neighborhoods and embedded restarts are designed to solve it. Computational results show that the tabu search algorithm developed is superior to sweep algorithms and that compared with handling each on separate routes, the transportation costs can be reduced by 43% through combining pickups with deliveries.展开更多
针对带时间窗的时间依赖型同时取送货车辆路径问题(Time Dependent Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows,TDVRPSPDTW),本文建立以车辆固定成本、驾驶员成本、燃油消耗及碳排放成本之和为优化...针对带时间窗的时间依赖型同时取送货车辆路径问题(Time Dependent Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows,TDVRPSPDTW),本文建立以车辆固定成本、驾驶员成本、燃油消耗及碳排放成本之和为优化目标的数学模型;并在传统蚁群算法的基础上,利用节约启发式构造初始解初始化信息素,改进状态转移规则,引入局部搜索策略,提出一种带自适应大邻域搜索的混合蚁群算法(Ant Colony Optimization with Adaptive Large Neighborhood Search,ACO-ALNS)进行求解;最后,分别选取基准问题算例和改编生成TDVRPSPDTW算例进行实验。实验结果表明:本文提出的ACO-ALNS算法可有效解决TDVRPSPDTW的基准问题;相较于模拟退火算法和带局部搜索的蚁群算法,本文算法求解得到的总配送成本最优值平均分别改善7.56%和2.90%;另外,相比于仅考虑碳排放或配送时间的模型,本文所构建的模型综合多种因素,总配送成本平均分别降低4.38%和3.18%,可有效提高物流企业的经济效益。展开更多
目的针对当前物流背景下普遍出现的送货公司外包、退换货频繁等问题,结合现有的碳排放政策,提出低碳背景下开放式同时送取货选址−路径模型(Low-Carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem,LO...目的针对当前物流背景下普遍出现的送货公司外包、退换货频繁等问题,结合现有的碳排放政策,提出低碳背景下开放式同时送取货选址−路径模型(Low-Carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem,LOLRPSPD),并通过改进野马算法进行求解。方法首先设计一种新的解码方式,使得原离散问题可以采用连续算法求解。之后,运用哈尔顿序列生成初始解,改进非线性进化概率因子,使用模拟二进制交叉,增加变异操作,以及精英保留、设置连续失败重新初始化等步骤,改进野马算法。最后,通过6组不同大小的算例将改进野马算法与原始野马算法、模拟退火算法、粒子群算法、遗传算法进行对比。结果针对中大型算例,改进野马算法远超原始野马算法。针对小型算例,在确保准确率的同时,改进野马算法对比各经典算法也在速度上具有优势。结论提出的LOLRPSD模型具备合理性,改进的野马算法针对选址路径问题具有较好的搜索能力。展开更多
外卖配取过程中实时订单的不断插入具有强烈的不确定性,需持续进行滚动优化以动态更新配取路径。动态条件下,有效地合并取餐与配送作业(dynamic order combination,DOC)可显著减少冗余路径。本文将动态配取路径规划问题转化为变长开放...外卖配取过程中实时订单的不断插入具有强烈的不确定性,需持续进行滚动优化以动态更新配取路径。动态条件下,有效地合并取餐与配送作业(dynamic order combination,DOC)可显著减少冗余路径。本文将动态配取路径规划问题转化为变长开放链滚动优化问题,并构建多目标滚动配取路径规划模型对DOC与节点排序进行集成决策。考虑滚动优化框架下紧前决策对紧后决策的调度影响,模型在兼顾配取效率和客户满意度的同时,考虑了基于look-forward的滚动调度后效性。针对该模型,本文基于NSGA-Ⅲ框架开发了多目标元启发式算法进行求解,并设计了基于插入限制规则的元胞数组解编码和混合PMX&SBX交叉方式以适应模型的复杂可行域结构。通过一系列的仿真实验,本文验证了所提出的模型和算法的有效性与优越性。展开更多
针对同时送取货的选址路径问题(Location-routing Problem with Simultaneous Pickup and Delivery,LRPSPD),设计一种改进烟花算法(Improved Firework Algorithm,IFWA)求解。首先,考虑仓库建设、车辆启用、车辆路径等成本因素,建立最小...针对同时送取货的选址路径问题(Location-routing Problem with Simultaneous Pickup and Delivery,LRPSPD),设计一种改进烟花算法(Improved Firework Algorithm,IFWA)求解。首先,考虑仓库建设、车辆启用、车辆路径等成本因素,建立最小成本的LRPSPD模型,该模型强调需求点的送货需求和取货需求只能由一辆车同时进行服务。其次,设计一种改进烟花算法,该算法结合贪心聚类算法生成初始解,由烟花爆炸算子操作生成邻域解,利用变异操作协助产生新种群。最后,通过使用混合免疫算法、模拟退火算法求解相同算例,对结果进行分析比较,验证模型的可行性和改进算法的有效性。展开更多
文摘In this paper, a hybrid genetic algorithm （GA） is proposed for the traveling salesman problem （TSP） with pickup and delivery （TSPPD）. In our algorithm, a novel pheromone-based crossover operator is advanced that utilizes both local and global information to construct offspring. In addition, a local search procedure is integrated into the GA to accelerate convergence. The proposed GA has been tested on benchmark instances, and the computational results show that it gives better convergence than existing heuristics.
基金supported by the National Key R&D Program of China(2018AAA0101203)the National Natural Science Foundation of China(61673403,71601191)the JSPS KAKENHI(JP17K12751)。
文摘The multitrip pickup and delivery problem with time windows and manpower planning(MTPDPTW-MP)determines a set of ambulance routes and finds staff assignment for a hospital. It involves different stakeholders with diverse interests and objectives. This study firstly introduces a multiobjective MTPDPTW-MP(MO-MTPDPTWMP) with three objectives to better describe the real-world scenario. A multiobjective iterated local search algorithm with adaptive neighborhood selection(MOILS-ANS) is proposed to solve the problem. MOILS-ANS can generate a diverse set of alternative solutions for decision makers to meet their requirements. To better explore the search space, problem-specific neighborhood structures and an adaptive neighborhood selection strategy are carefully designed in MOILS-ANS. Experimental results show that the proposed MOILS-ANS significantly outperforms the other two multiobjective algorithms. Besides, the nature of objective functions and the properties of the problem are analyzed. Finally, the proposed MOILS-ANS is compared with the previous single-objective algorithm and the benefits of multiobjective optimization are discussed.
基金the financial support of the National Natural Science Foundation of China(No.52102453)。
文摘The weapon transportation support scheduling problem on aircraft carrier deck is the key to restricting the sortie rate and combat capability of carrier-based aircraft.This paper studies the problem and presents a novel solution architecture.Taking the interference of the carrier-based aircraft deck layout on the weapon transportation route and precedence constraint into consideration,a mixed integer formulation is established to minimize the total objective,which is constituted of makespan,load variance and accumulative transfer time of support unit.Solution approach is developed for the model.Firstly,based on modeling the carrier aircraft parked on deck as convex obstacles,the path library of weapon transportation is constructed through visibility graph and Warshall-Floyd methods.We then propose a bi-population immune algorithm in which a population-based forward/backward scheduling technique,local search schemes and a chaotic catastrophe operator are embedded.Besides,the randomkey solution representation and serial scheduling generation scheme are adopted to conveniently obtain a better solution.The Taguchi method is additionally employed to determine key parameters of the algorithm.Finally,on a set of generated realistic instances,we demonstrate that the proposed algorithm outperforms all compared algorithms designed for similar optimization problems and can significantly improve the efficiency,and that the established model and the bi-population immune algorithm can effectively respond to the weapon support requirements of carrier-based aircraft under different sortie missions.
基金The National Natural Science Foundation of China(No.70772059)Youth Science and Technology Innovation Foundation of Nanjing Agriculture University(No.KJ06029)
文摘A new type of vehicle routing problem （VRP）, multiple vehicle routing problem integrated reverse logistics （MVRPRL）, is studied. In this problem, there is delivery or pickup （or both） and uncertain features in the demands of the clients. The deliveries of every client as uncertain parameters are expressed as triangular fuzzy numbers. In order to describe MVRPRL, a multi-objective fuzzy programming model with credibility measure theory is constructed. Then the simulationbased tabu search algorithm combining inter-route and intra-route neighborhoods and embedded restarts are designed to solve it. Computational results show that the tabu search algorithm developed is superior to sweep algorithms and that compared with handling each on separate routes, the transportation costs can be reduced by 43% through combining pickups with deliveries.
文摘针对带时间窗的时间依赖型同时取送货车辆路径问题(Time Dependent Vehicle Routing Problem with Simultaneous Pickup-Delivery and Time Windows,TDVRPSPDTW),本文建立以车辆固定成本、驾驶员成本、燃油消耗及碳排放成本之和为优化目标的数学模型;并在传统蚁群算法的基础上,利用节约启发式构造初始解初始化信息素,改进状态转移规则,引入局部搜索策略,提出一种带自适应大邻域搜索的混合蚁群算法(Ant Colony Optimization with Adaptive Large Neighborhood Search,ACO-ALNS)进行求解;最后,分别选取基准问题算例和改编生成TDVRPSPDTW算例进行实验。实验结果表明:本文提出的ACO-ALNS算法可有效解决TDVRPSPDTW的基准问题;相较于模拟退火算法和带局部搜索的蚁群算法,本文算法求解得到的总配送成本最优值平均分别改善7.56%和2.90%;另外,相比于仅考虑碳排放或配送时间的模型,本文所构建的模型综合多种因素,总配送成本平均分别降低4.38%和3.18%,可有效提高物流企业的经济效益。
文摘目的针对当前物流背景下普遍出现的送货公司外包、退换货频繁等问题,结合现有的碳排放政策,提出低碳背景下开放式同时送取货选址−路径模型(Low-Carbon Open Location-routing Problem with Simultaneous Pickup and Delivery Problem,LOLRPSPD),并通过改进野马算法进行求解。方法首先设计一种新的解码方式,使得原离散问题可以采用连续算法求解。之后,运用哈尔顿序列生成初始解,改进非线性进化概率因子,使用模拟二进制交叉,增加变异操作,以及精英保留、设置连续失败重新初始化等步骤,改进野马算法。最后,通过6组不同大小的算例将改进野马算法与原始野马算法、模拟退火算法、粒子群算法、遗传算法进行对比。结果针对中大型算例,改进野马算法远超原始野马算法。针对小型算例,在确保准确率的同时,改进野马算法对比各经典算法也在速度上具有优势。结论提出的LOLRPSD模型具备合理性,改进的野马算法针对选址路径问题具有较好的搜索能力。
文摘外卖配取过程中实时订单的不断插入具有强烈的不确定性,需持续进行滚动优化以动态更新配取路径。动态条件下,有效地合并取餐与配送作业(dynamic order combination,DOC)可显著减少冗余路径。本文将动态配取路径规划问题转化为变长开放链滚动优化问题,并构建多目标滚动配取路径规划模型对DOC与节点排序进行集成决策。考虑滚动优化框架下紧前决策对紧后决策的调度影响,模型在兼顾配取效率和客户满意度的同时,考虑了基于look-forward的滚动调度后效性。针对该模型,本文基于NSGA-Ⅲ框架开发了多目标元启发式算法进行求解,并设计了基于插入限制规则的元胞数组解编码和混合PMX&SBX交叉方式以适应模型的复杂可行域结构。通过一系列的仿真实验,本文验证了所提出的模型和算法的有效性与优越性。
文摘针对同时送取货的选址路径问题(Location-routing Problem with Simultaneous Pickup and Delivery,LRPSPD),设计一种改进烟花算法(Improved Firework Algorithm,IFWA)求解。首先,考虑仓库建设、车辆启用、车辆路径等成本因素,建立最小成本的LRPSPD模型,该模型强调需求点的送货需求和取货需求只能由一辆车同时进行服务。其次,设计一种改进烟花算法,该算法结合贪心聚类算法生成初始解,由烟花爆炸算子操作生成邻域解,利用变异操作协助产生新种群。最后,通过使用混合免疫算法、模拟退火算法求解相同算例,对结果进行分析比较,验证模型的可行性和改进算法的有效性。
