运输网络运量分配问题的模型及算法研究

针对我国在运量分配模型及算法方面研究比较薄弱的现状,本文对此问题进行了系统深人的研究,应用运筹学、计算机科学的新的理论和方法,建立了多目标运量分配优化模型,且在模型中,将一些重要特性考虑成运输流量的函数,从而可使分配结果更符合实际情况。同时为求解该模型,本文研究设计了鲁棒性强、高效、实用的自适应搜索算法。     

The hierarchical model for load balancing on two machines

Following previous work, we consider the hierarchical load balancing model on two machines of possibly different speeds. We first focus on maximizing the minimum machine load and show that no competitive algorithm exists for this problem. We overcome this barrier in two ways, both related to previously known models. The first one is fractional assignment, where each job can be arbitrarily split between the machines. The second one is a semi-online model where the sum of jobs is known in advance. We design algorithms of best possible competitive ratios for both these cases. Furthermore, we show that the combination of the two models leads to the existence of an optimal algorithm (i.e., an algorithm of competitive ratio 1). This algorithm is clearly optimal for the makespan minimization problem as well. For the latter problem, we consider the fractional assignment model and design an algorithm of best possible competitive ratio for it. This work was submitted as the M.Sc. thesis of the first author.     

基于ASRank和MMAS的蚁群算法求解飞机指派问题

本文将航班串的飞机指派问题归结为车辆路径问题,考虑连续航班串之间衔接时间、衔接机场的约束、每架飞机的总飞行时间约束,建立了带有飞行时间约束的车辆路径问题的混合整数规划模型。构造了蚁群系统算法,引入基于排序的蚂蚁系统和最大最小蚂蚁系统算法的信息素更新策略。选取某航空公司7组初始航班串集合进行测试,并对算法中的重要参数进行了分析。实验结果表明,本文设计的模型和算法可以有效地减少连续航班串之间的总衔接时间,在可接受的计算时间内获得满意解。     

公交系统随机平衡网络设计模型及求解算法

本文根据公交网络的具体特点,对公交网络进行了系统的描述,提出一个双层规划模型来描述随机平衡公交网络设计问题。在双层规划模型中,上层模型为一个标准的公交网络设计模型,下层模型是一个公交网络随机平衡配流模型。针对所提出的模型,设计了基于灵敏度分析的求解算法。最后,给出一个简单算例加以证明。     

考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究

在政府政策大力支持以及社会环境意识不断增长的背景下,电动汽车在物流配送行业快速普及。电动汽车参与的物流配送服务需要物流专员、电动汽车和顾客三方协作完成。因此,在传统车辆配送路径优化的基础上,车辆的多样性、充电策略、人车的匹配以及服务时间差异化等因素都会影响物流运营成本。本文提出了考虑差异化服务成本的多车型电动汽车路径优化与充电策略问题并建立了该问题的整数规划数学模型。其次,提出了混合启发式算法MCWGATS,并通过多组算例验证了算法的有效性。最后,采用多组算例分析了多车型和差异化服务时间对运营成本的影响。实验结果表明,该模型有助于物流企业提高人员、物流车辆、服务时间等资源的利用效率,降低运营成本。     

物流配送中心直通配送运作时间优化研究

针对直通配送需要尽可能缩短配送中心内运作时间的问题,利用总运作时间与完成所有操作所需时间最长的货源操作时间等价的关系,构建了以最小化总运作时间为目标的配送中心内货源及目的地的出入站口指派问题模型。设计了对个体分2段进行编码、交叉和变异等操作的遗传算法,对模型进行求解,通过算例验证了模型及其算法能够对配送中心内的运作时间进行有效优化。     

A heuristic for the time constrained asymmetric linear sum assignment problem

The linear sum assignment problem is a fundamental combinatorial optimisation problem and can be broadly defined as: given an \(n \times m, m \ge n\) benefit matrix \(B = (b_{ij})\), matching each row to a different column so that the sum of entries at the row-column intersections is maximised. This paper describes the application of a new fast heuristic algorithm, Asymmetric Greedy Search, to the asymmetric version (\(n \ne m\)) of the linear sum assignment problem. Extensive computational experiments, using a range of model graphs demonstrate the effectiveness of the algorithm. The heuristic was also incorporated within an algorithm for the non-sequential protein structure matching problem where non-sequential alignment between two proteins, normally of different numbers of amino acids, needs to be maximised.     

