This paper gives integer linear programming (ILP) models for scheduling the League Phase of one of the most popular professional club competitions in the world, UEFA Champion’s League. There are 36 teams in the compe...This paper gives integer linear programming (ILP) models for scheduling the League Phase of one of the most popular professional club competitions in the world, UEFA Champion’s League. There are 36 teams in the competition, but each team plays only 8 other teams in the League Phase. Thus, the difficulty or ease of a team’s opponents, known as strength of schedule (SOS), compared to other teams will be different. Our main ILP model aims to minimize the maximum difference between SOS of any two teams, thus making the schedule as fair as possible. We also give a model for creating a timetable of all the matchups obtained by the first model. The models were implemented and tested using optimization software AMPL. Our main model obtained a schedule with a difference 0.4 between the highest and the lowest SOS, while that difference is 19 for the actual 2024-2025 competition. Thus, our model returns a schedule that is significantly fairer compared to the actual competition.展开更多
Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show th...Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show that it is possible to accommodate realistic models for energy consumption and communication protocols into integer linear programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models that are also shown to provide efficient and practical solving tools. We present a strategy to substantially speed up the convergence of the solving process of our algorithm. This strategy introduces a practical drawback, however, in the characteristics of the optimal solutions retrieved. A method to overcome this drawback is discussed. Computational experiments are reported.展开更多
飞机货舱中非集装器的配载是重要的运输环节,而如何保障非集装器的配载,是亟须研究的重要内容。其中二维矩形切割排样问题是解决非集装器运输的重要理论方法。二维矩形切割排样理论在原材料切割、装箱等问题中有着广泛应用,但尚无很好...飞机货舱中非集装器的配载是重要的运输环节,而如何保障非集装器的配载,是亟须研究的重要内容。其中二维矩形切割排样问题是解决非集装器运输的重要理论方法。二维矩形切割排样理论在原材料切割、装箱等问题中有着广泛应用,但尚无很好的求解算法。该方法会因求解速度而拖累整个实际生产作业进度。因此,本文提出了二维切割排样的混合整数线性规划(Mixed-integer linear programming,MILP)模型,模型目标是以矩形板面积利用率和切割排样价值最大为目标,模型考虑了不超边界、不重叠、可正交旋转等限制。设计了启发式分组策略的求解算法:首先基于启发式把矩形块分组为不同组别的小矩形块,降低变量和计算规模;其次,采用混合整数规划精确算法对每个小矩形块进行切割排样。以经典Benchmark实验数据为例,将Gurobi分组与Gurobi、CutLogic2D、基于遗传算法和最低水平线算法的混合算法对比。实验结果表明,CutLogic2D综合求解质量和速度较好;Gurobi分组方法是一种启发式算法,总体上要稍差于CutLogic2D;遗传算法和最低水平线算法因是启发式算法且未使用分组策略,和Gurobi分别在部分算例上求解时间相对较长,达到了7200 s,这是无法接受的。展开更多
The rapid evolution of unmanned aerial vehicle(UAV)technology and autonomous capabilities has positioned UAV as promising last-mile delivery means.Vehicle and onboard UAV collaborative delivery is introduced as a nove...The rapid evolution of unmanned aerial vehicle(UAV)technology and autonomous capabilities has positioned UAV as promising last-mile delivery means.Vehicle and onboard UAV collaborative delivery is introduced as a novel delivery mode.Spatiotemporal collaboration,along with energy consumption with payload and wind conditions play important roles in delivery route planning.This paper introduces the traveling salesman problem with time window and onboard UAV(TSPTWOUAV)and emphasizes the consideration of real-world scenarios,focusing on time collaboration and energy consumption with wind and payload.To address this,a mixed integer linear programming(MILP)model is formulated to minimize the energy consumption costs of vehicle and UAV.Furthermore,an adaptive large neighborhood search(ALNS)algorithm is applied to identify high-quality solutions efficiently.The effectiveness of the proposed model and algorithm is validated through numerical tests on real geographic instances and sensitivity analysis of key parameters is conducted.展开更多
The circle geometric constraint model （CGCM） was put forward for resolving the open-pit mine ore-matching problems （OMOMP）. By adopting the approaches of graph theory, block model of blasted piles was abstracted i...The circle geometric constraint model （CGCM） was put forward for resolving the open-pit mine ore-matching problems （OMOMP）. By adopting the approaches of graph theory, block model of blasted piles was abstracted into a set of nodes and directed edges, which were connected together with other nodes in the range of circle constraints, to describe the mining sequence. Also, the constructing method of CGCM was introduced in detail. The algorithm of CGCM has been realized in the DIM1NE system, and applied to a short-term （5 d） program calculation for ore-matching of a cement limestone mine in Hebei Province, China. The applications show that CGCM can well describe the mining sequence of ore blocks and its mining geometric constraints in the process of mining blasted piles. This model, which is applicable for resolving OMOMP under complicated geometric constraints with accurate results, provides effective ways to solve the problems of open-pit ore-matching.展开更多
文摘This paper gives integer linear programming (ILP) models for scheduling the League Phase of one of the most popular professional club competitions in the world, UEFA Champion’s League. There are 36 teams in the competition, but each team plays only 8 other teams in the League Phase. Thus, the difficulty or ease of a team’s opponents, known as strength of schedule (SOS), compared to other teams will be different. Our main ILP model aims to minimize the maximum difference between SOS of any two teams, thus making the schedule as fair as possible. We also give a model for creating a timetable of all the matchups obtained by the first model. The models were implemented and tested using optimization software AMPL. Our main model obtained a schedule with a difference 0.4 between the highest and the lowest SOS, while that difference is 19 for the actual 2024-2025 competition. Thus, our model returns a schedule that is significantly fairer compared to the actual competition.
文摘Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show that it is possible to accommodate realistic models for energy consumption and communication protocols into integer linear programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models that are also shown to provide efficient and practical solving tools. We present a strategy to substantially speed up the convergence of the solving process of our algorithm. This strategy introduces a practical drawback, however, in the characteristics of the optimal solutions retrieved. A method to overcome this drawback is discussed. Computational experiments are reported.
文摘飞机货舱中非集装器的配载是重要的运输环节,而如何保障非集装器的配载,是亟须研究的重要内容。其中二维矩形切割排样问题是解决非集装器运输的重要理论方法。二维矩形切割排样理论在原材料切割、装箱等问题中有着广泛应用,但尚无很好的求解算法。该方法会因求解速度而拖累整个实际生产作业进度。因此,本文提出了二维切割排样的混合整数线性规划(Mixed-integer linear programming,MILP)模型,模型目标是以矩形板面积利用率和切割排样价值最大为目标,模型考虑了不超边界、不重叠、可正交旋转等限制。设计了启发式分组策略的求解算法:首先基于启发式把矩形块分组为不同组别的小矩形块,降低变量和计算规模;其次,采用混合整数规划精确算法对每个小矩形块进行切割排样。以经典Benchmark实验数据为例,将Gurobi分组与Gurobi、CutLogic2D、基于遗传算法和最低水平线算法的混合算法对比。实验结果表明,CutLogic2D综合求解质量和速度较好;Gurobi分组方法是一种启发式算法,总体上要稍差于CutLogic2D;遗传算法和最低水平线算法因是启发式算法且未使用分组策略,和Gurobi分别在部分算例上求解时间相对较长,达到了7200 s,这是无法接受的。
基金Fundamental Research Funds for the Central Universities(2024JBZX038)National Natural Science F oundation of China(62076023)。
文摘The rapid evolution of unmanned aerial vehicle(UAV)technology and autonomous capabilities has positioned UAV as promising last-mile delivery means.Vehicle and onboard UAV collaborative delivery is introduced as a novel delivery mode.Spatiotemporal collaboration,along with energy consumption with payload and wind conditions play important roles in delivery route planning.This paper introduces the traveling salesman problem with time window and onboard UAV(TSPTWOUAV)and emphasizes the consideration of real-world scenarios,focusing on time collaboration and energy consumption with wind and payload.To address this,a mixed integer linear programming(MILP)model is formulated to minimize the energy consumption costs of vehicle and UAV.Furthermore,an adaptive large neighborhood search(ALNS)algorithm is applied to identify high-quality solutions efficiently.The effectiveness of the proposed model and algorithm is validated through numerical tests on real geographic instances and sensitivity analysis of key parameters is conducted.
基金Project(2011AA060407) supported by the National High Technology Research and Development Program of ChinaProject(51074073) supported by the National Natural Science Foundation of China
文摘The circle geometric constraint model （CGCM） was put forward for resolving the open-pit mine ore-matching problems （OMOMP）. By adopting the approaches of graph theory, block model of blasted piles was abstracted into a set of nodes and directed edges, which were connected together with other nodes in the range of circle constraints, to describe the mining sequence. Also, the constructing method of CGCM was introduced in detail. The algorithm of CGCM has been realized in the DIM1NE system, and applied to a short-term （5 d） program calculation for ore-matching of a cement limestone mine in Hebei Province, China. The applications show that CGCM can well describe the mining sequence of ore blocks and its mining geometric constraints in the process of mining blasted piles. This model, which is applicable for resolving OMOMP under complicated geometric constraints with accurate results, provides effective ways to solve the problems of open-pit ore-matching.
