A Multiple-Neighborhood-Based Parallel Composite Local Search Algorithm for Timetable Problem

This paper presents a parallel composite local search algorithm based on multiple search neighborhoods to solve a special kind of timetable problem. The new algorithm can also effectively solve those problems that can be solved by general local search algorithms. Experimental results show that the new algorithm can generate better solutions than general local search algorithms.

A simulation-based optimization approach for passenger train timetabling with periodic track maintenance and stops for praying

This paper presents two optimization methods for solving the passenger train timetabling problem to minimize the total delay time in the single track railway networks. The goal of the train timetable problem is to determine departure and arrival times to or from each station in order to prevent collisions between trains and effective utilization of resources. The two proposed methods are based on integration of a simulation and an optimization method to simulate train traffic flow and generate near optimal train timetable under realistic con- straints including stops for track maintenance and praying. The first proposed method integrates a cellular automata （CA） simulation model with genetic algorithm optimiza- tion method. In the second proposed approach, a CA simulation model combines with dynamically dimensioned search optimization method. The proposed models are applied to hypothetical case study to demonstrate the merit of them. The Islamic Republic of Iran Railways （IRIR） data and regulations have been used to optimize train timetable. The results show the first method is more effi- cient than the second method to obtain near optimal train timetabling.

考虑可变接续时间窗的高铁周期列车运行图优化

精准高效的换乘接续设计对于周期列车运行图在我国的全面推广至关重要。我国高速铁路网络结构复杂、空间跨度广,不同距离的换乘客流OD所能接受的中转换乘时间范围有着明显的不同。现有研究对换乘接续时间的考虑多基于固定接续时间窗,造成实际换乘时间与各OD旅客可接受的换乘时间不匹配,限制了换乘服务水平的进一步提升。基于此,结合“事件-活动”网络和周期事件规划问题(Periodic Event Scheduling Problem,PESP),构建了考虑可变接续时间窗的高铁周期列车运行图优化模型,实现了列车接续关系选择、OD换乘接续关系分配、换乘时间优化的同步决策。模型首先引入OD换乘接续关系分配变量,使得模型可在优化过程中动态决策列车接续关系是否为特定客流OD提供服务。在此基础上,引入了可变接续时间窗约束,实现列车接续时间窗根据所分配客流OD合理换乘时间范围动态确定。同时,设计了最小化周期列车运行图换乘服务水平与理想服务水平偏差的线性化目标函数,使得模型得以在GUROBI整数规划求解器中求解。研究案例编制了京沪高铁以及与之衔接的部分高铁线路路网周期列车运行图,与固定换乘接续时间窗的研究案例相比,换乘服务频率和换乘接续时间指标均有显著提升,验证了所提模型的正确性及有效性。

UTP中一种分阶段求解算法

大学课程表问题UTP是一个应用广泛的、典型的组合优化和不确定性调度问题,并且已经被证明是NP完全问题。本文提出了一种分阶段解决大学课程表问题的算法,将课程表问题划分为时间安排和空间安排两个阶段,分别采用智能算法和最佳适应算法逐段求解,并最终求得全局较优解。通过设计实验对算法进行分析,结果表明这种分阶段决策算法在保证课表质量的同时能够有效减小遗传算法在求解UTP问题中的复杂度,提高程序的运行速度。

TTP中合班问题的模型与实现

将TTP中的合班问题单独提出,给出了解决该问题的数学模型及可行的算法,且在求解合班数学模型的过程中,提出了严格合班对角线法和改进的严格合班对角线法,然后通过班级组合问题的解决,使课程表问题得到了简化.

回答集程序设计在TTP求解中的应用

课程表问题是一个应用广泛、典型的组合优化和不确性调度问题,目前存在的求解算法多数缺乏声明性。一种基于回答集程序设计的TTP求解方法,可成功生成正确解集(答案),并用实验结果论证了算法的可行性。

Analysis on the Influencing Factors and Comprehensive Management of Environmental Problems in Dongping Lake