炼钢连铸生产调度问题的两阶段遗传算法

将炼钢连铸生产过程抽象为混合流水车间,建立了0-1型混合整数线性规划调度模型。模型将严格连续浇注作为等式约束,并通过分段惩罚来平衡炉次的驻留时间。在对模型进行Benders分解的基础上,提出了将GA与LP结合的两阶段遗传算法。在算法设计中,提出了一种新的染色体编码来表示炉次设备指派与排序方案,给出了相应的遗传操作方法。算法的第一阶段通过最小化设备析取冲突来寻找高质量的种群,第二阶段通过求解线性规划模型来指导遗传算法的迭代过程。基于生产实际数据的仿真实验表明,该算法能够有效求解炼钢连铸生产调度问题。     

基于遗传算法的装备采购决策优化研究

在装备采购中，由于需求单位地域分布和担负的任务各不相同，对装备的品种、数量、时限要求也就不一样，如何使装备采购科学化、合理化，是一个涉及多变量、多目标的复杂系统问题。在综合考虑装备采购各项因素的基础上，构建多约束条件下的多目标模糊指派模型，提出了基于遗传算法的解决方案，最后通过案例进行仿真实验，验证该算法的可行性和有效性，解决了采用传统优化方法难以解决的装备采购优化决策问题。     

无人仓系统储位分配问题的优化模型与算法

考虑到无人仓系统补货阶段货架上只有部分空余储位的特点，研究了补货商品储位分配问题的优化模型与算法。以同一货架上存放的商品之间关联度之和最大化为目标建立了混合整数规划模型；结合贪婪算法和邻域搜索算法设计了求解模型的两阶段方法。第一阶段利用贪婪算法求初始可行解；第二阶段利用邻域搜索算法对初始可行解进行优化。利用一个具体算例验证了邻域搜索算法的优化效果，结果显示，通过邻域搜索算法对初始可行解的优化，可以使目标函数值至少提升27%。进一步利用多个小规模算例分析了两阶段算法的近似比和求解速度，验证了算法的快速有效性。本文的研究结果不仅解决了货架初始状态非空情况下的储位分配问题，同样适合解决货架初始状态为空的情况，因此更加符合实际场景，可以作为无人仓管理信息系统的核心模型和算法。     

越库配送下考虑时空距离的库门分配与车辆调度优化

针对越库配送下考虑时空距离的库门分配与车辆路径问题,建立以车辆派遣成本、运输成本、时间惩罚成本、越库内部操作成本总和最小化为目标的库门分配与车辆路径优化模型。根据问题的特征设计改进的自适应遗传算法,并根据时空距离生成初始解。通过对不同规模的算例进行对比和分析,验证了模型的正确性和算法的有效性,结果表明,所得出的库门分配和车辆调度优化方案可以有效降低越库配送中心的运营成本。研究成果拓展和丰富了越库配送下的车辆路径问题研究,能为物流企业优化配送方案提供理论依据。     

自动化立体仓库中的储位分配及存取路径优化

储位分配和存取作业路径优化是仓储管理中的两个重要决策问题。本文研究如何在自动化立体仓库中对这两个问题进行同时决策。提出了一个混合整数规划模型对该问题进行优化建模,设计开发了一个基于有向连接图的两阶段优化算法对问题求初始解,并利用禁忌搜索算法对所求得的解进行改进。算法第一阶段解决储位分配问题,在此基础上第二阶段利用Hungarian算法对堆垛机的存取作业路径优化问题进行求解。最后利用实例对算法效率和精度进行分析评价,计算结果验证了算法的有效性。     

Multiple criteria approach for solving feeder assignment and assembly sequence problem in PCB assembly

The feeder assignment and assembly sequence problem in printed circuit board (PCB) assembly with the twin objectives of minimizing magazine travel time and minimizing board travel time is presented in this study. The problem uses Dynamic Pick-and-Place (DPP) model where robot arm, board and magazine move together with different speeds based on relative coordinates between consecutive assembled points. The difficulty of the problem is that the feeder assignment depends on assembly sequence and vice versa. A new approach is proposed to improve the existing approaches. The trade-off between two strategies, assembly by area and assembly by component types, can give better results. The numerical experiments proved the efficiency of the new algorithm.     

A memetic differential evolution algorithm for energy-efficient parallel machine scheduling

