时变路网下多中心电动车-无人机协同配送路径优化

针对车辆行驶时间依赖配送区域路网速度变化的多中心电动车-无人机协同配送路径问题,本文综合考虑配送区域路网交通信息,无人机最大飞行距离、承重能力,配送过程中电动车电池的荷电状态,以及车辆行驶速度、载重量等对电动车能耗的影响等,以总配送成本最小化为目标建立多中心车辆-无人机协同配送路径优化模型。根据问题特征,本文设计遗传大邻域搜索混合算法求解模型,该算法在传统遗传算法基础上,采用整数编码随机生成初始种群,通过无人机最大承重能力、飞行距离筛选无人机可服务的客户,然后确定车辆及无人机的配送路径生成初始解,并嵌入2组摧毁和重建算子进行进化操作。本文通过多组算例验证了算法及模型的有效性,并分析了车辆搭载的无人机数量以及车辆行驶速度对配送方案制定的影响。研究成果丰富和拓展了车辆路径优化的研究领域,可为交通、物流企业优化决策配送方案提供理论依据。     

基于改进蚁群算法的低碳车辆路径问题研究

全球气候恶化危及人类生存环境,物流运输过程中产生的大量温室气体则是祸源之一。本文考虑带有碳排放约束的车辆路径问题（VRP）,以车辆行驶里程最短和碳排放量最小为目标,构建了多目标的VRP非线性规划模型。提出了一种改进的蚁群系统算法对该模型进行求解,算法在更新路径上的蚂蚁信息素时引入了混沌扰动机制,此举能降低算法运行时陷入局部最优解的概率并有效提高算法的适应性。同时,对启发因子、状态转移概率、信息素更新等环节进行了优化设计,提高了最优路径的搜索效率。最后,数值仿真实验证明了该算法的求解表现优于同类研究常用的遗传算法和禁忌搜索算法,具有较强的全局寻优能力。在灵敏性和有效性的保证下,本研究所设计的改进蚁群算法能够较好地处理低碳车辆路径问题（LCVRP）。     

求解带时间窗的客户需求可分条件下的车辆路径问题

物流运输中的车辆路径问题历来是一个重要的理论和实际问题,在同时考虑客户需求可分以及客户方和配送中心时间窗限制的前提下,重新构造了问题模型,并结合蚂蚁算法中转移概率的改进和最大-最小蚂蚁系统,设计了问题求解过程和分割点选取规则,计算结果显示出算法的可行性。另外还与客户需求不可分的情况进行了对比,从而说明在大规模物流运输需求下,可分能带来更好的效果。     

时间依赖型多配送中心带时间窗的开放式车辆路径问题研究

本文研究了时间依赖型多配送中心带时间窗的开放式车辆路径问题,基于道路通行情况,建立车辆行驶速度时间函数;考虑车辆载重、里程限制与客户点服务时间窗的约束,建立混合整数规划模型,目标函数为最小化车辆总成本,具体包括车辆行驶时间成本和车辆固定发车成本;提出了一种二维编码方式的混合遗传算法,针对混合遗传算法设计了多分区段单点交叉策略、动态插入算子及局部搜索策略;最后,基于Solomon VRPTW基准数据集生成27个测试算例,使用混合遗传算法进行求解。数值实验结果表明,考虑道路通行情况,选择合理的出发时间,避免拥堵时段进行配送服务,能明显减少车辆的总行驶时间,且验证了混合遗传算法能够获得问题的满意解。     

动态需求下车辆路径问题的周期性优化模型及求解

针对客户点不断更新的动态需求车辆路径问题,依据滚动时域对配送中心工作时间进行划分,提出基于延迟服务的周期性客户点实时重置策略,策略中延迟服务机制能结合车辆启动延迟系数对照当前时域的时间进行检验,满足所有客户点的服务需求,保证车辆满足中心时间窗约束。设计多阶段求解的混合变邻域人工蜂群算法对各时间片内子问题进行连续迭代优化,算法中子路径动态转变的设计能较好平衡原有客户点和新客户点对路径更新和车辆实时信息匹配的要求。算例验证及对比分析表明本文策略和算法在求解动态问题时的有效性和可行性。     

有顾客时间窗和发货量变化的紧急车辆调度研究

