考虑订单合并和货物转运的多式联运路径优化研究

为了获得运输的规模经济效应,本文研究了一种考虑订单合并和货物转运的零担多式联运路径优化问题。首先,以总运输成本为目标函数,以网络中的运输工具容量、可以提供的运输工具最大数量、运输工具服务的关闭时间以及订单时间窗为约束,构建混合整数规划模型,在模型中允许多个订单进行合并运输并考虑运输过程中的转运成本。其次,由于多式联运路径优化问题是典型的NP-hard问题,为了快速求解该模型,开发了一种可以快速为该问题提供近似最优解和下界的列生成启发式算法。最后,生成并测试了大量算例,结果表明所开发的列生成启发式算法可以在较短的时间内提供高质量的近似最优解。文章所构建的模型和开发的列生成启发式算法可以为零担自营多式联运物流企业提供高效的决策支持。     

面向多编组站铁路枢纽的列流-车流协同组织优化

研究一类面向多编组站铁路枢纽的列流-车流协同组织优化问题。以列车进出站走行、货车改编与集结、地方作业车取送费用最小为目标,考虑枢纽各编组站接入方向、衔接装卸站情况、场站到解集编发能力和枢纽转站能力等限制构建模型,并根据模型特点设计两阶段融合求解策略。该策略首先给出主核心车组接入编组站作为列车接入站的贪婪匹配方法,进而利用次核心车组进行方案调整,然后根据到解集编发能力和转站能力限制完成匹配方案检验,得到可行匹配方案集。其次,给出列车与编组站相互匹配的编码方案,进而利用基于优选集的交互-内生更新过程找出最优列车-编组站匹配方案。最后通过不同规模算例测试所提方法的求解性能。     

随机需求收益最大化分销网络设计问题

研究随机需求的供应链分销网络设计问题。考虑供应商可以选择所服务的零售商,且供应商通过定价决策确定所服务的零售商。针对此问题,建立了一个非线性整数规划模型和一个等价的集合包裹模型,并利用列生成算法求解集合包裹模型,同时提出一种O（ n3 logn）时间的算法求解列生成算法中产生的子问题。数值计算表明,本文所提出的算法具有很好的最优性和可行性。     

工件带安装时间的单机排序问题的列生成算法

在求解大规模NP-困难的最优化问题方法中,列生成技术越来越受到重视.本文研究工件带有与加工次序有关的安装时间的单机排序问题,首先构造它的时间标号模型,结合D-W分解技术和分支定界方法,给出它的列生成算法.其中时间标号模型的线性松弛为原问题提供了很好的下界,然后提出一个近似算法.通过实验数据表明,我们的算法对中等规模的排序问题1|t_(ij),r_j|∑w_jC_j是有效的.     

选址-库存-路径问题模型及其集成优化算法

设施选址、库存控制和车辆路径安排是物流系统优化中的三个关键问题,三者之间存在相互依赖的关系,应该根据这种关系来相应地进行综合优化与管理物流活动。以典型的单一生产基地、单一产品、采用不断审查的(Q, r)库存策略的供应链二级分销网络为研究对象,建立了一个随机型选址-库存-路径问题优化模型;在将非线性混合整数规划转化为线性整数集合覆盖模型的基础上,采用列生成算法来获得一个近似最优解,再用分支定价法对初始解进行改进,以实现对整个问题“完全集成”的优化。最后,用随机生成的方式,产生了10至160个客户的计算实例,分析了运输费用和库存费用对总成本的影响,算法运算时间表明本文给出的算法能较快地求解这一复杂问题。     

随机活动工期下求解资源约束项目最大期望净现值的动态调度算法