This paper considers an energy-efficient bi-objective unrelated parallel machine scheduling problem to minimize both makespan and total energy consumption. The parallel machines are speed-scaling. To solve the problem, we propose a memetic differential evolution (MDE) algorithm. Since the problem involves assigning jobs to machines and selecting an appropriate processing speed level for each job, we characterize each individual by two vectors: a job-machine assignment vector and a speed vector. To accelerate the convergence of the algorithm, only the speed vector of each individual evolves and a list scheduling heuristic is applied to derive its job-machine assignment vector based on its speed vector. To further enhance the algorithm, we propose efficient speed adjusting and job-machine swap heuristics and integrate them into the algorithm as a local search approach by an adaptive meta-Lamarckian learning strategy. Computational results reveal that the incorporation of list scheduling heuristic and local search greatly strengthens the algorithm. Computational experiments also show that the proposed MDE algorithm outperforms SPEA-II and NSGA-II significantly.     

服务水平保证下应急抢修点选址模型及求解算法研究

本文研究了一类故障率低但重要性较高设备的应急抢修点选址问题。设备的故障发生过程和从应急抢修点到故障设备的通行时间是随机的,每个设备被分配给一个应急抢修点进行抢修,并且整个应急抢修系统的服务水平要大于给定标准。本文以应急抢修点总开设成本最小作为目标,同时考虑了设备覆盖约束、抢修分配关系约束和抢修系统服务水平约束,在合理的假设下证明设备发生故障且应急抢修小组迟到的总次数服从泊松分布,最终将应急抢修点选址问题描述为一个0-1整数规划模型。通过对模型中的覆盖约束和抢修系统服务水平约束进行松弛,设计了相应的拉格朗日启发式算法。最后通过对大量随机算例进行计算,证明了该模型和算法的有效性。     

自动化立体仓库中出入库任务顺序与出库位置选择集成优化研究

具有多个出口的自动化立体仓库系统是一种将存储和分拣相结合的新型仓储技术,其最典型的特征是在货架底层有很多个出库位置以供取货人员分拣。研究此系统中出入库任务排序与出口选择的集成优化问题,以最小化堆垛机完成所有任务的移动距离为目标,将此问题转化为一个混合整数规划模型。根据问题的特点设计了两阶段启发式算法求解此问题,数值结果表明设计的算法能在较短时间内给出近似最优解,同时与企业常用的先到先服务方法相比,该算法可以缩短超过20%的移动距离。     

Assembly block storage location assignment at a shipyard: a case of Hyundai Heavy Industries

It is not a trivial issue how to manage assembly blocks at a shipyard. Based on the project experience in Hyundai Heavy Industries, currently the largest shipbuilding company in the world and the leader in the Korean merchant shipbuilding industry, this study points out the difficulties on the block stockyard operations, formalises the assembly block storage location assignment problem, and develops the assembly block storage location assignment algorithm, the purpose of which is to reduce the number of unproductive block moves. Through simulation experiments for various situations, this study demonstrates the usefulness of the assembly block storage location assignment algorithm. In addition, this study examines the impacts of block move sequence rules and of block stockyard layouts on the block stockyard operations.     

同时集散货物的开放式车辆路径问题研究

本文研究了车辆工作时间限制下同时集散货物的多配送中心开放式车辆路径问题,以车辆数和运输里程最小为目标,建立了多目标规划模型,提出了基于拉格朗日松弛技术和禁忌搜索算法的混合求解算法。 该算法首先求出最优解的最大下界,然后采用客户点的分配和调整策略实现解的可行化,其中禁忌搜索引入了4种领域搜索方法,采用了随机变领域搜索方法和重起策略。算例分析表明,该算法能有效地找到满意解,且采用开放式安排路线比闭合式安排路线更加经济合理。     

An Appellate Court Case Assignment Algorithm

This paper describes a case assignment (calendaring) algorithm for a multi-judge appellate court system. In the algorithm, cases of unequal work content are selected for assignment to one of m panels (or clusters) from a set of N available cases. Each panel of cases is heard by a team of three judges. Each appellate case has an estimated work load and a priority ranking based on the type of appeal and filing date with the court. The algorithm balances both the total work load and the number of cases assigned to each panel while insuring that the highest priority cases are assigned to those available. The assignment problem is normally capacity constrained in that not all of the N cases can be assigned to one of the m panels on the monthly calendar. The algorithm is based on a neighborhood search and bounding principle that continually improves upon an initial feasible solution. Empirical results are presented to demonstrate the effectiveness and efficiency of the algorithm.