[Objective]We aimed to study the influencing factors and comprehensive management of environmental problems in Dongping Lake.[Method]Based on field investigation and historical data,environmental problems of Dongping Lake and their influencing factors were analyzed,and seven measures about comprehensive management of environmental issues and ecological protection of Dongping Lake were put forward.[Result]During recent years,the content of total nitrogen and total phosphorus in Dongping Lake showed a decreasing trend,but the water was still in the eutrophic state.The environmental problems of Dongping Lake,like flood,drought and pollution,are closely linked to natural and man-made factors,such as regional seasonal precipitation,industrial and agricultural pollution,etc.In order to control the environmental problems of Dongping Lake,we should strengthen the construction and management of wetland nature reserves,develop ecological agriculture,establish an integral system for environmental monitoring and information management,reinforce propaganda and education to improve residents’ environmental consciousness,etc.[Conclusion]The research could provide scientific references for the comprehensive management of environmental problems in Dongping Lake and its basin.

TP拉链机的改进

分析了TP拉链机轨道、车轮、料斗磨损,TP拉链机跑偏,TP拉链机过载保护的不足,TP拉链机车轮轴承不能满足使用要求等问题发生的原因,提出了相应的改进方案。通过对方案的实施,取得了良好的效果。

Annealing Harmony Search Algorithm to Solve the Nurse Rostering Problem

A real-life problem is the rostering of nurses at hospitals.It is a famous nondeterministic,polynomial time(NP)-hard combinatorial optimization problem.Handling the real-world nurse rostering problem(NRP)constraints in distributing workload equally between available nurses is still a difficult task to achieve.The international shortage of nurses,in addition to the spread of COVID-19,has made it more difficult to provide convenient rosters for nurses.Based on the literature,heuristic-based methods are the most commonly used methods to solve the NRP due to its computational complexity,especially for large rosters.Heuristic-based algorithms in general have problems striking the balance between diversification and intensification.Therefore,this paper aims to introduce a novel metaheuristic hybridization that combines the enhanced harmony search algorithm(EHSA)with the simulated annealing(SA)algorithm called the annealing harmony search algorithm(AHSA).The AHSA is used to solve NRP from a Malaysian hospital.The AHSA performance is compared to the EHSA,climbing harmony search algorithm(CHSA),deluge harmony search algorithm(DHSA),and harmony annealing search algorithm(HAS).The results show that the AHSA performs better than the other compared algorithms for all the tested instances where the best ever results reported for the UKMMC dataset.

Mathematical model and simulated annealing algorithm for Chinese high school timetabling problems under the new curriculum innovation

As the first attempt,this paper proposes a model for the Chinese high school timetabling problems(CHSTPs)under the new curriculum innovation which was launched in 2011 by the Chine6e government.Aooording 10 the new our riculum innovation,students in high school can choose subjects that they are interested in instead of being forced to select one of the two study directions,namely,Science and Liberal Arts.Meanwhile,they also need to attend compulsory subjects as traditions.CHSTPs are student-oriented and involve more student constraints that make them more complex than the typi-cal"Class-Teacher model",in which the element"Teacher"is the primary constraint.In this paper,we first describe in detail the mathematical model of CHSTPs and then design a new two-part representation for the candidate solution.Based on the new representation,we adopt a two-phase simulated annealing(SA)algorithm to solve CHSTPs.A total number of 45 synthetic instances with different amounts of classes,teachers,and levels of student constraints are generated and used to ilustrate the characteristics of the CHSTP model and the effectiveness of the designed representation and algorithm.Finally,we apply the proposed model,the designed two-part representation and the two-phase SA on10 real high schools.

A memetic algorithm based on hyper-heuristics for examination timetabling problems

Purpose–The examination timetabling problem is an NP-hard problem.A large number of approaches for this problem are developed to find more appropriate search strategies.Hyper-heuristic is a kind of representative methods.In hyper-heuristic,the high-level search is executed to construct heuristic lists by traditional methods(such as Tabu search,variable neighborhoods and so on).The purpose of this paper is to apply the evolutionary strategy instead of traditional methods for high-level search to improve the capability of global search.Design/methodology/approach–This paper combines hyper-heuristic with evolutionary strategy to solve examination timetabling problems.First,four graph coloring heuristics are employed to construct heuristic lists.Within the evolutionary algorithm framework,the iterative initialization is utilized to improve the number of feasible solutions in the population;meanwhile,the crossover and mutation operators are applied to find potential heuristic lists in the heuristic space(high-level search).At last,two local search methods are combined to optimize the feasible solutions in the solution space(low-level search).Findings–Experimental results demonstrate that the proposed approach obtains competitive results and outperforms the compared approaches on some benchmark instances.Originality/value–The contribution of this paper is the development of a framework which combines evolutionary algorithm and hyper-heuristic for examination timetabling problems.