对紧急车辆调度系统进行了研究,探讨了紧急车辆调度问题实现的关键技术.对有顾客时间窗和发货量变化的紧急车辆调度问题,运用了禁忌算法(TS)进行优化.算法基于实数编码,应用GENI插入法产生初始解和进行邻域操作,设计了三种邻域,利用容量约束控制单条路径配送点数,采用惩罚函数处理时间窗约束,通过设计虚拟车场等方法实现了车辆的紧急调度.本文给出了一个具有代表性的算例试验结果,算例结果及其分析表明了此方法对优化紧急车辆调度问题的有效性.     

基于风险的考虑成本和允许等待的车辆运输调度问题研究

本文同时考虑了成本约束和允许等待情形,研究了最小化风险的车辆运输调度问题,其中运输风险是随时间不同而变化的,即研究在时间依赖网络中基于风险的有约束的运输路径选择问题,以及在选定路径的顶点上决定的出发和等待时间的综合问题。建立了相应的混合整数规划模型,设计了相应的算法,并分析了算法复杂性,最后通过算例验证了该算法的有效性和可行性。     

具有周期特征的末阶段飞行员资源紧张度评估方法研究

近年来,随着我国航空业的快速发展,飞行员不足成了很多航空公司发展的制约因素。由于飞行员的飞行时间有周、月、年度飞行小时的约束,航空公司在执行每月第四周的航班计划时,往往由于飞行员前三周飞行时间不平衡,造成利用剩余的飞行员资源完成第四周计划航班任务的紧张状况。本文针对此问题,提出一种评估每月第四周飞行员资源紧张程度的方法。该模型首先按照带队机长可用的飞行小时,将带队机长分为若干类,以各类带队机长的投入数量为投入变量,利用历史数据分析航班任务和飞行员投入之间的关系。利用各类飞行员投入结构比例的约束,计算第四周可用带队机长飞行小时可完成的最大航班任务量,通过与计划航班任务量的比较,评估完成该航班计划的紧张程度,并根据结果在需要预警时,给出不同级别的预警。从而可以使得安全生产关口前移,提高航空公司的安全生产水平,同时为飞行员的培训提供依据。     

基于模糊聚类与车辆协作策略的随机车辆路径问题

以多辆车协作的随机车辆路径问题为研究对象,设计了通用的随机车辆路径问题机会约束模型,提出了大规模随机车辆路径问题的车辆协作策略,并基于该策略与模型设计了求解天规模随机车辆路径问题的混合启发式算法,计算实验结果说明了该算法与策略的有效性与实用性.     

基于自感应蚁群算法的VRPSDP问题研究

同时供货和取货的车辆路径问题是车辆路径问题的重要组成部分之一,问题的复杂性使得目前的主要求解方法局限于各种插入式启发算法。本文引用了近年来出现的蚁群算法,并通过对蚂蚁行为的深入研究,首次提出了感应因子、期望程度因子、距离性比因子以及加速因子的概念,在信息素更新方面融入了当前路径的距离特征,构建了一种全新的自感应蚁群算法。该方法充分利用全局分布的信息素感应信息,并且根据车辆容量支配值以及节点间距和节点-中心点间距性比进行状态转移,利用信息素更新公式中加速因子的动态调节有效地解决了算法快速收敛与陷入局部最优的矛盾。仿真试验证明了自感应蚁群算法的有效性,同时,该算法也拓展了车辆路径问题的算法空间。     

飞行频率、拥挤成本和互补型航空联盟:中枢轮辐网络机场拥挤分析

本文在基于飞行频率、拥挤成本和互补型航空联盟的基础上系统分析了中枢轮辐网络机场拥挤问题。研究表明:航空公司的利润最大化使得航班飞行频率存在过度供给,飞机大小也是次优的,这进一步恶化了中枢机场的机场拥挤;航班飞行频率与航空公司的拥挤成本系数、旅行计划延迟效用系数正相关,与飞机每次起降的固定成本负相关;互补型航空联盟使得联盟体利润增加,航空联盟对连接市场乘客有利,对本地市场乘客不利,航空联盟还可以内化伙伴间拥挤,航班飞行频率得以优化,机场拥挤得以缓解。     

Heuristic approaches for flight retiming in an integrated airline scheduling problem of a regional carrier