本文研究了随机活动工期下如何调度资源约束项目使得项目的期望净现值最大。首先对问题进行了界定,建立了相应的优化模型,其次针对问题的特点设计了一种动态规划算法。在算法设计的过程中,本文通过对项目网络图结构及不同状态最优值之间关系的分析,优化了动态规划算法状态的生成过程及状态最优值的求解过程,从而加快了算法的求解。使用随机生成的540个不同规模、不同结构的仿真案例对算法的有效性进行了验证,并分析了项目网络特征对算法效率的影响。实验发现:项目的次序强度对算法所需时间有着较大的影响,随着项目次序强度的减小,生成的状态数量会增加,从而计算时间也会增加。本文的研究可以为不确定环境下的项目调度提供决策支持。     

到货不确定的多商品多阶段多折扣的采购与存储问题

考虑一个制造商和多个供应商的采购与存储问题。多个供应商分别提供多种原材料，采用一种折扣方案，或单品全量折扣，或总量全量折扣，或混合全量折扣。制造商根据供应商提供的原材料品种和折扣方案，考虑不能按时到货的情况下，确定订货量，制定运输和仓储方案，以最小化总体运营成本。受运输过程中多种因素的影响，到货时间存在一定的不确定性，由此引出调货问题。用模糊随机变量表示到货率，建立相应的模糊随机数学优化模型，通过建立模糊随机期望值模型的方法将不确定的模糊随机优化模型转化为确定的混合整数非线性规划模型。给出求解该问题的算法——基于核搜索的启发式算法，对算例求解并证明了算法的可行性与有效性。通过数值实验，对相关参数进行分析，给出其经济解释，为管理者决策提供参考。     

一个基于货物运输的批处理机随机调度模型研究

本文以货物运输为背景新建立了一个批处理机随机调度模型,目的是为了应付货物运输中运输时间的不确定性和货主取货时间的不确定性.首先将模型转化为与其等价的确定优化问题,接着研究给出了确定优化问题的性质,最后基于这些性质给出了一个求解确定优化问题的启发式算法.该问题的解决可望为物流公司等进一步改善服务质量提供了一些理论依据     

航班登机口分配问题的数学建模

登机口作为机场的重要组成部分,其资源利用率直接影响航班服务的效率.针对不同的优先级建立多目标规划模型对航班进行优化分配,采用贪心算法和禁忌搜索算法,结合登机口类型、航班时间的约束,逐次对最大化分配航班问题、最小化中转旅客最短流程时间问题、最小化旅客总体紧张度问题进行建模求解.结果表明该算法不仅提升了求解速度,并且在航班登机口分配问题中展现了较好的综合寻优能力.这对民航机场实现经济效益、提高旅客满意度有一定的参考价值.     

考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法

快速充电站选址是电动汽车运营的重要内容之一。本文考虑电动汽车用户会通过绕行一定距离对车辆进行充电这一特征,建立了一个以电动汽车快速充电站建站成本和旅客整体绕行成本之和最小的双层整数规划模型。本文首先给出了用于生成绕行路径集合的A^*算法,然后设计了一种包含局部迭代搜索的自适应遗传算法对该模型进行求解。为了测试算法性能,通过两个不同规模的算例图与已有求解FPLM问题的遗传算法进行了比较,数值试验部分证明了算法的正确性和有效性。最后引入浙江省的高速路网图,从建站成本和截流量两方面对电池续航里程带来的影响进行了相关的灵敏度分析。     

Delay resistant line planning with a view towards passenger transfers

The line planning step, as part of the public transportation planning process, is an elementary problem. When generating public transportation systems in a conventional fashion, the line planning problem is one of the first to solve. Hence, subsequent problems rely on the solution of the line planning problem. Line planning has been studied from various perspectives and is understood very well. Still, the effect of this planning step on to the next ones has only received minor attention. In this paper, we study the effect of transfers on the delay resistance and propose a line planning model which provides a good basis for a delay resistant transportation system. To this end, the concept of preferable paths from the direct travelers line planning model is further extended. The model includes the routing of passengers in order to minimize passenger transfers. A column generation approach is shown to properly solve the proposed model. As such, this is the first line planning model which detailedly routes the passengers and is still tractable on realistically sized instances. Finally, it is shown that minimizing the passenger transfers at the line planning stage contributes to an increasing delay resistance in the public transportation system.     