基于协同发车的区域公交时刻表生成模型研究

编制出能够最大限度地减少乘客在不同线路交叉点处换乘等待时间的公交时刻表是实现公交调度区域化的关键任务之一,而协同发车是实现这一目标的有效手段.本文将以乘客换乘时间最少为目标的区域公交时刻表的编制问题,归结为一类特殊的带有协同系数且无容量约束的0-1背包问题,并定义了协同系数,建立了相应的数学模型,给出了基于嵌套式的禁忌搜索算法的模型解法.实验计算结果表明,用本文设计的算法求解这类特殊的0-1背包问题可以取得良好的计算结果,该算法是可行的,也是有效的.

用自适应的遗传算法求解大学课表安排问题

课程表问题又称时间表问题 (timetable problem) ,是一个多因素的优化决策问题 ,也是组合规划中的典型问题 .本文研究的是大学课表安排问题 ,根据大学课表安排的特点并以优化时间和空间两种资源为目标 ,将课程分为 P、Q两类 .采用鲁棒性比较好的遗传算法 ,并对两类课分别给出其染色体编码和适应度函数 ,并采用了自适应的杂交和变异概率 。

基于演化算法的一类时间表问题的自动求解

本文给出了一种有效的基于演化算法的求解大学的时间表问题 (编排课程和考试 ) ,即在很强的资源约束条件下将一些事件 (课程或考试 )安排到时间段和空间位置的问题的方法 .此方法采用直接的时间表编码表示和启发式演化算子 ,并通过惩罚函数保证对约束条件的满足 .计算实验表明该方法在求解大学考试时间表问题中是有效的 .

基于小生境遗传算法的排课问题研究

建立排课问题的数学优化模型,构建其基本求解框架,引入遗传算法并设计多种改进方案,包括新的二进制编码方案、初始种群生成方案、适应度函数设计方案、小生境策略、自适应交叉概率和自适应变异概率设计方案。仿真结果表明,该算法能够满足排课问题的多重约束条件,更有效地解决排课问题。

基于遗传算法求解时间表问题

基于遗传算法求解时间表问题,通过具体时间表问题的描述和分析,定义了一个新颖的染色体编码方式,然后基于该编码,进一步分析并设计了遗传操作—交叉和变异。算法运行结果显示该方法是可行的。

应用遗传算法求解排课问题

给出了排课问题的描述和五元组定义。针对排课问题的关键因素,根据遗传算法的特点,设计了排课问题的编码方式,对求解的目标进行了优化,满足了实际应用。

遗传算法在排课问题中的运用

遗传算法借鉴生物界自然选择和遗传机制,使用群体搜索技术,处理传统搜索方法难以解决的复杂的非线性问题.排课问题是一个多因素的优化决策问题,是组合规划中的典型问题,属于NP完全类问题.根据大学课表的特点,采用遗传算法,给出染色体编码和适应度函数,并采用了自适应的调整概率进行排课,数值试验证明了方法的有效性和可行性.

城轨线路运营时段前车底空驶出场路径优化

城市轨道交通线路运营时段初许多列车需由从车场始发的车底来担当,由此,运营时段前许多车底集中从车场出发,通过直达或折返路径直接空驶至担当列车的始发站。本文探讨具有多交路、多车场和多车型的车底运用问题,为运营时段初各列车所需的车底指派配属车场和对应的空驶出场路径。以总空驶距离最小为目标,考虑车场检修和出车能力以及折返站能力等限制,构建混合整数线性规划模型。该模型的规模只随车场、折返站和列车的数量呈多项式增长,采用商业优化软件便可快速求解大规模问题。计算结果表明,该优化方法在解的质量上优于现场的经验方法,且通过开放未启用的折返站或延长车场的可用出车时间有望进一步缩短车底的总空驶距离。