Flight retiming in airline scheduling consists in slightly modifying the scheduled departure time of some flights with the goal of providing a better service with a cheaper cost. In this research, the departure times must be selected from a small discrete set of options. The whole problem embeds flight retiming, fleet assignment, aircraft routing and crew pairing. Thus, the aim is to determine the departure times of the flights, the fleet assignment and the minimum cost aircraft and crew routes. The objective function takes into account a large cost associated with each crew member, a penalization for short or long connection times, a cost for crew members changing aircraft along their routes, and a minor penalty associated with the use of each aircraft. The constraints enforce aircraft maintenance and crew working rules. In this setting, flight retiming is allowed to potentially reduce the total costs and increase the robustness of the solution against delays by decreasing the number of aircraft changes.We propose and compare four heuristic algorithms based on a Mixed Integer Linear Programming model for the whole problem. The model contains path variables representing the crew pairings, and arc variables representing the aircraft routes. In the heuristic algorithms, column generation is applied on the path variables, and different flight retiming options are considered. The algorithms are tested on real-world instances of a regional carrier flying in the Canary Islands to evaluate their advantages and drawbacks. In particular, one of the algorithms, that uses the solution of the Linear Programming relaxation of the model to select promising options for the departure of the flights, turns out to be the most effective one. The obtained results show that costs can be significantly reduced through flight retiming while still keeping the computing times reasonably short. In addition, we perform a sensitivity analysis by including more retiming options and by using different aircraft and crew costs. Finally, we report the results on larger size instances obtained by combining real-world ones.     

基于飞行品质数据的飞行员调度模型研究

随着近几年我国航空业的迅猛发展,各大航空公司都在不断扩张自身规模,增加任务量,同时各公司又必须在保障安全的前提下进行飞行生产活动,这就使得飞行员的调度工作更为重要。本文在传统的飞行员调度模型基础上充分考虑安全的因素提出基于飞行品质数据的飞行员调度模型。通过考察调度过程中飞行员前期飞行品质表现情况,对飞行品质数据进行分类,设定搭配规则限制某些飞行品质分类级别较低的飞行员组成机组,实现提高排班安全性的目的。文中提出了根据飞行员工龄和千次率的分类方法,并运用列生成算法求解以周为单位的调度模型,这对于我国航空公司"安全第一,保障生产"的要求有着一定的借鉴意义。     

Assessing fairness of selfish revenue sharing mechanisms for airline alliances

Airline alliances offer flights including flight legs operated by different airlines. A major problem is how to share the revenue obtained through selling a flight ticket among the airlines in a fair way. Recently, Kimms and Çetiner [1] have proposed fair revenue allocations based on the solution concept nucleolus, which assumes that the decisions of the alliance are given centrally. However, in an alliance, each airline has a selfish behavior and tries to maximize its own revenue. The contribution of this paper is twofold. First, we provide a method to evaluate the fairness of revenue sharing mechanisms applied in a selfish setting. The method includes a simulation model for the booking process of the alliance and uses the nucleolus-based allocations as benchmark. Second, we develop a revenue sharing mechanism based on the transfer of dual prices. The fairness of the new mechanism and several other existing approaches is assessed through a numerical study.     

Revenue management games with government mandate

In 2007, the Chinese aviation authority asked the five airlines that offer service between Shanghai and Beijing to form an express shuttle alliance so that tickets from one airline could be used for any flight offered by any of the other airlines. In this paper, we study the impact of such a government mandate on the competitiveness of the market and on airline operations. First we extend a competitive airline seat allocation model to include such a government mandate and provide sufficient conditions for the existence of a pure-strategy Nash equilibrium in such a model. Both our analytical and numerical results show that fewer low-fare seats would be made available in a market with the government mandate, and furthermore, revenues of individual airlines would be lower as well. We then study a seat inventory and price competition game between duopoly airlines with the government mandate and establish the existence of pure-strategy Nash equilibriums. We show that with the government mandate, the airlines would reserve more high-fare seats and raise the prices of high-fare seats. In addition, we show that the revenues of the airlines would decrease as fewer low-fare seats are offered and increase as the prices of high-fare seats are increased. We also discuss how the government mandate should be designed so that the market could operate as efficiently as possible.     

An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems

The main characteristic of today's manufacturing environments is volatility. Under a volatile environment, demand is not stable. It changes from one production period to another. To operate efficiently under such environments, the facilities must be adaptive to changing production requirements. From a layout point of view, this situation requires the solution of the dynamic layout problem (DLP). DLP is a computationally complex combinatorial optimization problem for which optimal solutions can only be found for small size problems. It is known that classical optimization procedures are not adequate for this problem. Therefore, several heuristics including taboo search, simulated annealing and genetic algorithm are applied to this problem to find a good solution. This work makes use of the ant colony optimization (ACO) algorithm to solve the DLP by considering the budget constraints. The paper makes the first attempt to show how the ACO can be applied to DLP with the budget constraints. In the paper, example applications are presented and computational experiments are performed to present suitability of the ACO to solve the DLP problems. Promising results are obtained from the solution of several test problems.     

Operations research in the management of the airlines

This paper is intended to present an introduction to the use of operations research in the international airline industry, and to demonstrate the scope and significance of the airline OR activities. First, the special reasons for the viability and spread of airline OR are discussed. Then a functional framework for an airline is outlined, to be used in analyzing the problems of an airline and relating the OR work to it. Four major applications are described, corresponding to four major components of the framework. These applications are: schedule development, overbooking control, crew scheduling and engine management, respectively. In each case we describe the problem and its significance, indicate the types of solution techniques which have been developed, and assess the implemented solutions. The paper concludes with comments on the current state-of-the-art and the future of airline OR. A detailed bibliography is given.Both of the authors have been operations research directors in major airlines and more recently have focused their attention upon the industry as academic researchers. This background has provided us with an unusual opportunity to analyze the role of OR in the airlines, and our paper seeks to share with the reader some of the insights we have gained thereby.     

Corporate planning in domestic airlines— An Indian case study

In this article the author considers the problems of planning in the airline industry, drawing specifically on experience in the domestic Indian airline. The article seeks to examine some of the strategic issues relevant to domestic airlines which, while related here to the Indian environment, may be seen to be pertinent in most developing countries.     

Aircraft routing and crew pairing: Updated algorithms at Air France

Aircraft routing and crew pairing problems aim at building the sequences of flight legs operated respectively by airplanes and by crews of an airline. Given their impact on airlines operating costs, both have been extensively studied for decades. Our goal is to provide reliable and easy to maintain frameworks for both problems at Air France. We propose simple approaches to deal with Air France current setting. For routing, we introduce an exact compact IP formulation that can be solved to optimality by current MIP solvers in at most a few minutes even on Air France largest instances. Regarding crew pairing, we provide a methodology to model the column generation pricing subproblem within a new resource constrained shortest path framework recently introduced by the first author. This new framework, which can be used as a black-box, leverages on bounds to discard partial solutions and speed-up the resolution. The resulting approach enables to solve to optimality Air France largest instances. Recent literature has focused on integrating aircraft routing and crew pairing problems. As a side result, we are able to solve to near optimality large industrial instances of the integrated problem by combining the aforementioned algorithms within a simple cut generating method.     

Measuring the Benefit of Offering Auxiliary Services: Do Bag‐Checkers Differ in Their Sensitivities to Airline Itinerary Attributes?

When firms evaluate their service system design choices, there is typically more uncertainty surrounding the value that a particular auxiliary service provides than there is on the cost of providing that service. To help inform this decision, we propose an approach where we compare the relative value of the segment of passengers who use an auxiliary service to the relative value of the segment that does not use it. We demonstrate this approach for a typical auxiliary service common to the airline industry. In 2008, most US airlines implemented checked baggage fee policies to decrease their costs by reducing the number of customer service agents needed in the check‐in and baggage handling processes. The success of this change has led to a current debate at many of these airlines on whether to make further staffing cuts in these areas, essentially making it even less attractive for passengers to check their baggage. Our proposed methodology helps answer whether passengers who continue to check bags in today's baggage‐fee era are more or less valuable than passengers who do not check bags. We explore this question empirically by examining, through a stated preference survey, if a history of checking or not checking bags can be used to segment passengers based on how their itinerary choices are influenced by common airline service attributes (on‐time performance, itinerary time, number of connections, airfare, and schedule delay). Contrary to the opinions of some top airline executives, we find that the passengers who continue to check bags at airlines that charge baggage fees are generally less sensitive to differences in three of these important service attributes and are less likely to switch airlines when a competing airline improves its offerings along these dimensions. Thus, airlines that charge for checked bags should consider improving the customer experience for their bag‐checking passengers, as they represent a potentially more valuable segment class to the airline.