Exact methods for large-scale multi-period financial planning problems

A relevant financial planning problem is the periodical rebalance of a portfolio of assets such that the portfolio’s total value exhibits certain characteristics. This problem can be modelled using a transition graph G to represent the future state space evolution of the corresponding economy and mathematically formulated as a linear programming problem. We present two different mathematical formulations of the problem. The first considers explicitly the set of the possible scenarios (scenario-based approach), while the second considers implicitly the whole set of scenarios provided by the graph G (graph-based approach). Unfortunately, for both the formulations the size of the corresponding linear programs can be huge even for simple financial problems. However, the graph-based approach seems to be a more powerful model, since it allows to consider a huge number of scenarios in a very compact formulation. The purpose of this paper is to present both heuristic and exact methods for the solution of large-scale multi-period financial planning problems using the graph-based model. In particular, in this paper we propose lower and upper bounds and three exact methods based on column, row and column/row generation, respectively. Since the methods based on column/row generation exploits simultaneously both the primal and the dual structure of the problem we call it Criss-Cross generation method. Computational results are given to prove the effectiveness of the proposed methods.      

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.     

基于动态列生成算法的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.     

A column generation approach for an employee scheduling problem with multiple shifts and work locations

This paper is concerned with the problem of assigning employees to a number of work centres taking into account employees' expressed preferences for specific shifts, off-days, and work centres. This particular problem is faced by the Kuwait National Petroleum Corporation that hires a firm to prepare schedules for assigning employees to about 86 stations distributed all over Kuwait. The number of variables in a mixed-integer programming model formulated for this problem is overwhelming, and hence, a direct solution to even the continuous relaxation of this model for relatively large-scale instances is inconceivable. However, we demonstrate that a column generation method, which exploits the special structures of the model, can readily solve the continuous relaxation of the model. Based on this column generation construct, we develop an effective heuristic to solve the problem. Computational results indicate that the proposed approach can facilitate the generation of good-quality schedules for even large-scale problem instances in a reasonable time.     

A column generation approach for solving the patient admission scheduling problem

This paper addresses the Patient Admission Scheduling (PAS) problem. The PAS problem entails assigning elective patients to beds, while satisfying a number of hard constraints and as many soft constraints as is possible, and arises at all planning levels for hospital management. There exist a few, different variants of this problem. In this paper we consider one such variant and propose an optimization-based heuristic building on branch-and-bound, column generation, and dynamic constraint aggregation to solve it. We achieve tighter lower bounds than previously reported in the literature and, in addition, we are able to produce new best known solutions for five out of twelve instances from a publicly available repository.     

A biased random-key genetic algorithm for road congestion minimization

One of the main goals in transportation planning is to achieve solutions for two classical problems, the traffic assignment and toll pricing problems. The traffic assignment problem aims to minimize total travel delay among all travelers. Based on data derived from the first problem, the toll pricing problem determines the set of tolls and corresponding tariffs that would collectively benefit all travelers and would lead to a user equilibrium solution. Obtaining high-quality solutions for this framework is a challenge for large networks. In this paper, we propose an approach to solve the two problems jointly, making use of a biased random-key genetic algorithm for the optimization of transportation network performance by strategically allocating tolls on some of the links of the road network. Since a transportation network may have thousands of intersections and hundreds of road segments, our algorithm takes advantage of mechanisms for speeding up shortest-path algorithms.     

A lexicographic pricer for the fractional bin packing problem

We propose an exact lexicographic dynamic programming pricing algorithm for solving the Fractional Bin Packing Problem with column generation. The new algorithm is designed for generating maximal columns of minimum reduced cost which maximize, lexicographically, one of the measures of maximality we investigate. Extensive computational experiments reveal that a column generation algorithm based on this pricing technique can achieve a substantial reduction in the number of columns and the computing time, also when combined with a classical smoothing technique from the literature.